Method and apparatus for monitoring a data stream

1. A method for using a computer to determine whether a data element exists within a set of data elements observed from a stream of data, comprising:

storing a value representing the data element in an enhanced Bloom filter that includes multiple instances of a Bloom filter when the data element is observed in the stream of data in a time interval, wherein each instance of the Bloom filter is associated with a different time interval, and wherein storing the value representing the data element comprises storing the value in two or more of the multiple instances associated with two or more consecutive time intervals to indicate that the data element was observed;

in response to receiving a query that seeks to determine whether the data element was observed in the stream of data, performing a lookup in the enhanced Bloom filter to determine whether the value representing the data element is present in the enhanced Bloom filter; and

because the value representing the data element is present in the enhanced Bloom filter, generating a notification that the data element was observed.

2. The method of claim 1 , wherein the method further comprises clearing an instance of a Bloom filter associated with a preceding time interval which causes the enhanced Bloom filter to forget information associated with the preceding time interval.

3. The method of claim 2 , wherein prior to clearing the instance of the Bloom filter associated with a preceding time interval, the method further comprises storing the instance of the Bloom filter to a storage device.

4. The method of claim 1 , wherein if the number of time intervals to be recorded exceeds the number of Bloom filter instances in the enhanced Bloom filter, the Bloom filter instance associated with the oldest time interval is cleared and is associated with the current time interval.

5. The method of claim 1 , wherein the stream of data is a stream of network packets.

6. The method of claim 1 ,

wherein the stream of data is a stream of stock market transaction data, which includes timestamps; and

wherein the method is used to determine whether a stock or a derivative of a stock was traded during a specified time period.

7. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for determining whether a data element exists within a set of data elements observed from a stream of data, wherein the method comprises:

storing a value representing the data element in an enhanced Bloom filter that includes multiple instances of a Bloom filter when the data element is observed in the stream of data in a time interval, wherein each instance of the Bloom filter is associated with a different time interval, and wherein storing the value representing the data element comprises storing the value in two or more of the multiple instances associated with two or more consecutive time intervals to indicate that the given data element was observed;

in response to receiving a query that seeks to determine whether the data element was observed in the stream of data, performing a lookup in the enhanced Bloom filter to determine whether the value representing the data element is present in the enhanced Bloom filter; and

because the value representing the data element is present in the enhanced Bloom filter, generating a notification that the data element was observed.

8. The computer-readable storage medium of claim 7 , wherein the method further comprises clearing an instance of a Bloom filter associated with a preceding time interval which causes the enhanced Bloom filter to forget information associated with the preceding time interval.

9. The computer-readable storage medium of claim 8 , wherein prior to clearing the instance of the Bloom filter associated with a preceding time interval, the method further comprises storing the instance of the Bloom filter to a storage device.

10. The computer-readable storage medium of claim 7 , wherein if the number of time intervals to be recorded exceeds the number of Bloom filter instances in the enhanced Bloom filter, the Bloom filter instance associated with the oldest time interval is cleared and is associated with the current time interval.

11. The computer-readable storage medium of claim 7 , wherein the stream of data is a stream of network packets.

12. The computer-readable storage medium of claim 7 ,

wherein the stream of data is a stream of stock market transaction data, which includes timestamps; and

wherein the method is used to determine whether a stock or a derivative of a stock was traded during a specified time period.

13. An apparatus that determines whether a data element is within a set of data elements observed from a stream of data, comprising:

a memory; and

a data monitoring mechanism configured to:

store a value representing the data element in an enhanced Bloom filter that includes multiple instances of a Bloom filter when the data element is observed in the stream of data in a time interval, wherein each instance of the Bloom filter is associated with a different time interval, and wherein storing the value representing the data element comprises storing the value in two or more of the multiple instances associated with two or more consecutive time intervals to indicate that the data element was observed;

in response to receiving a query that seeks to determine whether the data element was observed in the stream of data, perform a lookup in the enhanced Bloom filter to determine whether the value representing the data element is present in the enhanced Bloom filter; and

because the value representing the data element is present in the enhanced Bloom filter, generate a notification that the data element was observed.

14. The method of claim 1 , wherein storing the value in two or more of the multiple instances comprises marking all but one of the multiple instances.