Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-5371

Range faceting should use O(log(N)) search per hit

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 4.7, 6.0
    • modules/facet
    • None
    • New

    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.

      Attachments

        1. LUCENE-5371.patch
          31 kB
          Michael McCandless
        2. LUCENE-5371.patch
          35 kB
          Michael McCandless

        Activity

          People

            mikemccand Michael McCandless
            mikemccand Michael McCandless
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: