Storage system for randomly named blocks of data

Details Storage system for randomly named blocks of data Storage system for randomly named blocks of data

2005-10-06

2008-11-25

Wu, Yicun (Department: 2169)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

07457813

ABSTRACT:
An index is constructed that is suitable for indexing a large set of records identified by randomly distributed record names and for answering membership queries about the set. The index has more than one level and the first-level index typically resides in RAM. Like a Bloom Filter, the first level index provides a non-membership indication with certainty and a membership indication with a controlled probability of error. Unlike a Bloom filter, entries in the first level index correspond uniquely to distinct records. Use is made of the statistical properties of a sorted list of random numbers in order to represent the first level index compactly.

REFERENCES:
patent: 3668647 (1972-06-01), Evangelisti et al.
patent: 4438522 (1984-03-01), Bluethgen
patent: 5450553 (1995-09-01), Kitagaki et al.
patent: 5717908 (1998-02-01), Dulong
patent: 5813008 (1998-09-01), Benson et al.
patent: 5870747 (1999-02-01), Sundaresan
patent: 5990810 (1999-11-01), Williams
patent: 6119133 (2000-09-01), Nusbickel et al.
patent: 6366900 (2002-04-01), Hu
patent: 6374266 (2002-04-01), Shnelvar
patent: 6470287 (2002-10-01), Smartt
patent: 6496830 (2002-12-01), Jenkins, Jr.
patent: 6499033 (2002-12-01), Vagnozzi
patent: 6625591 (2003-09-01), Vahalia et al.
patent: 6912645 (2005-06-01), Dorward et al.
patent: 7107416 (2006-09-01), Stuart et al.
patent: 2002/0038296 (2002-03-01), Margolus et al.
patent: 2002/0144057 (2002-10-01), Li et al.
patent: 2003/0046497 (2003-03-01), Dandrea
patent: 2003/0065652 (2003-04-01), Spacey
patent: 2003/0110356 (2003-06-01), Williams, III
patent: 2003/0135495 (2003-07-01), Vagnozzi
patent: 2003/0225974 (2003-12-01), Bopardikar et al.
patent: 2004/0024778 (2004-02-01), Cheo
patent: 2005/0055257 (2005-03-01), Senturk et al.
patent: 2005/0138031 (2005-06-01), Wefers
patent: 2005/0210028 (2005-09-01), Kodama
patent: 2005/0216669 (2005-09-01), Zhu et al.
patent: 01/61438 (2001-08-01), None
patent: 2004/074968 (2004-09-01), None
Burton H. Bloom in “Space/Time Tradeoffs in Hash Coding with Allowable Errors,” Communications of the ACM, Jul. 1970.
National Institute of Standards and Technology, NIST FIPS PUB 180-2, “Secure Hash Standard,” U.S. Department of Commerce, Aug. 2002.
Quinlan et al., “Venti: a new approach to archival storage,” in the Proceedings of the Conference on File and Storage Technologies (2002).
Witten et al., “Managing Gigabytes,” Morgan Kaufmann (1999).
Little et al., “Using Bloom Filters to Speed-Up Name Lookup in Distributed Systems,” Computer Journal Oxford University Press for British Comput. Soc UK, vol. 45, No. 6, pp. 645-652 (2002).

Affiliated with

Also associated with

Rating

Storage system for randomly named blocks of data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Storage system for randomly named blocks of data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Storage system for randomly named blocks of data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4022676