Sequence online analytical processing system

• US 8,160,996 B2
• Filed: 02/02/2009
• Issued: 04/17/2012
• Est. Priority Date: 02/02/2009
• Status: Active Grant

• Current Assignee: Versitech Limited (Government of Hong Kong Special Administrative Region)
• Original Assignee: Versitech Limited (Government of Hong Kong Special Administrative Region), Hong Kong Polytechnic University
• Inventors: Kao, Benjamin Chi Ming, Ho, Wai-Shing, Chui, Chun-Kit, Lee, Sau-Dan, Lo, Eric Chi Lik
• Primary Examiner(s): Wu, Yicun
• Application Number:
  US12/364,265
• Publication Number:
  US 20100198777A1
• Time in Patent Office: 1,170 Days
• Field of Search: 707600-604, 705/10
• US Class Current: 707/600
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A sequence online analytical processing (S-OLAP) system 50 for analysing an event database (41) storing events (12), the system (50) comprising: an S-OLAP engine (53) to compute an S-cuboid (49) for a query on the event database (41); a sequence query engine (54) to form part of the S-cuboid (49) by performing the steps of: selection, clustering, sequence formation and sequence grouping; a cuboid repository (52) to store computed S-cuboids (49) and to be searched by the S-OLAP engine (53) for an S-cuboid query to determine whether an S-cuboid has previously been computed; and a sequence cache (56) to cache constructed sequence groups.

Claims

1. A sequence online analytical processing (S-OLAP) system for analysing an event database storing events, each event consisting of at least one dimension and measure, the system comprising:

a sequence cuboid (S-cuboid) builder to build an S-cuboid, the S-cuboid defining a logical view of sequences of the events at a predetermined degree of summarization;

wherein the S-cuboid built by the S-cuboid builder is specified by;

a WHERE clause to select events of interest from the events stored in the database;

a CLUSTER BY clause to specify those of the selected events of interest that are elements of respective sequences to be clustered together, thereby forming one or more clusters of events;

a SEQUENCE BY clause to form sequences from respective clusters of events;

a SEQUENCE GROUP BY clause to group those of the sequences whose events share a common dimension value, thereby forming one or more sequence groups;

a CUBOID BY clause to specify the logical view of the sequences of the events, the CUBOID BY clause comprising (i) a pattern template to define a format of substring/subsequence patterns to be matched against the sequences of events, (ii) a cell restriction to define how a response and content of the sequence of events should be assigned to a cell of the S-cuboid when a sequence of events contains multiple occurrences of a cell'"'"'s pattern, and (iii) a matching predicate to select sequences of interest; and

at least one aggregation function to be applied to sequences of the events in each cell of the S-cuboid.

2. The system according to claim 1, wherein each attribute in the CLUSTER BY clause is associated with an abstraction level in a concept hierarchy.

3. The system according to claim 1, wherein the pattern template consists of a sequence of symbols each associated with a domain of values, and the domain of values is specified as a domain of an attribute at a predetermined abstraction level.

4. The system according to claim 3, wherein the pattern template instantiates a pattern for each cell of the S-cuboid based upon a set of values associated with the sequence of symbols.

5. The system according to claim 1, wherein the cell restriction is specified by a keyword.

6. The system according to claim 1, wherein the matching predicate is specified by introducing a sequence of event placeholders after the cell restriction.

7. The system according to claim 1, further comprising six S-OLAP operations:

APPEND to add a pattern symbol after a last pattern symbol of the pattern template,

PREPEND to add a pattern symbol before a first pattern symbol of the pattern template,

DE-TAIL to remove the last pattern symbol from the pattern template,

DE-HEAD to remove the first pattern symbol from the pattern template,

PATTERN-ROLLUP (P-ROLL-UP) to modify an abstraction level of a pattern dimension by moving the abstraction level of the pattern dimension one level up in a concept hierarchy, and

PATTERN-DRILL-DOWN (P-DRILL-DOWN) to modify the abstraction level of the pattern dimension by moving the abstraction level of the pattern dimension one level down in the concept hierarchy.

8. The system according to claim 1, wherein respective sequences are each characterized by a logical ordering among their respective events.

9. The system according to claim 1, wherein a set of S-cuboids form a lattice (S-cube) and an S-cuboid at a higher level in the lattice contains (i) fewer global and/or pattern dimensions or (ii) dimensions at a higher level of abstraction.

10. The system according to claim 1, wherein the S-cuboid is computed by associating each cell in the S-cuboid with a counter and for each sequence of events, cells whose associated patterns are contained in the sequence are determined and their corresponding counter is incremented by one.

11. The system according to claim 1, wherein the S-cuboid is computed by creating a set of inverted indices by pre-processing data offline, and the set of inverted indices are used to dynamically assemble and compute the cells of the S-cuboid.

12. A method for building a sequence cuboid (S-cuboid) for a database query of an event database, the method comprising:

selecting events from the event database;

clustering the selected events;

forming sequences from the clustered events; and

grouping the sequences into sequence groups for sequences whose events share a common dimension value, further comprising grouping patterns to specify a logical view of results from the database query according to a user defined pattern template, cell restriction and a matching predicate, wherein (i) the user defined pattern template defines a format of substring/subsequence patterns to be matched against the sequences of events, (ii) the cell restriction defines how a response and content of the sequences should be assigned to a cell when a sequence of events contains multiple occurrences of a cell'"'"'s pattern, and (iii) the matching predicate is used to select sequences of interest.

13. The method according to claim 12, further comprising aggregating the results of the database query according to a selected aggregation function.

14. The method according to claim 12, further comprising returning an n-dimensional array, wherein n indicates a number of pattern dimensions.

15. A sequence online analytical processing (S-OLAP) system for analysing an event database storing events, the system comprising:

an S-OLAP engine to compute an S-cuboid for a query on the event database; and

a sequence query engine to form part of the S-cuboid by performing the steps of;

selection, clustering, sequence formation, sequence grouping, and grouping patterns to specify a logical view of results from the query according to a user defined pattern template, cell restriction and a matching predicate, wherein (i) the user defined pattern template defines a format of substring/subsequence patterns to be matched against a sequences of events, (ii) the cell restriction defines how a response and content of the sequences should be assigned to a cell when a sequence of events contains multiple occurrences of a cell'"'"'s pattern, and (iii) the matching predicate is used to select sequences of interest.

16. The system according to claim 15, further comprising a cuboid repository to store computed S-cuboids, the cuboid repository to be searched by the S-OLAP engine in response to an S-cuboid query to determine whether an S-cuboid has previously been computed.

17. The system according to claim 15, further comprising a sequence cache to cache constructed sequence groups.

18. The system according to claim 15, further comprising auxiliary data structures to compute the query online.

19. The system according to claim 15, further comprising a user interface to assist a user in specifying the S-cuboid.