ROLLUP FUNCTIONS FOR EFFICIENT STORAGE, PRESENTATION, AND ANALYSIS OF DATA
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.
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.