Parameterized bloom filters

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.

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.

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.