Rollup functions for efficient storage, presentation, and analysis of data

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.

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.