Method and apparatus for storage and retrieval of handwritten information

• US 5,524,240 A
• Filed: 10/17/1994
• Issued: 06/04/1996
• Est. Priority Date: 05/24/1994
• Status: Expired due to Term

• Current Assignee: Panasonic Corporation Of North America (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Technologies, Inc. (Panasonic Holdings Corporation)
• Inventors: Korth, Henry F., Barbara, Daniel
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): PHAM, CUAN
• Application Number:
  US08/324,231
• Time in Patent Office: 596 Days
• Field of Search: 395/600, 395/575, 395/1, 395/100, 382/13
• US Class Current: 707/741
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 30/2276 with probabilistic networks, e.g. hidden Markov models
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

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.

Claims

1. A method for generating and querying an indexed database stored in a computer system, comprising the steps of:

(a) establishing a database which includes a plurality of data objects each defined by a respective tuple of attributes, the attributes including at least one attribute having a domain of values that includes handwritten objects, each handwritten object including a plurality of symbols ordered in an output sequence;

each symbol being a feature vector;

(b) establishing an index having a root node and a plurality of leaf nodes, each 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, for which input sequence the respective leaf node includes a set of pointers to a subset of the tuples;

(c) analyzing the output sequence of each handwritten object and determining a respective probability that each input sequence matches the output sequence;

(d) including, in the respective set of pointers in each respective leaf node, a pointer to any tuple for which the respective output sequence has at least a threshold probability of matching the input further plurality of symbols ordered in an input sequence and traversing one of the paths, the one path corresponding to a sequence of symbols which matches the respective input sequence of symbols of the handwritten input object.

2. A method according to claim 1, wherein step (e) includes:

identifying, from the pointers in the leaf node corresponding to the one path, the subset of the tuples for which the value of the one attribute has at least a threshold probability of matching the input sequence of the handwritten input object; and

identifying the data objects which correspond to the identified tuples as being found by the query.

3. A method according to claim 1, wherein the database is a relational database plurality of relations and has a domain of values that includes:

handwritten objects;

(2) repeating, for each tuple in the first relation and for each tuple in the second relation, the step of;

forming a result tuple having the attribute values of a first tuple from the first relation and a second tuple from the second relation, if the respective values of the common attribute for the first and second tuples have at least a threshold probability of being equal to one another;

(3) forming the result relation to include the result tuples identified in step (2).

4. A method according to claim 3, wherein the step of forming the result tuple includes:

(a) selecting the first tuple and identifying the input sequence of symbols that is included in the common attribute of the selected tuple;

(b) traversing one of the paths of the index, the one path corresponding to the identified input sequence;

(c) identifying, from the pointers in the leaf node corresponding to the one path, the subset of the tuples for which the value of the common attribute has at least a threshold probability of matching the identified input sequence;

(d) forming the result tuple if the second tuple is included in the subset of the tuples for which the value of the common attribute has at least a threshold probability of matching the identified input sequence.

5. A method according to claim 1, wherein the database is a relational database including a plurality of relations, and step (a) includes:

(1) displaying a skeleton table which represents a relation scheme of one of the plurality of relations,

(2) entering a handwritten object in the skeleton table, and

(3) storing the handwritten object entered in step (a) (2) as the value of the one attribute for one of the data objects.

6. A method according to claim 5, further comprising querying the database by the steps of:

(e) displaying the skeleton table,

(f) entering a handwritten input object in the skeleton table, and

(g) identifying, without executing a recognition operation any data object for which the value of the one attribute has at least a threshold probability of matching the handwritten input object as being found by the search.

7. A method according to claim 6, wherein the method is performed using a digitizing pad of a computer, the computer has an operating system which includes a copy and paste function, further comprising the steps of:

(h) entering a handwritten example element a first time by writing the handwritten example element in a first portion of the skeleton table, using the digitizing pad, and

(i) entering the handwritten example element a second time by;

(1) copying the handwritten example element from the first portion of the skeleton table, and

(2) pasting the handwritten example element into a second portion of the skeleton table, wherein steps (i) (1) and (i) (2) are performed using the copy and paste function.

8. A method according to claim 7, wherein the step of querying the database includes:

(j) selecting and copying from a menu one of an arithmetic operator and a logical operator, and

(k) pasting the selected one of the arithmetic and logical operators into a condition box of the skeleton table,

wherein steps (j) and (k) are performed using the copy and paste function.

9. A method for generating and querying an indexed database stored in a computer system, comprising the steps of:

(a) establishing a database which includes a plurality of data objects each defined by a respective tuple of attributes, the attributes including at least one attribute having a domain of values that includes handwritten objects, each handwritten object including a plurlaity of symbols ordered in an output sequence, each symbol being a feature vector;

for which input sequence the respective leaf node includes a respective set of pointers to a subset of the tuples;

(c) analyzing the output sequence of each handwritten object and determining a respective probability that each input sequence matches the output sequence;

(d) including, in the respective set of pointers in each respective leaf node, 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, as determined for the output sequence of each handwritten object; and

(e) querying the database by inputting a handwritten input object to the computer system, said querying comprising the steps of,

(1) executing a first query matching algorithm to generate an approximate response to the query,

(2) displaying the approximate response,

(3) executing a second query matching algorithm after executing the first query matching algorithm, to generate a second response to the query that is more accurate than the approximate response, and

(4) displaying the second response.

10. A method for indexing and querying a database, comprising the steps of:

(a) establishing a database which includes a plurality of data objects defined by tuples of attributes, the attributes including at least one attribute having a domain of values that includes handwritten objects, each handwritten object including a plurality of output symbols ordered in an output sequence, each output symbol being a feature vector;

(b) modelling each handwritten object by a common alphabet including n output symbols, and a common output sequence length of T symbols, where n and T are integers;

(c) establishing an index for the one attribute, the index having T levels, each level between zero and T-1 having a respective minimum probability value, each level having at least one node;

(d) indexing the symbols in one of the handwritten objects by performing, for each node in one of the levels of the index, the steps of;

(1) determining a probability that a symbol stored in said node represents a corresponding output symbol in the one handwritten object,

(2) adding a node in a next level of the index, if the probability determined in step (d) (1) exceeds the minimum probability value of the one level and the next level is between the oneth level and the T-1th level,

(3) executing step (d) for the added node in the next level, if the node is added in step (d) (2), and

(4) adding a pointer to the one handwritten object in a list of pointers stored in a node in the Tth level of the index, if the next level is the Tth level and the probability determined in step (d) (1) is greater than the minimum probability value of the T-1th level;

(e) repeating step (d), for each of the plurality of handwritten objects other than the one handwritten object; and

(f) querying the database by inputting to the computer system a handwritten input objects including a further plurality of symbols ordered in an input sequence and matching the respective input sequence of symbols of the handwritten input object to the output sequence of output symbols included in one of said handwritten objects.

11. A method for generating and querying a database stored in a computer system, comprising the steps of:

(a) establishing a database which includes a plurality of data objects each defined by a respective tuple of attributes, the attributes including at least one attribute having a domain of values that includes handwritten objects, each handwritten object including a probability that each input sequence matches the output sequence;

(c) including in an index of the database a pointer to any tuple for which the respective output sequence has at least a threshold probability of matching the input sequence, as determined for the output sequence of each handwritten object; and

(d) querying the database by inputting to the computer system a handwritten input object including a further plurality of symbols ordered in an input sequence and matching the respective inputs sequence of symbols of the handwritten input object to the output sequence of output symbols included in said handwritten objects.