Time-space trade-off analysis of morphic trie images

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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 languageEnglish
Pages (from-to)1028-1032
Number of pages5
JournalIEEE Transactions on Knowledge and Data Engineering
Volume13
Issue number6
DOIs
Publication statusPublished - 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

Cite this