Panasonic Technologies, Inc.

Matsushita Electric Corporation of America

Daniel Barbara

Walid G Aref

Ibrahim Mostafa Kamel

Tomasz Imielinski

Stephen L Johnson

Henry F Korth

Calton Pu

Padmavathi Vallabhaneni

Sharad Mehrotra

A method of searching for one of a plurality of objects that matches an input sequence of handwritten objects is provided. The objects are modeled by concatenating members of a set of component objects. A Trie structure representing the plurality of objects is generated. Component objects of each object are assigned to the elements of respective nodes of the Trie structure. A respective hidden Markov model (HMM) is associated with each element of each non-leaf node. The HMMs represent the respective component object of the element. A maximum probability of any HMM accepting any of the set of component objects is estimated. The root node of the Trie structure is selected. A plurality of elements of the selected node are selected. A plurality of segments of the input sequence are applied to respective HMMs associated with the selected elements to generate respective acceptance values.

Trie structure based method and apparatus for indexing and searching

Apparatus for determining a distance between two handwritten strings in a database. A processor extracts global features from each string. The processor divides the string into strokes, and identifies a plurality of bounding boxes. Each box contains a different stroke. The processor extracts global features from the suing, including: (1) a number of points; (2) a maximum angle between a first point in the string and a corner of the tallest bounding box; (3) a number of positive inversions; and (4) a number of negative inversions. The apparatus calculates the distance between the strings based on all of the numbers of points, maximum angles, numbers of positive inversions and numbers of negative inversions. A fixed query tree index may be formed. The tree has leaves and internal nodes belonging to multiple levels. A different key is associated with each level. Each key is a handwritten string. Each string is associated with one of the leaves, such that each child of each internal node in any of the levels between the one leaf and the root node is a root of a respective subtree. Each string associated with any leaf in the subtree which includes the one leaf is equally distant from the key associated with the one level, based on the global features. The tree is queried to search for a subset of the strings, such that each string in the subset is within a threshold distance of an input string, according to the distance function.

Method and apparatus for similarity matching of handwritten data objects

A method and system are provided for maintaining coherency between a server processor and a client processor that has a cache memory. The server may, for example, be a fixed location mobile unit support station. The client may, for example, be a palmtop computer. The server stores a plurality of data values, and the client stores a subset of the plurality of data values in the cache. The server processor periodically broadcasts invalidation reports to the client processor. Each respective invalidation report includes information identifying which, if any, of the plurality of data values have been updated within a predetermined period of time before the server processor broadcasts the respective invalidation report. The client processor determines, based on the invalidation reports, whether a selected data value in the cache memory of the client processor has been updated in the server processor since the selected data value was stored in the cache memory. The client processor invalidates the selected data value in the cache memory of the client processor, if the selected data value has been updated in the server processor.

System for maintaining data coherency in cache memory by periodically

A method for indexing a plurality of handwritten objects is provided. A B-tree data structure of order m is generated, where m is an integer. The B-tree has a plurality of nodes divided into a plurality of levels ordinally numbered 0.sup.th through n.sup.th. Each node in the 0.sup.th level is a leaf. Each node in the 1.sup.th level has at least m/2 leaves as children. Each one of the handwritten objects is assigned to a respective leaf. A respectively different hidden Markov model (HMM) is associated with each respective child of each of the nodes in the 1.sup.th to n.sup.th levels. Each one of the nodes in the 1.sup.th to n.sup.th levels contains the respective HMM associated with the child of the one node. Each HMM in each one of the nodes in the 1.sup.th level is trained to accept the handwritten object of the respective leaf that is a child of the one node. Each HMM associated with any of the nodes in the 2.sup.th through n.sup.th levels is trained to accept all of the handwritten objects in the leaves of a subtree that has as a root the respective child with which the HMM is associated.

Method and apparatus for indexing a plurality of handwritten objects

A method for indexing electronic handwritten documents is provided. Each document includes a plurality of output symbols in an output sequence, and is modeled by a respective Hidden Markov Model (HMM). The HMMs share a common alphabet and a common sequence length. A tree is established, having linked nodes stored in a memory. Each node has n pointers, each identifying a different node in the next level of the tree. Each path from the root to a different one of the leaf nodes defines a respective sequence of pointers. An indexing procedure is performed, for each of a subset of the nodes in one of the levels of the tree. The procedure includes: (1) determining the probability that a subset of one of the sequences of pointers leading from the root to that node represents a subset of the output symbols in one of the documents; (2) invoking the procedure for the next level, if the determined probability exceeds the minimum probability value of that level; and (3) adding a pointer to that document in the list of pointers of the leaf node associated with that sequence of pointers, if the next level is the last level and the probability is greater than the threshold value. The procedure is repeated for each other document.

Method for indexing and searching handwritten documents in a database

A method is provided for generating an indexed database stored in a computer system. A database is established. The database includes a plurality of data objects. Each data object is defined by a respective tuple of attributes. The attributes include at least one attribute having a domain of values that includes handwritten objects. Each handwritten object includes a plurality of symbols ordered in an output sequence. An index is established, having a root node and a plurality of leaf nodes. Each leaf node is connected to the root node by a respective path, such that each path from the root node to one of the plurality of leaf nodes corresponds to a respective input sequence of symbols. The input sequence for the respective leaf node includes a set of pointers to a subset of the tuples. A respective Hidden Markov Model (HMM) is executed to analyze the output sequence of each handwritten object and to determine a respective probability that each input sequence matches the output sequence. A pointer to any tuple for which the respective output sequence has at least a threshold probability of matching the input sequence (corresponding to the leaf node) is included in the respective set of pointers in each respective leaf node. The probability is determined by the respective HMM for the output sequence of each handwritten object.

Method and apparatus for storage and retrieval of handwritten information

A method of searching a database having a plurality of objects is provided. Each object includes attributes and, for each attribute, a number of values. A query specifies two attributes and a maximum distance. A respective set of ranges is established for each object that has a value for the first attribute. Each set includes a range for each value of the first attribute. Each range is defined by minimum and maximum location values. A test range is established for one of the ranges. The test range has values equal to the minimum and maximum values of one of the ranges. The test range is adjusted, if necessary, so that it includes one of the values of the second attribute of the corresponding object. The test range is added to a group of ranges corresponding to the object if the minimum and maximum test values do not differ from one another by more than the maximum distance. The steps of (1) establishing a test range, (2) adjusting the test range and (3) adding the test range to the group are repeated for each range in the set of ranges corresponding to the one object. Steps (1) to (3) are repeated for each value of the second attribute of each respective object for which a set of ranges is established. Each object for which the group of ranges includes at least one range is identified as being found by the searching.

Method for proximity searching with range testing and range adjustment

A method and apparatus by which the recipient of several pieces of newly released information can automatically verify its accurate delivery is disclosed. The first step in the method is to generate a certificate, for example, a checksum, for each of the pieces of information. The certificates are combined, for example, using an exclusive OR function to form elements of a release vector such that each certificate is used to generate multiple ones of the release vector elements. The release vector and a program are then delivered to the recipient by one medium while the pieces of information are delivered by another medium. The program is used at the recipient's location to generate a current vector using the same methods that were used to generate the release vector. Next, the current vector is compared to the release vector and the result is used to identify missing or corrupted pieces of the delivered information.

Growing community of inventors

Princeton, NJ, United States of America

Daniel Barbara