Quick and dirty spatial index

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.

user923005 wrote:

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.

user923005 wrote:

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