Heuristics for Trie Index Minimization.

@article{DBLP:journals/tods/Comer79,
  author    = {Douglas Comer},
  title     = {Heuristics for Trie Index Minimization},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {3},
  year      = {1979},
  pages     = {383-395},
  ee        = {http://doi.acm.org/10.1145/320083.320102, db/journals/tods/Comer79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A trie is a digital search tree in which leaves correspond to records in a file. Searching proceeds from the root to a leaf, where the edge taken at each node depends on the value of an attribute in the query. Trie implementations have the advantage of being fast, but the disadvantage of achieving that speed at great expense in storage space. Of primary concern in making a trie practical, therefore, is the problem of minimizing storage requirements. One method for reducing the space required is to reorder attribute testing. Unfortunately, the problem of finding an ordering which guarantees a minimum-size trie is NP-complete. In this paper we investigate several heuristics for reordering attributes, and derive bounds on the sizes of the worst tries produced by them in terms of the underlying file. Although the analysis is presented for a binary file, extensions to files of higher degree are shown.

Another alternative for reducing the space required by a trie is an implementation, called an O-trie, in which the order of attribute testing is contained in the trie itself. We show that for most applications, O-tries are smaller than other implementations of tries, even when heuristics for improving storage requirements are employed.

Copyright © 1979 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[2]

Walter A. Burkhard: Hashing and Trie Algorithms for Partial Match Retrieval. ACM Trans. Database Syst. 1(2): 175-187(1976) BibTeX

[3]

Richard G. Casey: Design of Tree Structures for Efficient Querying. Commun. ACM 16(9): 549-556(1973) BibTeX

[4]

Douglas Comer, Ravi Sethi: The Complexity of Trie Index Construction. J. ACM 24(3): 428-440(1977) BibTeX

[5]

...

[6]

Theodore Rotwitt Jr., Paul A. D. de Maine: Storage Optimization of Tree Structured Files. SIGFIDET Workshop 1971: 207-217 BibTeX

[7]

...

[8]

Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX

[9]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[10]

Donald R. Morrison: PATRICIA - Practical Algorithm To Retrieve Information Coded in Alphanumeric. J. ACM 15(4): 514-534(1968) BibTeX

[11]

...

[12]

Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976) BibTeX

[13]

Larry E. Stanfel: Tree Structures for Optimal Searching. J. ACM 17(3): 508-517(1970) BibTeX

[14]

Edward H. Sussenguth Jr.: Use of Tree Structures for Processing Files. Commun. ACM 6(5): 272-279(1963) BibTeX

[15]

...

Referenced by

1. R. Ramesh, A. J. G. Babu, J. Peter Kincaid: Variable-Depth Trie Index Optimization: Theory and Experimental Results. ACM Trans. Database Syst. 14(1): 41-74(1989)
2. M. Al-Suwaiyel, Ellis Horowitz: Algorithms for Trie Compaction. ACM Trans. Database Syst. 9(2): 243-263(1984)
3. Douglas Comer: Analysis of a Heuristic for Trie Minimization. ACM Trans. Database Syst. 6(3): 513-537(1981)