Using an ID Domain to Improve Searching

• US 20100023497A1
• Filed: 07/25/2008
• Published: 01/28/2010
• Est. Priority Date: 07/25/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: El-Saban, Motaz, Magdy, Walid
• Granted Patent: US 8,131,720 B2
• Time in Patent Office: Days
• US Class Current: N/A
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps

Abstract

Methods which use an ID domain to improve searching are described. An embodiment describes an index phase in which an image of a document is converted into the ID domain. This is achieved by dividing the text in the image into elements and mapping each element to an identifier. Similar elements are mapped to the same identifier. Each element in the text is then replaced by the appropriate identifier to create a version of the document in the ID domain. This version may be indexed and searched. Another embodiment describes a query phase in which a query is converted into the ID domain and then used to search an index of identifiers which has been created from collections of documents which have been converted into the ID domain. The conversion of the query may use mappings which were created during the index phase or alternatively may use pre-existing mappings.

Claims

1. A method comprising:

segmenting text in an image of a document into elements;

assigning an identifier to each element based on a comparison of elements;

replacing each element in the text with the corresponding identifier; and

creating an index of identifiers in the document.

2. A method according to claim 1, wherein assigning an identifier to each element based on a comparison of elements comprises:

grouping similar elements into clusters; and

allocating an identifier to each cluster.

3. A method according to claim 2, further comprising:

creating a cluster table, the cluster table comprising a mappings between an identifier allocated to a cluster and characteristics of elements in said cluster.

4. A method according to claim 1, wherein assigning an identifier to each element based on a comparison of elements comprises:

grouping similar elements into clusters; and

allocating at least one identifier to each cluster using a cluster table, the cluster table comprising mappings between identifiers and element characteristics.

5. A method according to claim 4, wherein allocating at least one identifier to each cluster using a cluster table comprises:

comparing a cluster to the cluster table;

if there is a match between said cluster and an entry in the cluster table, allocating at least one identifier to the cluster using the cluster table; and

if there is no match between said cluster and an entry in the cluster table, updating the cluster table before allocating at least one identifier to the cluster using the cluster table.

6. A method according to claim 1, wherein assigning an identifier to each element based on a comparison of elements comprises:

allocating at least one identifier to each element using a cluster table, the cluster table comprising mappings between identifiers and element characteristics.

7. A method according to claim 6, wherein allocating at least one identifier to each element using a cluster table comprises:

comparing an element to the cluster table;

if there is a match between said element and an entry in the cluster table, allocating at least one identifier to the element using the cluster table; and

if there is no match between said element and an entry in the cluster table, updating the cluster table before allocating at least one identifier to the element using the cluster table.

8. A method according to claim 1, wherein replacing each element in the text with the corresponding identifier comprises:

replacing each element in a cluster with the identifier allocated to the cluster; and

ordering identifiers within the document according to an order of the text.

9. A method according to claim 1, further comprising:

converting query text into an image;

segmenting the image into elements and matching each element to at least one cluster using a cluster table, the cluster table comprising mappings between identifiers and element characteristics;

replacing each element in said image with at least one identifier based on said matching to formulate a query defined in terms of identifiers; and

searching an index of identifiers using said query defined in terms of identifiers.

10. A method according to claim 9, wherein replacing each element in said image with at least one identifier based on said matching to formulate a query defined in terms of identifiers comprises:

replacing each element in said image with at least one identifier; and

restricting a sequence of identifiers to formulate a query defined in terms of identifiers.

11. A method according to claim 1, further comprising:

converting query text into a plurality of images, each image being created using a different font;

creating a query in terms of identifiers associated with each of the plurality of images, each query being created using a cluster table associated with the font used to create the associated image; and

using each query to search at least one index of identifiers for the associated font.

12. A system comprising:

a processor;

an input for receiving a query; and

a memory arranged to store executable instructions arranged to cause the processor to;

convert the query into an image;

perform a comparison between elements in said image to a cluster table defining mappings between image elements and identifiers;

create a query defined in terms of identifiers based on the comparison; and

search an index of identifiers created from at least one document image using said query defined in terms of identifiers.

13. A system according to claim 12, wherein the query is created by replacing each element in said image with at least one identifier based on the comparison.

14. A system according to claim 13, wherein the query is created by replacing each element in said image with N identifiers corresponding to the N most similar image elements in the cluster table.

15. A system according to claim 14, wherein each of said N identifiers has an associated weight and wherein the search of an index of identifiers uses said query defined in terms of identifiers and the weight associated with each of said identifiers.

16. A system according to claim 12, wherein a first font is used to convert the query into an image and the memory is further arranged to store executable instructions arranged to cause the processor to:

convert the query into a second image using a second font;

create a second query defined in terms of identifiers based on a comparison between elements of the second image and a cluster table associated with the second font; and

search a second index of identifiers created from at least one document image using said second query defined in terms of identifiers.

17. A system according to claim 12, wherein the query defined in terms of identifiers is created by:

replacing each element in said image with at least one identifier based on the comparison; and

creating a query comprising a restricted sequence of identifiers.

18. A system according to claim 12, wherein the memory is further arranged to store executable instructions arranged to cause the processor to:

divide text in an image of a document into a plurality of elements;

arrange the plurality of elements into clusters of similar elements;

allocate a unique identifier to each cluster;

replace each element in the image with one or more identifiers, one of said one or more identifiers comprising the identifier corresponding to the unique identifier of the cluster comprising the element; and

create an index of identifiers in the image.

19. One or more tangible device-readable media with device-executable instructions for performing steps comprising:

receiving an image of a document;

segmenting text in said image into a plurality of elements;

grouping said elements based on similarity of elements;

allocating an identifier to each group of elements;

replacing each element in a group with the identifier of the group;

ordering the identifiers according to an order of the text in said image; and

creating an index of identifiers.

20. One or more tangible device-readable media according to claim 19, further comprising device-executable instructions for performing steps comprising:

receiving a text query;

converting the text query into an image of the query;

using pre-defined mappings to convert each element in the image of the query into at least one identifier;

formulating a query based on said at least one identifier corresponding to each element in the image of the query; and

searching said index of identifiers using said query.