Method and apparatus for monitoring a data stream

• US 20080071903A1
• Filed: 09/19/2006
• Published: 03/20/2008
• Est. Priority Date: 09/19/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Schuba, Christoph L., Stern, Hal L.
• Granted Patent: US 8,260,909 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 43/18 Protocol analysers

Abstract

A system that determines whether a data element exists within a set of data elements observed from a stream of data. During operation, the system receives a query which seeks to determine whether the data element exists within a set of data elements observed from a stream of data. In response to the query, the system performs a lookup in an enhanced Bloom filter to determine whether the pattern of data elements was observed in the stream of data, wherein the enhanced Bloom filter includes multiple instances of a Bloom filter, and wherein each instance of the Bloom filter is associated with a different time interval. If so, the system generates a notification that the data element was observed.

Claims

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

receiving a query which seeks to determine whether the data element exists within a set of data elements observed from a stream of data;

in response to the query, performing a lookup in an enhanced Bloom filter to determine whether the pattern of data elements was observed in the stream of data, wherein the enhanced Bloom filter includes multiple instances of a Bloom filter, and wherein each instance of the Bloom filter is associated with a different time interval; and

if so, generating a notification that the data element was observed.

2. The method of claim 1, wherein prior to receiving the query, the method further comprises:

observing the stream of data; and

storing data elements observed in the stream of data in the enhanced Bloom filter.

3. The method of claim 1, wherein storing a given data element in the enhanced Bloom filter involves marking multiple instances of the enhanced Bloom filter which is associated with multiple consecutive time intervals to indicate that the given data element was observed.

4. The method of claim 1, wherein storing a given data element in the enhanced Bloom filter involves marking a single instance of the enhanced Bloom filter associated with a current time interval to indicate that the given data element was observed.

5. 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.

6. The method of claim 5, 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.

7. 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.

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

9. 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.

10. A 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:

receiving a query which seeks to determine whether the data element exists within a set of data elements observed from a stream of data;

in response to the query, performing a lookup in an enhanced Bloom filter to determine whether the pattern of data elements was observed in the stream of data, wherein the enhanced Bloom filter includes multiple instances of a Bloom filter, and wherein each instance of the Bloom filter is associated with a different time interval; and

if so, generating a notification that the data element was observed.

11. The computer-readable storage medium of claim 10, wherein prior to receiving the query, the method further comprises:

observing the stream of data; and

storing data elements observed in the stream of data in the enhanced Bloom filter.

12. The computer-readable storage medium of claim 10, wherein storing a given data element in the enhanced Bloom filter involves marking multiple instances of the enhanced Bloom filter which is associated with multiple consecutive time intervals to indicate that the given data element was observed.

13. The computer-readable storage medium of claim 10, wherein storing a given data element in the enhanced Bloom filter involves marking a single instance of the enhanced Bloom filter associated with a current time interval to indicate that the given data element was observed.

14. The computer-readable storage medium of claim 10, 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.

15. The computer-readable storage medium of claim 14, 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.

16. The computer-readable storage medium of claim 10, 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.

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

18. The computer-readable storage medium of claim 10,

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.

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

a processor;

a memory;

a storage device; and

a data-monitoring mechanism configured to;

receive a query which seeks to determine whether the data element exists within a set of data elements observed from a stream of data;

in response to the query, to perform a lookup in an enhanced Bloom filter to determine whether the pattern of data elements was observed in the stream of data, wherein the enhanced Bloom filter includes multiple instances of a Bloom filter, and wherein each instance of the Bloom filter is associated with a different time interval; and

if so, to generate a notification that the data element was observed.

20. The apparatus of claim 19, wherein prior to receiving the query, the data-monitoring mechanism is configured to:

observe the stream of data; and

to

store data elements observed in the stream of data in the enhanced Bloom filter.