[
https://issues.apache.org/jira/browse/LUCENE-7159?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15223861#comment-15223861
]
Michael McCandless commented on LUCENE-7159:
--------------------------------------------
+1, cool!
> improve spatial point/rect vs. polygon performance
> --------------------------------------------------
>
> Key: LUCENE-7159
> URL: https://issues.apache.org/jira/browse/LUCENE-7159
> Project: Lucene - Core
> Issue Type: Bug
> Reporter: Robert Muir
> Attachments: LUCENE-7159.patch
>
>
> Now that we can query on complex polygons without going OOM (LUCENE-7153), we
> should do something to address the current 🐢 performance.
> Currently, we use a basic crossings test ({{O\(n)}}) for boundary cases. We
> defer these expensive per-doc checks on boundary cases to a two phase
> iterator (LUCENE-7019, LUCENE-7109), so that it can be avoided if e.g.
> excluded by filters, conjunctions, deleted doc, and so on. This is currently
> important for performance, but basically its shoving the problem under the
> rug and hoping it goes away. At least for point in poly, there are a number
> of faster techniques described here:
> http://erich.realtimerendering.com/ptinpoly/
> Additionally I am not sure how costly our "tree traversal" (rectangle
> intersection algorithms). Maybe its nothing to be worried about, but likely
> it too gets bad if the thing gets complex enough. These don't need to be
> perfect but need to behave like java's Shape#contains (can conservatively
> return false), and Shape#intersects (can conservatively return true). Of
> course, if they are too inaccurate, then things can get slower.
> In cases of precomputed structures we should also consider memory usage: e.g.
> we shouldn't make a horrible tradeoff there.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
