7. The system of claim 4 , wherein the shape of the trie is determined by a sequence of split and merge operations, wherein: in a split operation a leaf node gets two new children nodes, each covering a different half of a region of the leaf, and wherein the occupied bits of the newly created children nodes are initialized to be the same as the occupied bit of their parent node before the parent node was split, and wherein in a merge operation two leaf nodes that have the same parent are removed and as a result their parent becomes a leaf and its occupied bit is set to the logical OR of the existence bits of its two children before they were removed.
9. The system of claim 7 , wherein the trie automatically adapts to changes in query distribution and data distribution by merging nodes that are infrequently queried and by subdividing nodes that are frequently queried.