Patent application EP17174406A (EP), filed 2017-06-02
Publication number: EP3255571A1
Title: SYSTEM AND METHOD FOR EFFICIENT INTERVAL SEARCH USING LOCALITY-PRESERVING HASHING
Abstract: Embodiments of the present invention 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. A new structure called an interval hash table is introduced to significantly reduce the average search time, thereby improving computing and search technology. During operation, the system obtains data indicating a set of intervals to be hashed. The system divides a respective interval into a set of sub-intervals based on a locality-preserving hashing. The system then obtains a hash code associated with a respective sub-interval, and inserts the respective sub-interval into an interval hash table at a location corresponding to the hash code. The system may further search the interval hash table.
IPC codes: G06F  17/    30            A I
G06F  16/    00            A I
G06F  16/   901            A I
G06F  16/   903            A I
Claims: number: 1
text: A computer-implemented method for hashing an interval, comprising:
number: 2
text: The method of claim 1, wherein dividing the respective interval further comprises:
number: 3
text: The method of claim 1, further comprising searching the interval hash table, which comprises:
number: 4
text: The method of claim 3:
number: 5
text: A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for hashing an interval, the method comprising:
number: 6
text: The non-transitory computer-readable storage medium of claim 5, wherein dividing the respective interval further comprises:
number: 7
text: The non-transitory computer-readable storage medium of claim 5, wherein the method further comprises searching the interval hash table, which comprises:
number: 8
text: The non-transitory computer-readable storage medium of claim 7, wherein searching for intervals that overlap with the respective search sub-interval further comprises using a one-sided binary search, which comprises:
number: 9
text: A computing system for hashing an interval, the system comprising:
number: 10
text: The computing system of claim 9, wherein dividing the respective interval further comprises:
Office action: search_report, dated 2017-12-13
Prior art cited: ref_id: US2006143206A1
ref_type: patent
severity: background
ref_id: EP1515501A1
ref_type: patent
severity: background
ref_id: EP1160682A1
ref_type: patent
severity: background
ref_id: US2007136243A1
ref_type: patent
severity: background
ref_id: EP1160682
ref_type: patent
severity: background
ref_id: EP1515501
ref_type: patent
severity: background
ref_id: US2006143206
ref_type: patent
severity: background
ref_id: US2007136243
ref_type: patent
severity: background
Final disposition: pending (2017-12-13)