A Class of Data Structures for Associative Searching.

@inproceedings{DBLP:conf/pods/OrensteinM84,
  author    = {Jack A. Orenstein and
               T. H. Merrett},
  title     = {A Class of Data Structures for Associative Searching},
  booktitle = {Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada},
  publisher = {ACM},
  year      = {1984},
  isbn      = {0-89791-128-8},
  pages     = {181-190},
  ee        = {http://doi.acm.org/10.1145/588011.588037, db/conf/pods/OrensteinM84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1984 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.

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[Baye72]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX

[Bent75a]

Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX

[Bent79a]

Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) BibTeX

[Bent79b]

Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) BibTeX

[Burk83]

Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89 BibTeX

[Come79]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[Fagi79]

Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) BibTeX

[Fred60]

...

[Gopa80]

V. Gopalakrishna, C. E. Veni Madhavan: Performance Evaluation of Attribute-Based Tree Organization. ACM Trans. Database Syst. 5(1): 69-87(1980) BibTeX

[IBM66]

...

[Kash77]

Rangasami L. Kashyap, S. K. C. Subas, S. Bing Yao: Analysis of the Multiple-Attribute-Tree Data-Base Organization. IEEE Trans. Software Eng. 3(6): 451-467(1977) BibTeX

[Knut73]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[Litw80]

Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX

[Oren82]

Jack A. Orenstein: Multidimensional Tries Used for Associative Searching. Inf. Process. Lett. 14(4): 150-157(1982) BibTeX

[Oren83a]

...

[Oren83b]

Jack A. Orenstein: A Dynamic Hash File for Random and Sequential Accessing. VLDB 1983: 132-141 BibTeX

[Ouks83]

Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105 BibTeX

[Robi81]

John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX

[Sche82]

Peter Scheuermann, Aris M. Ouksel: Multidimensional B-trees for associative searching in database systems. Inf. Syst. 7(2): 123-137(1982) BibTeX

[Suss63]

...

[Tamm81]

Markku Tamminen: Order Preserving Extendible Hashing and Bucket Tries. BIT 21(4): 419-435(1981) BibTeX

[Yao78]

Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

1. H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava: Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse. SIGMOD Conference 1999: 37-48
2. Kaushik Chakrabarti, Sharad Mehrotra: Efficient Concurrency Control in Multidimensional Access Methods. SIGMOD Conference 1999: 25-36
3. Volker Markl, Martin Zirkel, Rudolf Bayer: Processing Operations with Restrictions in RDBMS without External Sorting: The Tetris Algorithm. ICDE 1999: 562-571
4. Dimitris G. Kapopoulos, Michael Hatzopoulos: The G^r_Tree: The Use of Active Regions in G-Trees. ADBIS 1999: 141-155
5. Bongki Moon, Joel H. Saltz: Scalability Analysis of Declustering Methods for Multidimensional Range Queries. IEEE Trans. Knowl. Data Eng. 10(2): 310-327(1998)
6. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
7. Kaushik Chakrabarti, Sharad Mehrotra: Dynamic Granular Locking Approach to Phantom Protection in R-Trees. ICDE 1998: 446-454
8. Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hB-Pi-Tree: A Multi-Attribute Index Supporting Concurrency, Recovery and Node Consolidation. VLDB J. 6(1): 1-25(1997)
9. Shashi Shekhar, Duen-Ren Liu: CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations. IEEE Trans. Knowl. Data Eng. 9(1): 102-119(1997)
10. John C. Shafer, Rakesh Agrawal: Parallel Algorithms for High-dimensional Similarity Joins for Data Mining Applications. VLDB 1997: 176-185
11. Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Integrated Query Processing Strategies for Spatial Path Queries. ICDE 1997: 477-486
12. Chialin Chang, Bongki Moon, Anurag Acharya, Carter Shock, Alan Sussman, Joel H. Saltz: Titan: A High-Performance Remote Sensing Database. ICDE 1997: 375-384
13. Christos Faloutsos, Volker Gaede: Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension. VLDB 1996: 40-50
14. Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270
15. Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation. VLDB 1995: 551-561
16. Shashi Shekhar, Duen-Ren Liu: CCAM: A Connectivity-Clustered Access Method for Aggregate Queries on Transportation Networks: A Summary of Results. ICDE 1995: 410-419
17. Akhil Kumar: G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994)
18. Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Kumar V. Vadaparty: A Scientific Database System for Polymers and Materials Engineering Needs. SSDBM 1994: 138-148
19. Georgios Evangelidis, Betty Salzberg: Using the Holy Brick Tree for Spatial Data in General Purpose DBMSs. IEEE Data Eng. Bull. 16(3): 34-39(1993)
20. Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246
21. Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214
22. 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)
23. Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601
24. H. V. Jagadish: On Indexing Line Segments. VLDB 1990: 614-625
25. Jack A. Orenstein: A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces. SIGMOD Conference 1990: 343-352
26. H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342
27. H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319
28. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The R-File: An Efficient Access Structure for Proximity Queries. ICDE 1990: 372-379
29. Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305
30. Doron Rotem: Clustered Multiattribute Hash Files. PODS 1989: 225-234
31. Christos Faloutsos, Shari Roseman: Fractals for Secondary Key Retrieval. PODS 1989: 247-252
32. David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304
33. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
34. Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
35. Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376
36. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Globally Order Preserving Multidimensional Linear Hashing. ICDE 1988: 572-579
37. C. Thomas Wu, Walter A. Burkhard: Associative Searching in Multiple Storage Units. ACM Trans. Database Syst. 12(1): 38-64(1987)
38. Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336
39. Christos Faloutsos: Multiattribute Hashing Using Gray Codes. SIGMOD Conference 1986: 227-238
40. Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113
41. Aris M. Ouksel: The Interpolation-Based Grid File. PODS 1985: 20-27
42. Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984)
43. Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89