Michael A Sclafani

US Patent:

20060112112, May 25, 2006

Filed:

Oct 6, 2005

Appl. No.:

11/246897

Inventors:

Norman Margolus - Cambridge MA, US
Edwin Olson - Cambridge MA, US
Michael Sclafani - Somerville MA, US
J. Coburn - Cambridge MA, US
Michael Fortson - Cambridge MA, US

International Classification:

G06F 7/00

US Classification:

707100000

Abstract:

A method for constructing an index suitable for indexing a large set of records identified by long generally randomly distributed record names, and for answering membership queries about the set, the method comprising adding a new record to the set and assigning the new record a new record name using a process designed to produce names where at least a portion of each name is at least approximately random, determining that the new record name is not already represented in the index by checking a first level index, combining the new record name with record name information already represented in the index to form a combined record name which is shorter than the new record name, and adding the combined record name to the first level index to form a new first level index entry that represents the new record, wherein the first level index does not contain information sufficient to conclude that the new record name has been added to the index, wherein each different record in the set is assigned a different record name, wherein at least a portion of the first level index is ordered based on record names.

US Patent:

20060116990, Jun 1, 2006

Filed:

Oct 6, 2005

Appl. No.:

11/246004

Inventors:

Norman Margolus - Cambridge MA, US
Edwin Olson - Cambridge MA, US
Michael Sclafani - Somerville MA, US
J. Coburn - Cambridge MA, US
Michael Fortson - Cambridge MA, US

International Classification:

G06F 17/30

US Classification:

707003000

Abstract:

A method for constructing an index suitable for indexing a large set of records identified by long generally randomly distributed record names, and for answering membership queries about the set, the method comprising adding a new record to the set and assigning the new record a new record name using a process designed to produce names where at least a portion of each name is at least approximately random, determining that the new record name is not already represented in the index by checking a first level index that does not contain information sufficient to reconstruct the complete record names of records that have already been added to the index, abbreviating the new record name to form a new abbreviated name that is shorter than the new record name but that is sufficient to distinguish it from record names already represented in the index, combining the new abbreviated name with an abbreviated name of a record already represented in the first level index, to form a combined record name which is shorter than either of the abbreviated names that were combined, adding the combined record name to the first level index to form a new first level index entry that represents the new record, adding a new entry to a second level index that includes the complete new record name or enough information to reconstruct it, determining that a queried record name is already represented in the index by first determining that the queried record name is represented by the new first level index entry and then determining that the queried record name is represented by the new second level index entry, wherein each different record in the set is assigned a different record name, wherein each different record in the set has a different entry in the first level index, wherein at least a portion of the first level index is ordered based on abbreviated record names.