Rollup functions and methods

• US 20030190077A1
• Filed: 04/08/2003
• Published: 10/09/2003
• Est. Priority Date: 03/19/1999
• Status: Active Grant

• Current Assignee: Matthews International Corporation
• Original Assignee: RAF Technology, Incorporated (Constellation Software Incorporated)
• Inventors: Billester, Stephen E.M., Smith, Brent R., Ross, David Justin
• Granted Patent: US 7,379,603 B2
• Time in Patent Office: Days
• US Class Current: 382/229
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/268 Lexical context

Abstract

Methods of organizing a series of sibling data entities in a digital computer are provided for preserving sibling ranking information associated with the sibling data entities and for attaching the sibling ranking information to a joint parent of the sibling data entities to facilitate on-demand generation of ranked parent candidates. A rollup function of the present invention builds a rollup matrix (126) that embodies information about the sibling entities and the sibling ranking information and provides a method for reading out the ranked parent candidates from the rollup matrix in order of their parent confidences (141). Parent confidences are based on the sibling ranking information, either alone or in combination with n-gram dictionary ranking or other ranking information.

Claims

1. A method of organizing a series of sibling entities for facilitating on-demand production of a ranked parent candidate of the series of sibling entities, each of the sibling entities comprising one or more child possibilities having an associated child confidence, the ranked parent candidate including one or more component elements, each component element consisting of one of the child possibilities selected from one of the sibling entities, the ranked parent candidate having a parent rank representing an aggregate of the child confidences associated with the child possibilities that comprise the component elements of the ranked parent, the method comprising:

(a) receiving a series of sibling entities including a first sibling entity and a last sibling entity;

(b) establishing a rollup matrix having a matrix height and a matrix width, the rollup matrix including multiple columns spanning the matrix width and multiple rows spanning the matrix height, each row having a row position along the matrix height; and

(c) loading the rollup matrix with the series of sibling entities in a predetermined loading sequence starting with a first-loaded column of the rollup matrix and ending with a last-loaded column of the rollup matrix, the loading of the rollup matrix including;

i) storing the first sibling entity in the first-loaded column, including storing each child possibility of the first sibling entity in one of the rows, the row position of said row corresponding to the child confidence associated with the child possibility being stored,

ii) in an unfilled column of the rollup matrix immediately following a previously-loaded column in the loading sequence, for each loaded row of the previously-loaded column in which a child possibility has been stored, storing in the unfilled column a next one of the sequential sibling entities including storing each of its child possibilities in the matrix rows having row positions equal to the sum of the row position of the loaded row of the previously-loaded column and the child confidence associated with said child possibility being stored,

iii) repeating step (ii) until the last one of the sequential sibling entities has been stored in the last-loaded column of data matrix,

whereby the row position of each row of the last-loaded column containing one of the child possibilities corresponds to the parent rank of at least one ranked parent candidate that can be generated using said one of the child possibilities.

2. The method of claim 1 in which each sibling entity has a child population representing the total number of child possibilities and in which the rollup matrix is established with a matrix depth equal to the largest of the child populations of the sibling entities.

3. The method of claim 1 in which:

receiving the series of sibling entities includes receiving a predetermined number of sequential sibling entities, each sequential sibling entity having a predetermined number of child possibilities, a maximum child confidence, and a position, one or more of said sibling entities having a largest number of child possibilities; and

establishing the rollup matrix includes establishing a rollup matrix having a matrix height corresponding to the sum of the maximum child confidences of the received sibling entities, a matrix width corresponding to the predetermined number of sequential sibling entities, and a matrix depth corresponding to the largest number of child possibilities, the data matrix including multiple columns spanning the matrix width, multiple rows spanning the matrix height, and multiple tiers spanning the matrix depth.

4. The method of claim 1 in which:

at least one of the sibling entities includes a character possibility set, the character possibility set including character possibilities having associated character confidences; and

the ranked parent candidates include candidate strings.

5. The method of claim 1 in which:

at least one of the sibling entities includes an alt-set, the alt-set including candidate n-grams having associated n-gram confidences.

6. The method of claim 5 in which the candidate n-grams are 2-grams.

7. The method of claim 5 in which the candidate n-grams are 3-grams.

8. A method in accordance with claim 1 in which:

establishing the rollup matrix includes establishing a nested child matrix of the rollup matrix; and

at least one of the sibling entities includes a child possibility represented by a pointer to an entry point of the nested child matrix.

