Bloom filters for query simulation

• US 8,239,394 B1
• Filed: 03/31/2005
• Issued: 08/07/2012
• Est. Priority Date: 03/31/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rohde, Douglas L. T., Hogue, Andrew W., Weinberger, Peter J.
• Primary Examiner(s): Yen, Syling
• Application Number:
  US11/097,676
• Time in Patent Office: 2,686 Days
• Field of Search: 707/3, 709/203
• US Class Current: 707/754
• CPC Class Codes: G06F 16/332 Query formulation
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

A method of restricting a database access operation is disclosed. A plurality of Bloom filters corresponding to a plurality of fields in a database are applied to two or more terms in a record to produce a first plurality of outputs. The record may correspond to a query. Extraneous terms may be removed from the record. The access operation to the database is enabled if the first plurality of outputs correspond to a positive result.

Claims

1. A method of restricting a database access operation, comprising:

applying a plurality of Bloom filters corresponding to a plurality of fields in a database to two or more terms in a record to produce a first plurality of outputs;

enabling an access operation to the database if the first plurality of outputs correspond to a positive result; and

when the access operation is enabled, returning a result from the access operation.

2. The method of restricting a database access operation in claim 1, wherein the record corresponds to a query.

3. The method of restricting a database access operation in claim 2, further comprising:

identifying first and second subsets of the terms in the query;

applying a first Bloom filter in the plurality of Bloom filters to the first subset to produce a first output; and

applying a second Bloom filter in the plurality of Bloom filters to the second subset to produce a second output,

wherein enabling the access operation is further in accordance with the first output and the second output corresponding to the positive result.

4. The method of restricting a database access operation in claim 2, further comprising:

identifying a plurality of subsets of the terms in the query; and

applying one or more of the Bloom filters to each of the subsets to produce a second plurality of outputs,

wherein enabling the access operation is further in accordance with the second plurality of outputs from the one or more Bloom filters corresponding to at least one of a plurality of success patterns.

5. The method of restricting a database access operation in claim 2, further comprising:

applying a normalization operation to the query to produce a normalized set of terms; and

applying an additional Bloom filter to each of the terms in the normalized set of terms to produce an additional output;

wherein enabling the access operation is further in accordance with the additional output corresponding to the positive result.

6. The method of restricting a database access operation in claim 1, further comprising removing extraneous terms from the record.

7. The method of restricting a database access operation in claim 1, further comprising sorting the two or more terms in the record to produce a sorted record.

8. The method of restricting a database access operation in claim 7, further comprising:

applying a first Bloom filter to the sorted record to produce a first output,

wherein enabling the access operation is further in accordance with the first output corresponding to the positive result.

9. The method of restricting a database access operation in claim 1, wherein the database comprises factual information, and the plurality of fields in the database include objects, attributes and values.

10. The method of restricting a database access operation in claim 1, further comprising:

parsing the terms in the record in a plurality of ways to produce a plurality of parsed sets of terms; and

applying at least two of the Bloom filters in the plurality of Bloom filters to the plurality of parsed sets of terms to produce a second plurality of outputs;

wherein enabling the access operation is further in accordance with the second plurality of outputs corresponding to the positive result.

11. The method of restricting a database access operation in claim 10, wherein at least the two Bloom filters respectively correspond to an attribute field and a value field.

12. The method of restricting a database access operation in claim 1, further comprising:

applying a first Bloom filter in the plurality of Bloom filters to a first term in the record to produce a first output;

sorting remaining terms in the record; and

applying a second Bloom filter in the plurality of Bloom filters to the sorted remaining terms in the record to produce a second output,

wherein enabling the access operation is further in accordance with the first output and the second output corresponding to the positive result, and wherein a first field corresponding to the first Bloom filter includes attributes and a second field corresponding to the second Bloom filter includes values.

13. The method of restricting a database access operation in claim 1, further comprising:

applying a first Bloom filter in the plurality of Bloom filters to a first two terms in the record to produce a first output;

sorting remaining terms in the record; and

applying a second Bloom filter in the plurality of Bloom filters to the sorted remaining terms in the record to produce a second output,

wherein enabling the access operation is further in accordance with the first output and the second output corresponding to the positive result, and wherein a first field corresponding to the first Bloom filter includes attributes and a second field corresponding to the second Bloom filter includes values.

14. The method of restricting a database access operation in claim 1, further comprising:

applying a first Bloom filter in the plurality of Bloom filters to a last two terms in the record to produce a first output;

sorting remaining terms in the record; and

applying a second Bloom filter in the plurality of Bloom filters to the sorted remaining terms in the record to produce a second output,

wherein enabling the access operation is further in accordance with the first output and the second output corresponding to the positive result, and wherein a first field corresponding to the first Bloom filter includes attributes and a second field corresponding to the second Bloom filter includes values.

15. The method of restricting a database access operation in claim 1, further comprising:

applying a first Bloom filter in the plurality of Bloom filters to a last term in the record to produce a first output;

sorting remaining terms in the record; and

applying a second Bloom filter in the plurality of Bloom filters to the sorted remaining terms in the record to produce a second output,

wherein enabling the access operation is further in accordance with the first output and the second output corresponding to the positive result, and wherein a first field corresponding to the first Bloom filter includes attributes and a second field corresponding to the second Bloom filter includes values.

16. A computer-program product for restricting a database access operation, comprising:

a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising;

instructions for applying a plurality of Bloom filters corresponding to a plurality of fields in a database to two or more terms in a record to produce a first plurality of outputs;

instructions for enabling an access operation to the database if the first plurality of outputs correspond to a positive result; and

instructions for returning a result from the access operation when the access operation is enabled.

