# US 8,543,598 B2 · Semantic object characterization and search

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,543,598 B2
- Document ID: US8543598B2
- Status: Granted
- Kind: B2
- Application number: 12/715,174
- Filed: 2010-03-01
- Published: 2011-09-01
- Granted: 2013-09-24
- Earliest claimed: 2010-03-01
- Assignees: Microsoft Corporation
- Applicants: Uppinakuduru Raghavendra Udupa; Shaishav Kumar
- Inventors: Uppinakuduru Raghavendra Udupa; Shaishav Kumar
- Web page: https://patentgrep.com/patent/US8543598B2

## CPC

- G06F 16/30: of unstructured textual data (document management systems G06F16/93)
- G06F 16/3347: {using vector based model}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Semantic object characterization and its use in indexing and searching a database directory is presented. In general, a first binary hash code is generated to represent a first representation or view of a semantic object which when compared to a characterized version of a second representation or view of the same semantic object in the form of a second binary hash code, the first and second binary hash codes exhibit a degree of similarity indicative of the objects being the same object. In one implementation the semantic objects correspond to peoples' names and the first and second representations or views correspond to two different languages. Thus, a user can search a database of information in one language with a search query in another language.

## Claims

### Claim 1

A computer-implemented process for characterizing a first representation or view of a semantic object in the form of a first binary hash code representing that semantic object such that when compared to a characterized version of a second representation or view of the same semantic object in the form of a second binary hash code representing that semantic object, the first and second binary hash codes exhibit a degree of similarity indicative of the objects being the same object, said process comprising:
using a computer to perform the following process actions:
inputting pairs of parallel semantic objects, wherein a pair of parallel semantic objects comprises the same semantic object presented in the first and second representations or views;
subjecting each semantic object in each pair of parallel semantic objects to feature extraction to produce a feature vector representing the semantic object;
establishing a prescribed number of transforms for the first representation or view and the same number of transforms for the second representation or view based on the feature vectors representing the parallel semantic object pairs, wherein the transforms established for one of the first or second representations or views, when applied to a feature vector representing a semantic object exhibiting that representation or view, produces the first binary hash code representing that semantic object which is substantially similar to the second binary hash code representing that semantic object produced when the transforms established for the other of the first or second representations or views are applied to a feature vector representing the same semantic object exhibiting that other representation or view, and wherein said transforms established for the first representation or view are not all the same as the transforms established for the second representation or view; and
using the transforms established for the first representation or view to characterize a semantic object exhibiting the first representation or view as the first binary hash code representing that semantic object.

### Claim 2 (depends on 1)

The process of claim 1, wherein the process action of using the transforms established for the first representation or view to characterize a semantic object exhibiting the first representation or view in the form of the first binary hash code representing that semantic object, comprises the actions of:
subjecting the semantic object to the same feature extraction applied to the semantic object in each pair of parallel semantic objects exhibiting the first representation or view, to produce a feature vector representing the semantic object;
for each of the transforms established for the first representation or view, applying the transform to the feature vector representing the semantic object, and binarizing the result, to produce a bit of the first binary hash code representing the semantic object; and
concatenating the bits produced in a prescribed order to produce the first binary hash code representing the semantic object.

### Claim 3 (depends on 1)

The process of claim 1, wherein the process action of subjecting each semantic object in each pair of parallel semantic objects to feature extraction to produce a feature vector representing the semantic object, comprises an action of producing one of a binary feature vector or a real valued feature vector.

### Claim 4 (depends on 3)

The process of claim 3, wherein the process action of subjecting each semantic object in each pair of parallel semantic objects to feature extraction to produce a feature vector representing the semantic object, comprises an action of producing a lower-dimensional representation using a dimensionality reduction technique.

### Claim 5 (depends on 1)

The process of claim 1, wherein the process action of establishing a prescribed number of transforms for the first representation or view and the same number of transforms for the second representation of view based on the feature vectors representing the parallel semantic object pairs, comprises the actions of:
computing candidate transforms for each of the first and second representations or views using Canonical Correlation Analysis;
establishing a first set of transforms for the first representation or view from the candidate transforms computed for the first representation or view and a second set of transforms for the second representation or view from the candidate transforms computed for the second representation or view which, when, for each of the parallel pairs of semantic objects, the first set of transforms is applied to the feature vector representing the semantic object of the parallel pair of semantic objects exhibiting the first representation or view and the second set of transforms is applied to the feature vector representing the semantic object of the parallel pair of semantic objects exhibiting the second representation or view, a combined Hamming distance between the resulting first and second binary hash codes produced for all the parallel pairs of semantic objects is minimized.

