Fast Compressed Tries through Path Decompositions

Details Fast Compressed Tries through Path Decompositions Fast Compressed Tries through Path Decompositions

2011-11-22

arxiv.org/abs/1111.5220v2

Computer Science

Data Structures and Algorithms

Scientific paper

Tries are popular data structures for storing a set of strings, where common prefixes are represented by common root-to-node paths. Over fifty years of usage have produced many variants and implementations to overcome some of their limitations. We explore new succinct representations of path-decomposed tries and experimentally evaluate the corresponding reduction in space usage and memory latency, comparing with the state of the art. We study two cases of applications: (1) a compressed dictionary for (compressed) strings, and (2) a monotone minimal perfect hash for strings that preserves their lexicographic order. For (1), we obtain data structures that outperform other state-of-the-art compressed dictionaries in space efficiency, while obtaining predictable query times that are competitive with data structures preferred by the practitioners. In (2), our tries perform several times faster than other trie-based monotone perfect hash functions, while occupying nearly the same space.

Affiliated with

Also associated with

No associations

Rating

Fast Compressed Tries through Path Decompositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Compressed Tries through Path Decompositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Compressed Tries through Path Decompositions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-553626