Searching for information utilizing a probabilistic detector
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.
1. A method for mitigating denial of service attacks against and improving performance of an Internet search system, said method comprising:
receiving a request for information;
searching, with said request instead of a hash value based on said request, a first memory for an indication as to whether said information is in a second memory, wherein said first memory stores previous requests for information;
if a result of searching said first memory is indicative of said information being in said second memory and said information is in said first memory, providing said information from said first memory;
if said result of searching said first memory is indicative of said information being in said second memory and said information is not in said first memory, querying said second memory, with said request, for said information;
if said result of searching said first memory is indicative of said information not being in said second memory, forgoing a query of said second memory;
if on a condition that said result of searching said first memory is indicative of said request not being in said first memory:
computing at least one hash value based on said request;
querying with said at least one hash value a probabilistic detector, wherein said probabilistic detector is populated with at least one computed hash value based on each expression in an index of said second memory, for an indication as to whether said information is in said second memory;
determining if said queried for indication is indicative of said information being in said second memory; and
if said queried for indication is indicative of said information being in said second memory, querying with said request, and not with the at least one hash value based on said request, said second memory for said information.
2. A method in accordance with claim 1 , further comprising the act of creating said probabilistic detector.
3. A method in accordance with claim 1 , wherein said probabilistic detector comprises a Bloom filter.
4. A method in accordance with claim 1 , wherein said first memory comprises local memory.
5. A method in accordance with claim 1 , wherein said second memory comprises a plurality of distributed databases.
6. A system for mitigating denial of service attacks against and improving performance of an Internet search system, said system comprising:
an input/output portion for:
receiving a request for information, said request comprising at least one search expression; and
a memory portion, wherein said memory portion stores previous requests for information; and
a processor portion for:
searching, with said at least one search expression instead of a hash value based on said at least one search expression, said memory portion for an indication as to whether said information is in external memory;
if a result of searching said memory portion is indicative of said information being in said external memory and said information is in said memory portion, providing said information from said memory portion;
if said result of searching said memory portion is indicative of said information being in said external memory and said information is not in said memory portion, querying with said at least one search expression via said input/output portion said external memory for said information; and
if said result of searching said memory portion is indicative of said information not being in said external memory, forgoing a query of said external memory;
if on a condition that said result of searching said memory portion is indicative of said at least one search expression not being in said memory portion:
computing at least one hash value based on said at least one search expression;
querying with said at least one hash value a probabilistic detector, wherein said probabilistic detector is populated with at least one computed hash value based on each expression in an index of said external memory, for an indication as to whether said information is in said external memory;
determining if said queried for indication is indicative of said information being in said external memory; and
if said queried for indication is indicative of said information being in said external memory, querying with said at least one search expression, and not with the at least one hash value based on said at least one search expression, said external memory for said information.
7. A system in accordance with claim 6 , wherein said external memory comprises at least one database.
8. A system in accordance with claim 6 , wherein:
said memory portion comprises a probabilistic detector; and
said processor portion is capable of querying with said at least one hash value said probabilistic detector for said indication.
9. A system in accordance with claim 8 , said processor portion further for creating said probabilistic detector.
10. A system in accordance with claim 8 , wherein said probabilistic detector comprises a Bloom filter.
11. A system in accordance with claim 6 , wherein said memory portion comprises local memory.
12. A computer-readable storage medium having computer-executable instructions for performing a method useful to counter denial of service attacks against and improve performance of an Internet search system comprising the acts of:
receiving a request for information, said request comprising at least one search expression;
responsive to receiving said request for information, searching, with said at least one search expression instead of a hash value based on said at least one search expression, a first memory for an indication as to whether said information is in a second memory, wherein said first memory stores previous requests for information;
if searching said first memory results in an indication that said information is in said second memory and said information is in said first memory, providing said information from said first memory;
if searching said first memory results in an indication that said information in said second memory and said information is not in said first memory, querying with said at least one search expression said second memory for said information; and
if searching said first memory results in an indication that said information is not in said second memory, forgoing a query of said second memory;
if on a condition that said result of searching said first memory is indicative of said at least one search expression not being in said first memory:
computing at least one hash value based on said at least one search expression;
querying with said at least one hash value a probabilistic detector, wherein said probabilistic detector is populated with at least one computed hash value based on each expression in an index of said second memory, for an indication as to whether said information is in said second memory;
determining if said queried for indication is indicative of said information being in said second memory; and
if said queried for indication is indicative of said information being in said second memory, querying with said at least one search expression, and not with the at least one hash value based on said at least one search expression, said second memory for said information.
13. A computer-readable storage medium in accordance with claim 12 , said computer-readable medium having further computer-executable instructions for creating said probabilistic detector.
14. A computer-readable storage medium in accordance with claim 13 , wherein said probabilistic detector comprises a Bloom filter.
15. A computer-readable storage medium in accordance with claim 12 , wherein said first memory comprises non-volatile memory.
16. A computer-readable storage medium in accordance with claim 15 , wherein said probabilistic detector is stored in distributed memory.