article

Free access

Partial-match retrieval using indexed descriptor files

Authors:

John L. Pfaltz,

William J. Berman,

Edgar M. CagleyAuthors Info & Claims

Communications of the ACM, Volume 23, Issue 9

Pages 522 - 528

https://doi.org/10.1145/359007.359013

Published: 01 September 1980 Publication History

Abstract

In this paper we describe a practical method of partial-match retrieval in very large data files. A binary code word, called a descriptor, is associated with each record of the file. These record descriptors are then used to form a derived descriptor for a block of several records, which will serve as an index for the block as a whole; hence, the name “indexed descriptor files.”

First the structure of these files is described and a simple, efficient retrieval algorithm is presented. Then its expected behavior, in terms of storage accesses, is analyzed in detail. Two different file creation procedures are sketched, and a number of ways in which the file organization can be “tuned” to a particular application are suggested.

References

[1]

Aho, A.V., and Ullman, J.D. Optimal partial-match retrieval when fields are independently specified. Trans. Database Systs. 4, 2 (June 1979), 168-179.

Digital Library

[2]

Berman, W.J., and Pfahz, J.L. Multi-dimensional bucket arrays. DAMACS Tech. Rep. TR-16-78, Univ. of Virginia, March 1978.

[3]

Cagley, E.M. A retrieval strategy for large, multi-key files requiring frequent updating. TR-75, Executive Office of the President (Office of Emergency Preparedness), Dec. 1971.

[4]

Cagley, E.M., et al. Information Management System Reference Manual. GSA/FPA/MCL TM-208, Oct. 1976.

[5]

Cardenas, A.F. Analysis and performance of inverted data base structures, Comm. ACM. 18, 5 (May 1975), 253-263.

Digital Library

[6]

DATAPRO Res. Corp. A Buyer's Guide to Data Base Management Systems, 1974.

[7]

Files, J.R., and Huskey, H.D. An information retrieval system based on superimposed coding. Proc. AF1PS Fall Joint Comptr. Conf., Vol. 35, AFIPS Press, Arlington, Va., 1969.

[8]

Knuth, D.E. The Art of Computer Programming, Vol. 3. Addison- Wesley, Reading, Mass., 1973.

Digital Library

[9]

Lefkovitz, D. The large data base file structure dilemma. Rep. 76-5, Univ. of Penn. Moore School, 1976.

[10]

Rivest, R.L. Partial-match retrieval algorithms. SlAM J. Comptng. 5, 1 (March 1976), 19-50.

[11]

Roberts, C.S. Partial-match retrieval via the method of superimposed codes. Proc. IEEE, Vol. 67, No. 12 (Dec. 1979), pp. 1624-1642.

[12]

Schroeder, J., et al. Stanford's Generalized Data Base System. Internat. Conf. on Very Large Data Bases, Framingham, Mass., Sept. 1975.

[13]

Severance, D.G., and Carlis, J.V. A practical approach to selecting record access paths. Comptng. Surveys 9, 4 (Dec. 1977), 259- 272.

Digital Library

[14]

Vallarino, O. On the use of bit maps for multiple key retrieval. ACM S1GPLAN Notices 11 (March 1976), 108-114.

Digital Library

[15]

Wiederhold, G. Database Design. McGraw-Hill, N.Y., 1977.

Digital Library

Cited By

Akulich MSavnik IKrnc MŠkrekovski R(2023)Multiset-Trie Data StructureAlgorithms10.3390/a1603017016:3(170)Online publication date: 20-Mar-2023
https://doi.org/10.3390/a16030170
Savnik IAkulich MKrnc MŠkrekovski R(2021)Data structure set-trie for storing and querying sets: Theoretical and empirical analysisPLOS ONE10.1371/journal.pone.024512216:2(e0245122)Online publication date: 10-Feb-2021
https://doi.org/10.1371/journal.pone.0245122
Zhang CZhu LZhang SYu W(2020)TDHPPIR: An Efficient Deep Hashing Based Privacy-Preserving Image Retrieval MethodNeurocomputing10.1016/j.neucom.2019.11.119Online publication date: Apr-2020
https://doi.org/10.1016/j.neucom.2019.11.119
Show More Cited By

