System and method for efficient interval search using locality holding hashes

摘要

PROBLEM TO BE SOLVED: To provide a time- and space-efficient system for representing and searching a set of intervals to find all the intervals that overlap with a given query interval or point.SOLUTION: The system obtains data indicating a set of intervals to be hashed. The system divides each interval into a set of sub-intervals on the basis of a locality-preserving hashing. The system then obtains a hash code associated with each sub-interval, and inserts it into an interval hash table. The system obtains a low hash code for a lowest-ordered element and a high hash code for a highest-ordered element of the interval; forms a set of hash codes; obtains a maximal interval associated only with each hash code in the set, where the maximal interval is not subsumed in any larger interval associated only with the hash code; and identifies each sub-interval associated with the hash code on the basis of the obtained maximal interval and the lowest-ordered element and highest-ordered element of the interval.SELECTED DRAWING: Figure 5