lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Karl Wright (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (LUCENE-7270) Use better balanced trees for Geo3d complex polygons
Date Tue, 03 May 2016 17:14:12 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-7270?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15269117#comment-15269117
] 

Karl Wright commented on LUCENE-7270:
-------------------------------------

Works great; now performance on my laptop looks like this:

{code}
ITER 4: 0.75 M hits/sec, 9.21 QPS (3.58 sec for 33 queries), totHits=2693539
ITER 5: 0.76 M hits/sec, 9.29 QPS (3.55 sec for 33 queries), totHits=2693539
ITER 6: 0.76 M hits/sec, 9.26 QPS (3.56 sec for 33 queries), totHits=2693539
ITER 7: 0.75 M hits/sec, 9.18 QPS (3.59 sec for 33 queries), totHits=2693539
ITER 8: 0.74 M hits/sec, 9.03 QPS (3.65 sec for 33 queries), totHits=2693539
ITER 9: 0.76 M hits/sec, 9.28 QPS (3.56 sec for 33 queries), totHits=2693539
{code}


> 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
>
> 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: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message