9. A method of organizing a series of sibling entities for facilitating on-demand production of a ranked parent candidate of the series of sibling entities, the ranked parent candidate including one or more component elements, each component element consisting of one of the child possibilities selected from one of the sibling entities, the ranked parent candidate having a parent rank representing an aggregate of the child confidences associated with the child possibilities that comprise the component elements of the ranked parent candidate, the method comprising:

(a) receiving a series of sibling entities S₁, S₂, . . . S_n, each of the sibling entities comprising one or more child possibilities CP_i having an associated child confidence CF_i, where i=1 . . . n;

(b) establishing a rollup matrix having a matrix height and a matrix width, the rollup matrix including a series of columns COL₁, COL₂, . . . COL_n spanning the matrix width and a series of rows R₁, R₂, . . . R_n spanning the matrix height and located at respective row positions H=1, H=2, . . . H=n along the matrix height; and

(c) loading the rollup matrix with the series of sibling entities in a predetermined loading sequence starting with COL₁ and ending with COL_n, the loading of the rollup matrix, including the steps of;

i) storing S₁ in COL₁, including, for i=1, 2 . . . n, storing each child possibility CP_i of S₁ in one of the rows R_H, where H=CF_i,

ii) initializing a variable j so that j=1,

iii) incrementing j by 1,

iv) for each loaded row R_F of the previously-loaded column COL<sub>j−

1</sub> in which a child possibility has been stored, in which the row position of R_F is F, storing in COL_j the corresponding sibling entity S_j including storing each of its child possibilities CP_i in matrix rows R_H having row positions H=F+CF for i=1, 2, . . . n, and

v) repeating steps (iii) and (iv) until the last one of the sequential sibling entities (S_n) has been stored in the last-loaded column (COL_n) of the rollup matrix,

whereby the row position of each loaded row of the last-loaded column (COL_n) containing one of the child possibilities corresponds to the parent rank of at least one ranked parent candidate that can be generated using said one of the child possibilities.

10. The method of claim 9 in which each sibling entity has a child population representing the total number of child possibilities and in which the rollup matrix is established with a matrix depth equal to the largest of the child populations of the sibling entities.

11. The method of claim 9 in which:

receiving the series of sibling entities includes receiving a predetermined number of sequential sibling entities, each sequential sibling entity having a predetermined number of child possibilities, a maximum child confidence, and a position, one or more of said sibling entities having a largest number of child possibilities; and

establishing the rollup matrix includes establishing a rollup matrix having a matrix height corresponding to the sum of the maximum child confidences of the received sibling entities, a matrix width corresponding to the predetermined number of sequential sibling entities, and a matrix depth corresponding to the largest number of child possibilities, the data matrix including multiple columns spanning the matrix width, multiple rows spanning the matrix height, and multiple tiers spanning the matrix depth.

12. The method of claim 9 in which:

at least one of the sibling entities includes a character possibility set, the character possibility set including character possibilities having associated character confidences; and

the ranked parent candidates include candidate strings.

13. The method of claim 9 in which:

at least one of the sibling entities includes an alt-set, the alt-set including candidate n-grams having associated n-gram confidences.

14. The method of claim 13 in which the candidate n-grams are 2-grams.

15. The method of claim 13 in which the candidate n-grams are 3-grams.

16. A method in accordance with claim 9 in which:

establishing the rollup matrix includes establishing a nested child matrix of the rollup matrix; and

at least one of the sibling entities includes a child possibility represented by a pointer to an entry point of the nested child matrix.

17. A rollup function for use with a computer-implemented data storage, presentation, and analysis system comprising:

a matrix initialization routine for

receiving ranked sibling entities, the sibling entities including child possibilities representing siblings of a shared parent data entity,

sizing a rollup matrix, and

reserving matrix locations in a computer memory to accommodate the rollup matrix;

a loading routine for loading the sibling entities in the matrix locations in a first sequence, including loading the child possibilities of the sibling entities; and

a roll-out routine for reading the child possibilities of the sibling entities from the matrix locations in a second sequence opposite the first sequence and combining the child possibilities to form parent candidates.

18. The rollup function of claim 17, in which

the ranked sibling entities include child confidences associated with each of the child possibilities,

the matrix initialization routine calculates a parent candidate confidence representing an aggregate of the child confidences associated with the parent candidate;

the loading routine stores the parent candidate confidence in one of the matrix locations in association with a terminal one of the child possibilities; and

the roll-out routine selects the parent candidate based on the stored parent candidate confidence.

19. The rollup function of claim 17, further comprising a dictionary routine for analyzing the parent candidates.