Distributed OLAP-based association rule generation method and system

• US 7,007,020 B1
• Filed: 03/10/2000
• Issued: 02/28/2006
• Est. Priority Date: 03/10/2000
• Status: Expired due to Term

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Hsu, Meichun, Chen, Qiming, Dayal, Umeshwar, Deng, Jie
• Primary Examiner(s): Jeanty, Romain
• Application Number:
  US09/524,140
• Time in Patent Office: 2,181 Days
• Field of Search: 707/6, 707/3, 707/2, 705/8, 705/10, 705/7, 395/1, 706/6, 706/12, 706/45
• US Class Current: N/A
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A distributed OLAP-based method and system for generating association rules. An architecture is provided for processing transaction data to generate summary information, customer profiles, and association rules. The distributed system includes at least two layers of data warehouse/OLAP stations: local data-warehouse OLAP stations (LDOSs) and a global data-warehouse OLAP station (GDOS). The LDOSs perform local data mining and summarization, and the GDOS merges, mines, and summarizes the input data received from LDOSs. The summarized data is then utilized by the GDOS to generate association rules that can be provided to the LDOSs for business planning.

Claims

1. A method for generating association rules comprising:

in a processing system, receiving a volume cube that represents the purchase volume of customers;

in the processing system, generating scoped association cubes, a population cube and a base cube based on the volume cube, wherein the scoped association cubes comprise a plurality of bases from distinct data sources; and

in the processing system, deriving a confidence cube and a support cube of an association rule based on the association cube, population cube, and the base cube,

wherein said volume cube, association cube, population cube, base cube, and confidence cube comprise multi-dimensional data structures that have elements comprising one or more aggregated dimensions and that are processed in a multi-dimensional database.

2. The method of claim 1 wherein generating an association cube, a population cube and a base cube based on the volume cube comprises generating an association cube that has at least two levels and at least two dimensions.

3. The method of claim 1 wherein generating an association cube, a population cube and a base cube based on the volume cube comprises generating a scoped association rule cube and wherein deriving a confidence cube and a support cube of an association rule based on th association cube, population cube, and the base cube comprises deriving a confidence cube and a support cube of a scoped association rule based on the association cube, population cube, and the base cube.

4. The method of claim 1 wherein generating an association cube, a population cube and a base cube based on the volume cube comprises:

generating an association rule with conjoint items cube;

wherein deriving a confidence cube and a support cube of an association rule based on the association cube, population cube, and the base cube comprises;

deriving a confidence cube and a support cube of an association rule with conjoint items based on the association cube, population cube, and the base cube.

5. The method of claim 1 wherein generating an association cube, a population cube and a base cube based on the volume cube comprises:

generating a functional association rule cube;

wherein deriving a confidence cube and a support cube of an association rule based on the association cube, population cube, and the base cube comprises;

deriving a confidence cube and a support cube of a functional association rule based on the association cube, population cube, and the base cube.

6. The method of claim 1 wherein steps receiving, generating and deriving are implemented by utilizing a OLAP programming.

7. The method of claim 1 wherein receiving comprises:

receiving a first volume cube that represents the purchase volume of customers for a first region;

receiving a second volume cube that represents the purchase volume of customers for a second region; and

wherein generating comprises;

generating an association cube, a population cube and a base cube based on the first volume cube and the second volume cube.

8. A data processing system comprising:

a plurality of local stations (“

LDOSs”

) having a local computation engine for mining and summarizing the local transaction data and for generating local customer profile cubes; and

at least one global station (“

GDOS”

), coupled to the plurality of the local stations, the global station having a global computation engine for receiving the local customer profiles, merging and mining the local profile cubes, and generating global profile cubes and scoped association rules, the scoped association rules comprising a plurality of bases from distinct data sources and based on said local profile cubes, and providing the global profile cubes and the association rules to said plurality of LDOSs,

wherein said local customer profile cubes and global profile cubes comprise multi-dimensional data structures that have elements comprising one or more aggregated dimensions and that are processed in a multidimensional database.

9. The system according to claim 8, wherein each of said plurality of LDOSs comprises a local data warehouse and at least one local OLAP server,

the local data warehouse being adapted to receive and store said transaction data,

wherein the local computation engine builds the local profile cubes that contains at least partial information regarding customer profiling by periodically mining new transactions flowing into said local data warehouse and deriving patterns for local analysis, said local computation engine also being adapted to incrementally update F said local profile cubes.

10. The system according to claim 9 wherein said local data warehouse receives and stores transaction data in a first predetermined interval and wherein said local OLAP engine generates said local profile cubes in a second predetermined interval.

11. The system according to claim 9 wherein said GDOS comprises a global data warehouse and at least one global OLAP server,

the global data warehouse for receiving and storing the local profile cubes,

the global computation engine for combining summary information from each of said LDOSs to build and incrementally update said global profile cubes and association rules, and for providing feedback to said plurality of LDOSs.

12. The system according to claim 11, wherein said local and global profile cubes comprise information of a plurality of customers, said information being derived from transaction data with said customers as stored by said local and global data warehouses, said profiling information specifying at least the following:

kind, product, customer, merchant, time and area.

13. The system according to claim 12, wherein:

