Seminar Database Systems (MSc, BSc/6+)

Overview and objectives: The area of this year's seminar are similarity search, graph data, and security. Students learn how to critically read and study research papers, how to summarize the contents of a paper, and how to present it in a seminar.

Teaching format: Each participant writes a self-contained report of about 10 pages and gives a presentation (no computer). Each participant has a buddy. Buddies read the report and make suggestions for improvements. The first version of the report is due two weeks before the date of the presentation, and will be discussed with the buddy and the professor about one week before the presentation. The final versions of the report are due at the end of the semester.

Setup and Organization: The setup of the seminar will be discussed 14:15-16:00 in room HG F 33.1 at ETHZ. At the first meeting the papers will be assigned. The dates for the presentations are Saturday March 31, 2012 and Saturday May 12, 2012 (all day). Participation at all three meetings is compulsory. The assessment depends on the quality of the report, presentation, active participation during the seminar, and input as a buddy. The second series of talks will be on May 12, from 8:15am on, at ETH CAB Room H52. We will meet at 8:00am (sharp) at the back entrance (where the ASVZ is) of the CAB building. Please, be on time so that we can let you into the building.

Assignment: The assignment of papers is as follows.

1. Shuo Zhang, Xiaofeng Gao, Weili Wu, Jianzhong Li, Hong Gao: Efficient algorithms for supergraph query processing on graph databases. J. Comb. Optim. 21(2): 159-191 (2011)
2. James Cheng, Yiping Ke, Ada Wai-Chee Fu, Jeffrey Xu Yu: Fast graph query processing with a low-cost index. VLDB J. 20(4): 521-539 (2011)
3. Gaoping Zhu, Xuemin Lin, Wenjie Zhang, Wei Wang, Haichuan Shang: PrefIndex: An Efficient Supergraph Containment Search Technique. SSDBM 2010: 360-378
4. Weiguo Zheng, Lei Zou, Dongyan Zhao: Answering Subgraph Queries over Large Graphs. WAIM 2011: 390-402
5. Thanh Tran, Haofen Wang, Sebastian Rudolph, Philipp Cimiano: Top-k Exploration of Query Candidates for Efficient Keyword Search on Graph-Shaped (RDF) Data. ICDE 2009: 405-416
6. Vincenzo Bonnici, Alfredo Ferro, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha: Enhancing Graph Database Indexing by Suffix Tree Structure. PRIB 2010: 195-203
7. Raffaele Di Natale, Alfredo Ferro, Rosalba Giugno, Misael Mongiovì, Alfredo Pulvirenti, Dennis Shasha: SING: Subgraph search In Non-homogeneous Graphs. BMC Bioinformatics 11: 96 (2010)
8. Lei Zou, Lei Chen, M. Tamer Özsu, Dongyan Zhao: Answering pattern match queries in large graph databases via graph embedding. VLDB J. 21(1): 97-120 (2012)
9. Lei Zou, Lei Chen, M. Tamer Özsu: DistanceJoin: Pattern Match Query In a Large Graph Database. PVLDB 2(1): 886-897 (2009)
10. Zhaonian Zou, Jianzhong Li, Hong Gao, Shuo Zhang: Mining Frequent Subgraph Patterns from Uncertain Graph Data. IEEE Trans. Knowl. Data Eng. 22(9): 1203-1218 (2010)
11. Katia Abbaci, Allel HadjAli, Ludovic Lietard, Daniel Rocacher: A similarity skyline approach for handling graph queries - A preliminary report. ICDE Workshops 2011: 112-117
12. Camil Demetrescu, Irene Finocchi, Andrea Ribichini: Trading off space for passes in graph streaming problems. ACM Transactions on Algorithms 6(1): (2009)
13. Deepak Ajwani, Ulrich Meyer: Design and Engineering of External Memory Traversal Algorithms for General Graphs. Algorithmics of Large and Complex Networks 2009: 1-33
14. Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, Grzegorz Czajkowski: Pregel: a system for large-scale graph processing. SIGMOD Conference 2010: 135-146
15. Alexander G. Connor, Panos K. Chrysanthis, Alexandros Labrinidis: Key-key-value stores for efficiently processing graph data in the cloud. ICDE Workshops 2011: 88-93
16. Byoung-Kee Yi, H.V. Jagadish, Christos Faloutsos. Efficient Retrieval of Similar Time Sequences under Time Warping. ICDE 1998
17. Chuan Xiao, Wei Wang, Xuemin Lin, Jeffrey Xu Yu, Guoren Wang. Efficient similarity joins for near-duplicate detection. TODS 2011
18. Arup Nanda, Transparent Data Encryption, Oracle Magazine (Oracle10g: Security) 2005.
19. Damiani, Ernesto and Vimercati, S. De Capitani and Jajodia, Sushil and Paraboschi, Stefano and Samarati, Pierangela. Balancing confidentiality and efficiency in untrusted relational DBMSs. Proceedings of the 10th ACM Conference on Computer and Communications Security, CCS 2003, Washington, DC, USA, October 27-30, 2003.
20. Sion, Radu. Secure data outsourcing. Proceedings of the VLDB 2007.
21. Agrawal, Rakesh and Srikant, Ramakrishnan. Privacy-preserving data mining. SIGMOD Rec. Journal, 2000.
22. Evfimievski, Alexandre and Gehrke, Johannes and Srikant, Ramakrishnan. Limiting privacy breaches in privacy preserving data mining. Proceedings of the PODS 2003. ACM
23. Sweeney, Latanya. K-anonymity: a model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl.-Based Syst. Journal, 2002. World Scientific Publishing Co., Inc.
24. V. Vaikunthanathan, Computing Blindfolded: New Developments in Fully Homomorphic Encryption, IEEE FOCS Oct 2011.
25. C. Gentry, Computing arbitrary functions of encrypted data, CACM 2010.
26. Minos Garofalakis, Amit Kumar, XML Stream Processing Using Tree-Edit Distance Embeddings, TODS 2005
27. Sven Helmer, Measuring the Structural Similarity of Semistructured Documents Using Entropy, VLDB 2007
28. Dwork, Cynthia and Lei, Jing. Differential privacy and robust statistics, Proceedings of the STOC 2009. ACM
29. Shuchi Chawla and Cynthia Dwork and Frank Mcsherry and Adam Smith and Larry Joseph Stockmeyer.Toward privacy in public databases. Proceedings of the TCC 2005.