Geosearching a large database of places, for places which are near your current location, is a surprisingly wicked theoretical problem, especially for mobile app developers. Understanding the problem, and how the solution works, has important applications which go well beyond geosearch.
The difficulty is the search is two dimensional. To find a set of places which are near your current location, you have to match both latitude and longitude. But there is no relationship between latitude and longitude. You cannot infer a longitude, if you have the latitude, they are separate entities. Latitude and longitude are independent search criteria.
Why independent search criteria are a challenge
Say you want to find all places which are within a kilometre of your current location. Given your current location, you can easily convert a latitude into a range of values which is roughly a kilometre wide. Similarly you can convert a longitude into a range of values which is roughly a kilometre wide. But this is where the trouble starts.
Once you have your strip of land, you can search for places within that strip which are also within the range of longitudes you want. But consider what that strip of land you just requested actually represents; if you ask the database for all results within a range of latitude values, what you are actually asking for is all of the locations within a strip of land which encircles the entire world.
If your database contains millions of places, and you ask your database to return all the places within a world encompassing strip of land, your intermediate search result may contain many thousands of candidate places. If you started with latitude, filtering this long list of latitude candidates, for places which are also within the desired longitude range, can place impractical demands on your database’s computation capability – particularly if you are using a mobile device to perform the search.
Performing a traditional search, where you start with the first search criterion (the latitude), then refine the search using the second criterion (the longitude), is clearly very inefficient. What we need is a method of filtering the list, which allows us to efficiently apply both latitude and longitude to our search simultaneously.
R-Tree – A search which applies multiple criteria simultaneously
The secret of R-Tree is that it divides the problem domain into a series of concentric boxes. Each box contains smaller boxes, until at the end of the search, the last “branch” of the “tree”, the final box contains the results you want.
Even though the top level outer boxes contain thousands of results, the mobile app does not have to look at all of these results – all the mobile app sees is a manageable series of boxes. Searching the boxes is like opening a set of Russian dolls, one inside the other. The final results of your search, the results which the mobile app needs to display, are inside the innermost box.
Most importantly, defining the search algorithm as opening a series of concentric boxes, each box closer to the results you want, means you are applying both indices, latitude and longitude, simultaneously – which allows much more efficient filtering of results, than would be the case with searching latitude and longitude independently (world encompassing strips of land).
R-Tree your next mobile app development project!
The best part of R-Tree search is that it is fully supported by sqlite, which in turn is fully supported by the iPhone App Development and Android App Development environments.
You do not have to build the concentric index boxes yourself, the Sqlite R-Tree package will take care of the technical details of building and maintaining an efficient R-Tree index to your places data. All you have to do is specify which fields should be part of the R-tree search index (in this case, the fields you want are latitude and longitude).
If you wish to develop an Android App or iPhone App, which requires blinding fast geosearch, or if you have an esoteric data search problem which just doesn’t seem to be responding to normal database performance tuning, consider R-Tree – it might be the solution you need.
And of course, R-Tree is also well supported by server technology – so you can, if you choose, perform blinding fast geosearches using a server call, rather than embedding the data in your mobile app.
If you would like to know more about R-tree, and multiple independent database index search techniques and tricks, contact me for more information.
