[
https://issues.apache.org/jira/browse/LUCENE-7270?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15269696#comment-15269696
]
Karl Wright commented on LUCENE-7270:
-------------------------------------
Ok, [~rcmuir], making that change brings the 2D implementation to roughly the
same as the ordered 3D implementation I had earlier this afternoon:
{code}
ITER 0: 0.46 M hits/sec, 5.60 QPS (5.90 sec for 33 queries), totHits=2693539
***
ITER 1: 0.73 M hits/sec, 9.00 QPS (3.66 sec for 33 queries), totHits=2693539
***
ITER 2: 0.75 M hits/sec, 9.24 QPS (3.57 sec for 33 queries), totHits=2693539
***
ITER 3: 0.75 M hits/sec, 9.15 QPS (3.61 sec for 33 queries), totHits=2693539
ITER 4: 0.75 M hits/sec, 9.17 QPS (3.60 sec for 33 queries), totHits=2693539
ITER 5: 0.75 M hits/sec, 9.15 QPS (3.61 sec for 33 queries), totHits=2693539
ITER 6: 0.76 M hits/sec, 9.27 QPS (3.56 sec for 33 queries), totHits=2693539
***
ITER 7: 0.75 M hits/sec, 9.25 QPS (3.57 sec for 33 queries), totHits=2693539
ITER 8: 0.75 M hits/sec, 9.18 QPS (3.59 sec for 33 queries), totHits=2693539
ITER 9: 0.76 M hits/sec, 9.34 QPS (3.53 sec for 33 queries), totHits=2693539
***
ITER 10: 0.75 M hits/sec, 9.23 QPS (3.58 sec for 33 queries), totHits=2693539
ITER 11: 0.75 M hits/sec, 9.24 QPS (3.57 sec for 33 queries), totHits=2693539
ITER 12: 0.76 M hits/sec, 9.27 QPS (3.56 sec for 33 queries), totHits=2693539
{code}
Essentially it's the same performance-wise, maybe a touch slower, but I like it
better because there's no need to duplicate Edge's ever, and thus there's no
need to have a Set for deduplication. Hmm, decisions, decisions...
> Use better balanced trees for Geo3d complex polygons
> ----------------------------------------------------
>
> Key: LUCENE-7270
> URL: https://issues.apache.org/jira/browse/LUCENE-7270
> Project: Lucene - Core
> Issue Type: Improvement
> Components: modules/spatial3d
> Reporter: Karl Wright
> Assignee: Karl Wright
> Fix For: master, 6.x
>
>
> The current tree data structure in GeoComplexPolygon has a lot of weaknesses.
> A better algorithm maybe can be taken from Polygon2D, which basically does
> the following:
> Each node has:
> - low value (which is for that edge alone)
> - max value (which is for that edge and all children)
> Balanced tree building:
> - sort by low value (which is for the individual edge), and use max value as
> tie breaker (which is max for edge and all children)
> - build tree after sorting, picking midpoint and recursively building lesser
> and greater children that way
> Balanced tree traversal (looking for range minValue -> maxValue):
> - Descend the entire tree until the node fails this test:
> if (minValue <= max) { ... }
> So if the minimum value being sought is greater than the max for this edge
> and all children, we stop and don't look at children.
> (Q: does this represent a good split and a targeted range? Maybe... We
> can certainly try it.)
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
