Interval based fuzzy database search

Patent metadata

Field	Value
Publication number	US-9529865-B2
Application number	US-201414179307-A
Country	US
Kind code	B2
Filing date	Feb 12, 2014
Priority date	Feb 12, 2014
Publication date	Dec 27, 2016
Grant date	Dec 27, 2016

Abstract

A fuzzy database search technique is described for searching a database. The technique first prepares a database by first generating a reference hash value for each database entry to represent a value stored in a field of the database entry. The technique then receives search request to search for database entries in the database that have a value stored in the field that is within a provided range. The technique converts the search request into one or more search hash values and matches the search hash values to the reference hash values of the database to rapidly identify database entries that are likely relevant to the search.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
preprocessing a database in a data storage device to modify a database schema for the database from an initial schema into a database schema that comprises a reference hash field for each database entry of the database for adding reference hash values to the reference hash fields of the database entries;
receiving, by a processor in a search engine, a request from a client computer system to search the database, the request including a first search parameter identifying a first range of values, a second search parameter identifying a second range of values, and combinational logic for joining the first search parameter and the second search parameter;
converting, by the search engine processor, the first search parameter into a first search hash value and the second search parameter into a second search hash value in response to the request, wherein the first search hash value represents an interval containing the first range of values and the second search hash value represents an interval containing the second range of values;
searching, by the search engine processor, the database to identify database entries having reference hash values stored in the reference hash fields of the database entries that match the first search hash value and the second search hash value;
joining database entries having hash values matching the first hash values and the second hash values into a combined list of database entries based on the combinational logic; and
returning, by the search engine processor, the combined list of identified database entries to the client computer system.

2. The computer-implemented method of claim 1 , wherein the length of a search hash value is inversely proportional to the length of an interval.

3. The computer-implemented method of claim 1 , wherein a first database entry matching a first hash value generated from the first search parameter and a second database entry matching a second hash value generated from the second search parameter are identified when searching the database.

4. The computer-implemented method of claim 1 , wherein generating the search hash values comprises identifying, from a plurality of intervals, an interval that contains at least a portion of the first range of values.

5. The computer-implemented method of claim 1 , wherein the first and second range of values each represent a non-overlapping period of time.

6. The computer-implemented method of claim 1 further comprising:
dividing the interval containing the first range of values into a set of equally sized intervals; and
recursively dividing each interval into a set of equally sized sub-time intervals.

7. The computer-implemented method of claim 1 wherein searches with high precision are performed slower but result in a smaller set of database results, and wherein searches with low precision are performed faster but return a larger set of database results.

8. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a computer system, cause the computer system to perform operations for:
preprocessing a database in a data storage device to modify a database schema for the database from an initial schema into a database schema that comprises a reference hash field for each database entry of the database for adding reference hash values to the reference hash fields of the database entries;
receiving, by a processor in a search engine, a request from a client computer system to search the database, the request including a first search parameter identifying a first range of values, a second search parameter identifying a second range of values, and combinational logic for joining the first search parameter and the second search parameter;
converting, by the search engine processor, the first search parameter into a first search hash value and the second search parameter into a second search hash value in response to the request, wherein the first search hash value represents an interval containing the first range of values and the second search hash value represents an interval containing the second range of values;
searching, by the search engine processor, the database to identify database entries having reference hash values stored in the reference hash fields of the database entries that match the first search hash value and the second search hash value;
joining database entries having hash values matching the first hash values and the second hash values into a combined list of database entries based on the combinational logic; and
returning, by the search engine processor, the combined list of identified database entries to the client computer system.

9. The non-transitory computer readable storage medium of claim 8 , wherein the length of a search hash value is inversely proportional to the length of an interval.

10. The non-transitory computer readable storage medium of claim 8 , wherein a first database entry matching a first hash value generated from the first search parameter and a second database entry matching a second hash value generated from the second search parameter are identified when searching the database.

11. The non-transitory computer readable storage medium of claim 8 , wherein generating the search hash values comprises identifying, from a plurality of intervals, an interval that contains at least a portion of the first range of values.

12. The non-transitory computer readable storage medium of claim 8 , wherein the first and second range of values each represent a non-overlapping period of time.

13. A computer system comprising:
one or more computer processors; and
a non-transitory computer-readable storage medium comprising instructions, that when executed by the one or more computer processors, controls the one or more computer processors to be configured for performing operations comprising:
preprocessing a database in a data storage device to modify a database schema for the database from an initial schema into a database schema that comprises a reference hash field for each database entry of the database for adding reference hash values to the reference hash fields of the database entries;
receiving a request from a client computer system to search the database, the request including a first search parameter identifying a first range of values, a second search parameter identifying a second range of values, and combinational logic for joining the first search parameter and the second search parameter;
converting the first search parameter into a first search hash value and the second search parameter into a second search hash value in response to the request, wherein the first search hash value represents an interval containing the first range of values and the second search hash value represents an interval containing the second range of values;
searching the database to identify database entries having reference hash values stored in the reference hash fields of the database entries that match the first search hash value and the second search hash value; and
joining database entries having hash values matching the first hash values and the second hash values into a combined list of database entries based on the combinational logic; and
returning the combined list of identified database entries to the client computer system.

14. The computer system of claim 13 , wherein the length of a search hash value is inversely proportional to the length of an interval.

15. The computer system of claim 13 , wherein a first datab

Assignees

• Herz Andreas
• Sap Se

Inventors

• Herz Andreas

Classifications

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F16/2477

  Temporal data queries · CPC title

• G06F16/2468 Primary

  Fuzzy queries · CPC title

• G06F16/152

  using file content signatures, e.g. hash values · CPC title

• G06F17/30867

  Physics · mapped topic