I have a problem where I need to be able to efficiently find all of the intervals that contain a particular (integer) value. There are data-structures to do this efficiently, for example the interval tree. However, I have quite a lot of intervals, and I don't want to have to code up a complicated disk-based data structure, so I am constrained to use a database.
The solution I came up with is to assign each interval a particular numerical code, such that a query of a small set of such codes will guarantee finding each interval that contains a given value.
I'm not sure if this is novel. It seems a fairly obvious thing to do, so probably not. If not, can anyone tell me what it is called?
The code is this: I produce a trinary number from the binary representation of the lower and upper bounds of the interval. Starting with the most significant digit I map 0->1 and 1->2 until the first digit that varies between the lower and upper bounds. From there on I just produce 0s.
An example may make this clear:
Lower 00010101010 Upper 00010101111 Output 00021212000
To perform a query, I similarly convert the binary query number to trinary. The query set is then this trinary number with each least significant digit converted to zero in turn.
Query 00010101100 Output 00021212211 00021212210 00021212200 00021212000 00021210000 00021200000 00021000000 00020000000 00000000000
Here's the source code:
The source code includes code to test this idea using SQLite.
Update: This is hideous. Sorry. I am working on a much nicer scheme, stay tuned.
 Clarification: By efficiently I mean faster than O(n).