Algorithms for Trie Compaction.

M. Al-Suwaiyel, Ellis Horowitz: Algorithms for Trie Compaction. ACM Trans. Database Syst. 9(2): 243-263(1984)

@article{DBLP:journals/tods/Al-SuwaiyelH84,
  author    = {M. Al-Suwaiyel and
               Ellis Horowitz},
  title     = {Algorithms for Trie Compaction},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {2},
  year      = {1984},
  pages     = {243-263},
  ee        = {http://doi.acm.org/10.1145/329.295, db/journals/tods/Al-SuwaiyelH84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

The trie data structure has many properties which make it especially attractive for representing large files of data. These properties include fast retrieval time, quick unsuccessful search determination, and finding the longest match to a given identifier. The main drawback is the space requirement. In this paper the concept of trie compaction is formalized. An exact algorithm for optimal trie compaction and three algorithms for approximate trie compaction are given, and an analysis of the three algorithms is done. The analyses indicate that for actual tries, reductions of around 70 percent in the space required by the uncompacted trie can be expected. The quality of the compaction is shown to be insensitive to the number of nodes, while a more relevant parameter is the alphabet size of the key.

Copyright © 1984 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

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...

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

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

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

BibTeX

References

[1]: ...
[2]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[3]: ...
[4]: Douglas Comer, Ravi Sethi: The Complexity of Trie Index Construction. J. ACM 24(3): 428-440(1977) BibTeX
[5]: ...
[6]: Douglas Comer: The Difficulty of Optimum Index Selection. ACM Trans. Database Syst. 3(4): 440-445(1978) BibTeX
[7]: Douglas Comer: Heuristics for Trie Index Minimization. ACM Trans. Database Syst. 4(3): 383-395(1979) BibTeX
[8]: ...
[9]: ...
[10]: ...
[11]: Ellis Horowitz, Sartaj Sahni: Fundamentals of Computer Algorithms. Computer Science Press 1978
BibTeX
[12]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[13]: Theodore Rotwitt Jr., Paul A. D. de Maine: Storage Optimization of Tree Structured Files. SIGFIDET Workshop 1971: 207-217 BibTeX
[14]: ...

Referenced by

Jun-Ichi Aoe, Katsushi Morimoto, Masami Shishibori, Ki-Hong Park: A Trie Compaction Algorithm for a Large Set of Keys. IEEE Trans. Knowl. Data Eng. 8(3): 476-491(1996)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]