SEQUENCE ONLINE ANALYTICAL PROCESSING SYSTEM

• US 20100198777A1
• Filed: 02/02/2009
• Published: 08/05/2010
• Est. Priority Date: 02/02/2009
• Status: Active Grant

• Current Assignee: Versitech Limited (Government of Hong Kong Special Administrative Region)
• Original Assignee: University of Hong Kong (Government of Hong Kong Special Administrative Region), Hong Kong Polytechnic University
• Inventors: LO, Eric Chi Lik, Chui, Chun-Kit, Ho, Wai-Shing, Kao, Benjamin Chi Ming, Lee, Sau-Dan
• Granted Patent: US 8,160,996 B2
• Time in Patent Office: Days
• US Class Current: 707/601
• 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 the sequence data 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;

a CLUSTER BY clause to specify events that are elements of a sequence to be clustered together;

a SEQUENCE BY clause to form a sequence from a cluster of events;

a SEQUENCE GROUP BY clause to group sequences whose events share the same dimension values and form a sequence group;

a CUBOID BY clause to specify the logical view of the sequence data; and

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

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 CUBOID BY clause comprises:

a pattern template to define a format of the substring/subsequence patterns to be matched against the data sequences;

a cell restriction to define how a response when a data sequence contains multiple occurrences of a cell'"'"'s pattern and the content of the data shequence should be assigned to the cell; and

a matching predicate to select data sequences of interest.

4. The system according to claim 3, 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 the domain of an attribute at predetermined abstraction level.

5. The system according to claim 4, wherein the pattern template instantiates a pattern by a set of values that are associated with the symbols, and each cell is associated with a pattern.

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

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

8. The system according to claim 3, further comprising six S-OLAP operations:

APPEND to add a pattern symbol to the end of a pattern template,

PREPEND to add a pattern symbol to the front of a pattern template,

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

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

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

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

9. The system according to claim 1, wherein the events form a sequence if there is a logical ordering among a set of events.

10. The system according to claim 1, wherein a set of S-cuboids form a lattice (S-cube) and an S-cuboid at a coarser granularity is at a higher level in the lattice containing fewer global and/or pattern dimensions or the dimensions are at a higher level of abstraction.

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

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

13. 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 sequences whose events share the same dimensions'"'"' values.

14. The method according to claim 13, 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.

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

16. The method according to claim 13, further comprising returning an n-dimensional array where n is the number of pattern dimensions.

17. 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 and sequence grouping.

18. The system according to claim 17, further comprising a cuboid repository to store computed S-cuboids and to be searched by the S-OLAP engine for an S-cuboid query to determine whether an S-cuboid has previously been computed.

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

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

21. The system according to claim 17, further comprising a user interface to assist a user in specifying an S-cuboid.