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

@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

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb7588 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

...

[2]

Don S. Batory: On Searching Transposed Files. ACM Trans. Database Syst. 4(4): 531-544(1979)

[3]

...

[4]

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

[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)

[6]

Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976)

[7]

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

[8]

Jon Louis Bentley, Hermann A. Maurer: Efficient Worst-Case Data Structures for Range Searching. Acta Inf. 13: 155-168(1980)