Changing Bits: Fast range faceting using segment trees and the Java ASM library

Changing Bits: Fast range faceting using segment trees and the Java ASM library

Fast range faceting using segment trees and the Java ASM library In Lucene's facet module we recently added support for dynamic range faceting , to show how many hits match each of a dynamic set of ranges. For example, the Updated drill-down in the Lucene/Solr issue search application uses range facets. Another example is distance facets (< 1 km, < 2 km, etc.), where the distance is dynamically computed based on the user's current location. Price faceting might also use range facets, if the ranges cannot be established during indexing. To implement range faceting, for each hit, we first calculate the value (the distance, the age, the price) to be aggregated, and then lookup which ranges match that value and increment its counts. Today we use a simple linear search through all ranges, which has O(N) But this is inefficient! Segment trees O(log(N) + M) M is the number of ranges that match the given value. I chose to explore segment trees,

Read full article from Changing Bits: Fast range faceting using segment trees and the Java ASM library