I need an efficient data structure which holds mapping of pairs to values
(x,y) => v
and allows to find key-value pairs matching 2d range expression:
x1 < x < x2 && y1 < y < y2
faster then full search. I have some solution, though it is heavy to implement. Is there any standard algorithm/approach for such task? I believe DB developers had to solve this problem while addressing compound indexes problem.
If you want a very simple solution, try this:
keep the keys sorted on x;
given a query range, find the first point in the x range by dichotomy;
loop on x until the end of the x-range and test on y.
Assuming that your keys are uniformly spread, if the x-range occupies a fraction Fx of the whole domain, the speedup compared to exhaustive search is 1/Fx (not 1/Fx.Fy, unfortunately).
Even though the gain may look insignificant, it is worth to implement it to compare it against exhaustive search and any more sophisticated method that you could try.
Another easy solution is by gridding, i.e. storing the points in linked lists associated to every grid cell. Then the search can be limited to the cells that overlap the range.
You will need to find a good compromise on the cell size; cells much larger than the typical size of the ranges are inefficient; but cells so small that most of them are empty are also inefficient.
The quad-tree data structure can be seen as an adaptive version of gridding.