# lucene-java-user mailing list archives

##### Site index · List index
Message view
Top
From Dennis Watson <den...@guba.com>
Subject Re: Sorting on distance from a long/lat
Date Tue, 21 Nov 2006 15:42:29 GMT
```Hi,

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:

X1.X2.X3...Xn

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

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

X1.X2.*
X1.X2.X3.*

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

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
>
> http://www.visitpa.com/visitpa/visitNearbyActivities.pa?type=dining&name=Co
>lor+Me+MineThanks,Phillip
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org

---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org