ACM SIGMOD Anthology VLDB dblp.uni-trier.de

On B-Tree Indices for Skewed Distributions.

Christos Faloutsos, H. V. Jagadish: On B-Tree Indices for Skewed Distributions. VLDB 1992: 363-374
@inproceedings{DBLP:conf/vldb/FaloutsosJ92,
  author    = {Christos Faloutsos and
               H. V. Jagadish},
  editor    = {Li-Yan Yuan},
  title     = {On B-Tree Indices for Skewed Distributions},
  booktitle = {18th International Conference on Very Large Data Bases, August
               23-27, 1992, Vancouver, Canada, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1992},
  isbn      = {1-55860-151-1},
  pages     = {363-374},
  ee        = {db/conf/vldb/FaloutsosJ92.html},
  crossref  = {DBLP:conf/vldb/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

It is often the case that the set of values over which a B-Tree is constructed has a skewed distribution. We present a geometric growth technique to manage postings records in such cases, and show that the performance of such a technique is better than that of a straightforward fixed length postings list: It guarantees 1 disk access on searching, and it takes a fraction of the space that its competitor requires (55% to 66%, in our experiments).

Copyright © 1992 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

Li-Yan Yuan (Ed.): 18th International Conference on Very Large Data Bases, August 23-27, 1992, Vancouver, Canada, Proceedings. Morgan Kaufmann 1992, ISBN 1-55860-151-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Christodoulakis84a]
Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Faloutsos92b]
...
[Faloutsos90a]
Christos Faloutsos: Signature-Based Text Retrieval Methods: A Survey. IEEE Data Eng. Bull. 13(1): 25-32(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Faloutsos92a]
Christos Faloutsos, H. V. Jagadish: Hybrid Index Organizations for Text Databases. EDBT 1992: 310-327 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ioannidis91a]
Yannis E. Ioannidis, Stavros Christodoulakis: On the Propagation of Errors in the Size of Join Results. SIGMOD Conference 1991: 268-277 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sacks-Davis87a]
Ron Sacks-Davis, Alan J. Kent, Kotagiri Ramamohanarao: Multikey Access Methods Based on Superimposed Coding Techniques. ACM Trans. Database Syst. 12(4): 655-696(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wolf91a]
Joel L. Wolf, Daniel M. Dias, Philip S. Yu, John Turek: An Effective Algorithm for Parallelizing Hash Joins in the Presence of Data Skew. ICDE 1991: 200-209 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Zipf49a]
George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:22:51 2010 by Michael Ley (ley@uni-trier.de)