Multidimensional Binary Search Trees Used for Associative Searching.

@article{DBLP:journals/cacm/Bentley75,
  author    = {Jon Louis Bentley},
  title     = {Multidimensional Binary Search Trees Used for Associative Searching},
  journal   = {Commun. ACM},
  volume    = {18},
  number    = {9},
  year      = {1975},
  pages     = {509-517},
  ee        = {db/journals/cacm/Bentley75.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1975 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An4-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition: ACM Digital Library

Referenced by

1. Chung Keung Poon: Orthogonal Range Queries in OLAP. ICDT 2001: 361-374
2. Edwin M. Knorr, Raymond T. Ng, V. Tucakov: Distance-Based Outliers: Algorithms and Applications. VLDB J. 8(3-4): 237-253(2000)
3. Christian Böhm, Hans-Peter Kriegel: Dynamically Optimizing High-Dimensional Index Structures. EDBT 2000: 36-50
4. Gísli R. Hjaltason, Hanan Samet: Distance Browsing in Spatial Databases. ACM Trans. Database Syst. 24(2): 265-318(1999)
5. Marcel Kornacker: High-Performance Extensible Indexing. VLDB 1999: 699-708
6. Aristides Gionis, Piotr Indyk, Rajeev Motwani: Similarity Search in High Dimensions via Hashing. VLDB 1999: 518-529
7. Kothuri Venkata Ravi Kanth, Ambuj K. Singh: Optimal Dynamic Range Searching in Non-replicating Index Structures. ICDT 1999: 257-276
8. Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast and Effective Retrieval of Medical Tumor Shapes. IEEE Trans. Knowl. Data Eng. 10(6): 889-904(1998)
9. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
10. Edwin M. Knorr, Raymond T. Ng: Algorithms for Mining Distance-Based Outliers in Large Datasets. VLDB 1998: 392-403
11. Kothuri Venkata Ravi Kanth, Divyakant Agrawal, Ambuj K. Singh: Dimensionality Reduction for Similarity Searching in Dynamic Databases. SIGMOD Conference 1998: 166-176
12. Stacie Hibino, Elke A. Rundensteiner: Processing Incremental Multidimensional Range Queries in a Direct Manipulation Visual Query. ICDE 1998: 458-465
13. Andreas Henrich: The LSD^h-Tree: An Access Structure for Feature Vectors. ICDE 1998: 362-369
14. Shogo Nishida, Hiroshi Nozawa, Naoki Saiwaki: Proposal of Spatio-Temporal Indexing Methods for Moving Objects. ER Workshops 1998: 484-495
15. Yasuaki Nakamura, Hiroyuki Dekihara, Ryo Furukawa: Spatio-Temporal Data Management for Moving Objects Using the PMD-Tree. ER Workshops 1998: 496-507
16. Junping Sun, William I. Grosky: Dynamic Maintenance of Multidimensional Range Data Partitioning for Parallel Data Processing. DOLAP 1998: 72-79
17. Thomas A. Mück, Martin L. Polaschek: A Configrable Type Hierarchy Index for OODB. VLDB J. 6(4): 312-332(1997)
18. Euripides G. M. Petrakis, Christos Faloutsos: Similarity Searching in Medical Image Databases. IEEE Trans. Knowl. Data Eng. 9(3): 435-447(1997)
19. Christos Faloutsos, H. V. Jagadish, Yannis Manolopoulos: Analysis of the n-Dimensional Quadtree Decomposition for Arbitrary Hyperectangles. IEEE Trans. Knowl. Data Eng. 9(3): 373-383(1997)
20. Daniel Barbará, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond T. Ng, Viswanath Poosala, Kenneth A. Ross, Kenneth C. Sevcik: The New Jersey Data Reduction Report. IEEE Data Eng. Bull. 20(4): 3-45(1997)
21. Jong-Hak Lee, Young-Koo Lee, Kyu-Young Whang, Il-Yeol Song: A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations. VLDB 1997: 416-425
22. Norio Katayama, Shin'ichi Satoh: The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. SIGMOD Conference 1997: 369-380
23. Kyuseok Shim, Ramakrishnan Srikant, Rakesh Agrawal: High-Dimensional Similarity Joins. ICDE 1997: 301-311
24. Thomas A. Mück, Martin L. Polaschek: The Multikey Type Index for Persistent Object Sets. ICDE 1997: 22-31
25. Chee Yong Chan, Cheng Hian Goh, Beng Chin Ooi: Indexing OODB Instances based on Access Proximity. ICDE 1997: 14-21
26. Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996: 215-226
27. Clive G. Page: Astronomical Tables, 2-D Indexing, and Fuzzy-joins. SSDBM 1996: 44-52
28. Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270
29. Andreas Henrich: Improving the Performance of Multi-Dimensional Access Structures Based on k-d-Trees. ICDE 1996: 68-75
30. Nick Koudas, Christos Faloutsos, Ibrahim Kamel: Declustering Spatial Databases on a Multi-Computer Architecture. EDBT 1996: 592-614
31. Harry Leslie, Rohit Jain, Dave Birdsall, Hedieh Yaghmai: Efficient Search of Multi-Dimensional B-Trees. VLDB 1995: 710-719
32. Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145
33. Michael Freeston: A General Solution of the n-dimensional B-tree Problem. SIGMOD Conference 1995: 80-91
34. Alexander Brodsky, Catherine Lassez, Jean-Louis Lassez, Michael J. Maher: Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data. PODS 1995: 54-65
35. William C. Wake, Edward A. Fox: SortTables: A Browser for a Digital Library. CIKM 1995: 175-181
36. Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)
37. Akhil Kumar: G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994)
38. Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509
39. Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Kumar V. Vadaparty: A Scientific Database System for Polymers and Materials Engineering Needs. SSDBM 1994: 138-148
40. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multibucket Data Leaves with Partial Expansions. ACM Trans. Database Syst. 18(1): 157-180(1993)
41. Yasuaki Nakamura, Shigeru Abe, Yutaka Ohsawa, Masao Sakauchi: A Balanced Hierarchical Data Structure for Multidimensional Data with Highly Efficient Dynamic Characteristics. IEEE Trans. Knowl. Data Eng. 5(4): 682-694(1993)
42. Hongjun Lu, Beng Chin Ooi: Spatial Indexing: Past and Future. IEEE Data Eng. Bull. 16(3): 16-21(1993)
43. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
44. Ludger Becker, Klaus Hinrichs, Ulrich Finke: A New Algorithm for Computing Joins with Grid Files. ICDE 1993: 190-197
45. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
46. Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204
47. Jui-Tine Lee, Geneva G. Belford: An Efficient Object-based Algorithm for Spatial Searching, Insertion and Deletion. ICDE 1992: 40-47
48. Guido Moerkotte, Peter C. Lockemann: Reactive Consistency Control In Deductive Databases. ACM Trans. Database Syst. 16(4): 670-702(1991)
49. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multi-Bucket Data Leaves with Partial Expansions. PODS 1991: 164-180
50. Aris M. Ouksel, Otto Mayer: The Nested Interpolation Based Grid File. MFDBS 1991: 173-187
51. Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
52. David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990)
53. Lilian Harada, Miyuki Nakano, Masaru Kitsuregawa, Mikio Takagi: Query Processing for Multi-Attribute Clustered Records. VLDB 1990: 59-70
54. Dan E. Willard: Quasilinear Algorithms for Processing Relational Calculus Expressions. PODS 1990: 243-257
55. Yutaka Ohsawa, Masao Sakauchi: A New Tree Type Data Structure with Homogeneous Nodes Suitable for a Very Large Spatial Database. ICDE 1990: 296-303
56. H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319
57. Meng Chang Chen, Lawrence McNamee: On the Data Model and Access Method of Summary Data Management. IEEE Trans. Knowl. Data Eng. 1(4): 519-529(1989)
58. Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53
59. Georges Gardarin, Jean-Pierre Cheiney, Gerald Kiernan, Dominique Pastre, Hervé Stora: Managing Complex Objects in an Extensible Relational DBMS. VLDB 1989: 55-65
60. Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305
61. Beng Chin Ooi, Ron Sacks-Davis, Ken J. McDonell: Extending a DBMS for Geographic Applications. ICDE 1989: 590-597
62. David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304
63. Masaru Kitsuregawa, Lilian Harada, Mikio Takagi: Join Strategies on KB-Tree Indexed Relations. ICDE 1989: 85-93
64. Meng Chang Chen, Lawrence McNamee: A Data Model and Access Method for Summary Data Management. ICDE 1989: 242-249
65. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
66. Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
67. Clement T. Yu, Tsang Ming Jiang: Adaptive Algorithms for Balanced Multidimensional Clustering. ICDE 1988: 386-393
68. Jean-Pierre Cheiney, Gerald Kiernan: A Functional Clustering Method for Optimal Access to Complex Domains in a Relational DBMS. ICDE 1988: 394-401
69. C. Thomas Wu, Walter A. Burkhard: Associative Searching in Multiple Storage Units. ACM Trans. Database Syst. 12(1): 38-64(1987)
70. Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518
71. Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439
72. Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336
73. Christos Faloutsos: Multiattribute Hashing Using Gray Codes. SIGMOD Conference 1986: 227-238
74. Jay Banerjee, Won Kim: Supporting VLSI Geometry Operations in a Database System. ICDE 1986: 409-415
75. Christos Faloutsos: Access Methods for Text. ACM Comput. Surv. 17(1): 49-74(1985)
76. Shinya Fushimi, Masaru Kitsuregawa, Masaya Nakayama, Hidehiko Tanaka, Tohru Moto-Oka: Algorithm and Performance Evaluation of Adaptive Multidimensional Clustering Technique. SIGMOD Conference 1985: 308-318
77. D. A. Beckley, Martha W. Evens, V. K. Raman: Multikey Retrieval from K-d Trees and Quad-Trees. SIGMOD Conference 1985: 291-301
78. Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984)
79. Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984)
80. Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506
81. Dan E. Willard: Efficient Processing of Relational Calculus Expressions Using Range Query Theory. SIGMOD Conference 1984: 164-175
82. Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57
83. Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190
84. Tetsuro Ito, Makoto Kizawa: Hierarchical File Organization and Its Application to Similar-String Matching. ACM Trans. Database Syst. 8(3): 410-433(1983)
85. Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105
86. Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89
87. Jirun Dong, Richard Hull: Applying Approximate Order Dependency to Reduce Indexing Space. SIGMOD Conference 1982: 119-127
88. John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18
89. D. T. Lee, C. K. Wong: Quintary Trees: A File Structure for Multidimensional Database Systems. ACM Trans. Database Syst. 5(3): 339-353(1980)
90. Jo-Mei Chang, King-sun Fu: A Dynamic Clustering Technique for Physical Database Design. SIGMOD Conference 1980: 188-199
91. Per Svensson: On Search Performance for Conjunctive Queries in Compressed, Fully Transposed Ordered Files. VLDB 1979: 155-163
92. Harry B. Hunt III, Daniel J. Rosenkrantz: The Complexity of Testing Predicate Locks. SIGMOD Conference 1979: 127-133
93. Walter A. Burkhard: Hashing and Trie Algorithms for Partial Match Retrieval. ACM Trans. Database Syst. 1(2): 175-187(1976)