1
$\begingroup$

Lets say you have a data model that consists of a 2D grid of integer points. This grid is sparsely populated and boundless in x and y (up to the max of a 32-bit integer).

What is the best way to index these points in order to have an optimised lookup on an arbitrary (x,y) coordinate? Is an O(1) lookup solution possible?

$\endgroup$
  • 4
    $\begingroup$ If points are never deleted, you can put the points in an array and have indices into the array stored in a hash table. $\endgroup$ – Yuval Filmus Mar 4 '14 at 3:13
  • 1
    $\begingroup$ Please define what you mean by lookup. Are you looking for nearest-neighbor search, i.e., given $(x,y)$, find the point that is nearest to $(x,y)$? (If so, that's a standard problem in computational geometry.) Are you hoping to check whether there is a point at exactly at $(x,y)$? (If so, that's a totally trivial problem.) Something else? What have you done to try to answer your own question? Where have you looked? $\endgroup$ – D.W. Mar 11 '14 at 23:36
1
$\begingroup$

For quick look-up on multidimensional points you need to create a R-tree index (http://en.wikipedia.org/wiki/R-tree) or any of its variants (http://en.wikipedia.org/wiki/Spatial_index#Spatial_index).

From wikipedia: R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.

The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle. Since all objects lie within this bounding rectangle, a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects.

$\endgroup$
  • 1
    $\begingroup$ It would be helpful if you gave some more detail, to make your answer more self-contained. $\endgroup$ – David Richerby Mar 8 '14 at 17:10
1
$\begingroup$

Another option is to use an encoding scheme for coordinates like geohash (http://en.wikipedia.org/wiki/Geohash).

From wikipedia: The main usages of Geohashes are as a unique identifier. represent point data e.g. in databases. Geohashes have also been proposed to be used for geotagging. When used in a database, the structure of geohashed data has two advantages. First, data indexed by geohash will have all points for a given rectangular area in contiguous slices (the number of slices depends on the precision required and the presence of geohash "fault lines"). This is especially useful in database systems where queries on a single index are much easier or faster than multiple-index queries. Second, this index structure can be used for a quick-and-dirty proximity search - the closest points are often among the closest geohashes.

This scheme can answer nearest point, based on the "geohash" representation of each point. In addition, it is easy to implement and you can find implementations for all programming languages, quite easily.

$\endgroup$
1
$\begingroup$

Hash map / Hash table (depending on the language used)

Per comments, Some reasoning why: According to Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, the big O of hash tables is O(1) to O(N) for insert, size, and time.

So best case is O(1) solution. If you are able to control the upper and lower bounds, then you have a 'max' number that you could add and can create a table with that in mind.

If you have a 2 by 2, then you can have a table with 4 rows, where the index is the grid coordinate and the value is then the place in memory. Again, language dependent ( this may be hard to do in JS, where C would be easy)

$\endgroup$
  • $\begingroup$ You could improve the answer by also arguing or explaining why. $\endgroup$ – Juho Mar 7 '14 at 0:54
  • $\begingroup$ This is not correct. Hash maps can only test equality and not nearest points. Since, the OP asks for an "optimised lookup on an arbitrary (x,y)", hash maps cannot work $\endgroup$ – Alexandros Mar 9 '14 at 9:46
  • 1
    $\begingroup$ @Alexandros, I don't see where OP asks to find the nearest point(s). $\endgroup$ – vonbrand Mar 10 '14 at 18:32
  • $\begingroup$ @Alexandros Maybe I misunderstood the OP's question or your statement. By definition of a hash table, it is "a structure that can map keys to values". What the OP is asking for is how to look up a grid coordinate(key) to a value in O(1) time(or I assume time). If the OP is looking for nearest points, then yes this is not a great answer. Also, Hash Functions check equality. See HashMap for HashMaps and there use. $\endgroup$ – Jdahern Mar 11 '14 at 19:36
  • $\begingroup$ Sorry, to clarify, Hash Functions can be used to check equality, but are not a guarantee of it $\endgroup$ – Jdahern Mar 11 '14 at 19:46
0
$\begingroup$

While there are many spatial hashing methods, I will give you a very simple one, which makes use of 64 bit architectures. Try to concatenate the bits to a 64 bit variable: $z=(x64<<32)|y64$, where $x64$ and $y64$ are 64 bit variables obtained by casting your 32 bit variables $x$ and $y$. Then insert them to a fast 64 bit hashtable (such as http://en.wikipedia.org/wiki/MurmurHash). Then in the runtime do the same operation to your queries and look them up from this hashtable. I hope it is clear.

$\endgroup$
  • $\begingroup$ MurmurHash is a hash function, not a hash table. $\endgroup$ – jbapple Mar 8 '14 at 22:33
  • $\begingroup$ A standard hash table would do, as soon as you use a powerful hash function. That's what I meant. $\endgroup$ – Tolga Birdal Mar 8 '14 at 23:47
  • $\begingroup$ As noted on Jdahern answer, hash maps are not suitable for this kind of work $\endgroup$ – Alexandros Mar 9 '14 at 9:48
  • 1
    $\begingroup$ I am not noticing any "closest point" argument there. If it is what you mean, it should be stated more clearly. The question to me seems more like querying an arbitrary x-y pair which is indexed beforehand. $\endgroup$ – Tolga Birdal Mar 9 '14 at 13:32
0
$\begingroup$

Use a pairing function: http://en.wikipedia.org/wiki/Pairing_function

You could extend Cantor's pairing function to the integers (it's defined on the naturals) by rotating through the quadrants.

$\endgroup$
  • $\begingroup$ And how should this be implemented? A function is an infinite mathematical object, not a data structure. $\endgroup$ – David Richerby Mar 10 '14 at 7:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.