<p>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.</p>

CC BY-SA 2.5
2010-11-25T20:46:34.550Z
But this example does not show that you must store *redundant* information (i.e., that you need to duplicate the entries of the root node at each child as well)!
Jukka Suomela
CC BY-SA 2.5
2010-12-16T19:12:35.317Z
I'm confused. In a tree of depth $1$ with $n$ nodes it is clear that you can't store $m$ bindings in $o(m)$ space. Is your example showing something more?
Radu GRIGore
CC BY-SA 2.5
2010-11-25T20:35:32.750Z
2010-11-25T20:35:32.750Z
Jelani Nelson
<p>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.</p>

<p>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 <a href="http://people.csail.mit.edu/mip/papers/pred/pred.pdf">http://people.csail.mit.edu/mip/papers/pred/pred.pdf</a> for the optimal predecessor bounds.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-29T18:22:18.907Z
2010-11-29T18:22:18.907Z
Mihai
<p>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.</p>

<p>For example, there might be a root node:</p>

<pre><code>root = {'car':1, 'boat':2}
</code></pre>

<p>and 2 children, each adding an element to the parent map</p>

<pre><code>child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}
</code></pre>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 2.5
2010-11-25T19:47:50.157Z
so each node represents a map that refines the map stored in the parent ?
Suresh Venkat
CC BY-SA 2.5
2010-11-25T19:48:08.673Z
also, do you mean map in the mathematical or cartographical sense ?
Suresh Venkat
CC BY-SA 2.5
2010-11-25T19:51:21.240Z
I mean a map in the mathematical/CS sense. Like map in the STL for example.
phreeza
CC BY-SA 2.5
2010-11-25T19:53:10.297Z
@Suresh: It seems that it is not a refinement. If I got the question right, a child node *adds* new elements to the map of its parent node.
Jukka Suomela
CC BY-SA 2.5
2010-11-25T19:53:46.057Z
and to answer the first question, each node refines the map in the sense that more key/value pairs are added.
phreeza
CC BY-SA 2.5
2010-11-25T23:24:20.267Z
I wonder if what you need is a skip list or some kind of fractional cascading structure
Suresh Venkat
CC BY-SA 2.5
2010-12-16T17:30:36.420Z
This sounds like definition lookup for identifiers in a programming language with nested scopes. (I mention this application because it might make it easier for some readers to understand the question.)
Radu GRIGore
<ds.data-structures><tree><hash-function>
What is the optimal data structure for a tree of maps.
phreeza
# What is the optimal data structure for a tree of maps.

(Asked by: username_0 on 2010-11-25)

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.

**Tags:** ds.data-structures, tree, hash-function
> **Comments:**
> **username_1**: so each node represents a map that refines the map stored in the parent ?  
> **username_1**: also, do you mean map in the mathematical or cartographical sense ?  
> **username_0**: I mean a map in the mathematical/CS sense. Like map in the STL for example.  
> **username_2**: @Suresh: It seems that it is not a refinement. If I got the question right, a child node *adds* new elements to the map of its parent node.  
> **username_0**: and to answer the first question, each node refines the map in the sense that more key/value pairs are added.  
> **username_1**: I wonder if what you need is a skip list or some kind of fractional cascading structure  
> **username_3**: This sounds like definition lookup for identifiers in a programming language with nested scopes. (I mention this application because it might make it easier for some readers to understand the question.)  

---

## 2 answers

### Answer by username_4 on 2010-11-25. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_2**: But this example does not show that you must store *redundant* information (i.e., that you need to duplicate the entries of the root node at each child as well)!  
> **username_3**: I'm confused. In a tree of depth $1$ with $n$ nodes it is clear that you can't store $m$ bindings in $o(m)$ space. Is your example showing something more?  

---

### Answer by username_5 on 2010-11-29. Score: 15

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.


---

