Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An experimental study of compression methods for dynamic tries
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2002 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 33, no 1, 19-33 p.Article in journal (Refereed) Published
Abstract [en]

We study an order-preserving general purpose data structure for binary data, the LPC-trie. The structure is a compressed trie, using both level and path compression. The memory usage is similar to that of a balanced binary search tree, but the expected average depth is smaller. The LPC-trie is well suited to modem language environments with efficient memory allocation and garbage collection. We present an implementation in the Java programming language and show that the structure compares favorably with a balanced binary search tree.

Place, publisher, year, edition, pages
2002. Vol. 33, no 1, 19-33 p.
Keyword [en]
data structures, trie, LPC-trie, level compression, relaxed level compression, memory management, binary search tree, Java, efficient implementation, search-trees
Identifiers
URN: urn:nbn:se:kth:diva-21367DOI: 10.1007/s00453-001-0102-yISI: 000174307400003OAI: oai:DiVA.org:kth-21367DiVA: diva2:340065
Note
QC 20100525Available from: 2010-08-10 Created: 2010-08-10 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Nilsson, Stefan
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Algorithmica

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 84 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf