Custom Indexing for Latitude-Longitude Data

In the June 2012 issue of MSDN Magazine, I wrote an article that describes how to create custom indexes for SQL data which represents geo-spatial information, that is, latitude and longitude data. The essential problem that custom geo-spatial indexes solve is quickly finding neighbors to a given data point. For example, suppose you have a huge database of mobile device user information and one user is located at latitude 47.00 and longitude -122.00 (this is in Redmond, WA). You want to find all users that are within 1 degree latitude and longitude of the user. A simple statement like (note: avoiding >= and <= symbols)

SELECT userID FROM tblData
WHERE lat greater-or-equal 46.50 AND lat less-or-equal 47.50
AND lon greater-or-equal -122.50 AND lon less-or-equal -121.50

could take a very long time to execute. So the idea of custom indexing is to assign a geographical sector ID to every user. For example, suppose that the 1 degree by 1 degree rectangle above had sector ID 1234. Then the select statement to find all nearby users would be

SELECT userID FROM tblData
WHERE sectorID = 1234

Assuming sectorID is indexed, this would be very fast. Of course the devil is in the details. You can read the article online at http://msdn.microsoft.com/en-us/magazine/jj133823.aspx.

This entry was posted in Software Test Automation. Bookmark the permalink.