ROLLUP FUNCTIONS FOR EFFICIENT STORAGE, PRESENTATION, AND ANALYSIS OF DATA

• US 20080228469A1
• Filed: 04/21/2008
• Published: 09/18/2008
• Est. Priority Date: 03/19/1999
• Status: Abandoned Application

• Current Assignee: Matthews International Corporation
• Original Assignee: RAF Technology, Incorporated (Constellation Software Incorporated)
• Inventors: Smith, Brent R., Ross, David Justin, Billester, Stephen E.M.
• Application Number:
  US12/106,779
• Publication Number:
  US 20080228469A1
• Time in Patent Office: Days
• US Class Current: 704/10
• 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 computer-implemented system for organizing a set of sibling entities each having one or more child possibilities, at least one of the sibling entities including multiple child possibilities having a relative rank or confidence value and_from which multiple parent candidates can be generated, each of the parent candidates having a relative rank, and for generating an ordered series of parent candidates from the child possibilities, comprising:

a means for initializing a plurality of nodes in a computer-readable data storage medium for storing the child possibilities of the sibling entities;

a means for loading the sibling entities into the nodes to form a rollup matrix having an organization that represents the relative ranking of the parent candidates; and

a means for reading from the nodes to generate a series of parent candidates in order of their ranking.

2. The system of claim 1, further comprising:

a means for calculating a parent candidate confidence for at least some of the parent candidates;

a means for storing the parent candidate confidences in the rollup matrix in association with the corresponding parent candidates; and

in which the means for reading from the nodes generates the series of parent candidates based on the stored parent candidate confidences.

3. The system of claim 1, further comprising a means for comparing the generated parent candidates against a dictionary.

4. The system of claim 1 in which:

at least one of the sibling entities includes a nested child matrix having an entry point; and

the means for loading includes a means for loading the nested child matrix into one or more of the nodes, a means for creating a pointer to the entry point, and a means for storing the pointer in the rollup matrix.

5. A computer-implemented method for organizing a set of sibling entities each having one or more child possibilities, at least one of the sibling entities including multiple child possibilities having a relative rank or confidence value and from which multiple parent candidates can be generated, each of the parent candidates having a relative rank, and for generating an ordered series of parent candidates from the child possibilities, comprising:

initializing a plurality of nodes in a computer-readable data storage medium for storing the child possibilities of the sibling entities;

loading the sibling entities into the nodes to form a rollup matrix having an organization that represents the relative ranking of the parent candidates; and

reading from the nodes to generate a series of parent candidates in order of their ranking; and

outputting at least one of the parent candidates.

6. The method of claim 5, further comprising:

calculating a parent candidate confidence for at least some of the parent candidates;

storing the parent candidate confidences in the rollup matrix in association with the corresponding parent candidates; and

reading from the nodes generates the series of parent candidates based on the stored parent candidate confidences.

7. The method of claim 5, further comprising comparing the generated parent candidates against a dictionary.

8. The method of claim 5 in which:

at least one of the sibling entities includes a nested child matrix having an entry point; and

the loading of the sibling entities into the nodes includes loading the nested child matrix into one or more of the nodes, creating a pointer to the entry point, and storing the pointer in the rollup matrix.

9. A method for character recognition in an OCR system, the method comprising:

optically scanning a document to obtain data defining an image;

segmenting the image to determine a plurality of sibling glyphs;

each sibling glyph comprising an associated possibility set, the possibility set consisting of at least one alphanumeric character candidate information pair, each pair consisting of a respective candidate and an associated confidence value;

identifying a plurality of parent candidates based on the sibling glyphs, each parent candidate representing a candidate word;

calculating a parent candidate confidence value for at least some of the parent candidates;

storing the parent candidate confidences in a rollup matrix in association with the corresponding parent candidates; and

reading from the nodes so as to generate a series of parent candidate words based on the stored parent candidate confidence values.