[
https://issues.apache.org/jira/browse/LUCENE-6477?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14552070#comment-14552070
]
Michael McCandless commented on LUCENE-6477:
--------------------------------------------
bq. It looks like Mike's patch targets the sandbox entirely already...
Right, I think this really must start in sandbox... it's completely new and
quite complex, likely has exciting bugs, writes its own index files and there's
no guarantee of back compat, etc.
Longer term, when/if it graduates, I don't think it should go into
lucene/spatial: I don't like how "heavy" lucene/spatial is, with external libs
bleeding into the public APIs (spatial4j, JTS), too-many-abstractions causing
barriers for new contributions, test case base classes strangely forked from
external libraries and thus failing to print "reproduce with" lines, etc.
I think we need competing/alternative approaches that are much more
lightweight, and focus on the common case (index points, search shapes), like
LUCENE-6450 and this patch... and I think such support really could/should be
in Lucene's core, or "spatial2" or "spatiallight" or something. And then I
think that leaves lucene/spatial supporting the exotic/difficult cases that
require (\?) all the abstractions?
bq. except for some BitDocIdSet changes that need a little explanation
Woops, that was a leftover from struggling ... I'll revert it.
bq. Maybe its good to think about a documented way for codecs to freely and
easily use scratch files like this, where IndexFileDeleter could help out.
That's a good idea ... it's true this is a heavy user of OfflineSorter, because
it needs to recursively partition all points, separately in lat and lon.
I'll post a new patch soon, adding missing javadocs, marking things
experimental, adding polygon support.
> Add BKD tree for spatial shape query intersecting indexed points
> ----------------------------------------------------------------
>
> Key: LUCENE-6477
> URL: https://issues.apache.org/jira/browse/LUCENE-6477
> Project: Lucene - Core
> Issue Type: New Feature
> Reporter: Michael McCandless
> Assignee: Michael McCandless
> Fix For: Trunk, 5.2
>
> Attachments: LUCENE-6477.patch, LUCENE-6477.patch
>
>
> I'd like to explore using dedicated spatial trees for faster shape
> intersection filters than postings-based implementations.
> I implemented the tree data structure from
> https://www.cs.duke.edu/~pankaj/publications/papers/bkd-sstd.pdf
> The idea is simple: it builds a full binary tree, partitioning 2D
> space, alternately on lat and then lon, into smaller and smaller
> rectangles until a leaf has <= N (default 1024) points.
> It cannot index shapes (just points), and can then do fast shape
> intersection queries. Multi-valued fields are supported.
> I only implemented the "point is contained in this bounding box" query
> for now, but I think polygon shape querying should be easy to
> implement using the same approach from LUCENE-6450.
> For indexing, you add BKDPointField (takes lat, lon) to your doc, and
> must set up your Codec use BKDTreeDocValuesFormat for that field.
> This DV format wraps Lucene50DVFormat, but then builds the disk-based
> BKD tree structure on the side. BKDPointInBBoxQuery then requires this
> DVFormat, and casts it to gain access to the tree.
> I quantize each incoming double lat/lon to 32 bits precision (so 64
> bits per point) = ~9 milli-meter lon precision at the equator, I
> think.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