### Claim 6 (depends on 5)

The process of claim 5, wherein the process action of establishing a prescribed number of transforms for the first representation or view and the same number of transforms for the second representation of view based on the feature vectors representing the parallel semantic object pairs, further comprises the actions of:
establishing the first set of transforms to exhibit a constraint that substantially half of the bits of the first binary hash code produced exhibit a first binary value and the remaining bits exhibit the other binary value; and
establishing the second set of transforms to exhibit a constraint that substantially half of the bits of the second binary hash code produced exhibit the first binary value and the remaining bits exhibit the other binary value.

### Claim 7 (depends on 6)

The process of claim 6, wherein the process action of establishing a prescribed number of transforms for the first representation or view and the same number of transforms for the second representation of view based on the feature vectors representing the parallel semantic object pairs, further comprises the actions of:
establishing the first set of transforms to exhibit a constraint that the bits of the first binary hash codes produced are uncorrelated; and
establishing the second set of transforms to exhibit a constraint that the bits of the second binary hash codes produced are uncorrelated.

### Claim 8

A computer-implemented process for creating a searchable database wherein items in the database are semantic objects exhibiting a first representation or view, and wherein a semantic object that is the same as a semantic object included in the database, but exhibiting a second representation or view, when presented as a search query to the searchable database results in an output comprising an identity a semantic object exhibiting the first representation or view that corresponds to the semantic object of the search query, said process comprising:
using a computer to perform the following process actions:
establishing a prescribed number of transforms for the first representation or view and the same number of transforms for the second representation of view, wherein the transforms established for one of the first or second representations or views, when applied to a feature vector representing a semantic object exhibiting that representation or view, produces the first binary hash code representing that semantic object which is substantially similar to a second binary hash code representing that semantic object produced when the transforms established for the other of the first or second representations or views are applied to a feature vector representing the same semantic object exhibiting that other representation or view, and wherein said transforms established for the first representation or view are not all the same as the transforms established for the second representation or view; and
using the transforms established for the first representation or view to characterize each of the semantic objects included in the database in the form of the first binary hash code representing that semantic object, wherein the first binary code characterizing a semantic object included in the database is substantially different from the first binary codes characterizing the other semantic objects included in the database; and
respectively associating the first binary hash code characterizing each of the semantic objects included in the database with its corresponding semantic object in the database.

### Claim 9 (depends on 8)

The process of claim 8, further comprising the process action of:
whenever a search query is input to the database which exhibits the second representation or view,
generating a feature vector representing the search query;
for each of the transforms established for the second representation or view, applying the transform to the feature vector representing the search query, and binarizing the result, to produce a bit of the second binary hash code representing the search query;
concatenating the bits produced in a prescribed order to produce the second binary hash code representing the search query;
finding a semantic object or objects included in the database whose first binary hash code exhibits a prescribed degree of similarity to the second binary hash code representing the search query; and
outputting the identity of a matching semantic object or objects included in the database whose first binary hash code is found to exhibit the prescribed degree of similarity to the second binary hash code representing the search query.

### Claim 10 (depends on 9)

The process of claim 9, wherein the process action of finding a semantic object or objects included in the database whose first binary hash code exhibits a prescribed degree of similarity to the second binary hash code representing the search query, comprises the actions of:
respectively computing a Hamming distance value between the second binary hash code representing the search query and the first binary hash code associated with each of the semantic objects included in the database; and
finding the semantic object or objects included in the database whose first binary hash code exhibits a hamming distance between it and the second binary hash code representing the search query that is the smallest.

### Claim 11 (depends on 9)

The process of claim 9, wherein the process action of finding a semantic object or objects included in the database whose first binary hash code exhibits a prescribed degree of similarity to the second binary hash code representing the search query, comprises the actions of:
respectively computing a Hamming distance value between the second binary hash code representing the search query and the first binary hash code associated with each of the semantic objects included in the database; and
finding the semantic object or objects included in the database whose first binary hash code exhibits a Hamming distance between it and the second binary hash code representing the search query that falls below a Hamming distance threshold.

### Claim 12 (depends on 9)

The process of claim 9, wherein the search query input to the database comprises multiple semantic objects which have been combined into a single semantic object, and wherein at least some of the semantic objects included in the database are multiple semantic objects which have been combined into a single semantic object.

### Claim 13 (depends on 9)

