# Ideas on how to search nearby geospatial data fast

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

• 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. – dpmcmlxxvi Jun 29 '15 at 15:58

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).