Method and apparatus for storing, retrieving, and processing multi-dimensional customer-oriented data sets

• US 6,182,060 B1
• Filed: 04/08/1998
• Issued: 01/30/2001
• Est. Priority Date: 04/15/1997
• Status: Expired due to Term

• Current Assignee: Fidelity Information Services, LLC (Fidelity National Information Services Incorporated)
• Original Assignee: NuEdge Systems, LLC
• Inventors: Hedgcock, Robert, Naughton, Jeffrey F., Keane, Timothy J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): TRINH, WILLIAM B
• Application Number:
  US09/057,001
• Time in Patent Office: 1,028 Days
• Field of Search: 707/1, 707/7, 707/503, 707/962, 705/75, 705/5, 705/1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Method and apparatus for storing, retrieving, and processing customer-oriented data sets in which relatively large sets of customers and their transactions or the like may be quickly and efficiently analyzed. A multi-dimensional access structure is utilized in which each cell representing one dimension element or a combination of dimension elements may include a list of customers who have made purchases or other transactions associated with that cell. Each customer record in a list may summarize predetermined information pertaining to that customer'"'"'s behavior in the cell. Such records may be sorted by customer number to enable efficient combining of multiple lists. In applications wherein the number of such cells is prohibitively large, only a portion of these cells may actually include materialized lists. Additionally, a user-specified subset of the cells may be efficiently populated from input data, and lists which are not materialized may be materialized on demand from other lists in an efficient manner.

Claims

1. A method for obtaining desired information from data representative of a number of data items, comprising the steps of:

storing in a first memory portion of a computer memory a plurality of cells being represented as a multi-dimensional storage structure that is defined by a plurality of dimensions, wherein each of said dimensions includes a plurality of members for identifying said desired information, each of said cells corresponding to at least one of said members;

storing in a second memory portion of said computer memory a plurality of data lists, each of said data lists comprising a plurality of records for storing said desired information;

linking each said cell with a respective data list such that each respective cell represents a multi-dimensional index to the corresponding data list, whereby each said data list is identified by said at least one of said members; and

wherein each said data item corresponds to a customer such that said desired information selectively represents at least one transaction carried out by said customer or demographic data about said customer, said one transaction or demographic data being selectively defined by said at least one of said members.

2. The method according to claim 1, further comprising selectively storing in each of said records a first field corresponding to intra-data item summary information which is obtained by processing said desired information for the corresponding data item without referring to other data items in a respective data list, and selectively storing in each said record a second field corresponding to inter-data item summary information which is obtained by processing said desired information for the corresponding data item by referring to said other data items in said respective data list.

3. The method according to claim 1, wherein each said cell is linked with the corresponding data list via a pointer.

4. The method according to claim 3, wherein said plurality of cells in said first memory portion is arranged as a file system directory, each said cell being represented by a file name, each said data list in said second memory portion being represented by a file, said pointer being said file name.

5. The method according to claim 3, wherein said plurality of cells in said first memory portion is arranged as a relational database, at least one of said cells being represented by a table name, each said data list in said second memory portion being represented by a table, and said pointer being represented by said table name.

6. The method according to claim 3, wherein said plurality of cells in said first memory portion is arranged as one of a B-tree, a quad-tree, an R-tree, and an array, wherein each said data list is represented by a file.

7. The method according to claim 1, wherein said respective data list is identified by a combination of said members from different dimensions.

8. A method for generating a plurality of data lists in a multi-dimensional storage structure for storing desired information obtained from data representative of data items, said desired information having been stored in a first memory portion of a computer memory as a plurality of cells being represented as said multi-dimensional storage structure that is defined by a plurality of dimensions, wherein each of said dimensions includes a plurality of members for identifying said desired information, each of said cells corresponding to at least one of said members, said desired information having been further stored in a second memory portion of said computer memory as a plurality of data lists, each of said data lists comprising a plurality of records for storing said desired information and an identifier for each said data item, said method comprising the steps of:

sorting said data by using said identifier;

