Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2003-06-30
2008-09-09
Mofiz, Apu (Department: 2161)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
07424498
ABSTRACT:
A method and apparatus for different embodiments of probabilistic summary data structure based encoding for garbage collection are described. In one embodiment, a method comprises generating a probabilistic summary data structure that represents active blocks of data within a storage device based on identifications of the active blocks or the data within the active blocks. The method also includes performing garbage collection of at least a portion of the storage device based on the probabilistic summary data structure.
REFERENCES:
patent: 4714992 (1987-12-01), Gladney et al.
patent: 5619693 (1997-04-01), Troisi
patent: 5774588 (1998-06-01), Li
patent: 5920875 (1999-07-01), Clark et al.
patent: 5963962 (1999-10-01), Hitz et al.
patent: 5966708 (1999-10-01), Clark et al.
patent: 5990810 (1999-11-01), Williams
patent: 6073160 (2000-06-01), Grantham et al.
patent: 6173293 (2001-01-01), Thekkath et al.
patent: 6249792 (2001-06-01), Zwilling et al.
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6343834 (2002-02-01), Wurmlinger
patent: 6480862 (2002-11-01), Gall
patent: 6594678 (2003-07-01), Stoutamire et al.
patent: 6868488 (2005-03-01), Garthwaite
patent: 2001/0037323 (2001-11-01), Moulton et al.
patent: 2002/0038304 (2002-03-01), Gelfand
patent: 2003/0208500 (2003-11-01), Daynes et al.
A.Z. Broder, “Some Applications of Rabin's Fingerprinting Method.”, In Sequences II: Methods in Communication, Security, and Computer Science, Springer-Verlag, 1993 (10pg).
U. Manber, “Finding Similar Files in A Large File System.” USENIX Conference, 1994 (11pg).
A. Muthitacharoen, B. Chen, and D. Mazieres. “A low-bandwidth network file system.” ACM SOSP Conference, 2001 (14pg).
S. Quinlan and S. Dorward, “Venti: a new approach to archival storage”, USENIX FAST conference, 2002. (14pg).
Bloom Filter, National Institute of Standards and Technology, (1pg); Bloom Filters Short Tutorial (5 pgs); Flip Code—Tutorial—Coding Bloom Filters (6 pgs) dated Nov. 2, 2002.
Proceedings of the FAST 2002 Conference on File and Storage Technologies, USENIX Association; Monterey, California USA, Jan. 28-30, 2002 (13 pgs).
Microsoft, Microsoft Computer Dictionary 2002, Microsoft Press, 5thed.
Chilimbi, et al., Using Generational Garbage Collection to Implement Cache-Concious Data Placement, 1998, ACM.
Chilimbi, et al., Cache-Concious Structure Layout, 1999 ACM.
Menon, et al., An Age-Threshold Algorithm for Garbage Collection in Log-Structured Arrays and File Systems.
Menon, Jai, A Performance Comparison of RAID-5 and Log-Structured Arrays, 1995 IEEE.
Blakely , Sokoloff, Taylor & Zafman LLP
Data Domain, Inc.
Mofiz Apu
Stace Brent
LandOfFree
Probabilistic summary data structure based encoding for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Probabilistic summary data structure based encoding for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic summary data structure based encoding for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3985229