[jira] [Updated] (LUCENE-7239) Speed up LatLonPoint's polygon queries when there are many vertices
[ https://issues.apache.org/jira/browse/LUCENE-7239?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Hoss Man updated LUCENE-7239: - Fix Version/s: (was: 6.0) master (7.0) Manually correcting fixVersion per Step #S5 of LUCENE-7271 FWIW: This issue has no commits linked in comments, so I'm only assuming "fix=6.0" should be replaced with "fix=master" based on the timeframe the issue was created/resolved in. > Speed up LatLonPoint's polygon queries when there are many vertices > --- > > Key: LUCENE-7239 > URL: https://issues.apache.org/jira/browse/LUCENE-7239 > Project: Lucene - Core > Issue Type: Improvement >Reporter: Robert Muir > Fix For: 6.1, master (7.0) > > Attachments: LUCENE-7239.patch, LUCENE-7239.patch > > > This is inspired by the "reliability and numerical stability" recommendations > at the end of http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf. > Basically our polys need to answer two questions that are slow today: > contains(point) > crosses(rectangle) > Both of these ops only care about a subset of edges: the ones overlapping a y > interval range. We can organize these edges in an interval tree to be > practical and speed things up a lot. Worst case is still O(n) but those > solutions are more complex to do. -- 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
[jira] [Updated] (LUCENE-7239) Speed up LatLonPoint's polygon queries when there are many vertices
[ https://issues.apache.org/jira/browse/LUCENE-7239?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Robert Muir updated LUCENE-7239: Attachment: LUCENE-7239.patch I added minor cleanups and comments to make this less sandy. Its passed 100 beast rounds. I will test some more and get it in jenkins and followup with other improvements. > Speed up LatLonPoint's polygon queries when there are many vertices > --- > > Key: LUCENE-7239 > URL: https://issues.apache.org/jira/browse/LUCENE-7239 > Project: Lucene - Core > Issue Type: Improvement >Reporter: Robert Muir > Attachments: LUCENE-7239.patch, LUCENE-7239.patch > > > This is inspired by the "reliability and numerical stability" recommendations > at the end of http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf. > Basically our polys need to answer two questions that are slow today: > contains(point) > crosses(rectangle) > Both of these ops only care about a subset of edges: the ones overlapping a y > interval range. We can organize these edges in an interval tree to be > practical and speed things up a lot. Worst case is still O(n) but those > solutions are more complex to do. -- 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
[jira] [Updated] (LUCENE-7239) Speed up LatLonPoint's polygon queries when there are many vertices
[ https://issues.apache.org/jira/browse/LUCENE-7239?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Robert Muir updated LUCENE-7239: Attachment: LUCENE-7239.patch Here is a patch for the sandbox. Ultimately, I think we should just yank the slower polygon support out of Polygon.java, make it a pure holder class. Feels wrong to do stuff like this when e.g. spatial3d does not care. But for now lets improve it here. Synthetic polygons from luceneUtil ||vertices||old QPS||new QPS| |5|24.4|38.4| |50|21.7|29.7| |500|14.4|27.5| |5000|3.3|18.8| Real polygons (33 london districts: http://data.london.gov.uk/2011-boundary-files) ||vertices||old QPS||new QPS| |avg 5.6k|8.6|73.0| Since relations are much faster, startup cost is reduced substantially: e.g. for those real polygons it drops from 85ms to 3ms. We keep our grid for now (its still a decent speedup and now has a cheap cost). Less complex polygons get a nice speedup too since we are less trappy and the two-phase iteration doesn't buy us stuff anymore (similar to distance case). > Speed up LatLonPoint's polygon queries when there are many vertices > --- > > Key: LUCENE-7239 > URL: https://issues.apache.org/jira/browse/LUCENE-7239 > Project: Lucene - Core > Issue Type: Improvement >Reporter: Robert Muir > Attachments: LUCENE-7239.patch > > > This is inspired by the "reliability and numerical stability" recommendations > at the end of http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf. > Basically our polys need to answer two questions that are slow today: > contains(point) > crosses(rectangle) > Both of these ops only care about a subset of edges: the ones overlapping a y > interval range. We can organize these edges in an interval tree to be > practical and speed things up a lot. Worst case is still O(n) but those > solutions are more complex to do. -- 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
