Hashing and Trie Algorithms for Partial Match Retrieval.

Walter A. Burkhard: Hashing and Trie Algorithms for Partial Match Retrieval. ACM Trans. Database Syst. 1(2): 175-187(1976)

@article{DBLP:journals/tods/Burkhard76,
  author    = {Walter A. Burkhard},
  title     = {Hashing and Trie Algorithms for Partial Match Retrieval},
  journal   = {ACM Trans. Database Syst.},
  volume    = {1},
  number    = {2},
  year      = {1976},
  pages     = {175-187},
  ee        = {http://doi.acm.org/10.1145/320455.320469, db/journals/tods/Burkhard76.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

File designs suitable for retrieval from a file of k-letter words when queries may be only partially specified are examined. A new class of partial match file designs (called PMF designs) based upon hash coding and trie search algorithms which provide good worst-case performance is introduced. Upper bounds on the worst-case performance of these designs are given along with examples of files achieving the bound. Other instances of PMF designs are known to have better worst-case performances. The implementation of the file designs with associated retrieval algorithms is considered. The amount of storage required is essentially that required of the records themselves.

Copyright © 1976 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...

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/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

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/aDVD2 or /dvd

BibTeX

References

[1]: Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[2]: Walter A. Burkhard: Partial-Match Queries and File Designs. VLDB 1975: 523-525 BibTeX
[3]: ...
[4]: ...
[5]: ...
[6]: Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX
[7]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[8]: ...
[9]: Robert Morris: Scatter Storage Techniques. Commun. ACM 11(1): 38-44(1968) BibTeX
[10]: Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976) BibTeX
[11]: Edward H. Sussenguth Jr.: Use of Tree Structures for Processing Files. Commun. ACM 6(5): 272-279(1963) BibTeX

Referenced by

Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
R. Ramesh, A. J. G. Babu, J. Peter Kincaid: Variable-Depth Trie Index Optimization: Theory and Experimental Results. ACM Trans. Database Syst. 14(1): 41-74(1989)
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
Chin-Chen Chang, C. Y. Chen: Orthogonal Range Retrieval Using Bucket Address Hashing. SSDBM 1988: 133-140
Myoung-Ho Kim, Sakti Pramanik: Optimal File Distribution For Partial Match Retrieval. SIGMOD Conference 1988: 173-182
C. Thomas Wu, Walter A. Burkhard: Associative Searching in Multiple Storage Units. ACM Trans. Database Syst. 12(1): 38-64(1987)
Jo-Mei Chang, King-sun Fu: A Dynamic Clustering Technique for Physical Database Design. SIGMOD Conference 1980: 188-199
Douglas Comer: Heuristics for Trie Index Minimization. ACM Trans. Database Syst. 4(3): 383-395(1979)
Walter A. Burkhard: Partial-Match Hash Coding: Benefits of Redundancy. ACM Trans. Database Syst. 4(2): 228-239(1979)
Alfred V. Aho, Jeffrey D. Ullman: Optimal Partial-Match Retrieval When Fields Are Independently Specified. ACM Trans. Database Syst. 4(2): 168-179(1979)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]