CODEWITHSUNDEEP
algorithm
OutputLogic
OutputLogic

Reputation: 409

Interval search algorithm with O(1) lookup speed

I need to design an interval search algorithm that works on 64-bit keys. The match is when key k is between k1 and k2. An important requirement is that the lookup speed is better than O(log n). Researching available literature didn't turn up anything better than interval search trees. I wonder if it's feasible at all.

Upvotes: 4

Views: 1865

Answers (2)

btilly
btilly

Reputation: 46507

You can dispatch by leading bytes until the problem is small. That avoids most of the overhead of an interval tree, while maintaining the flexibility of one.

So you have a table of 256 structs that point to 256 structs on down as far as needed until you either encounter a flag saying, "no match", or you are pointed to a small interval tree for the exact matching condition. Processing the top of this tree with straightforward jumps rather than traversing multiple comparisons, possible pipeline stalls, etc, may be a significant performance improvement for you.

Upvotes: 1

olegarch
olegarch

Reputation: 3891

If your keys have distribution, closed to uniform, you can use Interpolation search, which has O(log log N) time - this is much better, than O(log n).

UPD: Just an idea: If you have enough extra memory, you can build trie-like structure. There will be O(1) search time. Idea following: For example, lets we set tree of arrays[256], where each array indexed by some byte of key. Arrays linked to trie. So, root element of trie - is array[265], where index is high byte of the key. But anyway this is not practical, because of in the bottom node, for search borders, need to perform linear search with ~64 iterations.

Upvotes: 1

Related Questions