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

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

Michael McCandless created LUCENE-5371:
------------------------------------------

             Summary: 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


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.4#6159)

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