|
Posted by Chris on April 18, 2007, 4:48 pm
Please log in for more thread options user923005 wrote:
>> user923005 wrote:
>>>> I need to search a database table of locations to find all with X miles
>>>> of a certain point. Each location has a latitude and longitude.
>>>> Unfortunately, this particular database does not have the ability to
>>>> create spatial indexes.
>>>> Is there a quick and dirty way for me to create my own spatial index and
>>>> store it in the database?
>>>> It doesn't have to be most efficient method. It just has to reduce the
>>>> search space enough to speed things up. I don't think that creating a
>>>> simple index on lat+long is going to cut it, though.
>>> PostgreSQL has spatial indexes, if you choose the PostGIS option.
>>> What database are you using?
>>> Alternatively, you could create an index on lat+lon, and then do your
>>> own cookie cutter on coordinates that would fit into a box around the
>>> data (a circle {or ellipse for eccentricty} is correct, but you will
>>> need a larger region since the index will not be aware).
>>> Something like this:
>>> given: someLat, someLon
>>> given: radius somRad
>>> calculate the box of dimention 2* someRad that has someLat, someLon at
>>> its center. Use great circles north, south, east, and west from
>>> (someLat, someLon) to generate the coordinates. Then search inside of
>>> this box with your query. You will need to individually filter the
>>> resultant data set, but it should only be a small fraction of the data
>>> you would have had to examine otherwise. Having a key on the lat+lon
>>> will help some. It might also be a good idea to have a key on lat and
>>> a key on lon for some difficult queries so that you can always do some
>>> restrictions of the data set.
>> Thanks. Unfortunately, the database I'm using is specialized and
>> proprietary, and spatial indexes are not available. It's not possible to
>> switch to another database.
>>
>> My sense is that the lat+long index won't work well when the dataset is
>> large. It reduces the search space, but not enough. For example, let's
>> say you're searching for all data points +- 10 miles of a given point.
>> The lat+long index will make you examine all points within a 20 mile
>> band across the whole area.
>>
>> I read somewhere that you can create a combined lat/long value that
>> interleaves the digits of each, and that this can reduce the search
>> space. I can't find any references to it, though. Have you heard of such
>> a thing?
>
> The right kind of index is a K-D tree, a trie, a quadtree and things
> of that nature. A B-Tree index is not going to cut the mustard. Even
> an R-Tree index is marginal.
> PostgreSQLs indexes are open source. Perhaps the GIS stuff can be
> adapted to your proprietary database, if you are able to modify the
> source (but that will clearly be a BIG project). If not, your queries
> will crawl like a slug through molasses.
> Perhaps you can add a ton of RAM to the machine so it will mostly be
> cached in RAM. With 64 bit chips and operating systems you can do
> some remarkable things if you throw enough money at it.
>
Just for reference, I've found these papers:
http://citeseer.ist.psu.edu/234227.html
http://www.dcs.bbk.ac.uk/TriStarp/pubs/bncod17.pdf
They both purport to provide a way to do two-dimensional indexing in
one-dimensional space. Slogging through them now...
| 
XML Sitemap