Distributed, compressed Bloom filter Web cache server

Patent 6920477 Issued on July 19, 2005. Estimated Expiration Date:

April 6, 2021. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Data compression system and method with buffer control
Patent #: 4882754
Issued on: 11/21/1989
Inventor: Weaver, et al.

Method and system for proactive password validation
Patent #: 5394471
Issued on: 02/28/1995
Inventor: Ganesan, et al.

Method for compressing full text indexes with document identifiers and location offsets
Patent #: 5649183
Issued on: 07/15/1997
Inventor: Berkowitz, et al.

Parameterized bloom filters
Patent #: 5701464
Issued on: 12/23/1997
Inventor: Aucsmith

Prefetching to service multiple video streams from an integrated cached disk array
Patent #: 5737747
Issued on: 04/07/1998
Inventor: Vishlitzky, et al.

B tree structure and method
Patent #: 5813000
Issued on: 09/22/1998
Inventor: Furlani

Method for compressing full text indexes with document identifiers and location offsets
Patent #: 5832479
Issued on: 11/03/1998
Inventor: Berkowitz, et al.

System and method for maintaining a shared cache look-up table
Patent #: 5864854
Issued on: 01/26/1999
Inventor: Boyle

Compressed representation of a data base that permits AD HOC querying
Patent #: 5946692
Issued on: 08/31/1999
Inventor: Faloutsos, et al.

Compression protocol with multiple preset dictionaries
Patent #: 5953503
Issued on: 09/14/1999
Inventor: Mitzenmacher, et al.

More ...

Inventor

Mitzenmacher, Michael

Assignee

President and Fellows of Harvard College

Application

No. 09827557 filed on 04/06/2001

US Classes:

709/203, Client/server709/214, Plural shared memories709/216, Accessing another computer's memory709/218, Using interconnected networks709/246, COMPUTER-TO-COMPUTER DATA MODIFYING707/101, Manipulating data structure (e.g., compression, compaction, compilation)711/118, Caching711/113, Caching704/201For storage or transmission

Examiners

Primary: Knight, Anthony
Assistant: Pham, Thomas

Attorney, Agent or Firm

International Class

G06F015/16

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.

Other References

Fan et al. “Summary Cache: a Scalable Wide-area Web Cache Sharing Protocol,” Proceedings of SIGCOMM '98, (1998: pp. 254-265).
Bloom, “Space/time Trade-offs in Hash Coding with Allowable Errors,” Communication of the ACM (1970, 13 (7): pp. 422-426).
Carter et al. “Universal Classes of Hash Functions,” Journal of Computer and System Sciences, (1979: pp. 143-154).
Ramakrishna, “Practical Performance of Bloom Filters and Parallel Free-text Searching,” Communications of the ACM (1989, 32 (10): pp. 1237-1239).
Moffat et al., “Arithmetic Coding Revisited,” ACM Transactions on Information Systems, (1998, 16(3): pp. 256-294).
Witten et al., Managing Gigabytes, (1999: pp. 35-41).
Pai-Hsiang Hsiao, “Geographical Region Summary Service for Geographical Routing” (2000, submitted to Mobicom 2001).