extracting from the sorted data intra-data item summary information which is obtained by processing said desired information for each corresponding data item without referring to other data items in a respective data list;

supplying the extracted intra-data item summary information to respective records in each said data list;

accessing each said data list for determining inter-data item summary information which is obtained by processing the extracted intra-data item summary information for the corresponding data item by referring to said other data items in said respective data list;

supplying said inter-data item summary information to said respective records;

linking each said cell with said respective data list such that each said cell represents a multi-dimensional index to each said data list, whereby each said data list is identified by said at least one of said members; and

wherein each said data item corresponds to a customer such that said data selectively represents at least one said transaction carried out by said customer, said one transaction or demographic data being selectively defined by said at least one of said members.

9. The method according to claim 8, wherein said respective data list is identified by a combination of said members from different dimensions.

10. The method according to claim 8, further comprising generating said data lists for a subset of said cells.

11. The method according to claim 10, further comprising performing Boolean operations on said data lists to generate a new list corresponding to a respective cell.

12. The method according to claim 11, wherein said dimensions are represented by a plurality of hierarchical orders, said new list being higher in a hierarchical order corresponding to a preselected dimension than the previously generated data lists corresponding to said preselected dimension.

13. The method according to claim 8, further comprising filtering said respective records in said data lists to generate a new list which does not correspond to any one of said cells.

14. An apparatus for obtaining desired information from data representative of a number of data items, comprising:

means for storing in a first memory portion of a computer memory a plurality of cells being represented as a multi-dimensional storage structure that is defined by a plurality of dimensions, wherein each of said dimensions includes a plurality of members for identifying said desired information, each of said cells corresponding to at least one of said members;

means for storing in a second memory portion of said computer memory a plurality of data lists, each of said data lists comprising a plurality of records for storing said desired information;

means for linking each said cell with a respective data list such that each respective cell represents a multi-dimensional index to the corresponding data list, whereby each said data list is identified by said at least one of said members; and

wherein each said data item corresponds to a customer such that said data selectively represents at least one transaction carried out by said customer or demographic data about said customer, said one transaction or demographic data being selectively defined by said at least one of said members.

15. The apparatus according to claim 14, further comprising means for selectively storing in each of said records a first field corresponding to intra-data item summary information which is obtained by processing said desired information for each corresponding data item without referring to other data items in said respective data list, and means for selectively storing in each said record a second field corresponding to inter-data item summary information which is obtained by processing said desired information for the corresponding data item by referring to said other data items in said respective data list.

16. The apparatus according to claim 14, wherein each said cell is linked with the corresponding data list via a pointer.

17. The apparatus according to claim 16, wherein said plurality of cells in said first memory portion is arranged as a file system directory, each said cell being represented by a file name, each said data list in said second memory portion being represented by a file, and said pointer being said file name.

18. The apparatus according to claim 16, wherein said plurality of cells in said first memory portion is arranged as a relational database, at least one of said cells being represented by a table name, each said data list in said second memory portion being represented by a table, said pointer being represented by said table name.

19. The apparatus according to claim 16, wherein said plurality of cells in said first memory portion is arranged as one of a B-tree, a quad-tree, an R-tree, and an array, each said data list being represented by a file.

20. The apparatus according to claim 14, wherein said respective data list is identified by a combination of said members from different dimensions.

21. An apparatus for generating, in response to a user query, at least one data list in a multi-dimensional storage structure for storing desired information obtained from data representative of data items, said desired information being stored in a first memory portion of a computer memory as a plurality of cells being represented as said multi-dimensional storage structure that is defined by a plurality of dimensions, wherein each of said dimensions includes a plurality of members for identifying said desired information, each of said cells corresponding to at least one of said members, said desired information being further stored in a second memory portion of said computer memory as a plurality of data lists, each of said data lists comprising a plurality of records for storing said desired information and an identifier for each said data item, said apparatus comprising:

means for sorting said data by using said identifier;

