Parameterized bloom filters
First Claim
1. A method in a first computer system of determining validity of a key comprising:
- a. updating a bloom filter at periodic intervals by;
i. providing said first computer system'"'"'s requirements of said bloom filter to a second computer system, said second computer system having access to an invalidity database which includes all invalid keys; and
ii. receiving bloom vectors and coefficients which comprise said bloom filter from said second computer system;
b. accepting said key; and
c. applying said bloom filter to said key to determine if said key is present in said invalidity database.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for determining validity of a key. A bloom filter is updated in a first computer system (e.g. a client system) at periodic intervals by providing the system'"'"'s requirements of the bloom filter to a second computer system (e.g. a server system). These requirements may include: a number of bits which are included in the bloom vectors; a number of the coefficients for hash functions of the bloom filter; or an error value indicating the possibility of error of the bloom filter. The second computer system has access to an invalidity database which includes all invalid keys and can generate a matrix of bloom vectors and coefficients for different client requirements. Responsive to the provision of the first system'"'"'s requirements, it receives bloom vectors and coefficients which comprise the bloom filter. The system can then accept a key and apply the bloom filter to the key to determine if the key is present in the invalidity database. Invalidity of the key can be confirmed if the bloom filter indicates that the key is present in the invalidity database by transmitting the key to the second computer system to determine the presence of the key in the invalidity database. In this way, communications bandwidth is conserved because no communication between the first computer system and the second computer system need take place if the bloom filter indicates that the key is not present in the invalidity database.
172 Citations
26 Claims
-
1. A method in a first computer system of determining validity of a key comprising:
-
a. updating a bloom filter at periodic intervals by; i. providing said first computer system'"'"'s requirements of said bloom filter to a second computer system, said second computer system having access to an invalidity database which includes all invalid keys; and ii. receiving bloom vectors and coefficients which comprise said bloom filter from said second computer system; b. accepting said key; and c. applying said bloom filter to said key to determine if said key is present in said invalidity database. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. An apparatus in a first computer system for determining validity of a key comprising:
-
a. a first circuit for updating a bloom filter at periodic intervals by; i. providing said first computer system'"'"'s requirements of said bloom filter to a second computer system, said second computer system having access to an invalidity database which includes all invalid keys; and ii. receiving bloom vectors and coefficients which comprise said bloom filter from said second computer system; b. a second circuit for accepting said key; and c. a third circuit for applying said bloom filter to said key to determine if said key is present in said invalidity database. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A method in a client of determining database membership of a key stored in a server comprising the following steps:
-
a. accepting said key; b. determining whether a bloom filter stored in said client is current, and if not, performing the following steps; i. providing parameters of said bloom filter to said server according to requirements of said client and requesting said bloom filter from said server; ii. receiving a bloom vector which comprises said bloom filter; and iii. receiving coefficients which comprise said bloom filter; c. determining whether said bloom filter of said key matches said bloom vector; d. if said bloom filter of said key does not match said bloom vector then indicating that said key is not a member of said database. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
-
22. A validity detection system comprising:
-
a. a key input circuit for accepting a key; b. a bloom filter coupled to said key input circuit for determining validity of said key, said bloom filter generating a valid signal if said key is not present in an invalidity database, said bloom filter generating an invalid signal if said key may be present in said invalidity database; c. a key invalidity confirmation circuit coupled to said bloom filter for confirming invalidity of said key if said bloom filter generates said invalid signal, said key invalidity confirmation circuit including; i. a key transmission circuit for transmitting said key to a server having said invalidity database; ii. a reception circuit for receiving a result signal indicating whether said key is present in said invalidity database; d. a bloom filter update circuit coupled to said bloom filter which is operative at periodic intervals for updating said bloom filter, said bloom filter update circuit including; i. a parameter provision circuit for providing client requirements of said bloom filter to said server; ii. a bloom vector reception circuit for receiving bloom vectors which comprise said bloom filter; iii. a coefficient reception circuit for receiving coefficients which comprise said bloom filter; and iv. a bloom filter request circuit for requesting said bloom vectors and said coefficients from said server according to said client requirements. - View Dependent Claims (23, 24, 25, 26)
-
Specification