Range Store

Range Store (Experimental)

This store is designed to work superfically like a large Interval Tree which stores a collection of ranges. This store will then allows a user to provide a range and query time that will allow the user to find all ranges that contain any portion touching the query range. The following is an example of using the range store to save and query ranges.

public class Example {

    RangeStore<Long> rangeStore;

    public Example(Connector connector) throws Exception{
        rangeStore = new AccumuloRangeStore<Long>(connector, new LongRangeHelper());
    }
    
    public void save(Collection<ValueRange<Long>> ranges) {
        rangeStore.save(ranges);
    }
    
    public Iterable<ValueRange<Long>> getRanges(long start, long end, Auths auths) {
        return rangeStore.query(new ValueRange<Long>(start, end), auths);
    }
}

Known Issues

While the range store does provide accurate results back, there are conditions where the store can perform suboptimally:

• Storing overly large ranges mixed with small ranges. For example, if the vast majority of the ranges are small but a few span a large portion of the data, this store will spend a lot of time scanning over a lot of smaller ranges that will simply be filtered out. The worse case for overly large ranges is that the query will have to scan the majority of the table to produce the right results. An alternative may be to store similarly sized ranges in seperate tables which will generate more efficient queries for each of the sets.
• Performing an overly large query across dense data. The store will scan the query range twice to find ranges intersecting via their lower and their upper bounds. This means on one of the scans, the ranges that were fully contained in the query ranges must be filtered out. An alternative approach for usecases with more densely packed ranges may be to break up the query ranges into smaller ranges query ranges combining the results.