means for extracting from the sorted data intra-data item summary information which is obtained by processing said desired information for each corresponding data item without referring to other data items in a respective data list;

means for supplying the extracted intra-data item summary information to respective records in each said list;

means for supplying the extracted intra-data item summary to respective records in each said data list;

means for accessing each said data list for determining inter-data item summary information which is obtained by processing the extracted intra-data item summary information for the corresponding data item by referring to said other data items in said respective data list;

means for supplying said inter-data item summary information to said respective records;

means for linking each said cell with said respective data list such that each said cell represents a multi-dimensional index to the corresponding data list whereby each said data list is identified by said at least one of said members;

means for outputting said data lists, and

wherein each said data item corresponds to a customer such that said data selectively represents at least one transaction carried out by said customer or demographic data about said customer, said one transaction or demographic data being selectively defined by said at least one of said members.

22. The apparatus according to claim 21, wherein said respective data list is identified by a combination of said members from different dimensions.

23. The apparatus according to claim 21, further comprising means for generating said data lists for a subset of said cells.

24. The apparatus according to claim 23, further comprising means for performing Boolean operations on said data lists to generate a new data list corresponding to a respective cell.

25. The apparatus according to claim 24, wherein said dimensions are represented by a plurality of hierarchical orders, said new data list being higher in a hierarchical order corresponding to a preselected dimension than the previously generated data lists corresponding to said preselected dimension.

26. The apparatus according to claim 21, further comprising means for filtering said respective records in said data lists to generate a new data list which does not correspond to any one of said cells.

27. The apparatus according to claim 21, wherein said means for outputting is one of a display device and a printer.

28. The apparatus according to claim 21, further comprising means for translating said user query to structured query language (SQL) and means for executing the translated user query in relational database system environment.

29. An apparatus for generating, in response to a user query, at least one data list in a multi-dimensional storage structure for storing desired information obtained from data representative of data items, said apparatus comprising:

means for storing said desired information as a plurality of cells being represented as said multi-dimensional storage structure that is defined by a plurality of dimensions, wherein each of said dimensions includes a plurality of members for identifying said desired information, each of said cells corresponding to at least one of said members;

means for further storing said desired information as a plurality of data lists, each of said data lists comprising a plurality of records for storing said desired information and an identifier for each said data item;

means for sorting said data by using said identifier;

means for extracting from the sorted data intra-data item summary information which is obtained by processing said desired information for each corresponding data item without referring to other data items in a respective data list;

means for supplying the extracted intra-data item summary information to respective records in each said data list;

means for accessing each said data list for determining inter-data item summary information which is obtained by processing the extracted intra-data item summary information for the corresponding data item by referring to said other data items in said respective data list;

means for supplying said inter-data item summary information to said respective records;

means for linking each said cell with said respective data list such that each said cell represents a multi-dimensional index to the corresponding data list, whereby each said data list is identified by said at least one of said members; and

means for outputting said data lists.

30. A method for generating, in response to a user query, at least one data list in a multi-dimensional storage structure for storing desired information obtained from data representative of data items, said method comprising the steps of:

storing said desired information as a plurality of cells being represented as said multi-dimensional storage structure that is defined by a plurality of dimensions, wherein each of said dimensions includes a plurality of members for identifying said desired information, each of said cells corresponding to at least one of said members;

storing said desired information as a plurality of data lists, each of said data lists comprising a plurality of records for storing said desired information and an identifier for each said data item;

sorting said data by using said identifier;

extracting from the sorted data intra-data item summary information which is obtained by processing said desired information for each corresponding data item without referring to other data items in a respective data list;

supplying the extracted intra-data item summary information to respective records in each said data list;

accessing each said data list for determining inter-data item summary information which is obtained by processing the extracted intra-data item summary information for the corresponding data item by referring to said other data items in said respective data list;

supplying said inter-data item summary information to said respective records;

linking each said cell with said respective data list such that each said cell represents a multi-dimensional index to the corresponding data list, whereby each said data list is identified by said at least one of said members; and

outputting said data lists.