Portal de Periódicos da CAPES

Optimal partial-match retrieval when fields are independently specified

1979; Association for Computing Machinery; Volume: 4; Issue: 2 Linguagem: Inglês

10.1145/320071.320074

1557-4644

Alfred V. Aho, Jeffrey D. Ullman,

Machine Learning and Algorithms

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.