Searching for information utilizing a probabilistic detector

• US 20070078827A1
• Filed: 10/05/2005
• Published: 04/05/2007
• Est. Priority Date: 10/05/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Isard, Michael, Abadi, Martin, Sareen, Gaurav, Manasse, Mark
• Granted Patent: US 7,730,058 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3346 using probabilistic model

Abstract

A probabilistic detector is utilized to query a database. Utilization of a probabilistic detector provides assurance with 100 per cent probability that a search expression in the query is not in the database index. The probabilistic detector is implemented in the form of a Bloom filter. The probabilistic detector is created by hashing expressions in the database index and mapping the resulting hash values into the probabilistic detector. Upon receiving a query, expressions of the query are hashed. The probabilistic detector is queried using these hash values. If the results of querying the probabilistic detector indicate that searched for information may be in the database, the database is not queried. If the results of querying the probabilistic detector indicate that the information may be in the database, the database is queried for the information using the original query. This technique is advantageous in mitigating detrimental effects of denial of service attacks.

Claims

1. A method for searching for information, said method comprising:

receiving a request for information;

computing at least one hash value based on said request;

querying with said at least one hash value a first memory for an indication as to whether said information is in a second memory, said indication having an associated probability equal to approximately 100 per cent for an indication that said information is not in said second memory;

determining if said indication is indicative of said information being in said second memory; and

if said indication is indicative of said information being in said second memory, querying said second memory for said information.

2. A method in accordance with claim 1, wherein said first memory comprises a probabilistic detector, said method further comprising:

querying with said at least one hash value said probabilistic detector for said indication.

3. A method in accordance with claim 2, further comprising the act of creating said probabilistic detector.

4. A method in accordance with claim 3, said method further comprising:

computing at least one hash value based on information in said second memory; and

populating said probabilistic detector with each computed hash value based on said information in said second memory.

5. A method in accordance with claim 2, wherein said probabilistic detector comprises a Bloom filter.

6. A method in accordance with claim 1, said method further comprising:

responsive to receiving said request and prior to computing said at least one hash value, searching a third memory for an indication as to whether said information is in said second memory;

if a result of searching said third memory is indicative of said information being in said second memory and said information is in said third memory, providing said information from said third memory;

if said result of searching said third memory is indicative of said information being in said second memory and said information is not in said third memory, querying said second memory for said information; and

if said result of searching said third memory is indicative of said information not being in said second memory, forgoing a query of said second memory.

7. A method in accordance with claim 1, wherein said second memory comprises at least one database.

8. A system for searching for information, said system comprising:

an input/output portion for;

receiving a request for information, said request comprising at least one search expression; and

providing a query for said information;

a memory portion; and

a processor portion for;

computing at least one hash value from a received search expression of a request for information;

querying with said at least one hash value said memory portion for an indication as to whether said information is in an external memory, said indication having an associated probability equal to approximately 100 per cent for an indication that said information is not in said external memory;

determining if said indication is indicative of said information being in said external memory; and

if said indication is indicative of said information being in said external memory, querying via said input/output portion said external memory for said information.

9. A system in accordance with claim 8, wherein said external memory comprises at least one database.

10. A system in accordance with claim 8, wherein:

said memory portion comprises a probabilistic detector; and

said processor portion is capable of querying with said hash value said probabilistic detector for said indication.

11. A system in accordance with claim 8, said processor portion further for creating said probabilistic detector.

12. A system in accordance with claim 11, said processor portion further for:

creating at least one hash value based on information in said external memory; and

populating said probabilistic detector with each created hash value.

13. A system in accordance with claim 8, wherein said probabilistic detector comprises a Bloom filter.

14. A system in accordance with claim 8, said processor portion further for:

prior to computing said at least one hash value, searching a cache portion of said memory portion for an indication as to whether said information is in said external memory;

if a result of searching said cache portion is indicative of said information being in said second memory and said information is in said cache portion, providing said information from said cache portion;

if said result of searching said cache portion is indicative of said information being in said second memory and said information is not in said cache portion, querying said second memory for said information; and

if said result of searching said cache portion is indicative of said information not being in said second memory, forgoing a query of said second memory.

15. A computer-readable medium having computer-executable instructions for performing the acts of:

receiving a request for information, said request comprising at least one search expression;

computing at least one hash value from said at least one search expression;

querying with said at least one hash value a probabilistic detector for an indication as to whether said information is in a first memory, said indication having an associated probability equal to approximately 100 per cent for an indication that said information is not in said first memory;

responsive to a result of said query, performing one of;

querying said first memory for said information; and

determining that said information is not in said first memory;

16. A computer-readable medium in accordance with claim 15, said computer-readable medium having further computer-executable instructions for creating said probabilistic detector.

17. A computer-readable medium in accordance with claim 16, wherein said act of creating comprises the acts of:

computing at least one hash value from at least one expression in said first memory; and

populating said probabilistic detector with each computed hash value from said at least one expression in said first memory.

18. A computer-readable medium in accordance with claim 16, wherein said probabilistic detector comprises a Bloom filter.

19. A computer-readable medium in accordance with claim 15, said computer-readable medium having further computer-executable instructions for:

responsive to receiving said request for information, searching a second memory for an indication as to whether said information is in said first memory.

20. A computer-readable medium in accordance with claim 19, said computer-readable medium having further computer-executable instructions for:

if searching said second memory results in an indication that said information is in said first memory and said information is in said second memory, providing said information from said second memory;

if searching said second memory results in an indication that said information in said first memory and said information is not in said second memory, querying said first memory for said information; and

if searching said second memory results in an indication that said information is not in said first memory, forgoing a query of said first memory.