Ideas on how to search nearby geospatial data fast

Question

I am looking at a very simple problem, but can't quite find the best solution. I need to accept a lat/lon coordinate and based on that coordinate find all the points within roughly ~1km (accuracy is not too important to me). It will always be ~1km searches as well (fixed). I now face how to store these coordinates in my database and how to retrieve the results very quickly. I am open to using any database or language to complete this.

Currently I am using MongoDB and there 2D spatial index (http://docs.mongodb.org/manual/applications/geospatial-indexes/) to store my locations as lat/long on a flat surface. I am then creating a bounding box (accuracy is not super important to me, so I accept with a box the distance is not the same in all directions) and using a bounding box search (http://docs.mongodb.org/manual/reference/operator/query/box/) for to get all the points. This approach brings decent performance, but I am looking for faster.

I know databases really love integer based indexes. They perform the quickest. I was looking for a way to maybe convert coordinates into integers or something along those lines?

I know some databases such as MySQL 5.7 have spatial index which utilize r-trees which is great for vast geospatial operations, but I have what I believe is a simple use case which can avoid these indexes and utilize faster structures such as native integers, etc.

Some thoughts on algorithms which could be utilized: z-order, hilbert, x-tree, geohash, kd-tree, etc.

To summarize my ultimate goal:

I want to use accept a lat/lon coordinate and transform this coordinate which can then be best stored in the database for very fast nearby searches on the database. I am open to any methods.

Cheers

Answer 1

I don't know much about using databases but it seems that a k-d tree would be a good way to do it. Look at the following link

http://web.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf

Answer 2

If your data is indexed, I'm not sure if a 3rd party algorithm would perform much faster than the ones already included in mongoDB. According to your link,

Changed in version 2.2.3: Applications can use $box without having a geospatial index. However, geospatial indexes support much faster queries than the unindexed equivalents. Before 2.2.3, a geospatial index must exist on a field holding coordinates before using any of the geospatial query operators.

However, if I were to do this from scratch, I would convert my geodetic data into Cartesian coordinates (using e.g. Haversine), then sort them into a balanced kd-tree. Kd-trees index k-dimensional points and sort them relative to a root node (usually the mean or median of the data set) using a divide-and-conquer methodology, making them especially adept for nearest-neighbor and range search algorithms. A range search will find points in $O(log\,n)$ time, which should be sufficiently fast. Of course, you would have to convert your target query into Cartesian coordinates before conducting a search. I suspect, however, that mongoDB implements search algorithms with the same level of performance, assuming your data is indexed.

It's important to first convert to Cartesian coordinates because most kd-tree searches rely on the $L_2$-norm as the metric for determining distance between points, which is incorrect for geospatial coordinates. Furthermore, using lat/long for the kd-tree's splitting plane may also result in difficulties, since longitudes are not equidistant from each other (i.e. distance between longitudes is a function of latitude, which might make it a poor choice for splitting the kd-tree).

Kd-trees are really only efficient for bulk-loading situations, where you know your dataset in advance and can sort them all in one go. It's possible to add new points to a kd-tree, but it's not ideal. If you expect your data set to change often, I would suggest an R-tree.