Distributed, compressed Bloom filter Web cache server

• US 20030005036A1
• Filed: 04/06/2001
• Published: 01/02/2003
• Est. Priority Date: 04/06/2001
• Status: Active Grant

• Current Assignee: Harvard University, Breed Automotive Technology, Inc. (Ningbo Junsheng Investment Group Co., Ltd.)
• Original Assignee: Breed Automotive Technology, Inc. (Ningbo Junsheng Investment Group Co., Ltd.)
• Inventors: Mitzenmacher, Michael
• Granted Patent: US 6,920,477 B2
• Time in Patent Office: Days
• US Class Current: 709/203
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Compressed Bloom filters that act as a message as well as a data structure provide smaller false positive rates, reduced bits broadcast and/or reduced computational overhead in distributed Web proxy servers and other distributed networks.

Claims

1. A distributed, compressed bloom filter Web server providing reduced probabilities of false positives, comprising:

a plurality of cache servers each having a cache memory and a cache processor coupled to the memory that is operative (1) to represent Web objects stored in its cache memory as a compressed Bloom filter data array having a preselected number of hash functions and a preselected array size which have been chosen to minimize the rate of false positives for a preselected transmission compression size, (2) to compress the Bloom filter data array to said transmission compression size, and (3) to periodically disseminate the compressed Bloom filter data array to neighboring servers when there is a change in its stored Web objects.

2. The distributed, compressed Bloom filter Web server providing reduced probabilities of false positives of claim 1 wherein the Bloom filter data array size is made as large as possible for a given cache memory size and the number of hash functions is chosen to minimize the rate of false positives for a preselected transmission compression size.

3. The distributed, compressed Bloom filter Web server providing reduced probabilities of false positives of claim 1, wherein arithmetic coding is employed to compress the Bloom filter data array to said transmission compression size.

4. The distributed, compressed Bloom filter Web server providing reduced probabilities of false positives of claim 1, wherein said cache processor is further operative to store in its cache memory at least one other decompressed Bloom filter data array each representative of the Web objects of another, at least one neighboring Web server.

7. The distributed computer network of claim 1, wherein said nodes are Web proxy servers.

8. The distributed computer network of claim 1, wherein said nodes are mobile or stationary agents in a network of mobile nodes, and the Web objects correspond to agent locations.

9. The distributed computer network of claim 1, wherein said predetermined compression algorithm is arithmetic coding.

5. A method reducing false positives in a network having distributed Web servers each storing information in cache memory as a Bloom filter data array representative of the information in its cache memory and broadcasting that data array to other Web servers periodically, comprising:

1) fixing a compression size for transmission of the Bloom filter data array at each Web server;

(2) choosing the number of hash functions and the array size so that the Bloom filter data array minimizes the rate of false positives when it is compressed down to the fixed compression size; and

(3) broadcasting the compressed Bloom filter data array of the fixed compression size to neighboring Web servers whenever there is a change in the contents of its cache memory.

6. A distributed computer network, comprising:

a plurality of periodically intercommunicating distributed network nodes;

each node including a cache memory and a processor coupled to the cache memory operative to (1) represent its memory contents as a compressed Bloom filter data structure having a preselected number of hash functions and a preselected array size which have been chosen for a target compression size to optimize at least one of the rate of false positives of the Bloom filter representing the memory contents and the computational requirements of the preselected number of hash functions, to (2) compress the Bloom filter data structure to the target compression size using a predetermined compression algorithm, and to (3) broadcast the compressed Bloom filter data structure to at least one other node whenever the contents of its cache memory has changed.

10. A method employing compressed Bloom filters for storing and transmitting data in a distributed network of nodes each having a processor coupled to a memory, comprising:

representing the data contents of a memory of a node as a compressed Bloom filter data structure stored in memory of a node having a preselected number of hash functions and a preselected array size which have been chosen to optimize at least one of the rate of false positives of the Bloom filter representing the data contents and the computational requirements of the preselected number of hash functions for a transmission compression size;

compressing the Bloom filter data structure to the transmission compression size; and

periodically transmitting the compressed Bloom filter data structure to at least one other node.

11. A method of storing data in memory for transmission, comprising:

representing the data as a compressed Bloom filter data structure in said memory having a preselected number of hash functions and a preselected array size which have been chosen for a target transmission compression size to optimize at least one of the rate of false positives of the Bloom filter representing the data and the computational requirements of the preselected number of hash functions.

13. The distributed computer network of claim 12, wherein said nodes are Web proxy servers.

14. The distributed computer network of claim 12, wherein said nodes are mobile or stationary agents in a network of mobile nodes, and the Web objects correspond to agent locations.

15. The distributed computer network of claim 12, wherein said predetermined compression algorithm is arithmetic coding.

12. A distributed computer network, comprising:

a plurality of periodically intercommunicating distributed network nodes;

each node including a cache memory and a processor coupled to the cache memory operative to (1) represent its memory contents as a compressed Bloom filter data structure having a preselected number of hash functions and a preselected array size which have been chosen for a target rate of false positives to optimize at least one of the compression size of the Bloom filter representing the memory contents and the computational requirements of the preselected number of hash functions, to (2) compress the Bloom filter data structure to the target compression size using a predetermined compression algorithm, and to (3) broadcast the compressed Bloom filter data structure to at least one other node whenever the contents of its cache memory has changed.

16. A method employing compressed Bloom filters for storing and transmitting data in a distributed network of nodes each having a processor coupled to a memory, comprising:

representing the data contents of a memory of a node as a compressed Bloom filter data structure stored in memory of a node having a preselected number of hash functions and a preselected array size which have been chosen to optimize at least one of the transmission compression size of the Bloom filter representing the data contents and the computational requirements of the preselected number of hash functions for a given rate of false positives;

compressing the Bloom filter data structure to the transmission compression size; and

periodically transmitting the compressed Bloom filter data structure to at least one other node.

17. A method of storing data in memory for transmission, comprising:

representing the data as a compressed Bloom filter data structure in said memory having a preselected number of hash functions and a preselected array size which have been chosen for a target rate of false positives to optimize at least one of the transmission compression size of the Bloom filter representing the data and the computational requirements of the preselected number of hash functions.