Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-04-09
2004-11-30
Alam, Shahid (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C717S156000, C345S440000, C370S258000
Reexamination Certificate
active
06826569
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to a method for identifying patterns, and in particular for identifying repeating patterns in sequential event streams.
Basic Terminology
We consider a stream of events, which are ordered according to some numerical criterion such as time, spatial position or relative proximity. Events are typed (i.e. each event is of a predetermined type), so that the event stream may be represented as a sequence of events each identified by a type identifier, or type-id, and a coordinate identifying the position of the event in the sequence; the event is said to occur at that position, which may for example be a time or a spatial position, or simply represent the ordering of the event relative to other events in the stream.
The following example represents a sequence of seven ordered events of four distinct types A, B, C and D, in which each event is represented as a (<type-id>, <position>) pair.
((A,
6
), (B,
7
), (C,
9
), (D,
29
), (A,
44
), (B,
47
), (C,
48
))
Notice that the type A, B and C events occur two times in the sequence, and that on both occasions their coordinates indicate that they are relatively close together. In the example, we use an integer to represent position, but any numerical value may be used.
A repeating pattern, or simply a pattern, is defined as a set of types whose corresponding events repeatedly occur at around the same position. When these events do occur at around the same position, we say that the pattern occurs or is instantiated at that position, and that the events form an occurrence or instance of the pattern. Referring again to the previous example, if the three types A, B, and C constitute a pattern, then the event stream can be said to illustrate two instances of that pattern.
BACKGROUND OF THE INVENTION
Previous approaches to the problem of searching data for repeating patterns have generally aimed to identify repeating temporal patterns, and have used the principle of moving a time window stepwise through the data and identifying events in the window at each position to reduce the problem to one of itemset counting (reference
1
). Each position of the time window is thus used to define an itemset, in which each item is an event type. The itemsets are then processed through a standard itemset counting algorithm (reference
2
). The frequent itemsets (itemsets occurring more than a specified number of times) are then declared to be the frequent repeating patterns. This approach has a number of drawbacks:
1. Successive positions of the moving time window overlap, leading to multiple counting of neighbouring event types. (If successive window positions do not overlap, pattern instances are too easily missed).
2. The frequent itemsets generally exhibit a complex pattern of nesting and overlap, which can conceal the true nature of the patterns in the data stream.
3. The itemset counting algorithms require the user to specify a minimum frequency for the patterns to be found. Setting this parameter is extremely difficult in practice. Setting it too high results in patterns being missed. More importantly, setting this parameter too low results in a huge increase in the amount of computer time and memory required to perform the count.
4. Event streams containing several comparatively infrequently repeating patterns present particular problems, because of the need to use a small frequency threshold to catch such patterns. Itemset counting algorithms perform poorly when searching for low frequency patterns.
SUMMARY OF THE INVENTION
The invention provides a method and a computer program for identifying repeating patterns in an event stream as defined in the appended independent claim, to which reference should now be made. Preferred or advantageous features of the invention are set out in dependent subclaims.
In a preferred aspect, the invention therefore provides a method for the detection of repeating patterns in sequential typed event streams, which advantageously makes use of the recognition that repeating patterns can be identified as clusters in an edge-weighted graph derived from a sliding or moving window scheme, together with the manner in which the edge weights are derived from the windows themselves.
Event types that form a repeating pattern tend to occur more frequently within a short distance of one another than with other event types. In a preferred embodiment, each event type is represented by a vertex in an edge-weighted graph. Our method then detects repeating patterns by examining the contents of a narrow fixed width window as it is moved, preferably in a single pass, through the event stream, and calculating edge weights in the graph to reflect the frequency with which types (vertices) co-occur in the moving window. Groups of types (vertices) that co-occur frequently emerge as clusters of higher edge weights in the graph, and can be detected by any standard graph clustering method.
One option would be to use a cluster detection method based on a graph connectivity criterion, such as the method set out in Appendix
1
herein. See reference
3
for a definition of connectivity and any other graph-theoretic terms used in this document.
Once clusters, or patterns, of types have been identified, pattern instances may advantageously be located by re-scanning the event stream for each pattern in turn. For the rescanning process, the event stream is preferably edited to retain only those events corresponding to types in the pattern under investigation, to reduce processing time. As the window passes through these events, the pattern instances emerge as non-overlapping sets of contiguous pattern events.
A pattern instance is said to be complete if every type in the pattern is represented by a corresponding event. A pattern instance is said to be partial if some of the types are not so represented. The coverage of a pattern instance is defined as the percentage of the types in the pattern represented by events. The frequency of a pattern is defined as the number of times a pattern is instantiated in a sequence.
It will be appreciated that the method described above may advantageously detect partial instances of patterns. In a preferred embodiment of the invention, a coverage threshold may be specified, for example by a user, and pattern instances with a coverage below the threshold may be rejected. This enables a user to search for and identify partial patterns in a controlled way.
The choice of window width is preferably under the user's control, and may depend on the nature of the event data being analysed. For example, for telephone call data where a search is being made to identify telephone calls between individuals which may be linked, a window width of half an hour to an hour might be appropriate. For financial data, where a search might be made for financial transactions which may be linked, the width might be greater—one to two days perhaps.
In some applications, events of different types may occur at markedly different rates. Consider, for example, an event stream consisting of a mixture of telephone call events and postal delivery events. Typically the telephone calls will be occurring frequently, whereas postal deliveries occur only once or perhaps twice a day. In order to capture a pattern of the form (Package Delivered to A, A calls B, A calls C), the following preferred embodiment of the invention may be used.
This embodiment allows sub-windows of different widths to be assigned to different types of event. The sub-window widths are chosen to match the characteristics of the event types to which they are applied. Also, separate event streams are prepared, each containing only events of predetermined types, but the corresponding edge-weighted graph contains vertices corresponding to all event types. The sub-windows are then moved simultaneously, in parallel, through their own event streams. The contents of the two sub-windows are treated as if they come from one window for the purposes of weighting the edges in the graph.
With the example of a mixture of telephone call
12 Limited
Alam Shahid
LandOfFree
Method for identifying patterns does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for identifying patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for identifying patterns will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3327082