Analysis of a heuristic for full trie minimization

ABSTRACT

A trie is a distributed-key search tree in which records from a file correspond to leaves in the tree. Retrieval consists of following a path from one root to a leaf, where the choice of edge at each node is determined by attribute values of the key. For full tries, those in which all leaves lie at the same depth, the problem of finding an ordering of attributes which yields a minimum size trie is NP-complete. This paper considers a “greedy” heuristic for constructing low-cost tries. It presents simulation experiments which show that the greedy method tends to produce tries with small size, and analysis leading to a worst case bound on approximations produced by the heuristic. It also shows a class of files for which the greedy method may perform badly, producing tries of high cost.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Douglas Earl Comer, Trie structured index minimization., 1976
• 3: Douglas Comer, Heuristics for trie index minimization, ACM Transactions on Database Systems (TODS), v.4 n.3, p.383-395, Sept. 1979 [doi>10.1145/320083.320102]
• 4: Douglas Comer , Ravi Sethi, The Complexity of Trie Index Construction, Journal of the ACM (JACM), v.24 n.3, p.428-440, July 1977 [doi>10.1145/322017.322023]
• 5: DEMAINE, P.A.D., AND ROTWITT, T. Storage optimization of tree structured files representing descriptor sets. In Proc. A CM SIGFIDET Workshop on Data Description, Access, and Control, Nov. I97I, pp. 207-217.
• 6: Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
• 7: YAO, S.B. A model for combined attribute index organizations. In Proc. 5th Texas Conf. Computing Systems, Austin, Tex., Oct. 1976, pp. 127-130.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
heuristic, trie index, trie size