Method and apparatus for determining a set of large sequences from an electronic data base

• US 20040220916A1
• Filed: 09/26/2003
• Published: 11/04/2004
• Est. Priority Date: 09/30/2002
• Status: Active Grant

• Current Assignee: prudsys AG (Fujitsu Limited)
• Original Assignee: prudsys AG (Fujitsu Limited)
• Inventors: Thess, Michael, Ittner, Andreas
• Granted Patent: US 7,209,910 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The instant invention relates to a method of and an apparatus for determining a set of large sequences from an electronic data base comprising a set D={d1, . . . , dn} of transactions di (1≦i≦n) in a computer system with an implemented query module, each of the large sequences on the set D of transactions di having a support value greater than or equal to a given support value S, each of the transactions di of the set D being a sequence of items of a record E={e1, . . . , em} of items ej (1≦j≦m). A set Lk (k>2) of large sequences is determined from the set D of transactions, the large sequences of set Lk each comprising exactly k items of record E in a respective order R_LK, and an associated support value S_LK on the sequence D of transactions each being greater than or equal to the given support value S, and nothing but sequences comprising two of the large sequences of set Lk−1, as partly overlapping partial sequences, with the respective order R_LK−1, being taken into account in determining set Lk.

Claims

1. A method of determining a set of large sequences from an electronic data base comprising a set D={d1, . . . , dn} of transactions di (1≦

i≦

n) in a computer system with an implemented query module, each of the large sequences on the set D of transactions di having a support value greater than or equal to a given support value S, each of the transactions di of the set D being a sequence of items of a record E={e1, . . . , em} of items ej (1≦

j≦

m) and the method comprising the following steps;

a) determining a set L1 of large sequences from the set D of transactions, the large sequences of set L1 each comprising exactly one item of the record E, and an assigned support value S_L1 on the sequence D of transactions each being greater than or equal to the given support value S;

b) determining a set L2 of large sequences from the set D of transactions, the large sequences of set L2 each comprising exactly two items of the record E in a respective order R_L2, and an assigned support value S_L2 on the set D of transactions each being greater than or equal to the given support value S, and nothing but sequences comprising one of the large sequences of set L1, as a partial sequence, being taken into account in determining set L2;

c) determining a set Lk (k>

2) of large sequences from the set D of transactions, the large sequences of set Lk each comprising exactly k items of record E in a respective order R_LK, and an assigned support value S_LK on the sequence D of transactions each being greater than or equal to the given support value S, and nothing but sequences comprising two of the large sequences of set Lk−

1, as partly overlapping partial sequences, with the respective order R<sub>LK−

1</sub>, being taken into account in determining set Lk; and

d) repeating step c) for k=k+1 and terminating the repetition of step c) when a given termination condition is fulfilled.

2. The method as claimed in claim 1, wherein the set D of transactions is searched for candidate sequences which comprise two of the large sequences of set L1 or set Lk−

1, respectively, as partly overlapping partial sequences, in determining set L2 in step b) and set Lk in step c), respectively, and wherein an assigned support value counter is registered for each candidate sequence found for the first time, and the assigned support value counter is incremented when the respective candidate sequence is determined again in searching the set D of transactions.

3. The method as claimed in claim 1, wherein:

the set D of transactions is searched for candidate sequences comprising one of the large sequences of set L1, as a partial sequence, when determining set L2 in step b), and an assigned support value counter is registered for each candidate sequence found for the first time, and the assigned support value counter is incremented when the respective candidate sequence is determined again in searching the set D of transactions; and

a candidate set of sequences is formed, when determining set Lk (k>

2) in step c), which set comprises all combinations in pairs of the sequences of set Lk−

1, and of the set D of transactions those transactions are defined which comprise at least one sequence of the candidate set, and the support value is determined for those sequences of the candidate set for which a transaction was found that comprised this sequence.

4. The method as claimed in claim 2 or 3, wherein a display value is generated and updated for each assigned support value counter to indicate the transaction for which the assigned support value counter was last incremented.

5. The method as claimed in claim 3 or 4, wherein only those sequences of the candidate set of sequences corresponding to all combinations in pairs of the sequences of set L1 are taken into account of which the first item lies within a given range of values.

6. A computer program product for determining a set of large sequences from an electronic data base comprising a set D={d1, . . . , dn} of transactions di (1≦

i≦

n) in a computer system with an implemented query module, each of the large sequences on the set D of transactions di having a support value greater than or equal to a given support value S, each of the transactions di of the set D being a sequence of items of a record E={e1, . . . , em} of items ej (1≦

j≦

m) and the product comprising the following means;

a) means recorded on an electronic storage medium for determining a set L1 of large sequences from the set D of transactions, the large sequences of set L1 each comprising exactly one item of the record E, and an assigned support value S_L1 on the sequence D of transactions each being greater than or equal to the given support value S;

b) means recorded on the electronic storage medium for determining a set L2 of large sequences from the set D of transactions, the large sequences of set L2 each comprising exactly two items of the record E in a respective order R_L2, and an assigned support value S_L2 on the set D of transactions each being greater than or equal to the given support value S, and nothing but sequences comprising one of the large sequences of set L1, as a partial sequence, being taken into account in determining set L2;

c) means recorded on the storage medium for determining a set Lk (k>

2) of large sequences from the set D of transactions, the large sequences of set Lk each comprising exactly k items of record E in a respective order R_LK, and an assigned support value S_LK on the sequence D of transactions each being greater than or equal to the given support value S, and nothing but sequences comprising two of the large sequences of set Lk−

1, as partly overlapping partial sequences, with the respective order R<sub>LK−

1</sub>, being taken into account in determining set Lk; and

d) means recorded on the electronic storage medium for repeating step c) for k=k+1 and terminating the repetition of step c) when a given termination condition is fulfilled.

7. An integrated sequential analysis system, comprising:

an electronic data base comprising a set D={d1, . . . , dn} of transactions di (1≦

i≦

n), each of the large sequences on the set D of transactions di having a support value greater than or equal to a given support value S, each of the transactions di of the set D being a sequence of items of a record E={e1, . . . , em} of items ej (1≦

j≦

m);

a query module comprising a query means coupled to the data base and a processing means for detecting query parameters and generating queries to the query means;

means for determining a set L1 of large sequences from the set D of transactions, the large sequences of set L1 each comprising exactly one item of the record E, and an assigned support value S_L1 on the sequence D of transactions each being greater than or equal to the given support value S;

means for determining a set L2 of large sequences from the set D of transactions, the large sequences of set L2 each comprising exactly two items of the record E in a respective order R_L2, and an assigned support value S_L2 on the set D of transactions each being greater than or equal to the given support value S, and nothing but sequences comprising one of the large sequences of set L1, as a partial sequence, being taken into account in determining set L2;

means for determining a set Lk (k>

2) of large sequences from the set D of transactions, the large sequences of set Lk each comprising exactly k items of record E in a respective order R_LK, and an assigned support value S_LK on the sequence D of transactions each being greater than or equal to the given support value S, and nothing but sequences comprising two of the large sequences of set Lk−

1, as partly overlapping partial sequences, with the respective order R<sub>LK−

1</sub>, being taken into account in determining set Lk; and

means for repeating step c) for k=k+1 and terminating the repetition of step c) when a given termination condition is fulfilled.