19. The computer-program product of claim 16, wherein the record corresponds to a query.

20. The computer-program product of claim 19, further comprising:

instructions for identifying first and second subsets of the terms in the query;

instructions for applying a first Bloom filter in the plurality of Bloom filters to the first subset to produce a first output; and

instructions for applying a second Bloom filter in the plurality of Bloom filters to the second subset to produce a second output,

wherein enabling the access operation is further in accordance with the first output and the second output corresponding to the positive result.

21. The computer-program product of claim 19, further comprising:

instructions for identifying a plurality of subsets of the terms in the query; and

instructions for applying one or more of the Bloom filters to each of the subsets to produce a second plurality of outputs,

wherein enabling the access operation is further in accordance with the second plurality of outputs from the one or more Bloom filters corresponding to at least one of a plurality of success patterns.

22. The computer-program product of claim 19, further comprising:

instructions for applying a normalization operation to the query to produce a normalized set of terms; and

instructions for applying an additional Bloom filter to each of the terms in the normalized set of terms to produce an additional output;

wherein enabling the access operation is further in accordance with the additional output corresponding to the positive result.

23. The computer-program product of claim 16, further comprising

instructions for sorting the two or more terms in the record to produce a sorted record;

and

instructions for applying a first Bloom filter to the sorted record to produce a first output,

wherein enabling the access operation is further in accordance with the first output corresponding to the positive result.

24. The computer-program product of claim 16, further comprising:

instructions for parsing the terms in the record in a plurality of ways to produce a plurality of parsed sets of terms; and

instructions for applying at least two of the Bloom filters in the plurality of Bloom filters to the plurality of parsed sets of terms to produce a second plurality of outputs;

wherein enabling the access operation is further in accordance with the second plurality of outputs corresponding to the positive result.

25. The computer-program product of claim 24, wherein at least the two Bloom filters respectively correspond to an attribute field and a value field.

26. The computer-program product of claim 16, further comprising:

instructions for applying a first Bloom filter in the plurality of Bloom filters to a first term in the record to produce a first output;

instructions for sorting remaining terms in the record; and

instructions for applying a second Bloom filter in the plurality of Bloom filters to the sorted remaining terms in the record to produce a second output,

wherein enabling the access operation is further in accordance with the first output and the second output corresponding to the positive result, and wherein a first field corresponding to the first Bloom filter includes attributes and a second field corresponding to the second Bloom filter includes values.

17. A computer, comprising:

memory;

a processor; and

a program for restricting a database access operation, wherein the program is stored in the memory and executed by the processor, the program including;

instructions for applying a plurality of Bloom filters corresponding to a plurality of fields in a database to two or more terms in a record to produce a first plurality of outputs;

instructions for enabling an access operation to the database if the first plurality of outputs correspond to a positive result; and

instructions for returning a result from the access operation when the access operation is enabled.

27. The computer of claim 17, wherein the record corresponds to a query.

28. The computer of claim 27, further comprising:

instructions for identifying first and second subsets of the terms in the query;

instructions for applying a first Bloom filter in the plurality of Bloom filters to the first subset to produce a first output; and

instructions for applying a second Bloom filter in the plurality of Bloom filters to the second subset to produce a second output,

wherein enabling the access operation is further in accordance with the first output and the second output corresponding to the positive result.

29. The computer of claim 27, further comprising:

instructions for identifying a plurality of subsets of the terms in the query; and

instructions for applying one or more of the Bloom filters to each of the subsets to produce a second plurality of outputs,

wherein enabling the access operation is further in accordance with the second plurality of outputs from the one or more Bloom filters corresponding to at least one of a plurality of success patterns.

30. The computer of claim 27, further comprising:

instructions for applying a normalization operation to the query to produce a normalized set of terms; and

instructions for applying an additional Bloom filter to each of the terms in the normalized set of terms to produce an additional output;

wherein enabling the access operation is further in accordance with the additional output corresponding to the positive result.

31. The computer of claim 17, further comprising

instructions for sorting the two or more terms in the record to produce a sorted record;

and

instructions for applying a first Bloom filter to the sorted record to produce a first output,

wherein enabling the access operation is further in accordance with the first output corresponding to the positive result.

32. The computer of claim 17, further comprising:

instructions for parsing the terms in the record in a plurality of ways to produce a plurality of parsed sets of terms; and

instructions for applying at least two of the Bloom filters in the plurality of Bloom filters to the plurality of parsed sets of terms to produce a second plurality of outputs;

wherein enabling the access operation is further in accordance with the second plurality of outputs corresponding to the positive result.

33. The computer of claim 32, wherein at least the two Bloom filters respectively correspond to an attribute field and a value field.

34. The computer of claim 17, further comprising:

instructions for applying a first Bloom filter in the plurality of Bloom filters to a first term in the record to produce a first output;

instructions for sorting remaining terms in the record; and

instructions for applying a second Bloom filter in the plurality of Bloom filters to the sorted remaining terms in the record to produce a second output,

wherein enabling the access operation is further in accordance with the first output and the second output corresponding to the positive result, and wherein a first field corresponding to the first Bloom filter includes attributes and a second field corresponding to the second Bloom filter includes values.

18. A computer, comprising:

one or more processors;

a network interface;

memory; and

one or more signal lines for interconnecting the one or more processors, a network interface, and memory, wherein the computer includes;

means for applying a plurality of Bloom filters corresponding to a plurality of fields in a database to two or more terms in a record to produce a first plurality of outputs;

means for enabling an access operation to the database if the first plurality of outputs correspond to a positive result; and

means for returning a result from the access operation when the access operation is enabled.