ACM SIGMOD Anthology TODS dblp.uni-trier.de

Variable-Depth Trie Index Optimization: Theory and Experimental Results.

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)
@article{DBLP:journals/tods/RameshBK89,
  author    = {R. Ramesh and
               A. J. G. Babu and
               J. Peter Kincaid},
  title     = {Variable-Depth Trie Index Optimization: Theory and Experimental
               Results},
  journal   = {ACM Trans. Database Syst.},
  volume    = {14},
  number    = {1},
  year      = {1989},
  pages     = {41-74},
  ee        = {http://doi.acm.org/10.1145/62032.77249, db/journals/tods/RameshBK89.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We develop an efficient approach to Trie index optimization. A Trie is a data structure used to index a file having a set of attributes as record identifiers. In the proposed methodology, a file is horizontally partitioned into subsets of records using a Trie index whose depth of indexing is allowed to vary. The retrieval of a record from the file proceeds by "stepping through" the index to identify a subset of records in the file in which a binary search is performed. This paper develops a taxonomy of optimization problems underlying variable-depth Trie index construction. All these problems are solvable in polynomial time, and their characteristics are studied. Exact algorithms and heuristics for their solution are presented. The algorithms are employed in CRES - an expert system for editing written narrative material, developed for the Department of the Navy. CRES uses several large-to-very-large dictionary files for which Trie indexes are constructed using these algorithms. Computational experience with CRES shows that search and retrieval using variable-depth Trie indexes can be as much as six times faster than pure binary search. The space requirements of the Tries are reasonable. The results show that the variable-depth Tries constructed according to the proposed algorithms are viable and efficient for indexing large-to-very-large files by attributes in practical applications.

Copyright © 1989 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 ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

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]
...
[3]
Walter A. Burkhard: Hashing and Trie Algorithms for Partial Match Retrieval. ACM Trans. Database Syst. 1(2): 175-187(1976) BibTeX
[4]
Richard G. Casey: Design of Tree Structures for Efficient Querying. Commun. ACM 16(9): 549-556(1973) BibTeX
[5]
Douglas Comer: Heuristics for Trie Index Minimization. ACM Trans. Database Syst. 4(3): 383-395(1979) BibTeX
[6]
Douglas Comer, Ravi Sethi: The Complexity of Trie Index Construction. J. ACM 24(3): 428-440(1977) BibTeX
[7]
...
[8]
...
[9]
...
[10]
...
[11]
...
[12]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[13]
...
[14]
...
[15]
...
[16]
...
[17]
...
[18]
...
[19]
...
[20]
...
[21]
Dennis G. Severance: Identifier Search Mechanisms: A Survey and Generalized Model. ACM Comput. Surv. 6(3): 175-194(1974) BibTeX
[22]
Edward H. Sussenguth Jr.: Use of Tree Structures for Processing Files. Commun. ACM 6(5): 272-279(1963) BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:05 2008