Parameterized bloom filters

Details Parameterized bloom filters Parameterized bloom filters

1995-09-15

1997-12-23

Black, Thomas G.

395602, G06F 1730

Patent

active

057014647

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.

REFERENCES:
patent: 5394471 (1995-02-01), Ganesan et al.
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-426.

Affiliated with

Also associated with

Rating

Parameterized bloom filters does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Parameterized bloom filters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized bloom filters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1808021