Complexity of trie index construction

Douglas Comer; Ravi Sethi

doi:10.1109/SFCS.1976.4567904

Complexity of trie index construction

Douglas Comer, Ravi Sethi

Computer Science

Research output: Contribution to journal › Conference article › peer-review

9 Scopus citations

Abstract

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 language	English (US)
Article number	4567904
Pages (from-to)	197-207
Number of pages	11
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume	1976-October
DOIs	https://doi.org/10.1109/SFCS.1976.4567904
State	Published - 1976
Event	17th Annual Symposium on Foundations of Computer Science, SFCS 1976 - Houston, United States Duration: Oct 25 1976 → Oct 27 1976

ASJC Scopus subject areas

General Computer Science

Access to Document

10.1109/SFCS.1976.4567904

Cite this

@article{4853bc06f136492d9d95a2933d5500c7,

title = "Complexity of trie index construction",

abstract = "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.",

author = "Douglas Comer and Ravi Sethi",

note = "Publisher Copyright: {\textcopyright} 1976 Institute of Electrical and Electronics Engineers, Inc.; 17th Annual Symposium on Foundations of Computer Science, SFCS 1976 ; Conference date: 25-10-1976 Through 27-10-1976",

year = "1976",

doi = "10.1109/SFCS.1976.4567904",

language = "English (US)",

volume = "1976-October",

pages = "197--207",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

}

TY - JOUR

T1 - Complexity of trie index construction

AU - Comer, Douglas

AU - Sethi, Ravi

PY - 1976

Y1 - 1976

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85027389722&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027389722&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1976.4567904

DO - 10.1109/SFCS.1976.4567904

M3 - Conference article

AN - SCOPUS:85027389722

SN - 0272-5428

VL - 1976-October

SP - 197

EP - 207

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

M1 - 4567904

T2 - 17th Annual Symposium on Foundations of Computer Science, SFCS 1976

Y2 - 25 October 1976 through 27 October 1976

ER -

Complexity of trie index construction

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this