[
https://issues.apache.org/jira/browse/LUCENE-6699?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14645732#comment-14645732
]
Michael McCandless commented on LUCENE-6699:
--------------------------------------------
OK, thanks [~daddywri], I think I understand.
Yes BKD tree can easily split on the 3 (x,y,z) dimensions ... I just need to
generalize it (it's currently "hardwired" for just 2 dimensions).
So for this to work, I need to be able to efficiently ask the query shape
whether it separately overlaps with a range in each of the 3 dimensions. E.g.
"do you intersect 0.3 <= x < 0.7", and same for y and z. I assume this is
fast/simple to do with the spatial3d APIs?
And then of course with each indexed x,y,z point I also need to test whether
the shape includes it.
Hmm, one source of efficiency for the BKD tree is it can recognize at search
time when a given indexed cell is fully contained by the query shape, and then
it doesn't need to test every point against the shape (it just blindly collects
all docIDs in that cell). But in the 3D case, I think that optimization would
never apply? I.e, the leaf cells would all be little cubes on the earth's
surface, which include a volume (above and below earth's surface) that the
shape does not accept?
> Integrate lat/lon BKD and spatial3d
> -----------------------------------
>
> Key: LUCENE-6699
> URL: https://issues.apache.org/jira/browse/LUCENE-6699
> Project: Lucene - Core
> Issue Type: New Feature
> Reporter: Michael McCandless
> Assignee: Michael McCandless
>
> I'm opening this for discussion, because I'm not yet sure how to do
> this integration, because of my ignorance about spatial in general and
> spatial3d in particular :)
> Our BKD tree impl is very fast at doing lat/lon shape intersection
> (bbox, polygon, soon distance: LUCENE-6698) against previously indexed
> points.
> I think to integrate with spatial3d, we would first need to record
> lat/lon/z into doc values. Somewhere I saw discussion about how we
> could stuff all 3 into a single long value with acceptable precision
> loss? Or, we could use BinaryDocValues? We need all 3 dims available
> to do the fast per-hit query time filtering.
> But, second: what do we index into the BKD tree? Can we "just" index
> earth surface lat/lon, and then at query time is spatial3d able to
> give me an enclosing "surface lat/lon" bbox for a 3d shape? Or
> ... must we index all 3 dimensions into the BKD tree (seems like this
> could be somewhat wasteful)?
--
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
