ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Efficient Search of Multi-Dimensional B-Trees.

Harry Leslie, Rohit Jain, Dave Birdsall, Hedieh Yaghmai: Efficient Search of Multi-Dimensional B-Trees. VLDB 1995: 710-719
@inproceedings{DBLP:conf/vldb/LeslieJBY95,
  author    = {Harry Leslie and
               Rohit Jain and
               Dave Birdsall and
               Hedieh Yaghmai},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {Efficient Search of Multi-Dimensional B-Trees},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {710-719},
  ee        = {db/conf/vldb/LeslieJBY95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Data in relational databases is frequently stored and retrieved using B-Trees. In decision support applications the key of the B-Tree frequently involvesthe concatenation of several fields of the relational table. During retrieval, it is desirable to be able to access a small subset of the table based on partial key information, where some fields of the key may either not be present, involve ranges, or lists of values. It is also advantageous to allow this type of access with general expressions involving any combination of disjuncts on key columns. This paper describes a method whereby B-Trees can be efficiently used to retrieve small subsets, thus avoiding large scans of potentially huge tables. Another benefit is the ability of this method to reduce the need for additional secondary indexes, thus saving space, maintenance cost, and random accesses.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Bayer & Schkolnick 1977]
Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bayer & Unterauer 1977]
Rudolf Bayer, Karl Unterauer: Prefix B-Trees. ACM Trans. Database Syst. 2(1): 11-26(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Beckmann et al. 1990]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bentley 1975]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chang & Fu 1980]
Jo-Mei Chang, King-sun Fu: A Dynamic Clustering Technique for Physical Database Design. SIGMOD Conference 1980: 188-199 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Comer 1979]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Guttman 1984]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Held & Stonebraker 1975]
Gerald Held, Michael Stonebraker: B-trees Re-examined. Commun. ACM 21(2): 139-143(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Knuth 1973]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lomet & Salzberg 1989]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nievergelt & Hinterberger 1981]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multi-Key File Structure. ECI 1981: 236-251 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Robinson 1981]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rothnie & Lozano 1974]
James B. Rothnie Jr., Tomas Lozano: Attribute Based File Organization in a Paged Memory Environment. Commun. ACM 17(2): 63-69(1974) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Seeger & Krieger 1990]
Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sellis et al. 1987]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Ming-Chuan Wu, Alejandro P. Buchmann: Encoded Bitmap Indexing for Data Warehouses. ICDE 1998: 220-230

Copyright © Mon Nov 2 21:18:59 2009 by Michael Ley (ley@uni-trier.de)