A nonexhaustive algorithm, linear with respect to memory, for solving a two-dimensional interval search problem

We suggest an algorithm to solve a two-dimensional interval search problem which is characterised by the memory consumed of order $k$, the average search time (without the time needed to output the answer) of order $\sqrt k$, where $k$ is the database size.
This research was supported by the Russian Foundation for Basic Research, grant 01–01–00748.