There are a number of specialized data structures that implement ordered dictionaries for integer keys: van Emde Boas trees, y-Fast tries, fusion trees, etc. Each of these data structures implement the key ordered dictionary primitives in sublogarithmic time.

However, to the best of my knowledge, all three of the above data structures are interesting only in a theoretical context, since their hidden constant factors are so large that they're effectively impractical. (I may be wrong about that, though!)

Are there any integer data structures that support sublogarithmic query times in theory which are also efficient in practice?

  • $\begingroup$ vEB trees have very low constant factors. $\endgroup$ – jbapple May 16 '16 at 4:20
  • $\begingroup$ @jbapple Do you have a source on that? The last time I read up on this they weren't practical, in part due to poor cache locality from their high memory usage. $\endgroup$ – templatetypedef May 16 '16 at 6:08
  • $\begingroup$ No, I simply counted it up. As for cache locality, a binary search tree has at least $log_2 n + \Omega(1)$ cache misses, on average, per search, ans uses at least $2n$ words of space. vEB trees can use arrays (if the keys are dense in the universe) or hash tables and use no more than $O(n)$ words of space, with a small constant. In fact, when using arrays, the space usage can be brought down to $O(n)$ bits of space! $\endgroup$ – jbapple May 16 '16 at 13:24
  • $\begingroup$ @jbapple I'm not sure that constant factors are things you can "count up." They often have to be determined empirically. As for locality - there are fewer nodes visited in a vEB tree, as you noted, but those nodes are so huge that they're likely to cache poorly, while a BST often will keep its nodes in cache because they take up such little space, particularly if you have a few nodes you access a lot. As for space usage - are you sure about that? vEB trees use space proportional to the universe size, not the number of elements stored (unless I'm mistaken?) $\endgroup$ – templatetypedef May 16 '16 at 16:12
  • $\begingroup$ OK, in order: 1. You can "count up" constant factors by counting operations. That is what "hidden factors" (as in your original question) usually refers to. Google "Galactic Algorithm" or Flajolet-style Analysis of Algorithms. Donald Knuth and Kurt Mehlhorn do this sometimes. 2. Hardware caching doesn't know about the size of your nodes. It caches 64-bytes (or a page address, in the TLB) of nearby data. The top very few levels in a binary tree are in cache at once, so that doesn't save you much. 3. Yes, I am sure about that. Most modern vEB explanations explain how to use HTs to save space. $\endgroup$ – jbapple May 16 '16 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.