Building data structures that are smaller than an array and faster (in C)

Re:Building data structures that are smaller than an array a... by ot on Thursday March 01, 2012 @03:17AM (#3651379)

> I'm primarily using as a compact order preserving structure to support fast lookups for both (token -> position) and (position -> token). I'm using an updatable variant to support O(1) appends, and then use it for realtime indexing/compression. I probably should do a blog post at one point...

That's very interesting, are you using raw or compressed bitmaps (such as RLE or RRR)? A limitation of (updatable) wavelet trees is that you need to know in advance the set of symbols that you will see (otherwise you would need to change the tree structure). Is it a problem for you? I wrote a paper with a solution to this problem, I can't share it until mid march, let me know if you are interested.

[ Parent | on HN ]

Re:Building data structures that are smaller than an array a... by gorset on Thursday March 01, 2012 @06:43AM (#3651738)

My solution is to use a fixed tree with bloated leaf nodes (use more bits per element in the leaf node). A high number of nodes with a low number of elements causes a high overhead, so I simply rebuild the tree at a few given thresholds to keep the overhad and the cost of the bloated leaf nodes down. We can discuss further by email, if you want. I'd love to read your paper! :-)

[ Parent | on HN ]

Re:Building data structures that are smaller than an array a... by alexbowe on Thursday March 01, 2012 @01:13PM (#3653258)

I'm interested in the paper too of course :D

[ Parent | on HN ]