1.Nearest Neighbor Search in Multidimensional Spaces (1999) by Panayiotis Tsaparas / Oral Report

  1. You Jung Kim, Jignesh M. Patel: Performance Comparison of the R*-Tree and the Quadtree for kNN and Distance Join Queries. IEEE Trans. Knowl. Data Eng. 22(7): 1014-1027 (2010)
  2. Norbert Beckmann, Bernhard Seeger: A revised r*-tree in comparison with related index structures. SIGMOD 2009:799-812
  3. Quad trees a data structure for retrieval on composite keys R. A. Finkel and J. L. Bentley
  4. The Performance of the hB-pi Tree Panfeng Zhou , Betty Salzberg
  5. P. Zezula, P. Ciaccia, and F. Rabitti. M- tree: A dynamic index for similarity queries in multimedia databases.
  6. Stefan Berchtold, Christian Böhm, Daniel A. Keim, Hans-Peter Kriegel: A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space. PODS 1997:78-86
  7. The K-D-B-tree: a search structure for large multidimensional dynamic indexes John T. Robinson Sigmod 1981
  8. Hung-Yi Lin, Po-Whei Huang: Perfect KDB-Tree: A Compact KDB-Tree Structure for Indexing Multidimensional Data. ICITA 2005:411-414
  9. KDBKD-Tree:A Compact KDB-Tree Structure for Indexing Multidimensional DataByunggu Yu, Ratko Orlandic, Thomas Bailey, Jothi Somavaram
  10. Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. (CSUR) 11(2):121-137 (1979)
  11. Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. (TODS) 9(1):38-71 (1984)
  12. Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD 1984:47-57
  13. Hung-Yi Lin, Po-Whei Huang, Kuang-Hua Hsu: A new indexing method with high storage utilization and retrieval efficiency for large spatial databases. Information & Software Technology (INFSOF) 49(8):817-826 (2007)
  14. Ratko Orlandic, Byunggu Yu: Implementing KDB-Trees to Support High-Dimensional Data. IDEAS 2001:58-67
  15. Yves Lépouchard, John L. Pfaltz, Ratko Orlandic: Performance of KDB-Trees with Query-Based Splitting. ITCC 2002:218-223
  16. Beomseok Nam, Alan Sussman: A Comparative Study of Spatial Indexing Techniques for Multidimensional Scientific Datasets. SSDBM 2004:171-180
  17. Yván J. García, Mario A. Lopez, Scott T. Leutenegger: On Optimal Node Splitting for R-trees. VLDB 1998:334-344
  18. Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD 1995:71-79
  19. Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997:249-256
  20. A transparent parallel I/O environment (1994) Darren Erik Vengroff
  21. Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter: Implementing I/O-efficient Data Structures Using TPIE. ESA 2002:88-100
  22. King-Ip Lin, H. V. Jagadish, Christos Faloutsos: The TV-Tree: An Index Structure for High-Dimensional Data VLDB J. (VLDB) 3(4):517-542 (1994)
  23. Christian Böhm, Stefan Berchtold, Daniel A. Keim: Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. ACM Comput. Surv. (CSUR) 33(3):322-373 (2001)
  24. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. (CSUR) 30(2):170-231 (1998)
  25. Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD 1987:260-269
  26. Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990:590-601
  27. Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, Jeffrey Scott Vitter: Bkd-Tree: A Dznamic Scalable kd-Tree. SSTD 2003:46-65
  28. Kaushik Chakrabarti, Sharad Mehrotra: The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces. ICDE 1999:440-447
  29. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects Roussopoulos, Nick and Faloutsos, Christos (1987)
  30. Paolo Ciaccia, Marco Patella, Pavel Zezula: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. VLDB 1997:426-435
  31. Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989:45-53
  32. The LSDh-Tree: An Access Structure for Feature Vectors Andreas HenrichICDE '98
  33. Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data VLDB 1996:28-39
  34. Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel: The Pyramid-Technique: Towards Breaking the Curse of Dimensionality. SIGMOD 1998:142-153
  35. Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD 1990:322-331
  36. Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM (CACM) 18(9):509-517 (1975)
  37. Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. (TSE) 5(4):333-340 (1979)
  38. Andreas Henrich: A Hybrid Split Strategy for k-d-Tree Based Access Structures. ACM-GIS 1996:1-8
  39. Achieving optimal average data node storage utilization in k-dimensional point data indexes Evangelos outsios ,Georgios Evangelidis 2010
  40. Ricardo Rodrigues Ciferri, Ana Carolina Salgado: Performance evaluation of multidimensional access methods. ACM-GIS 2000:183-184
  41. Beng Chin Ooi, Kian-Lee Tan, Cui Yu, Stéphane Bressan: Indexing the Edges - A Simple and Yet Efficient Approach to High-Dimensional Indexing. PODS 2000:166-174
  42. Cui Yu, Beng Chin Ooi, Kian-Lee Tan, H. V. Jagadish: Indexing the Distance: An Efficient Method to KNN Processing. VLDB 2001:421-430
  43. 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
  44. Jonathan K. Lawder, Peter J. H. King: Using Space-Filling Curves for Multi-dimensional Indexing. BNCOD 2000:20-35
  45. David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. (TODS) 15(4):625-658 (1990)
  46. Bin Yao, Feifei Li, Piyush Kumar: K nearest neighbor queries and kNN-Joins in large relational databases (almost) for free. ICDE 2010:4-15
  47. Jiyuan An, Yi-Ping Phoebe Chen, Qinying Xu, Xiaofang Zhou: A New Indexing Method for High Dimensional Dataset. DASFAA 2005:385-397
  48. Jiyuan An, Yi-Ping Phoebe Chen, Qinying Xu: Surface Spatial Index Structure of High-Dimensional Space. IDEAL 2004:272-278
  49. Sunil Arya, David M. Mount, Onuttom Narayan: Accounting for Boundary Effects in Nearest Neighbor Searching. SoCG 1995:336-344
  50. Jia Li, Cheng Wang: Indexing Method for Hyperspectral Data Fast Retrieval by Pyramid Technique. CSSE 2008:519-523
  51. Gerth Stølting Brodal: Cache-Oblivious Algorithms and Data Structures. SWAT 2004:3-13
  52. Yannis E. Ioannidis: The History of Histograms (abridged). VLDB 2003:19-30
  53. Yufei Tao, Ke Yi, Cheng Sheng, Panos Kalnis: Quality and efficiency in high dimensional nearest neighbor search. SIGMOD 2009:563-576
  54. Aristides Gionis, Piotr Indyk, Rajeev Motwani: Similarity Search in High Dimensions via Hashing. VLDB 1999:518-529
  55. David A. White, Ramesh Jain: Similarity Indexing with the SS-tree. ICDE 1996:516-523
  56. Norio Katayama, Shin'ichi Satoh: The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. SIGMOD 1997:369-380
  57. Dong-Ho Lee, Hyoung-Joo Kim: SPY-TEC: An efficient indexing method for similarity search in high-dimensional data spaces. Data Knowl. Eng. (DKE) 34(1):77-97 (2000)
  58. Rui Zhang, Beng Chin Ooi, Kian-Lee Tan: Making the Pyramid Technique Robust to Query Types and Workloads. ICDE 2004:313-324
  59. An Indexing Method for Similarity Search in High-Dimensional Image Databases I. Daoudi, S. E. Ouatik, and A. Elkharraz 2005 (RA Blocks Variant)
  60. Yasushi Sakurai, Masatoshi Yoshikawa, Shunsuke Uemura, Haruhiko Kojima: The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation. VLDB 2000:516-526
  61. Stefan Berchtold, Christian Böhm, H. V. Jagadish, Hans-Peter Kriegel, Jörg Sander: Independent Quantization: An Index Compression Technique for High-Dimensional Data Spaces. ICDE 2000:577-588
  62. Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995:562-573
  63. Sathish Govindarajan, Pankaj K. Agarwal, Lars Arge: CRB-Tree: An Efficient Indexing Scheme for Range-Aggregate Queries. ICDT 2003:143-157
  64. Tran Khanh Dang: The SH-Tree: A Novel and Flexible Super Hybrid Index Structure for Similarity Search on Multidimensional Data. IJCSA 3(1):1-25 (2006)
  65. David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD 1992:351-360
  66. David B. Lomet: Process Structuring, Synchronization, and Recovery Using Atomic Actions. Language Design for Reliable Software 1977:128-137
  67. William Kent: A Simple Guide to Five Normal Forms in Relational Database Theory. Commun. ACM 26(2): 120-125 (1983)
  68. Chih-Ming Hsu, Ming-Syan Chen: On the Design and Applicability of Distance Functions in High-Dimensional Data Space. IEEE Trans. Knowl. Data Eng. 21(4): 523-536 (2009)
  69. Vladimir Pestov: On the geometry of similarity search: Dimensionality curse and concentration of measure. Inf. Process. Lett. 73(1-2): 47-51 (2000)
  70. Kaushik Chakrabarti ,Sharad Mehrotra :High Dimensional Feature Indexing Using Hybrid Trees Technical Report 1999
  71. Charu C. Aggarwal: Re-designing Distance Functions and Distance-Based Applications for High Dimensional Data. SIGMOD Record 30(1): 13-18 (2001)
  72. Kevin S. Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft: When Is ''Nearest Neighbor'' Meaningful? ICDT 1999: 217-235
  73. Kevin S. Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft: When Is ''Nearest Neighbor'' Meaningful? Technical Report #1377
  74. Charu C. Aggarwal, Alexander Hinneburg, Daniel A. Keim: On the Surprising Behavior of Distance Metrics in High Dimensional Spaces. ICDT 2001: 420-434
  75. Alexander Hinneburg, Charu C. Aggarwal, Daniel A. Keim: What Is the Nearest Neighbor in High Dimensional Spaces? VLDB 2000: 506-515
  76. Damien François, Vincent Wertz, Michel Verleysen: The Concentration of Fractional Distances. IEEE Trans. Knowl. Data Eng. 19(7): 873-886 (2007)
  77. Charu C. Aggarwal, Philip S. Yu: The IGrid index: reversing the dimensionality curse for similarity indexing in high dimensional space. KDD 2000: 119-129
  78. Damien François, Vincent Wertz, Michel Verleysen: Non-Euclidean metrics for similarity search in noisy datasets. ESANN 2005: 339-344
  79. Robert J. Durrant, Ata Kabán: When is 'nearest neighbour' meaningful: A converse theorem and implications. J. Complexity 25(4): 385-397 (2009)
  80. Uri Shaft, Raghu Ramakrishnan: Theory of nearest neighbors indexability. ACM Trans. Database Syst. 31(3): 814-838 (2006) ///////////////////////////////////////////////////////////////////////////////
  81. Vladimir Pestov, Aleksandar Stojmirovic: Indexing Schemes for Similarity Search: an Illustrated Paradigm. Fundam. Inform. 70(4): 367-385 (2006)
  82. Vladimir Pestov: Intrinsic dimension of a dataset: what properties does one expect? CoRR abs/cs/0703125: (2007)
  83. Vladimir Pestov: An axiomatic approach to intrinsic dimension of a dataset. Neural Networks 21(2-3): 204-213 (2008)
  84. Vladimir Pestov: Lower Bounds on Performance of Metric Tree Indexing Schemes for Exact Similarity Search in High Dimensions CoRR abs/0812.0146: (2008)
  85. Vladimir Pestov: Indexability, concentration, and VC theory CoRR abs/1008.5105: (2010)
  86. Vladimir Pestov: Intrinsic dimensionality. SIGSPATIAL Special 2(2): 8-11 (2010)
  87. Joseph M. Hellerstein, Elias Koutsoupias, Daniel P. Miranker, Christos H. Papadimitriou, Vasilis Samoladas: On a model of indexability and its bounds for range queries. J. ACM 49(1): 35-55 (2002)
  88. Ilya Volnyansky, Vladimir Pestov: Curse of Dimensionality in Pivot-based Indexes CoRR abs/0906.0391: (2009)***
  89. Maya R. Gupta:A Measure Theory Tutorial (Measure Theory for Dummies) UWEE Technical Report Number UWEETR-2006-0008 May 2006
  90. Chih-Ming Hsu, Ming-Syan Chen: On the Necessary and Sufficient Conditions of a Meaningful Distance Function for High Dimensional Data Space. SDM 2006 ***
  91. Vladimir Pestov: Lower Bounds on Performance of Metric Tree Indexing Schemes for Exact Similarity Search in High Dimensions SISAP'11
  92. Benjamin Bustos, Tomás Skopal: Non-metric similarity search problems in very large collections. ICDE 2011: 1362-1365***
  93. Tomás Skopal: Where are you heading, metric access methods?: a provocative survey. SISAP 2010: 13-21***
  94. T. Skopal, B. Bustos On Nonmetric Similarity Search Problems in Complex Domains, ACM Computing Surveys, 43(4), pp. 56, December 2011 ***
  95. Magnus Lie Hetland The Basic Principles of Metric Indexing, Swarm Intelligence for Multi-objective Problems in Data Mining, SCI 242, Springer, 2009***
  96. Magnus Lie Hetland: Ptolemaic Indexing CoRR abs/0911.4384: (2009)***
  97. Charu C. Aggarwal: Towards systematic design of distance functions for data mining applications. KDD 2003: 9-18***
  98. Chris Giannella: New Instability Results for High Dimensional Nearest Neighbor Search CoRR abs/0906.0684: (2009)

