Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Crit-bit Trees: the best way to store sets

cr.yp.to

Post reply on HN
Print view View original

31–40 of 42 posts

Re: Crit-bit Trees: the best way to store sets

#31

Post by willvarfar »

pja wrote: post #26
willvarfar wrote: post #23

The article puts forward a tree as a better alternative to hashtables: "I have become convinced that this strategy should change. The revised strategy is much simpler: there should be one fundamental set-storage type, namely a crit-bit tree. Here's how a crit-bit tree stacks up against the competition: * A hash table supports insertion, deletion, and exact searches. A crit-bit tree supports insertion, deletion, exact…

He's not arguing that crit-bit trees are better than hash tables, he's arguing that they are a better choice for the fundamental set datatype for languages like python, perl etc etc. When you write an application, you know the performance requirements of the set representation you choose & can pick the most appropriate for your application. A language designer doesn't have this information: their choice of fundamenta…

You weaken his rhetoric; he writes like its crit-bit all the way for all purposes.

And since there is not a queue of people complaining that Python's dict is not iterable in order, I'd say he's wrong. Random access in a dict is the most common use-case by a very long chalk.

Re: Crit-bit Trees: the best way to store sets

#32

Post by fmap »

ot wrote: post #21

Crit-bit trees are great but they're not silver-bullet: like every tree structure, even in the lucky case a search can cause O(log n) cache misses, while a good hash table needs just one or two. Also, as pointed out in another comment, it is not necessarily balanced (like red-black trees) and there are some real-world datasets where crit-bit (or Patricia) trees behave poorly, for example URLs. I myself have seen Patr…

That's a very good point. One way to circumvent this problem is to combine hashing and crit-bit trees, by constructing an unordered tree on the hash values of the set elements. The nice thing here is that if the hash function behaves like a uniform random variable the resulting tree will be balanced. Furthermore, without ordering the implementation is trivial.

At the same time you will not need rehashing once the table "fills up" and since you use don't discard bits from the hash function the expected number of collisions after inserting n elements with a 32 bit hash is n / 2^32 - or 0 for reasonable values of n.

Additionally you can use clustering (e.g. build a crit-nibble tree, with 16 pointers per node - one 64 byte cache line) to reduce the number of cache misses. This can backfire spectacularly unless the data is essentially random, so the hashing step remains important.

It may not be a silver bullet, but there are some interesting trade-offs.

Re: Crit-bit Trees: the best way to store sets

#35

Post by bumbledraven »

dchest wrote: post #3

agl's C translation written in literate programming style: PDF: https://github.com/agl/critbit/blob/master/critbit.pdf Repo: https://github.com/agl/critbit

According to the paper, this code was actually extracted directly from qhasm, which djb released in 2006. This is notable because any code becomes more worthy of admiration once we know it was written by djb. As Mark-Jason Dominus used to say, "I'd drink poisoned cool-aid as long as djb told me he'd made it himself."

Re: Crit-bit Trees: the best way to store sets

#36

Post by ot »

fmap wrote: post #32
ot wrote: post #21

Crit-bit trees are great but they're not silver-bullet: like every tree structure, even in the lucky case a search can cause O(log n) cache misses, while a good hash table needs just one or two. Also, as pointed out in another comment, it is not necessarily balanced (like red-black trees) and there are some real-world datasets where crit-bit (or Patricia) trees behave poorly, for example URLs. I myself have seen Patr…

That's a very good point. One way to circumvent this problem is to combine hashing and crit-bit trees, by constructing an unordered tree on the hash values of the set elements. The nice thing here is that if the hash function behaves like a uniform random variable the resulting tree will be balanced. Furthermore, without ordering the implementation is trivial. At the same time you will not need rehashing once the tab…

That is true but you lose some of the most important properties of crit-bit trees, ordered operations.

If the data structure is unordered, I don't see any reason why it should be better than a normal hash table.

Re: Crit-bit Trees: the best way to store sets

#37

Post by fmap »

ot wrote: post #36
fmap wrote: post #32

Earlier quoted context omitted.

That's a very good point. One way to circumvent this problem is to combine hashing and crit-bit trees, by constructing an unordered tree on the hash values of the set elements. The nice thing here is that if the hash function behaves like a uniform random variable the resulting tree will be balanced. Furthermore, without ordering the implementation is trivial. At the same time you will not need rehashing once the tab…

That is true but you lose some of the most important properties of crit-bit trees, ordered operations. If the data structure is unordered, I don't see any reason why it should be better than a normal hash table.

The data structure is not better than a normal hash table. It is a different trade-off.

For instance, you don't have to do a rehashing step, which is important for real time applications. Memory usage is also very deterministic at 2*(n-1) words in an n element table (with 2 words per node).

If none of this matters to you and you merely want a map with fast lookups then a simple hash table is probably a better choice.

Re: Crit-bit Trees: the best way to store sets

#38

Post by jakab922 »

gorset wrote: post #30
jongraehl wrote: post #24

Earlier quoted context omitted.

The minimal-acceptor approach is also best when you're considering dynamic programs that effectively involve some kind of FSA-intersection, including best-first lazy versions like "find the closest spelling correction to a sequence of words in your lexicon of some text", because your state (suffix set) representation is canonical. I only skimmed the paper, but a simple n*log n approach to produce the same result is t…

Implementing approximate matching has been on my todo list for some time. I'm planning to either implement http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5362... or http://www.sciencedirect.com/science/article/pii/S1570866704... The data structure for the mealy recognizer described in the paper can very easily be changed to support minimal perfect hash numbers for all elements, without using more space (my i…

You might find this interesting as a testbed -> http://www.facebook.com/careers/puzzles.php?puzzle_id=17

Re: Crit-bit Trees: the best way to store sets

#39

Post by dchest »

bumbledraven wrote: post #35
dchest wrote: post #3

agl's C translation written in literate programming style: PDF: https://github.com/agl/critbit/blob/master/critbit.pdf Repo: https://github.com/agl/critbit

According to the paper, this code was actually extracted directly from qhasm, which djb released in 2006. This is notable because any code becomes more worthy of admiration once we know it was written by djb. As Mark-Jason Dominus used to say, "I'd drink poisoned cool-aid as long as djb told me he'd made it himself."

Thanks for clarification, you're right. I thought it was translated from qhasm to C.

Re: Crit-bit Trees: the best way to store sets

#40

Post by beagle3 »

jbapple wrote: post #16

> Another advantage is that a crit-bit tree guarantees good performance: it doesn't have any tricky slowdowns for unusual (or malicious) data. Consider a crit-bit tree over variable-length bit strings. The set 1, 11, 111, ... (with n bit strings) has depth n. Depending on how you count, it can be argued that this is still substantially better than the worst-case of hash tables, but in all of the ways I think of count…

Big O notation, it isn't. The big question is the cost of different types of comparisons.

The most important thing to remember is that a crit-bit lookup does O(string-length) "critical" bit lookups, and then an O(string-length) final comparison - for a total of O(string-length).

Whereas a hash lookup usually does O(string-length) computation of the hash value, average case O(1) lookups, and then O(string-length) comparison of the key value - for a total of O(string-length).

A balanced tree does O(log-n) comparisons, of O(string-length) each (the final one giving the confirmation, which was an independent step for both hash and critbit trees).

This is true even on this specific input. It boils down to how the amortized single-character comparison compares to a cache miss.

If crit-bit trees leafs are packed in a cache-friendly way (they are constant size, so this might actually be easy to arrange), they are likely to perform at least as well as balanced trees.

Post reply on HN