Access Restriction

Author Maly, Kurt
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
Language English
Subject Keyword Retrieval time ♦ Keys ♦ Database ♦ Data structure ♦ M-ary tree ♦ Storage requirement ♦ Trie
Abstract This paper presents a new data structure, called a compressed trie or C-trie, to be used in information retrieval systems. It has the same underlying m-ary tree structure as a trie, where m is a parameter of the trie, but whereas the fields of the nodes in a trie have to be large enough to hold a key or at least a pointer, the fields in a C-trie are only one bit long. In the analysis part of the paper it will be shown that for a collection of n keys the retrieval time, measured in terms of bit inspections of one key, is of the order logmn and the storage requirement of the order n·(m + log2n) bits. This improvement in storage requirements and retrieval time is achieved at the cost of decreasing the flexibility of the structure, and therefore updating costs are increased. First the C-trie is analyzed as a data structure, and then several methods of its use for relatively static databases are discussed.
Description Affiliation: Univ. of Minnesota, Minneapolis (Maly, Kurt)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 19
Issue Number 7
Page Count 7
Starting Page 409
Ending Page 415

Open content in new tab

   Open content in new tab
Source: ACM Digital Library