100.Sunil Arya, David M. Mount: Approximate Nearest Neighbor Queries in Fixed Dimensions. SODA 1993: 271-280

101.Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu: An Optimal Algorithm for Approximate Nearest Neighbor Searching. SODA 1994: 573-582

102.Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu: An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions. J. ACM 45(6): 891-923 (1998)

103.Piotr Indyk, Rajeev Motwani: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998: 604-613

104.Sunil Arya, Ho-Yam Addy Fu: Expected-Case Complexity of Approximate Nearest Neighbor Searching. SIAM J. Comput. 32(3): 793-815 (2003)

105.Sunil Arya, Theocharis Malamatos, David M. Mount: Space-time tradeoffs for approximate nearest neighbor searching. J. ACM 57(1): (2009)

106.Sunil Arya, Theocharis Malamatos, David M. Mount: Space-efficient approximate Voronoi diagrams. STOC 2002: 721-730

107.Sunil Arya, Theocharis Malamatos: Linear-size approximate voronoi diagrams. SODA 2002: 147-155

108.Sunil Arya, Theocharis Malamatos, David M. Mount: Space-time tradeoffs for approximate spherical range counting. SODA 2005: 535-544

109.Sunil Arya, David M. Mount: Approximate range searching. Comput. Geom. 17(3-4): 135-152 (2000)

110.Chan, T. M. 1998. Approximate nearest neighbor queries revisited. Disc. Comput. Geom. 20, 359–373.

111.Clarkson, K. L. 1994. An algorithm for approximate closest-point queries. In Proceedings of the 10th Annual ACM Symposium on Computer Geometry. ACM, New York, 160–164.

112.Marshall W. Bern: Approximate Closest-Point Queries in High Dimensions. Inf. Process. Lett. 45(2): 95-99 (1993)

113.Jon M. Kleinberg: Two Algorithms for Nearest-Neighbor Search in High Dimensions. STOC 1997: 599-608

114.Sariel Har-Peled, Nirman Kumar: Approximate Nearest Neighbor Search for Low Dimensional Queries. SODA 2011: 854-867

115.Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. SIAM J. Comput. 30(2): 457-474 (2000)

116.Omer Barkol, Yuval Rabani: Tighter bounds for nearest neighbor search and related problems in the cell probe model. STOC 2000: 388-396 *******

117.Logic and Database Queries Moshe Y. Vardi Ian Barland Ben McMahan August 2006