Michael McCandless created LUCENE-6697:
------------------------------------------
Summary: Use 1D KD tree for alternative to postings based numeric
range filters
Key: LUCENE-6697
URL: https://issues.apache.org/jira/browse/LUCENE-6697
Project: Lucene - Core
Issue Type: New Feature
Reporter: Michael McCandless
Assignee: Michael McCandless
Today Lucene uses postings to index a numeric value at multiple
precision levels for fast range searching. It's somewhat costly: each
numeric value is indexed with multiple terms (4 terms by default)
... I think a dedicated 1D BKD tree should be more compact and perform
better.
It should also easily generalize beyond 64 bits to arbitrary byte[],
e.g. for LUCENE-5596, but I haven't explored that here.
A 1D BKD tree just sorts all values, and then indexes adjacent leaf
blocks of size 512-1024 (by default) values per block, and their
docIDs, into a fully balanced binary tree. Building the range filter
is then just a recursive walk through this tree.
It's the same structure we use for 2D lat/lon BKD tree, just with 1D
instead. I implemented it as a DocValuesFormat that also writes the
numeric tree on the side.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
