Patent ID: 8055633

Claim:
A method of duplicate detection for data items in a stream of data items, the method comprising: receiving a data item from the stream of data items; applying at least two different hashing algorithms to the data item to generate hash keys that identify elements in a first bloom filter data structure having a plurality of elements; checking a state of each of the identified elements to determine whether the data item is a potential duplicate, the determination depending on whether the identified elements are indicated as having been also identified for a previous data item received from the stream; in response to the determination that the data item is a potential duplicate, checking an index of hash keys to determine if at least one of the generated hash keys exists in the index to identify the data item as an actual duplicate; in response to determining that at least one of the generated hash keys exists in the index, identifying the data item as an actual duplicate; in response to a determination that a predetermined criterion is satisfied, a second bloom filter data structure is generated and the generated hash keys identify elements in both the first and second bloom filter data structures, and the determination that the data item is a potential duplicate depends on whether the identified elements are indicated as having been also identified for a previous data item received from the stream in any of the first and second bloom filter data structures; in response to a determination that the data item is not one of an actual duplicate, adding at least one of the generated hash keys to the index of hash keys and indicating, in the bloom filter data structure, that the identified elements have been identified for the data item; and wherein the first bloom filter data structure is discardable after a predetermined time period.