Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/15221
Title: Time-space trade-off analysis of morphic trie images
Authors: Luk, RWP 
Keywords: Key retrieval algorithm
Key search techniques
Minimal prefix trie
Trie hashing
Trie structures
Issue Date: 2001
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on knowledge and data engineering, 2001, v. 13, no. 6, p. 1028-1032 How to cite?
Journal: IEEE transactions on knowledge and data engineering 
Abstract: In this paper, we explore the use of tries to represent tries. A morphic trie image is a trie that represents a set of transformed keywords using an isomorphism h: Σ* → (σ q)*. Morphic trie images using tenary alphabets achieve near optimal performances but approximation errors degrade their performances. A condition which determines whether tenary or bit tries should be used is found. Even though bit tries have better storage reduction in some cases, tenary tries access faster than bit tries. We show that the morphic trie images use less space than minimal prefix tries. If morphic trie images were compressed to form minimal prefix tries, then the total storage reduction is the product of the two. Approximation errors have no effect on minimal prefix tries.
URI: http://hdl.handle.net/10397/15221
ISSN: 1041-4347
EISSN: 1558-2191
DOI: 10.1109/69.971194
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

36
Last Week
1
Last month
Checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.