Patent Publication Number: US-2016239660-A1

Title: Sequence identification

Description:
PRIORITY CLAIM 
     The present application is a National Phase entry of PCT Application No. PCT/GB2014/000378, filed Sep. 24, 2014, which claims priority from EP Application No. 13250102.4, filed Sep. 26, 2013, each of which is hereby fully incorporated herein by reference. 
    
    
     TECHNICAL FIELD 
     The present disclosure relates to sequence identification for events. In particular it relates to representing event sequences for efficient filtering of incoming events and prediction of future events. 
     BACKGROUND 
     As the generation of information proliferates, vast quantities of data are created by systems, software, devices, sensors and all manner of other entities. Some data is intended for human review, problem identification or diagnosis, scanning, parsing or mining. As data sets are generated and stored in greater quantities, at greater rates, and with potentially greater levels of complexity and detail, the “big data” problem of storing, handling, processing or using the data arises. 
     Specifically, it can be problematic to identify meaning within data, or to identify relationships between data items in large or complex data sets. Further, data can be generated in real-time and received by data storage components or data processing components at regular or variable intervals and in predetermined or variable quantities. Some data items are generated over time to indicate, monitor, log or record an entity, occurrence, status, event, happening, change, issue or other thing. Such data items can be collectively referred to as ‘events’. Events include event information as attributes and have associated a temporal marker such as a time and/or date stamp. Accordingly, events are generated in time series. Examples of data sets of events include, inter alia: network access logs; software monitoring logs; processing unit status information events; physical security information such as building access events; data transmission records; access control records for secured resources; indicators of activity of a hardware or software component, a resource or an individual; and profile information for profiling a hardware or software component, a resource or an individual. 
     Events are discrete data items that may or may not have association directly or indirectly with other events. Determining relationships between events requires detailed analysis and comparison of individual events and frequently involves false positive determinations of relationship leading to inappropriate conclusions. Statistical methods such as time-series analysis and machine learning approaches to the modeling of event information are not ideally suited because they require numerical features in many cases, and because they typically seek to fit data to known distributions. There is evidence that human behavior sequences can differ significantly from such distributions—for example, in sequences of asynchronous events such as the sending of emails, exchange of messages, human controlled vehicular traffic, transactions and the like. In the paper “The origin of bursts and heavy tails in human dynamics,” (A. L. Barabasi, Nature, pp. 207-211, 2005), Barabasi showed that many activities do not obey Poisson statistics, and consist instead of short periods of intense activity which may be followed by longer periods in which there is no activity. 
     A related problem with statistical approaches and machine learning is that such approaches generally require a significant number of examples to form meaningful models. Where a new behavior pattern occurs (for example, in network intrusion events) it may be important to detect it quickly (i.e. before a statistically significant number of incidents have been seen). A malicious agent may even change the pattern before it can be detected. 
     The identification of sequences of events is a widespread and unsolved problem. For example, internet logs, physical access logs, transaction records, email and phone records all contain multiple overlapping sequences of events related to different users of a system. Information that can be mined from these event sequences is an important resource in understanding current behavior, predicting future behavior and identifying non-standard patterns and possible security breaches. 
     SUMMARY 
     Embodiments accordingly provide, in a first aspect, a sequence identification apparatus comprising a processor, wherein the apparatus is adapted to generate a directed acyclic graph data structure of equivalence classes of events in an event sequence identified in a plurality of time-ordered events, wherein the apparatus is further adapted to add a representation of a further event sequence to the graph such that initial and final sub-sequences of event sequences having common equivalence classes are combined in the graph. 
     Advantageously, in embodiments the apparatus further comprises a sequence identifier adapted to identify the event sequence and the further event sequence based on at least one sequence extending relation defining at least one relation between events. 
     Advantageously, in embodiments the apparatus further comprises an event categorizer adapted to determine an equivalence class for an event based on at least one event categorization definition. 
     Advantageously, in embodiments the apparatus further comprises an event filter component adapted to filter incoming time-ordered events based on the graph. 
     Advantageously, in embodiments the event filter component is further adapted to traverse the graph based on the at least one sequence extending relation and a categorization of each of the incoming events into an equivalence class so as to identify sequences of incoming events represented by the graph. 
     Advantageously, in embodiments the event filter component is further adapted to identify an incoming event being inconsistent with sequences of equivalence classes represented by the graph. 
     Advantageously, in embodiments the apparatus further comprises a notifier adapted to generate a notification responsive to the identification by the event filter component. 
     Advantageously, in embodiments the apparatus further comprises a predictor adapted to identify at least one predicted equivalence class for a predicted future incoming event as an equivalence class next indicated in the directed acyclic graph by the traversal of the event filter component. 
     Advantageously, in embodiments the at least one sequence extending relation is defined such that a relation between events is determined based on a measure of a level of satisfaction of at least one relational criterion and responsive to the measure meeting a predetermined threshold. 
     Advantageously, in embodiments each event includes a plurality of common attributes, each common attribute having a domain common to all events, and wherein each event categorization is defined by at least one criterion based on a plurality of common attributes. 
     Advantageously, in embodiments the event categorizer determines an equivalence class for an event based on a measure of a level of satisfaction of the event with the at least one criterion for at least one event categorization. 
     Advantageously, in embodiments the graph has at least two edges, each edge corresponding to an equivalence class for at least one event, and wherein the apparatus is further adapted to generate an association between each event and a corresponding graph edge such that events can be identified based on an edge. 
     In accordance with a second aspect, embodiments accordingly provide a sequence identification apparatus for identifying event sequences in a plurality of time-ordered events, each event being a data item accessible by a computer system, the apparatus comprising: a storage component for storing: at least one sequence extending relation defining at least one relation between events for identifying a sequence of events; and at least one event categorization definition for categorizing events in a sequence of events; a sequence identifier adapted to identify a first and a second sequence of events based on the at least one sequence extending relation such that each event in the plurality of events belongs to at most one of the first and second sequences; an event categorizer adapted to determine an event categorization for each event in the first and second sequences of events based on the at least one event categorization definition; a data structure processor adapted to generate a directed acyclic graph data structure; wherein the data structure processor is further adapted to generate a directed acyclic graph of event categorizations for the first sequence such that each edge of the graph corresponds to an event categorization for an event in the first sequence, wherein the data structure processor is further adapted to process the second sequence with the graph data structure to add event categorizations for events in the second sequence to the graph such that initial and final sub-sequences of the first and second sequences having common event categorizations are combined in the graph data structure. 
     In accordance with a third aspect, embodiments accordingly provide a computer implemented method of sequence identification comprising: generating a directed acyclic graph data structure of equivalence classes of events in an event sequence identified in a plurality of time-ordered events; and adding a representation of a further event sequence to the graph such that initial and final sub-sequences of event sequences having common equivalence classes are combined in the graph. 
     Advantageously, in embodiments the method further comprises traversing the graph based on a categorization of each of the incoming events into at least one equivalence class so as to identify sequences of incoming events represented by the graph. 
     Advantageously, in embodiments the method further comprises identifying an incoming event being inconsistent with sequences of equivalence classes represented by the graph. 
     Advantageously, in embodiments the method further comprises identifying at least one predicted equivalence class for a predicted future incoming event as an equivalence class next indicated in the directed acyclic graph by the traversal of the event filter component. 
     In accordance with a fourth aspect, embodiments accordingly provide a computer implemented method of sequence identification for a plurality of time-ordered events, each event being a data item accessible by a computer system, the method comprising receiving at least one sequence extending relation defining at least one relation between events for identifying a sequence of events; receiving at least one definition of an event categorization for categorizing events in a sequence of events; determining an event categorization for each event in a first sequence of events, the first sequence being identified based on the sequence extending relations; generating a directed acyclic graph data structure of event categorizations for the first sequence wherein each edge of the graph corresponds to an event categorization for an event in the first sequence; determining an event categorization for each event in a second sequence of events, the second sequence being identified based on the at least one sequence extending relation such that each event in the plurality of events belongs to at most one of the first and second sequences; processing the second sequence with the graph data structure to add event categorizations for events in the second sequence to the graph, wherein, in the processing step, initial and final sub-sequences of the first and second sequences having common event categorizations are combined in the graph data structure. 
     In accordance with a fifth aspect, embodiments accordingly provide a computer program element comprising computer program code to, when loaded into a computer system and executed thereon, cause the computer to perform the computer implemented method as described above. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Embodiments will now be described, by way of example only, with reference to the accompanying drawings, in which: 
         FIG. 1  is a block diagram of a computer system suitable for the operation of embodiments. 
         FIG. 2  is a component diagram of a sequence identification apparatus for identifying sequences in a plurality of events in accordance with an embodiment. 
         FIG. 3  is a flowchart of a method of the sequence identification apparatus of  FIG. 2  in accordance with an embodiment. 
         FIG. 4  is a component diagram of a sequence identification apparatus in use in accordance with one embodiment. 
         FIG. 5  is a flowchart of a method of the sequence identification apparatus of  FIG. 4  in accordance with one embodiment 
         FIGS. 6 a  to 6 e    are component diagram illustrating exemplary data structures employed and generated by the embodiments of  FIGS. 2 to 5 . 
         FIG. 7  is a component diagram of a sequence identification apparatus in use in accordance with an alternative embodiment. 
         FIG. 8  is a flowchart of a method of the filter of  FIG. 7  in accordance with the alternative embodiment. 
         FIG. 9  is an AllowedActions table in accordance with an exemplary embodiment. 
         FIG. 10  is a directed acyclic graph representation of a first sequence in accordance with the exemplary embodiment. 
         FIG. 11  is a directed acyclic graph representation of a first, second and third sequences in accordance with the exemplary embodiment. 
         FIG. 12  is a directed acyclic graph representation of a first and second sequences generated in accordance with an exemplary algorithm in an embodiment. 
         FIG. 13  is a directed acyclic graph representation of a first, second and third sequences generated in accordance with an exemplary algorithm in an embodiment. 
         FIG. 14  is a directed acyclic graph representation of a first, second, third and fourth sequences generated in accordance with an exemplary algorithm in an embodiment. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  is a block diagram of a computer system suitable for the operation of embodiments. A central processor unit (CPU)  102  is communicatively connected to a storage  104  and an input/output (I/O) interface  106  via a data bus  108 . The storage  104  can be any read/write storage device such as a random access memory (RAM) or a non-volatile storage device. An example of a non-volatile storage device includes a disk or tape storage device. The I/O interface  106  is an interface to devices for the input or output of data, or for both input and output of data. Examples of I/O devices connectable to I/O interface  106  include a keyboard, a mouse, a display (such as a monitor) and a network connection. 
       FIG. 2  is a component diagram of a sequence identification apparatus  200  for identifying sequences in a plurality of events in accordance with one embodiment. The sequence identification apparatus  200  includes a processor  202  for undertaking all or part of the function of the apparatus. Various functions and components of the sequence identification apparatus  200  will be described below with respect to multiple embodiments and it will be appreciated by those skilled in the art that the processor  202  may be adapted to carry out, perform, constitute or encapsulate one or more such functions and components in various configurations. For example, the processor  202  can be one or more CPUs such as CPU  102  of a generalized computing device such as that depicted in  FIG. 1 . Accordingly the particular embodiments depicted herein are purely exemplary and any suitable configuration of components could alternatively be employed. 
     The sequence identification apparatus  200  is adapted to receive event sequences  204  as sequences of events from a plurality of time-ordered events. The plurality of time-ordered events can be stored in a data structure, table, database or similar, or alternatively the events can be received as a stream of events. The plurality of time ordered events is used to identify the event sequences  204  based on defined sequence extending relations as described below. The event sequences  204  can be determined by a component external to the sequence identification apparatus  200 , such as an event sequence identifier, or alternatively the event sequences  204  can be determined by the sequence identification apparatus  200  itself. 
     The sequence identification apparatus  200  is further adapted to determine an equivalence class for each event in each of the event sequences  204 . An equivalence class is a class or type of event defined by one or more event categorization definitions and serves to classify or categorize events. In one embodiment the sequence identification apparatus  200  is adapted to determine the equivalence class itself for each event, based on one or more event categorization definitions as described below. In an alternative embodiment, the sequence identification apparatus  200  determines an equivalence class for an event by receiving an equivalence class for the event from a component external to the sequence identification apparatus  200 . 
     The sequence identification apparatus  200  is further adapted to generate a directed acyclic graph (DAG) data structure  206  as a data structure representation of equivalence classes for a first one of the event sequences  204 . For example, the DAG data structure  206  can be a data structure stored in a storage  104  of a computer system, such as a storage associated or comprised with the sequence identification apparatus  200 . In one embodiment the DAG data structure  206  is stored using data structure elements as nodes having memory pointers for providing links between nodes as edges of the DAG. Exemplary embodiments of the DAG data structure  206  are detailed below. 
     The sequence identification apparatus  200  is further adapted to add a representation of one or more further event sequences  204  to the DAG data structure. Thus, the sequence identification apparatus  200  receives one or more further event sequences  204  and modifies the DAG data structure  206  to include a representation of such further event sequences within the DAG. Equivalence classes for events in such further event sequences can be common. For example, equivalence classes for events at a beginning of a first event sequence can be common with equivalence classes for events at a beginning of a second event sequence. The sequence identification apparatus  200  combines such common sub-sequences represented in the DAG data structure  206  such that relationships between the first and second event sequences based on sub-sequences of events having common equivalence classes are represented in the DAG data structure  206 . The sequence identification apparatus  200  is adapted to combine equivalence class representations in the DAG data structure  206  for initial and final sub-sequences of event sequences having common equivalence classes (‘initial’ being at the beginning of an event sequence, and ‘final’ being at the end of an event sequence). 
       FIG. 3  is a flowchart of a method of the sequence identification apparatus  200  of  FIG. 2  in accordance with one embodiment. Initially, at  302 , the sequence identification apparatus  200  generates a DAG data structure  206  of equivalence classes of events in an event sequence  204 . Subsequently, at  304 , the sequence identification apparatus  200  adds representations of further event sequences  204  to the DAG data structure  206 . The addition, at  304 , includes combining equivalence class representations in the DAG data structure  206  as described above. 
     The DAG data structure  206  generated by the sequence identification apparatus  200  includes a directed representation of equivalence classes for each of the event sequences  204 . Such a representation is particularly advantageous for processing subsequently received streams of time-ordered events. Using such a DAG data structure  206  it is possible to efficiently filter incoming streams of time-ordered events to identify known sequences of events by traversing the DAG for new events. The DAG data structure  206  is particularly beneficial because it represents equivalence classes of events and so a filtering process based on the DAG is not hindered by an interpretation of the particular features of individual events, either in the plurality of events used to generate the DAG or a stream of incoming events. Further, such an approach to traversing the DAG for incoming events can be used to efficiently identify new sequences of events not correlating to the event sequences represented by the DAG. Such identifications can be useful where new sequences need to be identified. Yet further, the DAG data structure  206  allows for an efficient identification of new sequences having sub-sequences in common with existing sequences, such as new sequences of events having initial or final sub-sequences of events having common equivalence classes. 
     The DAG data structure  206  is further suitable for predicting future classes or types of event, and by extrapolation, the DAG can be used to predict one or more future events based on the event sequences used to generate the DAG. Where a path through the DAG data structure  206  is partially traversed in response to a sequence of incoming time-ordered events, one or more potential subsequent event classifications can be predicted based on the next elements in the DAG. Further, attributes for existing events in a sequence leading to such partial traversal of a path through the DAG can be used to generate one or more predicted events. Such predictions can be additionally based on sequence extending relations to inform a determination of attribute values for one or more predicted future events. For example, where the DAG data structure  206  represents event sequences of known attacks in a computer network intrusion detection system, with each event corresponding to a network action such as a network request, response, transmitted packet or other network occurrence, the DAG can be used to predict one or more future events from an incoming stream of events to identify a potential new attack before it occurs. Such early identification can be effective even if the incoming sequence of events is used to only partially traverse a path through the DAG. An extent of similarity of the equivalence classes for an incoming sequence of events with paths of equivalence classes in the DAG can be determined and, reactive to a threshold extent, predicted attacks can be identified. 
     The DAG data structure  206  is further suitable for identifying entities associated with events that may be related based on similarity of paths through the DAG data structure  206 . For example, events relating to wholly different entities but being represented in the DAG using common graphs of event classifications (such as combined graphs or sub-graphs) can identify a relationship between the entities. Thus, where entities constitute physical objects, devices or people and events indicate a behavior, action, change or other occurrence relating to the entity, the DAG can be used to group entities due to event classification commonality. For example, time-stamped events can relate to employees accessing resources using a security facility, such as access to a secure building via a badge-locked door, or access to a secure network via an authentication system. Such events can include an indication of a type of occurrence, such as an “entry occurrence” and an “exit occurrence” indicating commencement and cessation of access to the resource. Further, events can include an identification of a resource being accessed, such as a building or network identifier. Sequences of such events can be identified using sequence extending relations between events such as identity of employee identifier and a temporal limitation. A DAG data structure  206  generated by the sequence identification apparatus  200  models equivalence classes of events in such sequences. Such classes can include, for example, classes characterized by the type of occurrence (“entry” or “exit”), the time of day (e.g. “morning” or “afternoon”) and an identifier of a resource (building or network identifier). As sequences of events are represented in the DAG data structure  206 , event sequences relating to different employees may be found to overlap in the DAG and are accordingly combined. Such employees can be identified as similar based on such combining. For example, employees who enter a particular building in the morning and leave the same building in the afternoon can be identified as a group of employees who work at only a single site. Other different such groups can also be discerned based on the DAG. The identification of groups of entities can be valuable in security applications where entities grouped with known threats can be subject to close scrutiny. 
       FIG. 4  is a component diagram of a sequence identification apparatus  200  in use in accordance with one embodiment. Certain of the elements of  FIG. 4  are common with  FIG. 2  as previously described and these will not be repeated here. The embodiment of  FIG. 4  illustrates one exemplary implementation of the arrangement of  FIG. 3  for the generation of the DAG data structure  206 . The sequence identification apparatus  200  of  FIG. 4  is adapted to receive a plurality of time-ordered events  422 . Each event in the plurality of events  422  is a data item, data structure, message, record or other suitable means for recording an occurrence of the type, inter alia, previously described. Events  422  constitute data input into the sequence identification apparatus  200  and can be stored in a data store associated with, or communicable with, the apparatus  200 . For example, the events  422  can be stored in a table data structure, database, file, message list or other suitable format. Alternatively, the events  422  can be received by the apparatus  200  individually or in batches over a communication mechanism such as a software or hardware interface or a network. Each of the events  422  includes temporal information such as a time and/or date stamp to indicate the position of the event in the time-ordered plurality of event. Such temporal information can be absolute or relative. Each of the events  422  has a plurality of fields, columns, elements, values, parameters or data items that shall be collectively referred to as attributes. Attributes are most advantageously identified by an attribute name, though an offset, address, indicator, identifier, look-up or other suitable means for consistently referencing a particular attribute of an event are also possible. In one embodiment, attributes are common to all events  422  such that each event has all attributes, and the domain of each attribute is the same for all events. In an alternative embodiment some events have attributes in addition to common attributes and a subset of attributes used for sequence generation and event classification are common to all events. 
     The sequence identification apparatus  200  further includes a storage component  410  storing one or more sequence extending relations  412  and one or more event categorization definitions  414 . The sequence extending relations  412  are relations between events  422  based on common event attributes. In an event sequence  204 , each event is related to a temporally preceding event by one or more sequence extending relation  412 . A first event in an event sequence is not related to a preceding event. Thus, the sequence extending relations  412  serve to define a relationship between an event and a temporally later event to constitute all or part of an event sequence. One or more of the sequence extending relations  412  can be implemented as criteria, the satisfaction of which by a pair of events determines a relationship between the events. In one embodiment the criteria can be determinative of a relation. In an alternative embodiment, one or more of the sequence extending relations  412  can be implemented as a measurement of characteristics of a pair of events to determine a relationship between the events. In this way a fuzzy relation can be defined such that a relationship between events is based on one or more measures of characteristics based on attribute values of the events and one or more conditions or criteria relating to such measures. Thus, in such embodiments, one or more sequence extending relations  412  are defined such that a relation between events is determined based on a measure of a level of satisfaction of relational criteria and responsive to the measure meeting a predetermined threshold. 
     The event categorization definitions  414  define classes or types of events known as equivalence classes or event categories. Equivalence classes provide a mechanism for categorizing multiple events as “equivalent” events according to the event categorization definitions  414 . The event categorization definitions  414  are based on event attributes common to all events. Advantageously, each of the event categorization definitions  414  is defined by at least one criterion based on a plurality of common attributes. One or more of the event categorization definitions  414  can be implemented as one or more criteria, the satisfaction of which by an event can be used to determine that the event belongs to an equivalence class. In one embodiment the criteria can be determinative of a categorization of an event. In an alternative embodiment, one or more of the event categorization definitions  414  can be implemented as a measurement of characteristics of an event based on attributes of the event to determine one or more equivalence classes for the event. In this way a fuzzy association with equivalence classes can be defined such that an association between an event and equivalence classes is based on one or more measures of characteristics based on attribute values of the event and one or more conditions or criteria relating to such measures. Thus, in such embodiments, one or more event categorization definitions  414  are defined such that an equivalence class for an event is determined based on a measure of a level of satisfaction of the event with one or more criteria. 
     In use the sequence extending relations  412  are received by a sequence identifier  416 . The sequence identifier is a hardware, software or firmware component adapted to identify event sequences  204  in the plurality of time-ordered events  422  based on the sequence extending relations  412 . In one embodiment the sequence identifier  416  processes each event in the plurality of events  422  and applies criteria associated with each of the sequence extending relations  412  to determine if the event is related to a previous event. Related events are stored as event sequences  204  which can grow as more events in the plurality of events  422  are processed. It is conceivable that some events are not related to previous events and these may constitute the beginning of a new sequence. Further, some events may not appear in any of the sequences  204 . Such events may be identified or flagged for further consideration. It will be appreciated by those skilled in the art that the sequence identifier  416  is operable to identify, monitor and track multiple potential or actual sequences contemporaneously so as to identify all event sequences  204  existing in the plurality of events  422  based on the sequence extending relations  412 . 
     Further, in use the event categorization definitions  414  are received by an event categorizer  418 . The Event categorizer is a hardware, software or firmware component adapted to determine an equivalence class for each event in each of the event sequences  204 . In one embodiment the event categorizer  418  receives processes each event in each event sequence  204  and applies criteria associated with each of the event categorization definitions  414  to determine an appropriate equivalence class. 
     The sequence identification apparatus  200  further comprises a data structure processor  410  as a hardware, software or firmware component adapted to generate a DAG data structure  206  for each event in each of the event sequences  204 . In one embodiment the DAG data structure  206  includes nodes and edges such that each edge corresponds to an equivalence class for an event in a sequence. Thus, in use, the data structure processor  420  generates an initial DAG data structure  206  for a first event sequence  204 ′ including a plurality of graph edges each corresponding to an equivalence class for an event in the sequence. The edges connect nodes representative of, but not specifically associated with, the sequence extending relations  410  for the event sequence  204 ′. Consequently, after processing the first event sequence  204 ′, the DAG data structure  206  is generated as a graph having a single straight path from a start node to an end node, with edges corresponding to equivalence classes for each event in the sequence joining nodes along the path. Subsequently, the data structure processor  420  processes further event sequences  204 ″,  204 ′″ adding a representation of each further event sequence  204 ″,  204 ′″ to the DAG data structure  206 . In particular, where the data structure processor  420  determines that one or more initial and final sub-sequences of the first sequence  204 ′ and further sequences  204 ″,  204 ′″ have common event categorizations, the sub-sequences are combined in the DAG data structure  206 . The DAG is therefore a minimal representation of the equivalence classes of the event sequences  204  where event sequences having sub-sequences of events with a series of common equivalence classes are merged and represented only once in the DAG data structure  206 . Accordingly, the DAG data structure  206  can branch and join at points between a start node and an end node to define paths between the start node and end node. 
     It will be appreciated by those skilled in the art that, while the processor  202 , sequence identifier  416 , event categorizer  418  and data structure processor  420  are illustrated as separate components in  FIG. 4 , any or all of at least these components can be combined, merged, or further subdivided in embodiments. For example, the sequence identifier  416  and the event categorizer  420  can be a single component. Further, the data structure processor  420  may be omitted with its functions performed by the processor  202  or any other suitable component of the sequence identification apparatus  200 . It will further be appreciated that, while the storage component  410  is illustrated as being integral to the apparatus  200 , the storage may alternatively be provided external to the apparatus  200  or as an integral part of a subcomponent of the apparatus  200 . For example, the storage component  410  can be provided and maintained at an external device or apparatus communicatively connected to the sequence identification apparatus  200 , such as by a software and/or hardware interface or a network. 
       FIG. 5  is a flowchart of a method of the sequence identification apparatus  200  of  FIG. 4  in accordance with one embodiment. Initially, at  500 , the sequence identifier  416  accesses time ordered plurality of events  422  such as by accessing a data store, database or table containing event records. At  502  the sequence identifier  416  receives sequence extending relations  412  from the storage component  410 . At  504  the event categorizer  418  receives event categorization definitions  414  from the storage component  410 . At  506  the sequence identifier  416  identifies a first event sequence  204 ′ based on the sequence extending relations  412 .  508  the event categorizer  418  determines an equivalence class for each event in the first event sequence  204 ′. At  510  the data structure processor  420  generates a DAG data structure  206  of equivalence classes to represent the first sequence  204 ′. Subsequently, at  512 , the sequence identifier  416  identifies at least one further event sequence  204 ″ as a second event sequence  204 ″. At  514  the event categorizer  418  determines an equivalence class for each event in the second event sequence  204 ″. At  516  the data structure processor  420  processes the second event sequence  204 ″ with the DAG data structure  206  to add equivalence classes for events in the second event sequence  204 ″ to the DAG data structure  206 . 
     It will be appreciated that the particular ordering of the flowchart tasks illustrated in  FIG. 5  and described above is not limiting and any other suitable tasks and/or order of tasks could alternatively be employed. 
       FIGS. 6 a  to 6 e    are component diagram illustrating exemplary data structures employed and generated by the embodiments of  FIGS. 2 to 5 .  FIG. 6 a    illustrates an exemplary event data structure  740 . The event  740  includes a timestamp  742  as an example of a temporal indicator. The timestamp  742  can indicate a time of generation, dispatch, receipt or other point in time applied consistently by all events in a plurality of events  422 . The timestamp  742  provides a means by which the time-ordered nature of a plurality of events  422  can be determined and confirmed. For example, if a plurality of events  422  is not time-ordered, the timestamp  742  can be used to sort the events to provide a time-ordered plurality of events  422 . The event  740  further includes a plurality of common attributes  744 . The attributes  744  are common among all events in a plurality of events  422 . All or a subset of the attributes  744  are used to define sequence extending relations  412 . Further, all or a subset of the attributes  744  are used to define event categorization definitions  414 . Each of the attributes  744  has a domain common to all events. 
       FIG. 6 a    further illustrates an exemplary sequence extending relations data structure  412 ′. The sequence extending relations data structure  412 ′ includes a relation  748  defined by way of one or more criteria  750  based on event attributes  744 .  FIG. 6 a    further illustrates an exemplary event categorization definitions data structure  414 ′. The event categorization definitions data structure  414 ′ includes a plurality of equivalence class definitions  754   a ,  754   b  each being defined by way of one or more criteria  756   a ,  756   b  based on event attributes  744 . 
       FIG. 6 b    illustrates a plurality of time-ordered events  422 , each including a timestamp  742  and attributes  744 . The plurality of events  422  are illustrated as a stream of events which is one way the events can be received by the sequence identification apparatus  200 . The plurality of events  422  can equally be stored in a table or other suitable data structure as described above. 
       FIG. 6 c    illustrates a first exemplary DAG data structure. The DAG of  FIG. 6 c    represents equivalence classifications for at least one event sequence of two events, the second event being related to the first event by a sequence extending relation. A first event in the event sequence is represented as having an equivalence class “Class 1”. A second event in the event sequence is represented as having an equivalence class “Class 2”. The graph is delimited by predefined start and end nodes labeled “S” and “F” respectively. The relation between the events is indicated by the node “1” and the temporal relationship between the events in the event sequence provides a direction for the edges (equivalence classes) of the graph. Thus,  FIG. 6 c    provides a DAG representation of an event sequence. Other event sequences having different events but having events with equivalence classifications according to the DAG of  FIG. 6 c    can be said to be similar to the event sequence that was used to generate  FIG. 6   c.    
       FIG. 6 d    illustrates a second exemplary DAG data structure. The DAG of  FIG. 6 d    shares some features with  FIG. 6 a   , such as the start and end nodes. The DAG of  FIG. 6 d    represents equivalence classifications for at least two event sequences, each of three events in length. A first event sequence includes events in time order having equivalence classes “Class 1”, “Class 4” and “Class 1” respectively. A second event sequence includes events in time order having equivalence classes “Class 2”, “Class 3” and “Class 1”. The two event sequences overlap at sub-sequence at the end of each sequence, since the last event in both event sequences has equivalence class “Class 1”. Thus, the DAG of  FIG. 6 d    combines edges for the last event in each sequence between the node labeled “3” and the end node “F”. 
       FIG. 6 e    illustrates a third exemplary DAG data structure. The DAG of  FIG. 6 e    represents equivalence classifications for at least two event sequences where each of the event sequences overlap at a sub-sequence at the beginning of each sequence. Events at the beginning of both sequences are of equivalence class “Class 1”. Thus, the DAG of  FIG. 6 e    combines edges for the first event in each sequence between the start node “S” and the node labeled “1”. 
     Advantageously, in one embodiment the edges of the DAG data structure  206  are associated with events used in the generation of the DAG data structure  206  such that it is possible to relate an equivalence class representation in a DAG to events categorized to the equivalence class in a corresponding event sequence. For example, the DAG data structure  206  can be rendered for visualization to a user for analysis, review or other reasons. A user can navigate to specific events in event sequences based on edges in the DAG using such an association. It will be apparent to those skilled in the art that the association can be unidirectional (e.g. DAG edges reference events or events reference DAG edges) or bidirectional. 
       FIG. 7  is a component diagram of a sequence identification apparatus  200  in use in accordance with an alternative embodiment. Many of the features of  FIG. 7  are identical to those described above with respect to  FIGS. 2 and 4  and these will not be repeated here. The sequence identification apparatus  200  of  FIG. 7  further includes a filter  732  as a hardware, software or firmware component adapted to receive and filter incoming time-ordered events  730  based on a DAG data structure  206 . The DAG data structure  206  is predefined according to the components, methods and techniques described above with respect to  FIGS. 2 to 6 . The incoming events  730  are new events for filtering by the filter  732 . The filter  732  constitutes a component for employing a defined DAG data structure  206  to filter new incoming events  730 . For example, the filter  732  is suitable for efficiently filtering an incoming stream of time-ordered events  730  to identify event sequences in the incoming stream of events  730  corresponding to sequences known from the DAG data structure  206 . This is achieved by the filter  732  traversing the DAG data structure  732  for events in the incoming stream  730  where incoming events  730  satisfy sequence extending relations  412 . 
     Thus, on receiving a new event from the stream of incoming events  730 , the filter  732  operates in two respects: firstly, the filter  732  determines if the new event is related to a previously received event in accordance with the sequence extending relations  412 ; and secondly, the filter  732  determines if the new event corresponds to an equivalence class represented in the DAG data structure  206  as part of a path traversed through the DAG. In the first respect, the filter  732  can be adapted to store a record of all events as they are received in order to seek and identify previously received events with which a new event may be related. In the second respect, the filter  732  can be adapted to undertake and record potentially numerous traversals of the DAG data structure  206  simultaneously, each traversal corresponding to all partially received event sequences arising in the stream of incoming events  730 . Thus the filter  730  is preferably provided with a memory, store, data area or similar for storing information about received events and for storing DAG traversal information for all partially received event sequences. 
     In this way the filter  732  provides an efficient way to identify known event sequences in the stream of incoming events  730  even where the event sequence arrives interspersed with other events or event sequences. Further, the filter  732  can be used to efficiently identify new sequences of events not correlating to the event sequences represented by the DAG. Such identifications can be useful where new sequences need to be identified, such as for addition to the DAG data structure  206 . Alternatively, the identification of such new sequences can be used to identify atypical, suspicious, questionable or otherwise interesting sequences of events. For example, where a DAG data structure  206  is defined to represent acceptable sequences of events, a new sequence not conforming to any sequence represented by the DAG can be identified by the filter  732 . It will be appreciated by those skilled in the art that the filter  732  can be adapted to traverse the DAG data structure  206  starting at a node or edge not at the beginning (or start) of the DAG such that new event sequences partially corresponding to a sub-sequence represented in the DAG data structure  206  can be identified. 
     In a preferred embodiment the filter  732  is provided with a notifier  736   a  as a hardware, software or firmware component for generating a notification in response to the processing of the stream of incoming events  730 . For example, where the filter  732  identifies a new event sequence not corresponding to any sequence represented by the DAG data structure  206 , the notifier  736   a  can generate an appropriate notification. Additionally or alternatively, where the filter  732  identifies an event sequence corresponding or partially corresponding to a sequence represented by the DAG data structure  206 , the notifier  736   a  can generate an appropriate notification. 
     The sequence identification apparatus  200  of  FIG. 7  further includes a predictor  734  as a hardware, software or firmware component adapted to receive incoming time-ordered events  730  and predict one or more equivalent classes for future events or future events themselves based on the predefined DAG data structure  206 . 
     On receiving a new event from the stream of incoming events  730 , the predictor  734  operates in three respects: firstly, the predictor  734  determines if the new event is related to a previously received event in accordance with the sequence extending relations  412 ; secondly, the predictor  734  determines if the new event corresponds to an equivalence class represented in the DAG data structure  206  as part of a path traversed through the DAG; and thirdly the predictor  734  identifies one or more potential next equivalence classes from the DAG based on the path traversed through the DAG. In the first and second respects, the predictor  734  can be adapted to store a record of all events as they are received and undertake and record potentially numerous traversals of the DAG data structure  206  simultaneously, as is the case for the filter  732 . Thus the predictor  732  is preferably provided with a memory, store, data area or similar for storing information about received events and for storing DAG traversal information for all partially received event sequences. In the third respect, the predictor  732  is adapted to determine one or more predicted equivalence classes from the DAG as outgoing edges from a current node in a traversal of the DAG data structure  206  for an event sequence received in the stream of incoming events  730 . In the simplest case, the equivalence classes represented by outgoing edges are identified for a predicted future event. In some embodiments the prediction can be more sophisticated as described below. 
     In one embodiment, when the predictor  732  identifies more than one predicted equivalence class for a future event, the predictor  732  is further adapted to evaluate a most likely of the predicted equivalent classes based on a statistical, semantic or content analysis of the events received in the event sequence leading to the prediction and events used in the definition of the DAG data structure  206 . Thus, an event sequence in the stream of incoming events  730  that is statistically, semantically or literally more similar to events used in defining a particular path through the DAG can cause a particular path to be weighted more highly (and therefore more likely) than alternative paths. A predicted next equivalence class can then be determined as a most likely equivalence path. 
     Further, in some embodiments, the predictor  732  can employ event information, including attribute values, from events in an identified event sequence in the stream of incoming events that lead to a prediction. The event information can be used to generate a new predicted event by populating the predicted event attribute values based on the event information. For example, timestamp information can be predicted based on intervals between events in a current event sequence. Further, sequence extending relations  412  act as constraints on the potential values of attributes in a predicted event such that all predicted attribute values must at least satisfy criteria associated with the sequence extending relations  412 . Other attribute values, or ranges or enumerations of values, may also be predicted using similar techniques. 
     In one embodiment, either or both of the filter  732  and predictor  734  are provided with a notifier  736   a ,  736   b  as a hardware, software or firmware component for generating a notification in response to the processing of the stream of incoming events  730 . For example, where the filter  732  identifies a new event sequence not corresponding to any sequence represented by the DAG data structure  206 , the notifier  736   a  can generate an appropriate notification. Additionally or alternatively, where the filter  732  identifies an event sequence corresponding or partially corresponding to a sequence represented by the DAG data structure  206 , the notifier  736   a  can generate an appropriate notification. Similarly, the predictor  734  uses the notifier  736   b  to generate notifications of predicted equivalence classes or events. 
     For the avoidance of doubt, the stream of time-ordered incoming events  730  that is processed by the filter  732  and/or the predictor  734  is distinct over the plurality of events  422  used to generate the DAG data structure  206 . Thus the sequence identification apparatus  200  operates with two sets of events: a first set of events  422  for the generation of the DAG data structure; and a second set of events, incoming events  730 , for processing by the filter  732  and/or the predictor  734 . It will be appreciated by those skilled in the art that the incoming events  730  can additionally be used to adapt, evolve, modify or supplement the DAG data structure  206  by adding a representation of identified event sequences in the stream of incoming events  730  to the DAG data structure  206  as embodiments might require. 
     It will be appreciated by those skilled in the art that, while the filter  732  and predictor  734  are illustrated as comprised in the sequence identification apparatus  200 , either of the filter  732  or predictor  734  could be omitted. Alternatively, the functions and facilities provided by the filter  732  and predictor  734  can be provided by a single unified component or components subdivided in different ways. Yet further, the functions and facilities provided by the filter  732  and/or predictor  734  can be provided by one or more components external to the sequence identification apparatus  200 , such as components in communication with the apparatus  200  by hardware or software interface or over a network. 
       FIG. 8  is a flowchart of a method of the filter  732  of  FIG. 7  in accordance with the alternative embodiment. Initially, at  850 , the filter  732  receives a new incoming event from the plurality of incoming events  730 . At  852  the filter  732  determines if the received incoming event extends an event sequence the filter  732  is currently processing. The determination is based on a record of previously received events, previously identified partial event sequences, and the sequence extending relations  412 . If the received event does not extend a previously received event sequence the method records the received event as the start of a potentially new event sequence at  856 . In respect of the received event, the traversal of the DAG data structure  206  is initialized to the start node “S”. 
     Alternatively, at  854 , if the received event does extend a previously received partial event sequence, the method identifies the previously received partial event sequence and the current node in the DAG data structure  206  in respect of the most recent event received in the partial event sequence. 
     At  858  the method determines an equivalence classification for the received event. At  860  the method determines if the determined equivalence classification matches an outgoing edge from the current node in the DAG traversal. If the equivalence classification does not match an outgoing edge,  864  concludes that the received event does not correspond to any of the paths in the DAG and is not compliant with any of the event sequences represented by the DAG and the method terminates. 
     If the equivalence classification does match an outgoing edge,  862  traverses the DAG data structure  206  along the identified outgoing edge to a new current node in the DAG for the partial event sequence. If  866  determines that the new current node is an end node “F”, the method terminates, otherwise the method receives a next incoming event at  868  and iterates to  852 . 
     A detailed exemplary embodiment will now be described by way of example only. In the exemplary embodiment, event data is in a time-stamped tabular format (for example, as comma separated values with one or more specified fields storing date and time information) and arrives in a sequential manner, either row by row or in larger groups which can be processed row-by-row. Each column in the table has a domain D i  and a corresponding attribute name A i . There is a special domain O which plays the role of an identifier (e.g. row number or event id). Formally, data is represented by a function: 
       ƒ: O→D   1   ×D   2   × . . . ×D   n  
 
     which can be written as a relation 
     
       
      
       R ⊂ O×D 
       1 
       ×D 
       2 
       × . . . ×D 
       n  
      
     
     where any given identifier o i  appears at most once. The notation Ak(o i ) is used to denote the value of the k th  attribute for object o i . 
     The embodiment seeks to find ordered sequences of events (and subsequently, groups of similar sequences). To achieve this, sequence extending relations are defined. 
     In the exemplary embodiment, event sequences obey the following rules:
         each event is in at most one sequence   events in a sequence are ordered by date and time   an event and its successor are linked by relations between their attributes, such as equivalence, tolerance, and other relations.       

     These are referred to as sequence extending relations. Note that it is possible to have different sequence extending relations for different sequences. Further, it is possible to change the sequence extending relations dynamically. In the graph structure described below, the sequence extending relations are associated with nodes in the graph. In the exemplary embodiment, any event that is not part of an existing sequence is considered the start of a new sequence. For any attribute A i  a tolerance relation R i  can be defined where 
         R   i   :D   i   ×D   i →[0,1]
 
     is a reflexive and symmetric fuzzy relation and 
       ∀ j:R   i ( A   i ( O   i ), A   i ( O   i ))=1
 
     Then the tolerance class of objects linked through attribute A i  is 
         T ( A   i   ,o   m )={ o   j /χ mj   |R   i ( A   i ( o   m ), A   i ( o   j ))=χ mj }
 
     Note that this set includes (with membership  1 ) all objects with the attribute value A i (o m ). The tolerance class can be expressed equivalently as a set of pairs. 
     Finally the case of a total order relation P T  is included, defined on a distinguished attribute (or small set of attributes) representing a timestamp. Sequences and projected sequences can then be defined 
       ∀ i:P   T ( A   T ( o   i ), A   T ( o   i ))=1
 
       ∀ i≠j:P   T ( A   T ( o   i ), A   T ( o   j ))&gt;0→ P   T ( A   T ( o   j ), A   T ( o   i ))=0
 
         Q ( o   t )=( o   i /χ ti   |P   T ( o   t   ,o   i )=χ ti )
 
     where A T  is the timestamp attribute (or attributes) and the ordering of events models temporal ordering. The time attribute t i  obeys t i ≦t i+1  for all i. It is treated as a single attribute although could be stored as more than one (such as date, time of day). In the exemplary embodiment a number of sequence extending relations R 1  . . . R n  are defined on appropriate domains. Two events of and of are potentially linked in the same sequence if 
     
       
         
           
             
               min 
                
               
                 ( 
                 
                   
                     
                       Q 
                       T 
                     
                      
                     
                       ( 
                       
                         
                           o 
                           i 
                         
                         , 
                         
                           o 
                           j 
                         
                       
                       ) 
                     
                   
                   , 
                   
                     
                       min 
                       m 
                     
                      
                     
                       ( 
                       
                         
                           R 
                           m 
                         
                          
                         
                           ( 
                           
                             
                               o 
                               i 
                             
                             , 
                             
                               o 
                               j 
                             
                           
                           ) 
                         
                       
                       ) 
                     
                   
                 
                 ) 
               
             
             ≥ 
             μ 
           
         
       
     
     i.e. all required attributes satisfy the specified sequence extending relations to a degree greater than some threshold μ. Thus 
     
       
         
           
             
               potential 
                
               
                 - 
               
                
               
                 link 
                  
                 
                   ( 
                   
                     
                       o 
                       i 
                     
                     , 
                     
                       o 
                       j 
                     
                     , 
                     μ 
                   
                   ) 
                 
               
             
             ↔ 
             
               
                 min 
                  
                 
                   ( 
                   
                     
                       
                         Q 
                         T 
                       
                        
                       
                         ( 
                         
                           
                             o 
                             i 
                           
                           , 
                           
                             o 
                             j 
                           
                         
                         ) 
                       
                     
                     , 
                     
                       
                         min 
                         m 
                       
                        
                       
                         ( 
                         
                           
                             R 
                             m 
                           
                            
                           
                             ( 
                             
                               
                                 o 
                                 i 
                               
                               , 
                               
                                 o 
                                 j 
                               
                             
                             ) 
                           
                         
                         ) 
                       
                     
                   
                   ) 
                 
               
               ≥ 
               μ 
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               linked 
                
               
                 ( 
                 
                   
                     o 
                     i 
                   
                   , 
                   
                     o 
                     j 
                   
                   , 
                   μ 
                 
                 ) 
               
             
             ↔ 
             
               potential 
                
               
                 - 
               
                
               
                 link 
                  
                 
                   ( 
                   
                     
                       o 
                       i 
                     
                     , 
                     
                       o 
                       j 
                     
                     , 
                     μ 
                   
                   ) 
                 
               
             
           
         
       
       
         
           AND 
         
       
       
         
           
             ∄ 
             
               
                 o 
                 k 
               
                
               
                 : 
               
                
               
                 ( 
                 
                   potential 
                    
                   
                     - 
                   
                    
                   
                     link 
                      
                     
                       ( 
                       
                         
                           o 
                           i 
                         
                         , 
                         
                           o 
                           k 
                         
                         , 
                         μ 
                       
                       ) 
                     
                   
                    
                   
                       
                   
                    
                   AND 
                    
                   
                       
                   
                    
                   potential 
                    
                   
                     - 
                   
                    
                   
                     link 
                      
                     
                       ( 
                       
                         
                           o 
                           k 
                         
                         , 
                         
                           o 
                           j 
                         
                         , 
                         μ 
                       
                       ) 
                     
                   
                 
                 ) 
               
             
           
         
       
     
     i.e. two events are linked if they satisfy the specified tolerance and equivalence relations to a degree greater than some threshold μ and there is no intermediate event. 
     In the exemplary embodiment equivalence classes are also defined on some of the domains, used to compare and categorize events from different sequences. An equivalence class on one or more domains is represented by a value from each domain—for example, the relation “hasTheSameParity” defined on natural numbers can contains pairs such as (0, 2), (0, 4), (2, 4), (1, 5), etc. Two equivalence classes (representing the sets of even and odd numbers) can be written [0] and [1] since all elements are linked to either 0 or 1 under the relation “hasTheSameParity”. Similarly, for times denoted by day and hour values, equivalence can be defined for weekday rush hour (e.g. day=“Mon-Fri”, hour=“8,9,17,18”), other-weekday (e.g. day=“Mon-Fri”, hour“8,9,17,18”) and weekend (e.g. day=“Sat,Sun”). These can easily be extended to fuzzy equivalence classes. The equivalence classes partition the objects such that each object belongs to exactly one equivalence class for each domain considered. In the fuzzy case, the sum of memberships in overlapping classes is 1 and at least one membership is assumed to be 0.5 or greater. In creating the graph only the largest membership is considered. In the case of two equal memberships (e.g. 0.5) deterministic procedure is used to choose one equivalence class. Formally, for a specified attribute Ai 
         S ( A   i   ,o   m )={ o   j   |A   i ( o   j )= A   i ( o   m )} 
     and the set of associated equivalence classes (also called elementary concepts) is 
         C   i   ={S ( A   i   ,o   m )| o   m   εO}   
     (for example, time and elapsed time, as described below.) 
     In the propositional case C i  contains just one set, whose elements are the objects for which attribute i is true. In the fuzzy case, elements are equivalent to some degree. Specifying a membership threshold gives a nested set of equivalence relations so that once a membership threshold is known the technique can proceed as in the crisp case. The operation can be extended to multiple attributes. The selected attributes are used to find the “EventCategorisation”. This is an ordered set of equivalence classes arising from one or more attributes (or n-tuples of attributes) 
         B   k   ε{A   1   , . . . ,A   n } 
       EventCategorisation( o   i )=([ B   k ( o   i )| k= 1, . . .  m ]) 
     i.e. each B k  is one or more of the attributes and the event categorization of some object o i  is given by the equivalence classes corresponding to its attribute values. Note that the result is not dependent on the order in which the attributes are processed. This order can be optimized to give fastest performance when deciding which edge to follow from given node. For any set of sequences, a minimal representation of the sequences can be created using a DAG as illustrated in  FIGS. 10 and 11 . The graph is a deterministic finite automaton, with no loops. Each event is represented by a labeled edge. The edge label shows the equivalence classes applicable to the event, referred to as the event categorization below. The source node “S” is a single starting point for all sequences. To ensure a unique end node “F” a dummy “end of sequence” (“#END”) event is appended to all sequences. 
     An example of the exemplary embodiment in use will now be described based on sample data used by the IEEE “Visual Analytics Science and Technology” (VAST) challenge in 2009. The sample data simulates access by employees to badge-locked rooms via numerous entrances. In summary, events in the data set include six attributes: “eventID” as a unique event identifier; “Date”; “Time”; “Emp” or “Employee” as a unique employee identifier as either “10”, “11” or “12”; “Entrance” as a unique identifier of a security entrance as either “b”, corresponding to access to a building, or “c” corresponding to access to a classified section of the building; and “Direction” as an access direction as either “in” or “out”. 
     The table below provides the sample data set. Note that the data has been ordered by employee for ease of reading to identify event sequences, though in use the events would be time-ordered. 
     
       
         
           
               
               
               
               
               
               
             
               
                   
               
               
                 eventID 
                 Date 
                 Time 
                 Employee 
                 Entrance 
                 Direction 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
               
            
               
                 1 
                 jan-2 
                  7:30 
                 10 
                 b 
                 in 
               
               
                 2 
                 jan-2 
                 13:30 
                 10 
                 b 
                 in 
               
               
                 3 
                 jan-2 
                 14:10 
                 10 
                 c 
                 in 
               
               
                 4 
                 jan-2 
                 14:40 
                 10 
                 c 
                 out 
               
               
                 5 
                 jan-2 
                  9:30 
                 11 
                 b 
                 in 
               
               
                 6 
                 jan-2 
                 10:20 
                 11 
                 c 
                 in 
               
               
                 7 
                 jan-2 
                 13:20 
                 11 
                 c 
                 out 
               
               
                 8 
                 jan-2 
                 14:10 
                 11 
                 c 
                 in 
               
               
                 9 
                 jan-2 
                 15:00 
                 11 
                 c 
                 out 
               
               
                 10 
                 jan-3 
                  9:20 
                 10 
                 b 
                 in 
               
               
                 11 
                 jan-3 
                 10:40 
                 10 
                 c 
                 in 
               
               
                 12 
                 jan-3 
                 14:00 
                 10 
                 c 
                 out 
               
               
                 13 
                 jan-3 
                 14:40 
                 10 
                 c 
                 in 
               
               
                 14 
                 jan-3 
                 16:50 
                 10 
                 c 
                 out 
               
               
                 15 
                 jan-3 
                  9:00 
                 12 
                 b 
                 in 
               
               
                 16 
                 jan-3 
                 10:20 
                 12 
                 c 
                 in 
               
               
                 17 
                 jan-3 
                 13:00 
                 12 
                 c 
                 out 
               
               
                 18 
                 jan-3 
                 14:30 
                 12 
                 c 
                 in 
               
               
                 19 
                 jan-3 
                 15:10 
                 12 
                 c 
                 out 
               
               
                   
               
            
           
         
       
     
     First a set of sequence extending relations is defined as a set of equality and permitted transition relations to detect candidate sequences. For a candidate sequence of n events: 
         S   1 =( o   11   ,o   12   ,o   13   , . . . ,o   1n ) 
     the following computed quantities are defined 
       ElapsedTime Δ T   ij =Time( o   ij )−Time( o   ij-1 )
 
       with Δ T   i1 =Time( o   i1 )
 
     and restrictions (for j&gt;1) 
       Date( o   ij )=Date( o   ij-1 ) 
       0&lt;Time( o   ij )−Time( o   ij-1 )≦ T   thresh  
 
       Emp( o   ij )=Emp( o   ij-1 ) 
       (Action( o   ij-1 ),Action( o   ij ))εAllowedActions
 
       where Action( o   ij )=(Entrance( o   ij ),Direction( o   ij )) 
     where the relation “AllowedActions” is given by the table in  FIG. 9 . In the table of  FIG. 9  the first action is indicated by a row and a following action is indicated by a column. 
     These constraints can be summarized as
         events in a single sequence refer to the same employee; and   successive events in a single sequence conform to allowed transitions between locations and are on the same day, within a specified time of each other.       

     A suitable time threshold is chosen, such as T thresh =8. This ensures anything more than 8 hours after the last event is a new sequence. Candidate sequences are identified by applying the sequence extending relations. Any sequence has either been seen before or is a new sequence. From the sample data, candidate sequences are made up of the events:
         1-2-3-4   5-6-7-8-9   10-11-12-13-14   15-16-17-18-19       

     The equivalence class “EventCategorisation” is also defined for comparing events in different sequences: 
     EquivalentAction=IAction 
     For Direction In, EquivalentEventTime={[7],[8], . . . } 
     For Direction Out, EquivalentElapsedTime={[0],[1],[2], . . . } 
     where I is the identity relation and the notation [7] represents the set of all start times from 7:00-7:59, etc. With this definition events 5 and 10 are regarded as equivalent since they both have Entrance=“b”, Direction=“In” and Time in “7:00-7:59”. Formally, 
       EventCategorisation( o   5 )=([ b ,in],[7]) 
       EventCategorisation( o   10 )=([ b ,in],[7]) 
     Similarly, events 7 and 12 are equivalent, as both have Entrance=“c”, Direction=“Out” and ElapsedTime in “3:00-3:59”. Each identified sequence is represented as a graph labeled by its event categorizations and combine multiple sequences into a minimal DAG representing the categorized version of all sequences seen so far, as illustrated in  FIGS. 10 and 11 . 
     Assuming that nodes are denoted by unique numbering, since the graph is deterministic each outgoing edge is unique. An edge can therefore be specified by its start node and its partial event categorization. It is also acceptable to refer to an edge by its partial event categorization label if there is no ambiguity about its start node. Standard definitions are used for “InDegree”, “OutDegree”, “IncomingEdges” and “OutgoingEdges” of a node, giving respectively the number of incoming edges, the number of outgoing edges, the set of incoming edges and the set of outgoing edges. Functions “Start” and “End” can also be applied to an edge in order to find or set start and end nodes respectively. Further, a function “EdgeCategorisation” can be used to find a categorization class for an edge. Further, the function “ExistsSimilarEdge(edge, endnode)” can be defined to return “true” when:
         “edge” has end node “endnode”, event categorization “L” and start node “S 1 ”;   a second, distinct, edge has the same end node and event categorization “L” but a different start node “S 2 ”; and   “S 1 ” and “S 2 ” have the same incoming edges: IncomingEdges(S 1 )=IncomingEdges(S 2 ).       

     If such an edge exists, its start node is returned by the function “StartOfSimilarEdge(edge, endnode)”. The function “CreateNewNode(Incoming, Outgoing)” creates a new node with the specified sets of incoming and outgoing edges. 
     The DAG can be used to identify sequences of events that have already been seen. If a new sequence is observed (i.e. a sequence which differs from each sequence in the graph by at least one event categorization) then it can be added to the graph using an algorithm such as is provided below. Note that the algorithm assumes a graph G=(V, E) such that new nodes are added to the set V and edges are added to/deleted from the set E. The algorithm proceeds in three distinct stages. In the first and second parts, the algorithm moves step-by-step through a new event sequence and a DAG, beginning at a start node “S”. If an event categorization matches an outgoing edge, the algorithm follows that edge to a next node and moves on to the next event in the event sequence. If the new node has more than one incoming edge, the algorithm copies it; the copy takes the incoming edge that was just followed, and the original node retains all other incoming edges. Both copies have the same set of output edges. This part of the algorithm finds other sequences with one or more common starting events. 
     If at some point, a node is reached where there is no outgoing edge matching a next event&#39;s categorization. New edges and nodes for the remainder of the sequence are created, eventually connecting to the end node “F”. Note that as the sequence is new, the algorithm must reach a point at which no outgoing edge matches the next event&#39;s categorization; if this happens at the start node “S” then the first stage is effectively missed. 
     Finally, in the third stage, the algorithm searches for sequences with one or more common ending events. Where possible, the paths are merged.  FIGS. 12, 13 and 14  illustrate the development of the DAG after the first two sequences, then after addition of the third and finally after addition of the fourth sequence. 
     Algorithm ExtendGraph
         Input: Graph G with start node S, end node F, representing the current DAWG (minimal)
           CandidateSequence Q[0-NQ] representing the candidate sequence; each element is an event identifier. The sequence is terminated by #END NB the sequence is not already present in the graph.   
               

     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 Output : updated minimal graph, incorporating the new sequence 
               
               
                   
                 Local variables : Node startNode, newNode, endNode, matchingNode 
               
            
           
           
               
               
            
               
                   
                 Edge currentEdge, matchingEdge 
               
               
                   
                 Categorisation currentCategorisation 
               
               
                   
                 integer seqCounter; 
               
            
           
           
               
               
            
               
                   
                  startNode = S 
               
               
                   
                  seqCounter = 0 
               
               
                   
                 WHILE EventCategorisation(S[seqCounter]) ∈ OutgoingEdges(StartNode) 
               
               
                   
                  currentEdge = (startNode, EventCategorisation(Q[seqCounter]) 
               
               
                   
                  endNode = End (currentEdge) 
               
               
                   
                  IF InDegree (endNode) &gt; 1 
               
               
                   
                  THEN 
               
            
           
           
               
               
            
               
                   
                 newNode = CreateNewNode({currentEdge}, OutgoingEdges(endNode)) 
               
               
                   
                 IncomingEdges(endNode) = IncomingEdges (endNode) − currentEdge 
               
               
                   
                 startNode = newNode 
               
            
           
           
               
               
            
               
                   
                  ELSE 
               
            
           
           
               
               
            
               
                   
                 startNode = endNode 
               
            
           
           
               
               
            
               
                   
                  seqCounter++ 
               
               
                   
                 ENDWHILE 
               
            
           
           
               
               
               
            
               
                   
                 WHILE seqCounter &lt; NQ 
                 // create new path 
               
            
           
           
               
               
            
               
                   
                  currentEdge = (startNode, EventCategorisation (S[seqCounter])) 
               
               
                   
                  startNode = CreateNewNode({currentEdge}, { }) 
               
               
                   
                  seqCounter++ 
               
               
                   
                 ENDWHILE 
               
               
                   
                 currentCategorisation = #END 
               
            
           
           
               
               
               
            
               
                   
                 currentEdge = (startNode, #END ) 
                 // last edge, labelled by #END 
               
            
           
           
               
               
            
               
                   
                 IncomingEdges(F) = IncomingEdges (F) + currentEdge 
               
               
                   
                 endNode = F 
               
               
                   
                 WHILE nextEdgeSet contains exactly one element (i.e currentEdge) 
               
            
           
           
               
               
            
               
                   
                 AND ExistsSimilarEdge(currentEdge, endnode) 
               
            
           
           
               
               
            
               
                   
                 matchingNode = StartOfSimilarEdge(currentEdge, endnode) 
               
               
                   
                 startNode = Start (currentEdge) 
               
               
                   
                 IncomingEdges(endNode) = IncomingEdges (endNode) − {currentEdge} 
               
               
                   
                 nextEdgeSet = IncomingEdges (startNode) 
               
               
                   
                 IncomingEdges (matchingNode) = nextEdgeSet ∪ IncomingEdges 
               
            
           
           
               
            
               
                 (matchingNode) 
               
            
           
           
               
               
            
               
                   
                 endNode = matchingNode 
               
               
                   
                 currentEdge ∈ edgeSet //choose any element,“while” loop terminates if&gt;1 
               
               
                   
                 END WHILE 
               
               
                   
                   
               
            
           
         
       
     
     Algorithm ReduceGraph
         Input: Graph G, start node S, end node F, the current DAWG (minimal)
           Sequence C[0-NQ] representing the sequence of event categories to be removed. Each element is an event categorization. The sequence is terminated by #END NB the sequence must be present in the graph and there must be at least one sequence in the graph after removal.   
               

     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 Output : updated minimal graph, excluding the removed sequence 
               
               
                   
                 Local variables : Node startNode, endNode 
               
            
           
           
               
               
            
               
                   
                 Edge currentEdge, matchingEdge 
               
               
                   
                 Categorisation currentCategorisation 
               
               
                   
                 integer seqCounter; 
               
            
           
           
               
               
            
               
                   
                 startNode = S 
               
               
                   
                 seqCounter = 0 
               
               
                   
                 currentEdge = (startNode, C[0]) 
               
               
                   
                 endNode = End(currentEdge) 
               
               
                   
                 WHILE endNode ≠ F 
               
               
                   
                  WHILE OutDegree(startNode) &gt; 1 
               
            
           
           
               
               
            
               
                   
                 AND InDegree(endNode) == 1 
               
               
                   
                 AND OutDegree(endNode) == 1 
               
            
           
           
               
               
            
               
                   
                 currentEdge = (endNode, C[seqCounter]) 
               
               
                   
                 seqCounter++ 
               
            
           
           
               
               
            
               
                   
                  END WHILE 
               
               
                   
                  IF (InDegree(endNode) &gt; 1) 
               
            
           
           
               
               
            
               
                   
                 delete path from startNode to endNode 
               
            
           
           
               
               
            
               
                   
                  startNode = endNode 
               
               
                   
                  currentEdge = (startNode, C[seqCounter]) 
               
               
                   
                  endNode = End(currentEdge) 
               
               
                   
                  seqCounter++ 
               
               
                   
                 END WHILE 
               
               
                   
                   
               
            
           
         
       
     
     Insofar as embodiments described are implementable, at least in part, using a software-controlled programmable processing device, such as a microprocessor, digital signal processor or other processing device, data processing apparatus or system, it will be appreciated that a computer program for configuring a programmable device, apparatus or system to implement the foregoing described methods is envisaged as an aspect of embodiments. The computer program may be embodied as source code or undergo compilation for implementation on a processing device, apparatus or system or may be embodied as object code, for example. 
     Suitably, the computer program is stored on a carrier medium in machine or device readable form, for example in solid-state memory, magnetic memory such as disk or tape, optically or magneto-optically readable memory such as compact disk or digital versatile disk etc., and the processing device utilizes the program or a part thereof to configure it for operation. The computer program may be supplied from a remote source embodied in a communications medium such as an electronic signal, radio frequency carrier wave or optical carrier wave. Such carrier media are also envisaged as aspects of embodiments. 
     It will be understood by those skilled in the art that, although embodiments have been described in relation to the above described example embodiments, every embodiment is not limited thereto and that there are many possible variations and modifications which fall within the scope of the claims. 
     The scope of the present invention includes any novel features or combination of features disclosed herein. The applicant hereby gives notice that new claims may be formulated to such features or combination of features during prosecution of this application or of any such further applications derived therefrom. In particular, with reference to the appended claims, features from dependent claims may be combined with those of the independent claims and features from respective independent claims may be combined in any appropriate manner and not merely in the specific combinations enumerated in the claims.