Name
Abstract | ||
|---|---|---|
Trle structures are a convenient way of indexing files in which a key consists of a number of attributes Records correspond to leaves in the trle 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 trle for a file depends on the order in which attributes are tested It is shown that determining minimal size tries IS an NP-complete problem for several variants of tries and that, for tries m which leaf chains are deleted, determining the trie for which average access time is minimal is also an NP-complete problem These results hold even for files in which attribute values are chosen from a binary or ternary alphabet KE) WORDS AND PHRASES reformation retrieval, trle indexes, trte size, average search time, complexity |
Year | DOI | Venue |
|---|---|---|
1977 | 10.1145/322017.322023 | J. ACM |
Keywords | Field | DocType |
Trie Index Construction | Discrete mathematics,Computer science,Theoretical computer science,Trie | Journal |
Volume | Issue | ISSN |
24 | 3 | 0004-5411 |
Citations | PageRank | References |
38 | 18.51 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Douglas Comer | 1 | 38 | 18.85 |
| Ravi Sethi | 2 | 2281 | 1029.21 |