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.
| Original language | English |
|---|---|
| Pages (from-to) | 1028-1032 |
| Number of pages | 5 |
| Journal | IEEE Transactions on Knowledge and Data Engineering |
| Volume | 13 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - 1 Nov 2001 |
Keywords
- Key retrieval algorithm
- Key search techniques
- Minimal prefix trie
- Trie hashing
- Trie structures
ASJC Scopus subject areas
- Control and Systems Engineering
- Electrical and Electronic Engineering
- Artificial Intelligence
- Information Systems