The process of claim 9, wherein the search query input to the database comprises multiple semantic objects, and wherein the feature vector generating, transform application and binarization, concatenating, finding and outputting process actions are repeated for each of the multiple semantic objects of the search query, and wherein the process further comprises process action of:
constructing a weighted bipartite graph wherein the each of the semantic objects of the search query form a first set of nodes of the graph and the
identified matching semantic object or objects output for each of the semantic objects of the search query form a second set of nodes of the graph;
respectively computing a degree of similarity between the binary hash code of each of the semantic objects associated with the first set of nodes and the binary hash code of each of the semantic objects associated with the second set of nodes, if not already known;
assigning an edge between each semantic object associated with the first set of nodes and a semantic object associated with the second set of nodes if the degree of similarity between the semantic objects based on their binary hash codes crosses a threshold, wherein the weight of an edge is set equal to the degree of similarity;
finding a maximum weighted bipartite graph matching in the graph;
computing the weight of the matching;
normalizing the weight of the matching based on the difference in the number of nodes between the first and second sets of nodes.

### Claim 14 (depends on 8)

The process of claim 8, wherein the process action of respectively associating the first binary hash code characterizing each of the semantic objects included in the database with its corresponding semantic object in the database, comprises the action of:
establishing a hash table comprising database directory entries corresponding to the semantic objects included in the database;
adding the first binary hash code characterizing each of the semantic objects included in the database to the hash table; and
associating the first binary hash code characterizing each of the semantic objects included in the database with its corresponding database directory entry in the hash table.

### Claim 15

A computer-implemented process for characterizing a person's name in a first language in the form of a first binary hash code representing that name such that when compared to a characterized version of the same name in a second language in the form of a second binary hash code representing that name, the first and second binary hash codes exhibit a degree of similarity indicative of the names being the same name, said process comprising:
using a computer to perform the following process actions:
inputting pairs of parallel names, wherein each pair of parallel names comprises the a person's name presented in the first and second languages, and wherein each pair of parallel names corresponds to a different name;
subjecting each name in each pair of parallel names to feature extraction to produce a binary feature vector representing the name;
establishing a prescribed number of transforms for the first language and the same number of transforms for the second language based on the feature vectors representing the parallel name pairs, wherein the transforms established for one of the first or second languages, when applied to a feature vector representing a name in that language, produces the first binary hash code representing that name which is substantially similar to the second binary hash code representing that name produced when the transforms established for the other of the first or second languages are applied to a feature vector representing the same name in that other language, and wherein said transforms established for the first language are not all the same as the transforms established for the second language; and
using the transforms established for the first language to characterize a person's name in the first language as the first binary hash code representing that name.

### Claim 16 (depends on 15)

The process of claim 15, wherein the process action of using the transforms established for the first language to characterize a person's name in the first language as the first binary hash code representing that name, comprises the actions of:
subjecting the person's name to the same feature extraction applied to the name in each pair of parallel names in the first language, to produce a binary feature vector representing the name;
for each of the transforms established for the first language, applying the transform to the feature vector representing the person's name, and binarizing the result, to produce a bit of the first binary hash code representing the name; and
concatenating the bits produced in a prescribed order to produce the first binary hash code representing the person's name.

### Claim 17 (depends on 16)

The process of claim 16, wherein if the first language employs a script associated with that language, or if the second language employs a script associated with that language, or if both languages employ respective scripts associated with the language, a person's name in a language employing script associated with that language is employed in its associated script.

### Claim 18 (depends on 15)

The process of claim 15, wherein the process action of subjecting each name in each pair of parallel names to feature extraction to produce a binary feature vector representing the name, comprises the actions of:
for each of the first and second languages respectively,
extracting prescribed features from a prescribed number of names in the language under consideration to produce a set of features specific to that language,
establishing a prescribed order for the extracted features, and
equating a bit location of each feature vector being produced to each extracted feature in the established order;
for each of the names in each pair of parallel names in the first and second languages respectively,
identifying each of the prescribed features existing in the name that corresponds to a feature in the set of features specific to the language under consideration,
generating a feature vector for the name under consideration such that the bit locations corresponding to a feature found in the name are assigned a first binary value and the bit locations corresponding to a feature not found in the name are assigned the second binary value.

### Claim 19 (depends on 18)

The process of claim 18, wherein the prescribed features comprise character n-grams.

### Claim 20 (depends on 18)

The process of claim 18, wherein the prescribed features comprise syllables.