1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Here is a good discussion on Mongo vs. PostGIS. After reading your requirements it seems Mongo would be better option unless you expect to need more sophisticated spatial querying latter on. $\endgroup$ – dpmcmlxxvi Jun 29 '15 at 15:58
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ While a link might contain an answer to the posted Question, you provide Readers with a better choice if the content to be found there is explained in greater detail than "a k-d tree would be a good way to do it". Guidelines call for the important information to be found at a crucial link to be explained or quoted with attribution. $\endgroup$ – hardmath Jun 26 '15 at 1:34
1
+100
$\begingroup$

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.

$\endgroup$

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.