[ https://issues.apache.org/jira/browse/LUCENE-6697?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14650240#comment-14650240 ]
ASF subversion and git services commented on LUCENE-6697: --------------------------------------------------------- Commit 1693693 from [~mikemccand] in branch 'dev/trunk' [ https://svn.apache.org/r1693693 ] LUCENE-6697: rename NumericTree -> RangeTree > 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 > Fix For: 5.3, Trunk > > Attachments: LUCENE-6697.patch, LUCENE-6697.patch, LUCENE-6697.patch > > > 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-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org