Exponential Search Trees

Question

How is exponential search done?

According to http://en.wikipedia.org/wiki/Exponential_tree, "An exponential tree is almost identical to a binary search tree, with the exception that the dimension of the tree is not the same at all levels. In a normal binary search tree, each node has a dimension (d) of 1, and has 2d children. In an exponential tree, the dimension equals the depth of the node, with the root node having a d = 1. So the second level can hold two nodes, the third can hold eight nodes, the fourth 64 nodes, and so on."

But how would I actually represent this on a list, array, etc? Ordinary BBSTs are a way of kinda saying (or at least similar to): grab a sorted array and start searching from its middle (the root of BBST), and descend down by comparing the query key with a current child. It's either greater or smaller.

The mystery is - what's sort of comparison is behind an exponential search tree when searching for a query key? What can be stored in such a tree? Some mind exploding thought - how the heck is it balanced? If anyone has a simple literature source, that would be great!

Many thanks people!

Answer 1

"But how would I actually represent this on a list, array, etc" - it is not clear. Are you asking about ways to represent the exponential search tree?

Exponential search trees can bee used to store d-dimensional numeric data at nodes of depth d.

Comparisons are made on each of these dimensions (each child of a node can have d+1 values that are <, >, ..., < (any combinations of d operators), than that node's values, and a new value).

I do not know any paper introducing the basics of exponential trees, but they are used in problems such as the one describes in this paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.6676&rep=rep1&type=pdf.