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.

Other References

• Mullin, J.K. "Optimal Semijoins for Distributed Database Systems" IEEE Trans. on Software Engineering, vol. 16, No. 5, pp. 558-560, May 1990
• Gauthier, P., "Wide Area Information Retrieval" Masters Thesis, http:/http.cs.berkeley.edu/.apprxeq.gauthier/thesis/thesis.html, pp. 1-21, Oct. 1994
• Knuth, Donald E. The Art of Computer Programming,vol. 3: Sorting and Searching, Addison-Wesley Publishing Company, Inc. 1973, 561-562
• Bloom, Burton H., Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM 13, 7 (Jul. 1970), 422-42