|
|
|
@article{DBLP:journals/tods/Comer81,
author = {Douglas Comer},
title = {Analysis of a Heuristic for Trie Minimization},
journal = {ACM Trans. Database Syst.},
volume = {6},
number = {3},
year = {1981},
pages = {513-537},
ee = {http://doi.acm.org/10.1145/319587.319618, db/journals/tods/Comer81.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
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 the 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.
Copyright © 1981 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.