Partial-match retrieval using indexed descriptor files

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: Alfred V. Aho , Jeffrey D. Ullman, Optimal partial-match retrieval when fields are independently specified, ACM Transactions on Database Systems (TODS), v.4 n.2, p.168-179, June 1979 [doi>10.1145/320071.320074]
• 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: Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
• 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: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 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: D. G. Severance , J. V. Carlis, A Practical Approach to Selecting Record Access Paths, ACM Computing Surveys (CSUR), v.9 n.4, p.259-272, Dec. 1977 [doi>10.1145/356707.356709]
• 14: Vallarino, O. On the use of bit maps for multiple key retrieval. ACM S1GPLAN Notices 11 (March 1976), 108-114.
• 15: Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1977

INDEX TERMS

Keywords:
bit codes, multiattribute, partial-match, retrieval, storage access cost