Optimal Partial-Match Retrieval When Fields Are Independently Specified.

@article{DBLP:journals/tods/AhoU79,
  author    = {Alfred V. Aho and
               Jeffrey D. Ullman},
  title     = {Optimal Partial-Match Retrieval When Fields Are Independently
               Specified},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {2},
  year      = {1979},
  pages     = {168-179},
  ee        = {http://doi.acm.org/10.1145/320071.320074, db/journals/tods/AhoU79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper considers the design of a system to answer partial-match queries from a file containing a collection of records, each record consisting of a sequence of fields. A partial-match query is a specification of values for zero or more fields of a record, and the answer to a query is a listing of all records in the file whose fields match the specified values.

A design is considered in which the file is stored in a set of bins. A formula is derived for the optimal number of bits in a bin address to assign to each field, assuming the probability that a given field is specified in a query is independent of what other fields are specified. Implications of the optimality criterion on the size of bins are also discussed.

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

• 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

• 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

References

[1]

Alfred V. Aho, Margaret J. Corasick: Efficient String Matching: An Aid to Bibliographic Search. Commun. ACM 18(6): 333-340(1975) BibTeX

[2]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[3]

Azad Bolour: Optimality Properties of Multiple-Key Hashing Functions. J. ACM 26(2): 196-210(1979) BibTeX

[4]

...

[5]

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

[6]

...

[7]

...

[8]

Malcolm C. Harrison: Implementation of the Substring Test by Hashing. Commun. ACM 14(12): 777-779(1971) BibTeX

[9]

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

[10]

Donald E. Knuth, James H. Morris Jr., Vaughan R. Pratt: Fast Pattern Matching in Strings. SIAM J. Comput. 6(2): 323-350(1977) BibTeX

[11]

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

[12]

James B. Rothnie Jr., Tomas Lozano: Attribute Based File Organization in a Paged Memory Environment. Commun. ACM 17(2): 63-69(1974) BibTeX

[13]

Charles S. Roberts: Partial-Match Via the Method of Superimposed Codes. Proceedings of the IEEE 67(12): 1624-1642(1979) BibTeX

[14]

...

[15]

...

[16]

Ken Thompson: Regular Expression Search Algorithm. Commun. ACM 11(6): 419-422(1968) BibTeX

[17]

...

Referenced by

1. C. Y. Chen, H. F. Lin, Chin-Chen Chang, Richard C. T. Lee: Optimal Bucket Allocation Design of k-ary MKH Files for Partial Match Retrieval. IEEE Trans. Knowl. Data Eng. 9(1): 148-160(1997)
2. Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: Optimal Allocation of Two-Dimensional Data. ICDT 1997: 409-418
3. Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: Optimal Disk Allocation for Partial Match Queries. ACM Trans. Database Syst. 18(1): 132-156(1993)
4. David Hung-Chang Du, Sheau-Ru Tong: Multilevel Extendible Hashing: A File Structure for Very Large Databases. IEEE Trans. Knowl. Data Eng. 3(3): 357-370(1991)
5. Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
6. Muruganandan Kumar, Johnny Wong: A Data Model for Design Objects. DASFAA 1991: 274-282
7. David Hung-Chang Du, Subbarao Ghanta, Kurt Maly, Suzanne M. Sharrock: An Efficient File Structure for Document Retrieval in the Automated Office Environment. IEEE Trans. Knowl. Data Eng. 1(2): 258-273(1989)
8. Doron Rotem: Clustered Multiattribute Hash Files. PODS 1989: 225-234
9. Christos Faloutsos, Dimitris N. Metaxas: Declustering Using Error Correcting Codes. PODS 1989: 253-258
10. Kotagiri Ramamohanarao, John Shepherd, Ron Sacks-Davis: Partial-match Retrieval using Multiple-Key Hashing with Multiple File Copies. DASFAA 1989: 225-232
11. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
12. Chin-Chen Chang, C. Y. Chen: Orthogonal Range Retrieval Using Bucket Address Hashing. SSDBM 1988: 133-140
13. Myoung-Ho Kim, Sakti Pramanik: Optimal File Distribution For Partial Match Retrieval. SIGMOD Conference 1988: 173-182
14. Christos Faloutsos, Stavros Christodoulakis: Optimal Signature Extraction and Information Loss. ACM Trans. Database Syst. 12(3): 395-428(1987)
15. David Hung-Chang Du, Subbarao Ghanta, Kurt Maly, Suzanne M. Sharrock: An Efficient File Structure for Document Retrieval in the Automated Office Environment. ICDE 1987: 165-172
16. James A. Thom, Kotagiri Ramamohanarao, Lee Naish: A Superjoin Algorithm for Deductive Databases. VLDB 1986: 189-196
17. Christos Faloutsos: Multiattribute Hashing Using Gray Codes. SIGMOD Conference 1986: 227-238
18. T. S. Yuen, H. C. Du: Dynamic File Organizations For Partial Match Retrieval Based on Linear Hashing. ICDE 1986: 116-123
19. E. O. Onuegbe, H. C. Du: A Locking Scheme for Associative Retrieval. ICDE 1986: 574-579
20. Christos Faloutsos: Access Methods for Text. ACM Comput. Surv. 17(1): 49-74(1985)
21. Ekow J. Otoo: A Multidimensional Digital Hashing Scheme for Files With Composite Keys. SIGMOD Conference 1985: 214-229
22. Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984)
23. Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506
24. Kotagiri Ramamohanarao, John W. Lloyd: Partial-Match Retrieval Using Hashing and Descriptors. ACM Trans. Database Syst. 8(4): 552-576(1983)
25. Shlomo Moran: On the Complexity of Designing Optimal Partial-Match Retrieval Systems. ACM Trans. Database Syst. 8(4): 543-551(1983)
26. David Hung-Chang Du, J. S. Sobolewski: Disk Allocation for Cartesian Product Files on Multiple-Disk Systems. ACM Trans. Database Syst. 7(1): 82-101(1982)
27. Jo-Mei Chang, King-sun Fu: A Dynamic Clustering Technique for Physical Database Design. SIGMOD Conference 1980: 188-199
28. Walter A. Burkhard: Partial-Match Hash Coding: Benefits of Redundancy. ACM Trans. Database Syst. 4(2): 228-239(1979)