[jira] [Created] (LUCENE-6697) Use 1D KD tree for alternative to postings based numeric range filters

["Michael McCandless (JIRA)" <ji...@apache.org>]

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: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org