# 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 23:36:17 GMT
```It is similar to the two Range Filter approach except my way is precomputed
and probably faster than filtering through a potentially large result set.
Also I can quickly compute a rough max distance between two any lat, lon
pairs by compairing thier X1.X2.X3... path.

Dennis Watson
Sr SW Engineer
GUBA.com

On Tuesday 21 November 2006 11:05, Chris Hostetter wrote:
> I'm not really sure what an approach like this gaines you ... it provides
> a mechanism for ensuring that the lat/lon of all results are within a
> bounding box arround your start location -- but those bounding boxes
> are fixed when building your index.
>
> couldn't you achieve the same thing using a "lat" field, a "lon" field
> and two RangeFilters? ... except now you get variable sized/centered
> bounding boxes?
>
> : Date: Tue, 21 Nov 2006 07:42:29 -0800
> : From: Dennis Watson <dennis@guba.com>
> : To: java-user@lucene.apache.org
> : Cc: spamsucks <spamsucks@rhoderunner.com>
> : Subject: Re: Sorting on distance from a long/lat
> :
> : 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&nam
> : >e=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
> : For additional commands, e-mail: java-user-help@lucene.apache.org
>
> -Hoss
>
>
> ---------------------------------------------------------------------
> 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