said local profile cubes are maintained at LDOS and said global profile cubes are maintained at GDOS, each of said local profile cubes being populated by mapping values in transaction data records into each dimension of said profile cube, each of said global profile cubes being retrieved and updated by merging appropriate local profile cubes.

14. The system according to claim 12, wherein said profile cubes are used to derive a plurality of shopping pattern cubes, said shopping pattern cubes comprising:

shopping behavior of at least one customer;

shopping patterns based on probability distribution;

shopping patterns based on volume.

15. The system according to claim 8, wherein said association rules comprise:

scoped association rule with different bases, each of the bases being said scoped association rule'"'"'s population over which said scoped association rule is defined;

multidimensional association rule with “

customer”

being its base, products”

being its item, and “

merchant,”

“

area” and

“

time”

being underlying features of said multidimensional association rule; and

multilevel association rule with its features being represented at multiple levels.

16. The system according to claim 15, wherein said association rules are mined by:

converting a volume cube into an association cube, a base cube and a population cube, said volume cube representing purchase volumes of customers dimensioned by item, base and feature;

deriving a support cube based on said base cube and said association cube; and

deriving a confidence cube based on said association cube and said population cube.

17. A method of distributed data processing using on-line analytical processing (“

OLAP”

) engines for use with transaction data in electronic commerce, comprising the steps of;

mining and summarizing, using a plurality of local servers (“

LDOSs”

), said transaction data to generate local profile cubes;

merging and mining, using at least one global server (“

GDOS”

), said local profile cubes received from said plurality of LDOSs to generate global profile cubes and scoped association rules based on said local profile cubes, wherein the scoped association rules comprise a plurality of bases from distinct data sources; and

feeding back said global profile cubes and association rules from said GDOS to said plurality of LDOSs for their business applications,

wherein said local profile cubes and global profile cubes comprise multi-dimensional data structures that have elements comprising one or more aggregated dimensions and that are processed in a multi-dimensional database.

18. The method according to claim 17, wherein the step of mining and summarizing, using LDOSs, comprises:

receiving and storing said transaction data using a local data warehouse,

building, using a local OLAP engine, said local profile cubes containing at least partial information regarding customer profiling by periodically mining new transactions flowing into said local data warehouse and deriving patterns for local analysis; and

incrementally updating said local profile cubes with the new transactions.

19. The method according to claim 18 wherein the step of receiving and storing is in a first predetermined interval and wherein the step of building said local profiles is in a second predetermined interval.

20. The method according to claim 18 wherein said step of receiving, merging and mining by using the GDOS comprises:

storing said local profile cubes using a global data warehouse;

combining using a global OLAP engine summary information from each of said LDOSs to build and incrementally update said global profile cubes and association rules; and

feeding back said global profile cube and association rules.

21. The method according to claim 20 wherein said local and global profile cubes include information of a plurality of customers, said information being derived from transaction data with said customers as stored by said local and global data warehouses, said profiling information specifying at least the following:

kind, product, customer, merchant, time and area.

22. The method according to claim 21 wherein said local profile cubes are maintained at LDOS and said global profile cubes are maintained at GDOS, each of said local profile cubes being populated by mapping values in transaction data records into each dimension of said profile cube, each of said global profile cubes being retrieved and updated by merging appropriate local profile cubes.

23. The method according to claim 21 wherein said profile cubes, are used to derive a plurality of shopping pattern cubes, said shopping pattern cubes comprising:

shopping behavior of at least one customer;

shopping patterns based on probability distribution;

shopping patterns based on volume.

24. The method according to claim 17 wherein said association rules comprise:

scoped associate rule with different bases, each of the bases being said scoped association rule'"'"'s population over which said scoped association rule is defined;

multidimensional association rule with “

customer”

being its base, “

products”

being its item, and “

merchant,”

“

area” and

“

time”

being underlying features of said multidimensional association rule; and

multilevel association rule with its features being represented at multiple levels.

25. The method according to claim 24, wherein said association rules are mined by:

converting a volume cube into an association cube, a base cube and a population cube, said volume cube representing purchase volumes of customers dimensioned by item, base and feature;

deriving a support cube based on said base cube and said association cube; and

deriving a confidence cube based on said association cube and said population cube.

26. A computer-implemented method for generating association rules, comprising:

in the processing system, generating scoped association cubes, a population cube and a base cube based on a volume cube that represents a purchase volume of customers, wherein the scoped association cubes comprise a plurality of bases from distinct data sources; and

in the processing system, deriving a confidence cube and a support cube of an association rule based on the association cube, population cube, and the base cube.

27. The method of claim 26 wherein generating scoped association cubes, a population cube, and a base cube based on a volume cube comprises generating an association cube that has at least two levels and at least two dimensions.

28. A system, comprising:

a plurality of local stations having a local computation engine for mining and summarizing the local transaction data and for generating local customer profile cubes; and

at least one global station coupled to the plurality of the local stations, the global station having a global computation engine for receiving the local customer profiles, merging and mining the local profile cubes, and generating global profile cubes and scoped association rules, the scoped association rules comprising a plurality of bases from distinct data sources and based on said local profile cubes.

29. The system of claim 28 wherein the local and global stations comprise computer servers adapted to perform aggregations on the local customer profile cubes.