[
https://issues.apache.org/jira/browse/LUCENE-7110?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16326497#comment-16326497
]
Nicholas Knize commented on LUCENE-7110:
----------------------------------------
After getting away from this issue for a bit to investigate using Range fields
with doc values for the same purpose I wanted to raise attention back here to
solicit some quick feedback.
What are the general thoughts on building on/extending the BKD/Points codec
logic to create a complementary RTree/Ranges codec designed for fast bounding
box index/search? The bones are already there, its just a matter of changing:
# the \{min/max}PackedValue logic in the reader/writer to represent bounding
boxes/ranges
# Add logic to handle coordinate system wrapping.
Overly simplified, of course, but this codec would effectively support spatial
data only (not just spherical for lat/lon/alt, but also cartesian coordinates
for 2/3D gaming). It would also likely be better suited for the existing range
fields and would enable ranges to wrap the min/max boundary.
An alternative would be to add something like a rangeType property to
{{IndexableFieldType}} and modify the existing {{Point}} codec to handle range
encoding and coordinate system wrapping but I think that's too big of a risky
hack.
Any thoughts?
> Add Shape Support to BKD (extend to an R*/X-Tree data structure)
> ----------------------------------------------------------------
>
> Key: LUCENE-7110
> URL: https://issues.apache.org/jira/browse/LUCENE-7110
> Project: Lucene - Core
> Issue Type: New Feature
> Reporter: Nicholas Knize
> Priority: Major
>
> I've been tinkering with this off and on for a while and its showing some
> promise so I'm going to open an issue to (eventually) add this feature to
> either a 6.x or (more likely) a 7.x release.
> R*/X-Tree is a data structure designed to support Shapes (2D, 3D, nD) where,
> like the internal node, the key for each leaf node is the Minimum Bounding
> Range (MBR - sometimes "incorrectly" referred to as Minimum Bounding
> Rectangle) of the shape. Inserting a shape then boils down to the best way of
> optimizing the tree structure. This optimization is driven by a set of
> criteria for choosing the appropriate internal key (e.g., minimizing overlap
> between siblings, maximizing "squareness", minimizing area, maximizing space
> usage). Query is then (a bit oversimplified) a two-phase process:
> * recurse each branch that overlaps with the MBR of the query shape
> * compute the relation with the leaf node(s) - in higher dimensions (3+) this
> becomes an increasingly difficult computational geometry problem
> The current BKD implementation is a special simplified case of an R*/X tree
> where, for Point data, it is always guaranteed there will never be overlap
> between sibling nodes (because you're using the point data as the keys). By
> exploiting this property the tree algorithms (split, merge, etc) are
> relatively cheap (hence their performance boost over postings based
> numerics). By modifying the key data, and extending the tree generation
> algorithms BKD logic can be extended to support Shape data using the MBR as
> the Key and modifying split and merge based on the criteria needed for
> optimizing a shape-based data structure.
> The initial implementation (based on limitations of the GeoAPI) will support
> 2D shapes only. Once the GeoAPI can performantly handle 3D shapes the change
> is relatively trivial to add the third dimension to the tree generation code.
> Like everything else, this feature will be created in sandbox and, once
> mature, will graduate (likely to lucene-spatial or lucene-spatial-extras
> depending on the library needs).
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
