[ https://issues.apache.org/jira/browse/LUCENE-7159?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Hoss Man updated LUCENE-7159: ----------------------------- Fix Version/s: (was: 6.0) master (7.0) Manually correcting fixVersion per Step #S5 of LUCENE-7271 > 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 > Fix For: 6.1, master (7.0) > > Attachments: LUCENE-7159.patch, 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: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org