lucene-java-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dennis Watson <>
Subject Re: Sorting on distance from a long/lat
Date Tue, 21 Nov 2006 15:42:29 GMT

I apologize if this is slightly off topic.  I have not implemented this, but 
the idea came to me after reading another post about measuring distance in 
lucene.  It may be completely impractical, however it seems it COULD work at 
least if the area to be indexed could be constrained.

What if you divided the earth up into lets say 100 square blocks.  Each block 
would have sides of length x1 with an area x1^2.  You could number those 
blocks 0 - 99.  Then you could divide each of those blocks into 100 blocks 
with sides of length x2 = x1 / 10 and number these 0 - 99 as well.  You could 
do this until you had blocks with sides of length xn and area xn^2.

Each one of these blocks would have four corners with a lat and lon.  It would 
be fairly easy to tell if one block were in another block.  It should be 
fairly easy to tell which set of boxes any lat, lon pair belonged to.

It seems then you could specify locations almost like IP addresses:


where X1 is the 0-99 number of the first largest set of blocks and X2 is the 
0-99 number of the next smaller set of blocks inside the first X1 box and so 

You could search in lucene for objects within a certain proximity with a 
prefix search:


Moreover you would know that the longer the path that matches, the closer 
those objects are (it is fractal in nature).  If you needed more granularity 
you could do a prefix search like this down to the smallest granularity you 
have and then perform a greatcircle distance calculation on the the results 
to see if they are close enough.

Of course there might be too many squares to cover the whole Earth.  You will 
want to pick a number of boxes which is a power of two so there are a 
"square" number of squares.  I think this enables the fractal nature 
described above. You would want the corners of the squares to land on 
predicable lat, lon points.  This may be done more easily with some 
measurement systems than another.

Just my $.02...

Dennis Watson
Sr SW Engineer

On Monday 20 November 2006 11:05, spamsucks wrote:
> I am successfully able to search for "nearbys" given a longitude and a
> latitude.  The basic summary of how I do this is that I add 1000 to the
> long/lat values and use a RangeFilter in my query.
> In my display results, I display the results ordered by distance from the
> original long/lat.  What I do is calulate the distance for every document
> in my result from the original long/lat and perform a sort of the distance.
> Doing the sort this way (calculating the distances for all results
> documents) feels like I am being inefficient and wasteful with my CPU
> cycles.  In most cases, I am only displaying the closest 10 documents, but
> I need to calculate the distance for all documents (potentially 1000) in
> order to come up with the 10 closest.
> Has anyone wrestled with these questions before?  Is there another
> approache that I can take?
> Here is my current working implementation, so you can see what I am
> describing.  The long/lat is stored in a database that I use to build up my
> lucene query/filters
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message