lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "David Smiley (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (LUCENE-7069) Add LatLonPoint.nearest to find closest indexed point to a given query point
Date Thu, 14 Apr 2016 14:43:25 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-7069?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15241291#comment-15241291
] 

David Smiley commented on LUCENE-7069:
--------------------------------------

If the Bits (doc set) filter is sparsely populated, then I agree -- you're better off just
doing a typical sort.  If I recall (it's been years now), my implementation did that.  But
if it's heavily populated, then I picked a fairly large grid cell (possibly including some
adjacent cells if the query point was close to an edge)  and did a distance sort with that
rectangle a filter.  If I not only met the topN budget but the furthest distance in that topN
was close enough such that, if I inscribed a circle from the query point to that last point,
that the circle would be completely within the cells making the filter, then I'm done.  If
unlucky, I had to iterate up to larger cells/filters or give up and fall back to a standard
distance sort.  I recall this made a world of difference to an app that previously always
distance sorted.  To be clear, to the extent that this used the grid cells, it was only as
an approximate filter.  the points were always in DocValues and the distance was computed
from that.

> Add LatLonPoint.nearest to find closest indexed point to a given query point
> ----------------------------------------------------------------------------
>
>                 Key: LUCENE-7069
>                 URL: https://issues.apache.org/jira/browse/LUCENE-7069
>             Project: Lucene - Core
>          Issue Type: Improvement
>            Reporter: Michael McCandless
>            Assignee: Michael McCandless
>             Fix For: master, 6.1
>
>         Attachments: LUCENE-7069.patch, LUCENE-7069.patch, LUCENE-7069.patch, LUCENE-7069.patch
>
>
> KD trees (used by Lucene's new dimensional points) excel at finding "nearest neighbors"
to a given query point ... I think we should add this to Lucene's sandbox as:
> {noformat}
>   public static Document nearest(IndexReader r, String field, double lat, double lon)
throws IOException
> {noformat}
> I only implemented the 1 nearest neighbor for starters ... I think we can easily generalize
this in the future to K nearest.
> It could also be generalized to more than 2 dimensions, but for now I'm making the class
package private in sandbox for just the geo2d (lat/lon) use case.
> I don't think this should go into 6.0.0, but should go into 6.1: it's a new feature,
and we need to wrap up and ship 6.0.0 already ;)



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message