A Class of Data Structures for Associative Searching.
Jack A. Orenstein, T. H. Merrett:
A Class of Data Structures for Associative Searching.
PODS 1984: 181-190@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}
}
BibTeX
Abstract
By interleaving the bits of the binary representations of the attribute values in a tuple, an integer corresponding to the tuple is created. A set of these integers represents a relation. The usual ordering of these integers corresponds to an ordering of multidimensional data that allows the use of conventional file organizations, such as Btrees, in the efficient processing of multidimensional queries (e.g. range queries). The class of data structures generated by this scheme includes a type of kd tree whose balance can be efficiently maintained, a multidimensional Btree which is simpler than previously proposed generalizations, and some previously reported date structures for range searching. All of the data structures in this class also support the efficient implementation of the set operations.
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.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
BibTeX
Printed Edition
Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada.
ACM 1984, ISBN 0-89791-128-8
Contents BibTeX
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
- H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava:
Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse.
SIGMOD Conference 1999: 37-48
- Kaushik Chakrabarti, Sharad Mehrotra:
Efficient Concurrency Control in Multidimensional Access Methods.
SIGMOD Conference 1999: 25-36
- Volker Markl, Martin Zirkel, Rudolf Bayer:
Processing Operations with Restrictions in RDBMS without External Sorting: The Tetris Algorithm.
ICDE 1999: 562-571
- Dimitris G. Kapopoulos, Michael Hatzopoulos:
The Gr_Tree: The Use of Active Regions in G-Trees.
ADBIS 1999: 141-155
- Bongki Moon, Joel H. Saltz:
Scalability Analysis of Declustering Methods for Multidimensional Range Queries.
IEEE Trans. Knowl. Data Eng. 10(2): 310-327(1998)
- Volker Gaede, Oliver Günther:
Multidimensional Access Methods.
ACM Comput. Surv. 30(2): 170-231(1998)
- Kaushik Chakrabarti, Sharad Mehrotra:
Dynamic Granular Locking Approach to Phantom Protection in R-Trees.
ICDE 1998: 446-454
- 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)
- 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)
- John C. Shafer, Rakesh Agrawal:
Parallel Algorithms for High-dimensional Similarity Joins for Data Mining Applications.
VLDB 1997: 176-185
- Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner:
Integrated Query Processing Strategies for Spatial Path Queries.
ICDE 1997: 477-486
- Chialin Chang, Bongki Moon, Anurag Acharya, Carter Shock, Alan Sussman, Joel H. Saltz:
Titan: A High-Performance Remote Sensing Database.
ICDE 1997: 375-384
- Christos Faloutsos, Volker Gaede:
Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension.
VLDB 1996: 40-50
- Jignesh M. Patel, David J. DeWitt:
Partition Based Spatial-Merge Join.
SIGMOD Conference 1996: 259-270
- Georgios Evangelidis, David B. Lomet, Betty Salzberg:
The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation.
VLDB 1995: 551-561
- 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
- Akhil Kumar:
G-Tree: A New Data Structure for Organizing Multidimensional Data.
IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994)
- Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Kumar V. Vadaparty:
A Scientific Database System for Polymers and Materials Engineering Needs.
SSDBM 1994: 138-148
- 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)
- Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger:
Efficient Processing of Spatial Joins Using R-Trees.
SIGMOD Conference 1993: 237-246
- Erik G. Hoel, Hanan Samet:
A Qualitative Comparison Study of Data Structures for Large Line Segment Databases.
SIGMOD Conference 1992: 205-214
- 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)
- Bernhard Seeger, Hans-Peter Kriegel:
The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems.
VLDB 1990: 590-601
- H. V. Jagadish:
On Indexing Line Segments.
VLDB 1990: 614-625
- Jack A. Orenstein:
A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces.
SIGMOD Conference 1990: 343-352
- H. V. Jagadish:
Linear Clustering of Objects with Multiple Atributes.
SIGMOD Conference 1990: 332-342
- H. V. Jagadish:
Spatial Search with Polyhedra.
ICDE 1990: 311-319
- Andreas Hutflesz, Hans-Werner Six, Peter Widmayer:
The R-File: An Efficient Access Structure for Proximity Queries.
ICDE 1990: 372-379
- Jack A. Orenstein:
Redundancy in Spatial Databases.
SIGMOD Conference 1989: 295-305
- Doron Rotem:
Clustered Multiattribute Hash Files.
PODS 1989: 225-234
- Christos Faloutsos, Shari Roseman:
Fractals for Secondary Key Retrieval.
PODS 1989: 247-252
- David B. Lomet, Betty Salzberg:
A Robust Multi-Attribute Search Structure.
ICDE 1989: 296-304
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents - Bernhard Seeger, Hans-Peter Kriegel:
Techniques for Design and Implementation of Efficient Spatial Access Methods.
VLDB 1988: 360-371
- Hans-Peter Kriegel, Bernhard Seeger:
PLOP-Hashing: A Grid File without Directory.
ICDE 1988: 369-376
- Andreas Hutflesz, Hans-Werner Six, Peter Widmayer:
Globally Order Preserving Multidimensional Linear Hashing.
ICDE 1988: 572-579
- C. Thomas Wu, Walter A. Burkhard:
Associative Searching in Multiple Storage Units.
ACM Trans. Database Syst. 12(1): 38-64(1987)
- Jack A. Orenstein:
Spatial Query Processing in an Object-Oriented Database System.
SIGMOD Conference 1986: 326-336
- Christos Faloutsos:
Multiattribute Hashing Using Gray Codes.
SIGMOD Conference 1986: 227-238
- Ekow J. Otoo:
Balanced Multidimensional Extendible Hash Tree.
PODS 1986: 100-113
- Aris M. Ouksel:
The Interpolation-Based Grid File.
PODS 1985: 20-27
- Hanan Samet:
The Quadtree and Related Hierarchical Data Structures.
ACM Comput. Surv. 16(2): 187-260(1984)
- Walter A. Burkhard:
Interpolation-Based Index Maintenance.
PODS 1983: 76-89
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:45 2009