Partial-match retrieval using indexed descriptor files
1. Information systems
  1. Information retrieval

Recommendations

Information retrieval in files described using sets
SIGMOD '75: Proceedings of the 1975 ACM SIGMOD international conference on Management of data

A number of file structures (e.g., inverted files and multilist files) can be modelled as a collection of records whose contents are described using sets. With each of these sets is associated a definition which is stated as a Boolean expression of ...
Optimization of large sequential data files
ACM '77: Proceedings of the 1977 annual conference

The need for inexpensive data storage continues to grow and tape reels are usually used. For large data aggregations with even a few retrieval applications, it may not be as economical to store full reels as to split the data into smaller sized files. ...
Frame-Sliced Signature Files

A superimposed coding method, frame-sliced signature file, is proposed, and the performance of this method is studied and compared with that of other signature file methods. The response time of the method is improved due to its ability to effectively ...

Comments

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 23, Issue 9

Sept. 1980

38 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359007

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Copyright © 1980 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1980

Published in CACM Volume 23, Issue 9

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

103
Total Citations
View Citations
447
Total Downloads

Downloads (Last 12 months)84
Downloads (Last 6 weeks)14

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Akulich MSavnik IKrnc MŠkrekovski R(2023)Multiset-Trie Data StructureAlgorithms10.3390/a1603017016:3(170)Online publication date: 20-Mar-2023
https://doi.org/10.3390/a16030170
Savnik IAkulich MKrnc MŠkrekovski R(2021)Data structure set-trie for storing and querying sets: Theoretical and empirical analysisPLOS ONE10.1371/journal.pone.024512216:2(e0245122)Online publication date: 10-Feb-2021
https://doi.org/10.1371/journal.pone.0245122
Zhang CZhu LZhang SYu W(2020)TDHPPIR: An Efficient Deep Hashing Based Privacy-Preserving Image Retrieval MethodNeurocomputing10.1016/j.neucom.2019.11.119Online publication date: Apr-2020
https://doi.org/10.1016/j.neucom.2019.11.119
Wang HWu JHu WWu X(2019)Detecting and Assessing Anomalous Evolutionary Behaviors of Nodes in Evolving Social NetworksACM Transactions on Knowledge Discovery from Data10.1145/329988613:1(1-24)Online publication date: 23-Jan-2019
https://dl.acm.org/doi/10.1145/3299886
Pearce D(2017)Rewriting for sound and complete union, intersection and negation typesACM SIGPLAN Notices10.1145/3170492.313604252:12(117-130)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3170492.3136042
Sinclair MAlsop JAdve S(2017)Chasing Away RAtsACM SIGARCH Computer Architecture News10.1145/3140659.308020645:2(161-174)Online publication date: 24-Jun-2017
https://dl.acm.org/doi/10.1145/3140659.3080206
Chattopadhyay SBanerjee ABanerjee N(2017)A Fast and Scalable Mechanism for Web Service CompositionACM Transactions on the Web10.1145/309888411:4(1-36)Online publication date: 25-Aug-2017
https://dl.acm.org/doi/10.1145/3098884
Xu CZhang J(2017)Collusive Opinion Fraud Detection in Online ReviewsACM Transactions on the Web10.1145/309885911:4(1-28)Online publication date: 24-Jul-2017
https://dl.acm.org/doi/10.1145/3098859
Hogan A(2017)Canonical Forms for Isomorphic and Equivalent RDF GraphsACM Transactions on the Web10.1145/306833311:4(1-62)Online publication date: 25-Jul-2017
https://dl.acm.org/doi/10.1145/3068333
Chirigati FLiu JKorn FWu YYu CZhang H(2016)Knowledge exploration using tables on the webProceedings of the VLDB Endowment10.14778/3021924.302193510:3(193-204)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.14778/3021924.3021935
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