ACM SIGMOD Anthology VLDB dblp.uni-trier.de

On Search Performance for Conjunctive Queries in Compressed, Fully Transposed Ordered Files.

Per Svensson: On Search Performance for Conjunctive Queries in Compressed, Fully Transposed Ordered Files. VLDB 1979: 155-163
@inproceedings{DBLP:conf/vldb/Svensson79,
  author    = {Per Svensson},
  editor    = {Antonio L. Furtado and
               Howard L. Morgan},
  title     = {On Search Performance for Conjunctive Queries in Compressed,
               Fully Transposed Ordered Files},
  booktitle = {Fifth International Conference on Very Large Data Bases, October
               3-5, 1979, Rio de Janeiro, Brazil, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1979},
  pages     = {155-163},
  ee        = {db/conf/vldb/Svensson79.html},
  crossref  = {DBLP:conf/vldb/79},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A new file organization method, providing very high performance for a large class of associative queries. is abstractly defined. The organization may be viewed both as a development of the fully transposed file, and as a generalized trie. Its average search performance is modelled under some simplifying assumptions. Also, the model's predictions are compared with measurement results obtained from a prototype system, and a qualitative agreement is found.

For purposes of comparison, analytical and measured cost curves for fully transposed file search are also given.

Copyright © 1979 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Antonio L. Furtado, Howard L. Morgan (Eds.): Fifth International Conference on Very Large Data Bases, October 3-5, 1979, Rio de Janeiro, Brazil, Proceedings. IEEE Computer Society 1979
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
...
[2]
Don S. Batory: On Searching Transposed Files. ACM Trans. Database Syst. 4(4): 531-544(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
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
[5]
D. T. Lee, C. K. Wong: Worst-Case Analysis for Region and Partial Region Searches in Multidimensional Binary Search Trees and Balanced Quad Trees. Acta Inf. 9: 23-29(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
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
[8]
Jon Louis Bentley, Hermann A. Maurer: Efficient Worst-Case Data Structures for Range Searching. Acta Inf. 13: 155-168(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:55 2010 by Michael Ley (ley@uni-trier.de)