What is the optimal data structure for a tree of maps.

Question

I'm looking for a data structure, that is basically a tree of maps, where the map at each node contains some new elements, as well as the elements in its parent node's map. By map here I mean a programming map with keys and values, like map in the STL or dict in python.

For example, there might be a root node:

root = {'car':1, 'boat':2}

and 2 children, each adding an element to the parent map

child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}

I would like this to be as space efficient as possible, ie i don't want to store a complete copy of the resulting map at each node, but ideally the lookup would still be O(log N), N being the total number of elements at the node, not the entire tree.

I was thinking perhaps there is a smart hash function I might use for this, but couldn't come up with anything.

The naive approach would be storing the newly added entries in a map at each node and then move up the tree if nothing is found. I don't like this because it depends on the tree depth.

Answer 1

You haven't said what queries are, but I'll assume query() takes in a node and a key and wants the associated value (or null if no such value exists). In this case, I think in general you can't do better than storing a separate map at every node. Consider for example a caterpillar tree where each path node has one node connected to it that's forked off (a total of 2n nodes). Root it at one end of the path. Now suppose the universe size for keys is m. For each forked off node v and each of the m possible keys, that key can either exist or not exist at v, and both would be in compliance with your subtree constraint. So, there are $2^{mn}$ possibilities for whether each key exists at each fork node, so you need mn bits of space just to store the required information.

Answer 2

First of all, I think what you mean by "map" is a "dictionary" in TCS lingo. Second, I don't understand the phrase "ideally the lookup would still be $O(\log N)$", since in a dictionary the lookup takes O(1) time with various hash tables. Thirdly, you haven't stated whether the problem is static or dynamic; I'm assuming static.

The optimal complexity to this problem is $\Theta($predecessor search), e.g. $O(\lg\lg N)$ using van Emde Boas. This is optimal if you word size is $\Theta(\lg n)$; see http://people.csail.mit.edu/mip/papers/pred/pred.pdf for the optimal predecessor bounds.

The proper way to attack the problem is to build one global hash table and deal with the hierarchy separately for each key in the table. For one key $x$, we know the nodes where it appears. Consider an in-order traversal of the tree. The nodes where $x$ appears define intervals in this order. To determine whether $x$ is in the hash table of some node $v$, you have to ask whether $v$ stabs any segment as defined above. This is easily done by predecessor search, where we build a predecessor table for all interval end points.

For a lower bound, note that even one stabbing question is as hard as predecessor (see the reductions from colored predecessor search). Since the paper references above shows optimal direct-sum behavior for predecessor search, it means the algorithm described above is optimal for any ration between the number of nodes and the total number of keys.