Associative retrieval trie hash-coding

摘要

In this paper, data base designs for retrieval from a file of k-letter records when queries may be only partially specified are examined. A family of data base designs referred to as the Hαβκ PMF-trie designs which yield a data structure with good worst case and average case performances and require an amount of storage space essentially equal to that required of the records themselves is introduced. The analysis of the designs including bounds on the worst case performance and an explicit expression for the average performance is presented. Previously known families of PMF-trie designs are seen to be special cases within the Hαβκ family.