[jira] [Commented] (LUCENE-5371) Range faceting should use O(log(N)) search per hit

["ASF subversion and git services (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/LUCENE-5371?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13862268#comment-13862268 ] 

ASF subversion and git services commented on LUCENE-5371:
---------------------------------------------------------

Commit 1555338 from [~mikemccand] in branch 'dev/trunk'
[ https://svn.apache.org/r1555338 ]

LUCENE-5371, LUCENE-5339: speed up range faceting from O(N) per hit to O(log(N)) using segment trees; simplify facet APIs

> Range faceting should use O(log(N)) search per hit
> --------------------------------------------------
>
>                 Key: LUCENE-5371
>                 URL: https://issues.apache.org/jira/browse/LUCENE-5371
>             Project: Lucene - Core
>          Issue Type: Improvement
>          Components: modules/facet
>            Reporter: Michael McCandless
>            Assignee: Michael McCandless
>             Fix For: 5.0, 4.7
>
>         Attachments: LUCENE-5371.patch, LUCENE-5371.patch
>
>
> Today, Lucene's dynamic range faceting uses a simple linear search to
> find which ranges match, but there are known data structures to do
> this in log(N) time.  I played with segment trees and wrote up a blog
> post here:
>   http://blog.mikemccandless.com/2013/12/fast-range-faceting-using-segment-trees.html
> O(N) cost is actually OK when number of ranges is smallish, which is
> typical for facet use cases, but then scales badly if there are many
> ranges.



--
This message was sent by Atlassian JIRA
(v6.1.5#6160)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org