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

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 4.7, 6.0
• Component/s: modules/facet
• Lucene Fields: New
• Assignee: Michael McCandless
• Reporter: Michael McCandless
• Created: 17/Dec/13 15:09
• Updated: 28/Aug/22 13:57
• Resolved: 04/Jan/14 12:33

Description

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.