[
https://issues.apache.org/jira/browse/LUCENE-7974?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Steve Rowe updated LUCENE-7974:
-------------------------------
Attachment: LUCENE-7974.patch
Patch implementing the idea. Reviews welcome.
Some implementation notes:
* Most of the implementation was directly stolen from {{NearestNeighbor}},
which should incidentally be renamed to indicate that it's specific to
{{LatLonPoint}}; this patch doesn't do that.
* The new test was also mostly directly stolen from {{TestNearest}}. I removed
testing of sorting multi-dimensional points by distance from a given point,
though, since AFAICT {{FloatPoint}} doesn't have this functionality (see
LUCENE-7099 for the LatLonPoint impl).
* Most comparisons are of distance squared rather than distance, to avoid
{{Math.sqrt()}} calls. There are a couple of (non-squared) distance-based
optimizations though to disqualify cells and individual point values that are
beyond the search radius in one dimension.
* I tried to switch the (bounded) hit queue from Java's {{PriorityQueue}} to
Lucene's implementation (as mentioned in a TODO in the {{LatLonPoint}} impl),
but it was much much slower (like an order of magnitude-ish). I didn't look
into why, but I reverted back to the Java impl.
> Add N-dimensional FloatPoint K-nearest-neighbor implementation
> --------------------------------------------------------------
>
> Key: LUCENE-7974
> URL: https://issues.apache.org/jira/browse/LUCENE-7974
> Project: Lucene - Core
> Issue Type: New Feature
> Components: modules/sandbox
> Reporter: Steve Rowe
> Assignee: Steve Rowe
> Priority: Minor
> Attachments: LUCENE-7974.patch
>
>
> From LUCENE-7069:
> {quote}
> 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
> [...]
> 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.
> {quote}
> This issue is to generalize {{LatLonPoint.nearest()}} to more than 2
> dimensions.
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
