Re: Binary Tree vs. Hash

"Xiangrong Fang" <[e-mail]> wrote in message
news:[e-mail]...
> Hi Mikkel,
>
> Thanks for the detailed explanations. I have some qusestions regarding
> your explain:
>
> 1. You mentioned B-Tree and binary tree, seems that they are different?

In principle they are identical, but differ vastly in implementation.

A binary tree has two children, the left has smaller values, the right has
larger values.
A B-Tree has an array of children such that all values in the leftmost
subtree
is smaller than all values in the next subtree, etc.
In effect a B-Tree is a compressed binary tree.
In both cases you have logarithmic search. But if you assume the time is
consumed
by visiting new nodes and not by visiting values within a single B-Tree
node,
you get a much faster operation. This assumption is true if you read data
from
disk. There is a limit of B-Tree node sizes beyond which it takes
too long time to visit each key within each node. For disk based
B-Trees you usually have about 1000 keys (M=1000).
You can also use B-Trees in-memory, but then the node size must
reflect the size of the CPU cache. When data is in cache, a very
fast scan over the array of keys is more effecient than visiting
new nodes.
B-Trees are very complicated because a node can have between M / 2 and M
keys in a node. If you go above or below you must reorginize the tree,
This is efficient, but the implementation has lots of special cases.

A B-Tree guarantees that you must at most visit K nodes.
K is a small limited value. If K is 3 and you have 1000 keys per
node (M=1000), you have K^M = 1G possible keys.
That is about all you can address in a 32bit systems.
For in-memory operation (M=10), K is significantly larger,
but if you consider the realistic size of your dataset, it is still
small. The trick you can do to make in memory performance better
is to organize you tree so allocation of nodes happen close to
related nodes. This gives you benefits in lower level cache and
virtual memory. Effectively you a split a larger (M=1000) into
several smaller (M=10) nodes. This gives you both good in-memory
and on-disk performance. In praxis it is not that easy to manage,
but you can do something to make it work reasonably well.

Binary trees on the other hand do not have a small limit on the
number of nodes that you must visit. Therefore they truly have
logarithmic behavior. It's not too bad, it is just not the most
efficient way to deal with large datasets.

A binary tree requires you to visit a new node for each comparison.
Binary trees must be balanced otherwise all data could end up in one
subtree (becoming just a linked list).
There are several ways to balance binary trees (e.g. red-black trees and
splay trees).
In any case it solves the problem.


> 2. I didn't used any of my own hash algorithm, I just used Ruby's hash,
> and used Ruby's PStore to dump it to disk. The memory usage is an
> estimation from monitoring the task list in win2k. Do you have any
> comments about the efficiency of using Ruby's hash and pstore?

My best guess is that PStore would not save more than necessary, so you
should
expect in-memory to take up more space as I already suggested,
but I don't know what it does.
Your way of measuring is very crude, but probably fair because this is how
the
system is actually stressed no matter the theory.

> 3. My application is related to using N-GRAM method to cut Chinese text
> into words (a Chinese bigram is 4-byte string). Do you have any comments
> on which algorithm is better?

I'd like to here more about this, in private mail if you prefer.

It it appears that you are counting "word" or symbol frequencies and can do
this
by indexing a pair of symbols as a single 32bit word.
This is ideal for the hashtable I have implemented as it does not need to
visit any
external keys. However, it is not available in Ruby. I can send you the
C-Source.
I already suggested that this source be made available to Ruby but I don't
know how
well it fits with Ruby as is. It would be specialized for 32 bit words, not
general hashes.

I have been working a lot with B-Trees and I think I would choose B-Trees
over
hash tables because they scale better. B-Trees have a good trade-off. They
are easy to have
small and easy to have very very large and if they are not the fastest
solution, they are
always seem to be among the best performers.

With B-Trees you can have your data on disk and do efficient lookups without
needing
to load everything into memory.
It is possible to have on-disk hash tables, but in the end you need to do
some clever
memory mananagement that is going to make it look an awful lot like B-Trees.

Also, because the key is 32bit the B-Tree is efficient because it does not
need to
visit external keys. As soon as you visit external keys the cache benefit of
B-Trees
goes away. However, I do not recommend that you start implementing B-Trees.
They are
difficult to implement and difficult to make sure that they work.

You may be able to use the datastructures in the Berkeley DB database. I
don't know how
efficient it would be in you case (it's fast but it is a database after
all).
Berkeley DB does handle hashes and B-Trees. It can operate in in-memory mode
only
and I think there is a Ruby interface.
Note that Berkeley is free only for non-commerical usage.

> I am very interested in your comments
> about SkipList, can you expand more?

I don't recall exactly why skip-lists are better than binary trees, but they
are
in any case easy to implement (except efficient node allocation).

I can send you an implementation in C if you like.

This is only a rough outline according to memory:

A skiplist is a sorted linked list of all values.
Since it is slow to find a value this way, some nodes both point to the next
node
as well as to one or more nodes further down the list.
In fact a skiplist node has an array of next pointers.
All nodes have on next pointer, half the nodes have at least two next
pointers.
Only one nodes has log(N) next pointers (the head of the list).
Two nodes has log(N-1) next pointers, etc.
The search happens by looking at the longest jumping link first. If that was
too far,
you try the next shorter jumping node.
Eventually you find a node that has a key that matches or is shorter.
You now repeat the process jumping from that node. This goes on until you
have a match
(or conclude failure).
This is a bit simplified as there are a few more cases to consider, but this
is generally
the idea.
In reality the skiplist does not have a perfect distribution of nodes. The
number of nodes
with a certain number of next links may not be optimal, and the location of
these nodes may
also not be optimal. The distribution happens statistically, but works
pretty well in praxis.
A skiplist node thus has an array of pointers. This is not unlike B-Tree
nodes, except the
concept is radically different. There is no complex balancing or splitting
of nodes and
the performance is decent. However, you are jumping back and forth between a
lot of nodes,
so it is not friendly to your CPU cache. Since nodes have vastly different
sizes it is
difficult to make a fast node allocation scheme (if you choose malloc / new,
you have lost the
speed competition).


> Thanks a lot!

You are welcome.

Mikkel