 |
|
|
|
|
|
 Title: |
US5819266:
System and method for mining sequential patterns in a large database
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Agrawal, Rakesh; San Jose, CA
Srikant, Ramakrishnan; San Jose, CA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1998-10-06
/ 1995-03-03
|
| Application Number: |
US1995000398640
|
| IPC Code: |
Advanced:
G06F 12/00;
G06F 17/30;
G06F 19/00;
G06Q 30/00;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06Q30/00A;
|
| U.S. Class: |
Current:
707/006;
Original:
707/006;
|
| Field of Search: |
395/600,6
707/006
|
| Priority Number: |
| 1995-03-03 |
US1995000398640 |
|
| Abstract: |
A system and method for mining databases includes a computer-implemented program which identifies patterns of transaction sequences that are stored in a database and which recur in the database with a user-defined regularity. The invention first identifies which sequences are large, i.e., which recur with the defined regularity, and then determines which sequences are maximal, i.e., which large sequences are not subsets of other large sequences. The set of maximal large sequences is returned to the user to indicate recurring purchasing patterns over time.
|
| Attorney, Agent or Firm: |
Baker Maxham Jester & Meador ;
|
| Primary / Asst. Examiners: |
Amsbury, Wayne;
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Designated Country: |
DE FR GB
|
| Family: |
Show 8 known family members
|
First Claim:
Show all 33 claims |
We claim:
1. A computer program product, including:
- a program storage device readable by a digital processing apparatus; and
- a program of instructions tangibly embodied on the program storage device and executable by the digital processing apparatus to perform method steps for identifying sequential patterns in transaction sequences which are stored in a database, each sequence comprising a plurality of temporally-spaced transactions characterized by one or more itemsets, the method steps comprising:
- (a) entering an itemset into a set of large itemsets when the number of times the itemset is present in the database exceeds a minimum support value;
- (b) generating a transformed set of transaction sequences by discarding a transaction when the transaction does not include an itemset in the set of large itemsets and discarding a transaction sequence ("sequence") when the sequence does not include an itemset in the set of large itemsets;
- (c) defining a forward set of large sequences and concatenating sequences in the forward set of large sequences to generate a next set of candidate large sequences;
- (d) comparing each sequence in the next set of candidate large sequences to the sequences in the transformed set of sequences to determine the number of times the candidate large sequence is present in the transformed set of sequences;
- (e) entering a candidate large sequence into a next forward set of large sequences when the number of times the candidate large sequence is present in the transformed set of sequences is greater than the minimum support value; and
- (f) outputting the set of maximal large sequences for identifying particular transaction sequences over time.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 32 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G96-395197
|
| Other References: |
R. Agrawal et al., "Mining Association Rule Between Sets of Items in Large Databases", Proc. 1993 ACM Sigmod Conf., pp. 207-216, 1993.
R. Agrawal et al., "Fast Algorithms for Mining Association Rules", Proceedings of the 1994 VLDB Conference, pp. 487-499, 1994.
M. Houtsma et al., "Set-Oriented Mining for Association Rules in Relational Databases", Proc. 11th Conference on Data Engineering, pp. 25-33, 1995.
H. Mannila et al., "Improved Methods for Finding Association Rules", Pub. No. C-1993-65, 20 pages, Univ. Helsinki, 1993.
J.J. Bernardo et al., Sequencing Rules for Productivity Improvements, Pub. Decis, Sci., V. 22, #3, pp. 620-634, Jul.-Aug., 1991.
(15 pages)
Cited by 2 patents
[ISI abstract]
M.D. Merrill, et al., Instructional Transaction Shells: Responsibilities, Methods, and Parameters, Pub. Educ. Technol. V. 32, #2, pp. 5-25, Feb. 1992.
W.D. Hopkins, et al., "Sequential Pattern Recognition Machine", IBM TDB, vol. 16, No. 1, pp. 97-99, Jun. 1973.
O. Klaassen, "Modeling Data Base Reference Behavior", Computer Performance Evaluation, G. Balbo, et al, eds, pp. 47-60, 1992.
Wang et al, Combinational Pattern Discovery for Scientfic Data: Some Preliminary Results, Proc Acm Sigmod Conf. on Management of Data, Minneapolis, May, 1994.
Agrawal et al: "Mining Sequential Patterns", Proceedings of the 11th International Conference on Data Engineering, Mar. 6, 1995, Taipei, pp. 3-14, XP000670556.
Faloutsos et al: "Fast Subsequence Matching in Time-Series Databases" 1994 ACM Sigmod International Conference on Management of Data, vol. 23, No. 2, May 1994, Minneapolis, MN, pp. 419-429, XP002048519.
Agrawal et al: "Database Mining: A Performance Perspective", IEEE Transactions on Knowledge and Data Engineering, vol. 5, No. 6, Dec. 1993, USA, pp. 914-925, XP002048520.
(12 pages)
Cited by 35 patents
[ISI abstract]
European Search Report, Sep. 01, 1998, Berlin 28 Nov. 1997, Examiner J. Nicholls.
|
|
 Nominate this for the Gallery...
|
|
