Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2006-03-10
2011-11-01
Dudek, Jr., Edward J (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C707S747000
Reexamination Certificate
active
08051252
ABSTRACT:
Method and apparatus for rapidly determining whether a particular subblock of data is present in a reduced-redundancy storage system. An aspect of the invention achieves this by hashing each subblock in the storage system into a bitfilter that contains a ‘1’ bit for each position to which at least one subblock hashes. This bitfilter provides an extremely fast way to determine whether a subblock is in the storage system. In a further aspect of the invention, index entries for new subblocks may be buffered in a subblock index write buffer so as to convert a large number of random access read and write operations into a single sequential read and a single sequential write operation. The combination of the bitfilter and the write buffer yields a reduced-redundancy storage system that uses significantly less high speed random access memory than is used by systems that store the entire subblock index in memory.
REFERENCES:
patent: 5463389 (1995-10-01), Klaymen
patent: 5689567 (1997-11-01), Miyauchi
patent: 5742811 (1998-04-01), Agrawal et al.
patent: 5829018 (1998-10-01), Moertl et al.
patent: 5842196 (1998-11-01), Agarwal et al.
patent: 5860153 (1999-01-01), Matena et al.
patent: 5940841 (1999-08-01), Schmuck et al.
patent: 5990810 (1999-11-01), Williams
patent: 6292795 (2001-09-01), Peters et al.
patent: 6374266 (2002-04-01), Shnelvar
patent: 6407679 (2002-06-01), Evans et al.
patent: 6438562 (2002-08-01), Gupta et al.
patent: 6505206 (2003-01-01), Tikkenen et al.
patent: 6594665 (2003-07-01), Sowa et al.
patent: 6704730 (2004-03-01), Moulton et al.
patent: 6754799 (2004-06-01), Frank
patent: 6757686 (2004-07-01), Syeda-Mahmood et al.
patent: 6959384 (2005-10-01), Serret-Avila
patent: 2003/0009482 (2003-01-01), Benerjee
patent: 2003/0018878 (2003-01-01), Dorward et al.
patent: 2003/0093645 (2003-05-01), Wong et al.
patent: 2004/0064737 (2004-04-01), Milliken
patent: 2006/0271540 (2006-11-01), Williams
patent: 2006/0282457 (2006-12-01), Williams
Nelson, Mark, “Arithmetic Coding + Statistical Modeling = Data Compression”, Feb. 1991.
Madden, Sam, “Good things come in small packages: The advantage of compression in column databases”, Sep. 2007.
Langdon, G.G., Rissanen, J.J., “Compression of Black-White Images with Arithmetic Coding.” IEEE Transactions on Communications (1981), 29(6), pp. 858-867.
Madden, Sam, “Good Things Come in Small Packages: The Advantage of Compression in column Databases.” The Database Column (Sep. 11, 2007), pp. 1-5.
Nelson, Mark, “Arithmetic Coding + Statistical Modeling=Data Compression.” Dr. Dobb's Journal (Feb. 1991), pp. 1-12.
Tanaka, Hatsukazu, Leon-Garcia, Alberto, “Efficient Run-Length Encodings.” IEEE Transactions on Information Theory (Nov. 1982), 28(6), pp. 880-890.
Ramabhadran, Sriram, et al., “Prefix Hash Tree an Indexing Data Structure over Distributed Hash Tables,” Jan. 2004. http://www.icsi.berkeley.edu/cgi-bin/pubs/publication.pl?ID=000071.
Dynamic Hash Tables, Per-Ake Larson, Apr. 1988, vol. 31 No. 4.
Hash Table Methods, W.D. Maurer and T.G. Lewis, Computing Surveys, vol. 7 No. 1, Mar. 1975.
Williams, Dan and Sirer, Emin, “Optimal Parameter Selection for Efficient Memory Integrity Verification Using Merkle Hash Trees”, NCA (2004).
Litwin, Witold, “Linear Hashing: A New Tool for File and Table Addresses.” IEEE, (1980).
Nilsson, Stefan and Tikkanen, Matti, “Implementing a Dynamic Compressed Trie.” (1998).
European Search Report from co-pending European Application No. 06705001.3 having date of Sep. 17, 2010—7 pgs.
Garcia-Molina, et al.: “Database Systems: The Complete Book”, 2002, XP002599408, ISBN 0130980439—14 pgs.
LandOfFree
Method and apparatus for detecting the presence of subblocks... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for detecting the presence of subblocks..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for detecting the presence of subblocks... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4266316