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

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

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 4.7, 6.0
    • Component/s: modules/facet
    • Labels:
      None
    • Lucene Fields:
      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

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

              Dates

              • Created:
                Updated:
                Resolved: