Complexity of trie index construction

Douglas Comer, Ravi Sethi

Research output: Contribution to journalConference articlepeer-review

9 Scopus citations


Trie structures are a convenient way of indexing files in which keys are specified by values of attributes. Records correspond to leaves in the trie. Retrieval proceeds by following a path from the root to a leaf, the choice of edges being determined by attribute values. The size of a trie for a file depends on the order in which attributes are tested. We show that determining minimal size tries is an NP-complete problem for several variants of tries. For tries in which leaf chains are deleted we show that determining the trie for which average access time is minimal is also an NP-complete problem. Our results hold even for files in which attribute values are chosen from a binary or ternary alphabet.

Original languageEnglish (US)
Article number4567904
Pages (from-to)197-207
Number of pages11
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - 1976
Event17th Annual Symposium on Foundations of Computer Science, SFCS 1976 - Houston, United States
Duration: Oct 25 1976Oct 27 1976

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Complexity of trie index construction'. Together they form a unique fingerprint.

Cite this