[
https://issues.apache.org/jira/browse/LUCENE-5371?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Michael McCandless resolved LUCENE-5371.
----------------------------------------
Resolution: Fixed
> 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: [email protected]
For additional commands, e-mail: [email protected]
