Patent ID: 7457813

Claim:
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 that 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 a portion of the first level index where the new first level index entry is added is ordered based on record names; wherein the combining step depends both on the new record name and at least a portion of a record name already represented in the portion of the first level index where the new first level index entry is added; wherein the combining step determines a portion of the new record name that is sufficient to uniquely distinguish it from record names already represented in the index; and wherein entries in the first level index are constructed to be uniquely associated with distinct record names.