lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Ryan Ernst (JIRA)" <j...@apache.org>
Subject [jira] [Comment Edited] (LUCENE-7147) Improve disjoint check for geo distance query traversal
Date Tue, 29 Mar 2016 06:17:26 GMT

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

Ryan Ernst edited comment on LUCENE-7147 at 3/29/16 6:17 AM:
-------------------------------------------------------------

Here is a patch which adds the following simple logic: if the rect of the subtree does not
cross over any axis of the bbox, and none of the corners of the rect are in the circle, then
the rect is disjoint from the circle. Note that while the meridian axis of the bbox is simple
(it is just the longitude of the circle center), the latitude is a little more complicated.
This is the latitude at which the bbox longitudes intersect the circle, which is *not* the
latitude of the circle center (as it would be in normal 2D), except when the center is on
the equator. The patch provides a utility method to calculate this latitude for a given circle.
It also has a randomized test to check this disjoint logic in isolation, outside of the geo
data structures. And finally it has a nice utility for visualizing these circles and rects,
along with the bbox and its axis' (thanks Mike!).


was (Author: rjernst):
Here is a patch which adds the following simple logic: if the rect of the subtree do not cross
over any axis of the bbox, and none of the corners of the rect are in the circle, then they
are disjoint. Note that while the meridian axis of bbox is simple (it is just the longitude
of the circle center), the latitude is a little more complicated. This is the latitude at
which the bbox longitudes intersect the circle, which is *not* the latitude of the circle
center (as it would be in normal 2D), except when the center is on the equator. The patch
provides a utility method to calculate this latitude for a given circle. It also has a randomized
test to check this disjoint logic in isolation, outside of the geo data structures. And finally
it has a nice utility for visualizing these circles and rects, along with the bbox and its
axis' (thanks Mike!).

> Improve disjoint check for geo distance query traversal
> -------------------------------------------------------
>
>                 Key: LUCENE-7147
>                 URL: https://issues.apache.org/jira/browse/LUCENE-7147
>             Project: Lucene - Core
>          Issue Type: Improvement
>            Reporter: Ryan Ernst
>         Attachments: LUCENE-7147.patch
>
>
> When doing geo distance queries, it is important to avoid traversing subtrees which do
not contain any relevant points. We currently have checks which compare the bbox of the query
to the bounds of the subtree. However, it is possible for a subtree to overlap the bbox, but
still not intersect the query. This issue is to improve that check to avoid unnecessary traversals.



--
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