article

Free access

Partial-match hash coding: benefits of redundancy

Editor: David K. Hsiao Author:

Walter A. BurkhardAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 4, Issue 2

Pages 228 - 239

https://doi.org/10.1145/320071.320079

Published: 01 June 1979 Publication History

Abstract

File designs suitable for retrieval from a file of k-field records when queries may be partially specified are examined. Storage redundancy is introduced to obtain improved worst-case and average-case performances. The resulting storage schemes are appropriate for replicated distributed database environments; it is possible to improve the overall average and worst-case behavior for query response as well as provide an environment with very high reliability. Within practical systems it will be possible to improve the query response time performance as well as reliability over comparable systems without replication.

References

[1]

AHO, A.V., AND CORASICK, M.J. Efficient string matching: An aid to bibliographical search. Comm. ACM 18, 6 (June 1975), 333-340.

Digital Library

[2]

AHO, A.V., AND ULLMAN, J.D. Optimal partial-match retrieval when fields are independently specified. ACM Trans. Database Syst. 4, 2 (June 1979), 168-179.

Digital Library

[3]

BOLOUR, A. Optimality properties of multiple key hashing functions. J. ACM 26, 2 (April 1979) pp. 196-210.

Digital Library

[4]

BURKHARD, W.A. Partial-match retrieval. BIT 16 {1976), 13-31.

[5]

BURKHARD, W.A. Hashing and trie algorithms for partial-match retrieval. ACM Trans. Database Syst. 1 (1976), 175-187.

Digital Library

[6]

BURKHARD, W.A. Associative retrieval trie hash-coding. ACM SIGACT Conf. Record, 1976, pp. 211-219; and J. Comptr. and Syst. Sci. 15 (1977), 280-299.

Digital Library

[7]

BURKHARD, W.A. Non-uniform partial-match file designs. Theoret. Comptr. Sci. 5 (1977), 1-23.

[8]

BURKHARD, W.A. Partial-match hash coding: Benefits of redundancy. UCSD Comptr. Sci. Tech. Rep. 17, U. of California at San Diego, La Jolla, Calif., 1977, p. 43.

[9]

CHU, W.W. Optimal fde allocation in a multiple computer system. IEEE Trans. on Computers C-18 (1969), 885-889.

Digital Library

[10]

COMER, D., AND SETHI, R. NP-completeness of tree structured index minimization.TR #167, The Pennsylvania State University, University Park, Pa., 1975, p. 43.

[11]

GHOSH, S.P. Data Base Organization for Data Management. Academic Press, New York, 1977.

Digital Library

[12]

GUSTAFSON, R.A. A randomized combinatorial file structure for storage and retrieval systems. Ph.D. Th., U. of South Carolina, Columbia, S.C., 1969, p. 92.

[13]

HARRISON, M.C. Implementation of the substring test by hashing. Comm. ACM 14, 12 (Dec. 1971), 777-779.

Digital Library

[14]

KNUTH, D.E. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison- Wesley, Reading, Mass., 1973.

Digital Library

[15]

KNUTH, D.E., MORRIS, J., AND PRATT, V. Fast pattern matching in strings. SIAM J. Cornptg. 6 (1977), 323-350.

[16]

MILLS, W.H. Covering problems. Proc. Fourth Southeastern Conf. on Combinatorics, Graph Theory and Computing, 1973, pp. 23-52.

[17]

RIVEST, R.L. Partial-match retrieval algorithms. SIAM J. Comptg. 5 {1976), 19-50.

Cited By

Cunto WLau GFlajolet P(2005)Analysis of kdt-trees: Kd-trees improved by local reorganisationsAlgorithms and Data Structures10.1007/3-540-51542-9_4(24-38)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-51542-9_4
Chen CLin HChang CLee R(1997)Optimal Bucket Allocation Design of k-ary MKH Files for Partial Match RetrievalIEEE Transactions on Knowledge and Data Engineering10.1109/69.5670579:1(148-160)Online publication date: 1-Jan-1997
https://dl.acm.org/doi/10.1109/69.567057
Chen CLin HLee RChang C(1996)Redundant MKH files design among multiple disks for concurrent partial match retrievalJournal of Systems and Software10.1016/0164-1212(95)00102-635:3(199-207)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.1016/0164-1212%2895%2900102-6
Show More Cited By

Index Terms

Partial-match hash coding: benefits of redundancy
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data access methods
  2. Information retrieval
    1. Information retrieval query processing

Recommendations

Hashing and trie algorithms for partial match retrieval

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 ...
An Efficient Multiversion Access Structure

An efficient multiversion access structure for a transaction-time database is presented. Our method requires optimal storage and query times for several important queries and logarithmic update times. Three version operations inserts, updates, and ...
Range queries on uncertain data

Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 4, Issue 2

June 1979

128 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/320071

Editor:
David K. Hsiao
Ohio State Univ., Columbus

Issue’s Table of Contents

Copyright © 1979 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1979

Published in TODS Volume 4, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
561
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)7

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cunto WLau GFlajolet P(2005)Analysis of kdt-trees: Kd-trees improved by local reorganisationsAlgorithms and Data Structures10.1007/3-540-51542-9_4(24-38)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-51542-9_4
Chen CLin HChang CLee R(1997)Optimal Bucket Allocation Design of k-ary MKH Files for Partial Match RetrievalIEEE Transactions on Knowledge and Data Engineering10.1109/69.5670579:1(148-160)Online publication date: 1-Jan-1997
https://dl.acm.org/doi/10.1109/69.567057
Chen CLin HLee RChang C(1996)Redundant MKH files design among multiple disks for concurrent partial match retrievalJournal of Systems and Software10.1016/0164-1212(95)00102-635:3(199-207)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.1016/0164-1212%2895%2900102-6
Chang CChen C(1991)A note on allocating k-ary multiple key hashing files among multiple disksInformation Sciences: an International Journal10.1016/0020-0255(91)90006-G55:1-3(69-76)Online publication date: 3-Jun-1991
https://dl.acm.org/doi/10.1016/0020-0255%2891%2990006-G
Aoe J(1990)A compendium of key search referencesACM SIGIR Forum10.1145/101306.10130824:3(26-42)Online publication date: 1-Nov-1990
https://dl.acm.org/doi/10.1145/101306.101308
Ramamohanarao KShepherd JSacks-Davis R(1990)Multi-attribute hashing with multiple file copies for high performance partial-match retrievalBIT10.1007/BF0193165730:3(404-423)Online publication date: 1-Sep-1990
https://dl.acm.org/doi/10.1007/BF01931657
Kim MPramanik S(1988)Optimal file distribution for partial match retrievalACM SIGMOD Record10.1145/971701.5022117:3(173-182)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.1145/971701.50221
Kim MPramanik S(1988)Optimal file distribution for partial match retrievalProceedings of the 1988 ACM SIGMOD international conference on Management of data10.1145/50202.50221(173-182)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.1145/50202.50221
Chan MChung W(1988)Optimal multidisk partial match file designsInformation Processing Letters10.1016/0020-0190(88)90161-528:3(149-155)Online publication date: 4-Jul-1988
https://dl.acm.org/doi/10.1016/0020-0190%2888%2990161-5
Chang CLian L(1987)On Strict Optimality Property of Allocating Binary Cartesian Product Files on Multiple Disk SystemsFoundations of Data Organization10.1007/978-1-4613-1881-1_13(159-175)Online publication date: 1987
https://doi.org/10.1007/978-1-4613-1881-1_13
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents