Method and system for partial-order analysis of multi-dimensional data

• US 6,931,418 B1
• Filed: 03/26/2002
• Issued: 08/16/2005
• Est. Priority Date: 03/26/2001
• Status: Active Grant

• Current Assignee: Gula Consulting Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: Steven M. Barnes
• Inventors: Barnes, Steven M.
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US10/106,467
• Time in Patent Office: 1,239 Days
• Field of Search: 707/3, 707/10, 707/100, 707/5, 707/6, 707/101, 707/102, 707/103, 707/104
• US Class Current: 707/776
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/961 Associative
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and system for performing data analysis where multiple, categorical dimensions and statistical measures are used. The method includes preparing multi-dimensional data into nodes and arranging them logically in the form of a partial-order database. The database may then be traversed by a data-mining tool, or queried in an OLAP manner. Queries are answered through a process of associative partial-order search, which includes optional support for “children-of” requests, and optional support for fuzzy pattern-matching. By aggregating measures on-the-fly, this method is able to preform well without requiring a large number of summary nodes, when taken as a percentage of the total node count.

Claims

1. A method for supporting data analysis through use of a partial-order structuring of multi-dimensional data and aggregated measurements stored in computer memory, and use of a pattern-comparison means, said pattern-comparison means having the ability to compare two patterns across a multiplicity of dimensions so as to determine whether the first pattern is more-general-than the second pattern, comprising the steps of:

(a) loading of metadata defining the type hierarchy;

(b) transforming multi-dimensional fact data into a plurality of nodes, said nodes containing at least a pattern part and a measures part, and said pattern part having the ability to store a multiplicity of dimension values simultaneously;

(c) loading of said data nodes into a partial-order structure providing a functional representation of a rooted directed-acyclic graph whose arcs embody an ordering by the relationship established by the pattern-comparison means;

(d) loading of a plurality of additional nodes into said partial-order structure, wherein said additional nodes contain a pattern part that is more general than any pattern contained in said data nodes;

(e) aggregating the measures part from said data nodes into the measures part of said additional nodes;

(f) performing on-demand aggregation, facilitated by said partial-order structure, in response to a query for which insufficient pre-aggregated data is currently stored.

2. The method of claim 1, further comprising the step of:

(g) topologically-ordered associative searching of said partial-order structure using pattern-comparison against a query pattern, so as to return aggregate data specific to said query pattern by;

1. returning pre-aggregated data, should said query pattern be present in a node of said partial-order structure;

2. returning aggregation data assembled on-the-fly by means of said query pattern'"'"'s virtual position in the partial-order, should said query pattern not be present in a node of said partial-order structure.

3. The method of claim 1, further comprising the steps of:

(h) assembling a list of nodes through use of associative look-up means separate from said partial-order structure, said nodes being predecessors of a query pattern, as part of means for accelerating associative search;

(i) returning a null result for the query, in the case that said list is empty;

(j) proceeding with a topologically-ordered associative search of said partial-order structure using pattern-comparison against a query pattern, so as to return aggregate data specific to said query pattern, in the case that said list is non-empty, said associative search employing accelerating means.

4. The method of claim 1, further comprising the step of:

(k) traversing said partial-order structure, while processing data contained therein so as to separately accumulate data for specializations of a query pattern, said specializations along any number of dimensions being controlled by means of a children-of specification accompanying the query, and said accumulation being facilitated by means of pattern-promotion.

5. The method of claim 1, wherein said pattern-comparison means is able to return a fuzzy-valued test result.

6. A system of logic circuitry and computational instructions for supporting data analysis through use of a partial-order structuring of multi-dimensional data and aggregated measurements stored in computer memory, and use of a pattern-comparison means, said pattern-comparison means having the ability to compare two patterns across a multiplicity of dimensions so as to determine whether the first pattern is more-general-than the second pattern, comprising:

(a) means for loading of metadata defining the type hierarchy;

(b) means for transforming multi-dimensional fact data into a plurality of nodes, said nodes containing at least a pattern part and a measures part, and said pattern part having the ability to store a multiplicity of dimension values simultaneously;

(c) means for loading of said data nodes into a partial-order structure providing a functional representation of a rooted directed-acyclic graph whose arcs embody an ordering by the relationship established by the pattern-comparison means;

(d) means for loading of a plurality of additional nodes into said partial-order structure, wherein said additional nodes contain a pattern part that is more general than any pattern contained in said data nodes;

(e) means for aggregating the measures part from said data nodes into the measures part of said additional nodes;

(f) means for performing on-demand aggregation, facilitated by said partial-order structure, in response to a query for which insufficient pre-aggregated data is currently stored.

7. The system of claim 6, further comprising:

(g) means for topologically-ordered associative searching of said partial-order structure using pattern-comparison against a query pattern, so as to return aggregate data specific to said query pattern by;

1) returning pre-aggregated data, should said query pattern be present in a node of said partial-order structure;

2) returning aggregation data assembled on-the-fly by means of said query pattern'"'"'s virtual position in the partial-order, should said query pattern not be present in a node of said partial-order structure.

8. The system of claim 6, further comprising:

h. means for assembling a list of nodes through use of associative look-up means separate from said partial-order structure, said nodes being predecessors of a query pattern, as part of means for accelerating associative search;

i. means for returning a null result for the query, in the case that said list is empty;

j. means for proceeding with a topologically-ordered associative search of said partial-order structure using pattern-comparison against a query pattern, so as to return aggregate data specific to said query pattern, in the case that said list is non-empty, said associative search employing accelerating means.

9. The system of claim 6, further comprising:

(k) means for traversing said partial-order, while processing data contained therein so as to separately accumulate data for specializations of a query pattern, said specializations along any number of dimensions being controlled by means of a children-of specification accompanying the query, and said accumulation being facilitated by means of pattern-promotion.

10. The system of claim 6, wherein said pattern-comparison means is able to return a fuzzy-valued test result.