Papers For Presentation

These are the papers that we will be reading in class, at the rate of about two papers per week. I will be presenting the first two papers, which will take us through Monday, September 24th. After that, all papers are available for signup and student presentation. They will be presented more or less in the order that they appear on this page. Please email Subi with your paper preferences ASAP. Electronic versions of all of these papers are easily found via web search. If you have a hard time finding one, please let me know.

NOTE: All papers have been assigned! (Last updated on: Fri, Oct 12)

Fast Index Inserts

  1. Patrick E. O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth J. O'Neil: The Log-Structured Merge-Tree (LSM-Tree). Acta Inf. 33(4): 351-385 (1996)
  2. Chris Jermaine, Anindya Datta, Edward Omiecinski: A Novel Index Supporting High Volume Data Warehouse Insertion. VLDB 1999: 235-246

Spatial and Multidimensional Data

  1. Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 (Presenters: Seth Caplan, Nikhil Agashe) Slides
  2. Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 (Presenter: Twisha, Surendar) Slides
  3. Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data VLDB 1996: 28-39 (Presenter: Selvi Kadirvel, Suhasini) Slides
  4. Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel: The Pyramid-Technique: Towards Breaking the Curse of Dimensionality. SIGMOD Conference 1998: 142-153 (Presenters: Koushik Kalyanaraman, Umang Shah) Slides
  5. Scott T. Leutenegger, J. M. Edgington, Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing. ICDE 1997: 497-506 (Presenters: Sarath, Hima) Slides

Spatial Nearest Neighbor Queries

  1. Nick Roussopoulos, Stephen Kelley, Fredeic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79 (Presenter: Chris Buzzerd, David Boerner, Kevin Patrick) Slides
  2. Roger Weber, Hans-Jörg Schek, Stephen Blott: A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. VLDB 1998: 194-205 (Presenters: Kaushik, Umang shah) Slides
  3. Flip Korn, S. Muthukrishnan: Influence Sets Based on Reverse Nearest Neighbor Queries. SIGMOD Conference 2000: 201-212 (Presenter: Hariyani Anoopkumar) Slides

Time Series

  1. Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos: Fast Subsequence Matching in Time-Series Databases. SIGMOD Conference 1994: 419-429 (Presenters: Luis Perez, George Liu) Slides
  2. Eamonn J. Keogh: Exact Indexing of Dynamic Time Warping. VLDB 2002: 406-417 (Presenters: Piyush Goswami, Ankit Hirdesh) Slides

General Metric Similarity Search

  1. Paolo Ciaccia, Marco Patella, Pavel Zezula: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. VLDB 1997: 426-435 (Presenters: Amool Gupta) Slides
  2. Roberto F. Santos Filho, Agma J. M. Traina, Caetano Traina Jr., Christos Faloutsos: Similarity Search without Tears: The OMNI Family of All-purpose Access Methods. ICDE 2001: 623-630 (Presenters: Michael Kelleher, Kiyotaka Iwataki) Slides

Biological Sequences

  1. Tamer Kahveci, Ambuj K. Singh: Efficient Index Structures for String Databases. VLDB 2001: 351-360 (Presenters: Nikita, Atul) Slides
  2. Ela Hunt, Malcolm P. Atkinson, Robert W. Irving: A Database Index to Large Biological Sequences. VLDB 2001: 139-148 (Presenter: Raghav, Balaji Rajkumar) Slides
  3. Sandeep Tata, Richard A. Hankins, Jignesh M. Patel: Practical Suffix Tree Construction. VLDB 2004: 36-47 (Presenter: Niketan Pansare) Slides
  4. Benjarath Phoophakdee, Mohammed J. Zaki: Genome-scale disk-based suffix tree indexing. SIGMOD Conference 2007: 833-844 (Presenters: Venus Chaitra, Amit Mahajan) Slides

Graph/Tree Databases

  1. Dennis Shasha, Jason Tsong-Li Wang, Rosalba Giugno: Algorithmics and Applications of Tree and Graph Searching. PODS 2002: 39-52 (Presenters: Christian Grant, Jerod Watson) Slides
  2. Nicolas Bruno, Nick Koudas, Divesh Srivastava: Holistic twig joins: optimal XML pattern matching. SIGMOD Conference 2002: 310-321 (Presenters: Jose Luna, John Bassett) Slides
  3. Quanzhong Li, Bongki Moon: Indexing and Querying XML Data for Regular Path Expressions. VLDB 2001: 361-370 (Presenters: Supriya, Gnana Sundar) Slides
  4. Xifeng Yan, Philip S. Yu, Jiawei Han: Graph Indexing: A Frequent Structure-based Approach. SIGMOD Conference 2004: 335-346 (Presenter: Alicia Cosenza) Slides

Indexing for Data Warehousing

  1. Patrick E. O'Neil, Dallan Quass: Improved Query Performance with Variant Indexes. SIGMOD Conference 1997: 38-49
  2. Chee Yong Chan, Yannis E. Ioannidis: An Efficient Bitmap Encoding Scheme for Selection Queries. SIGMOD Conference 1999: 215-226 (Presenter: Zach Pulkin)