Re: clustering by latitude / longitude

[Dustin Burke]

Hey guys,
I agree that restricting your query to a latitude and longitude region is the best proposed solution thus far. However, it is a spatially partitioned indexing method and might not (or maybe it is!) right for your application. The problem with using a spatial partitioning indexing is that it does not reduce the complexity involved if the dataset has clustering (lots of datapoints densely packed within a given region - something probably very common for the service you're offering since one would expect the number of datapoints in a region to be directly proportional to the population in that area so cities would have a dense set of points whereas suburban areas would be much more sparse). In the extreme, if ALL your datapoints fell within a latitude/longitude region (of the smallest granularity region size you're using) then your query's performance is the same as if you didn't partition the space at all!

Also, how are you going to deal with searching for datapoints in neighboring regions that might fall within your range query?

To mitigate all of the above issues, my suggestion is to pursue the "spatial extensions" of mySql as was suggested by another member. mySql uses an R-Tree to index your dataset. It is a dataset partitioning index so it scales better with whatever dataset you give it (unless your dataset is uniformly distributed over the space then it's performance should be roughly that of the latitude/longitude method, no worse). Plus all the complex issues you raised above (especially with regard to performance) have been worked out and are highly optimized for storing on external memory.

I haven't used mySql for spatial queries so I couldn't help you out there (the mySql reference pages should though), but I have learned a bit of the algorithms and theory involved in spatial indexing methods. Sorry if this isn't of much practical value.



Edited 2 time(s). Last edit at 10/21/2005 10:22AM by Dustin Burke.