Back to Search
Start Over
Fast and compact updating algorithms of a double-array structure
- Source :
-
Information Sciences . Jan2004, Vol. 159 Issue 1/2, p53. 15p. - Publication Year :
- 2004
-
Abstract
- In many information retrieval applications, it is necessary to be able to adopt a trie search for looking at the input character by character. As a fast and compact data structure for a trie, a double-array is presented. However, the insertion time is not faster than other dynamic retrieval methods because the double-array is a semi-static retrieval method that cannot treat high frequent updating. Further, the space efficiency of the double-array degrades with the number of deletions because it keeps empty elements produced by deletion. This paper presents a fast insertion algorithm by linking empty elements to find inserting positions quickly and a compression algorithm by reallocating empty elements for each deletion. From the simulation results for 100 thousands keys, it turned out that the insertion time and the space efficiency are achieved. [Copyright &y& Elsevier]
- Subjects :
- *DATABASE searching
*ALGORITHMS
*ELECTRONIC data processing
*COMPUTER science
Subjects
Details
- Language :
- English
- ISSN :
- 00200255
- Volume :
- 159
- Issue :
- 1/2
- Database :
- Academic Search Index
- Journal :
- Information Sciences
- Publication Type :
- Periodical
- Accession number :
- 11825861
- Full Text :
- https://doi.org/10.1016/S0020-0255(03)00189-0