You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Michael McCandless (JIRA)" <ji...@apache.org> on 2015/05/11 17:06:59 UTC
[jira] [Created] (LUCENE-6477) Add BKD tree for spatial shape query
intersecting indexed points
Michael McCandless created LUCENE-6477:
------------------------------------------
Summary: 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
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: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org