SCALABLE INDEXING FOR LAYOUT BASED DOCUMENT RETRIEVAL AND RANKING

• US 20110022599A1
• Filed: 09/09/2009
• Published: 01/27/2011
• Est. Priority Date: 07/22/2009
• Status: Active Grant

• Current Assignee: Majandro LLC (IP Edge LLC)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Lecerf, Loïc M., Chidlovskii, Boris
• Granted Patent: US 7,953,679 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images

Abstract

A computer-based method and a system for indexing, querying, and ranking documents based on layout are provided. The method includes providing a plurality of documents to computer memory, extracting layout blocks from the provided documents, clustering the layout blocks into a plurality of layout block clusters, computing a representative block for each of the layout block clusters, generating a document index for each provided document based on the layout blocks of the document and the computed representatives blocks, clustering the created document indexes into a plurality of document index clusters, and generating a representative cluster index for each of the document index clusters. The indexes generated, together with the representative blocks and document index clusters, can be stored and used for retrieval of documents responsive to a layout query.

Claims

1. A computer-implemented method for creating a set of indexes for a:

collection of documents according to document layout, comprising;

providing a plurality of documents to computer memory;

extracting layout blocks from the provided documents;

using a computer processor, clustering the layout blocks into a plurality of layout block clusters;

computing a representative block for each of the layout block clusters;

generating a document index for each provided document based on the layout blocks of the document and the computed representative blocks;

clustering the created document indexes into a plurality of document index clusters;

generating a representative cluster index for each of the document index clusters; and

outputting the generated document indexes, representative blocks, document index clusters, and representative cluster indexes to memory.

2. The method of claim 1, wherein the clustering of the generated document indexes into document index clusters comprises:

clustering the generated document indexes into m′

document index clusters,

where m′

=√

{square root over (N)} and N is the number of documents provided to computer memory.

3. The method of claim 1, wherein at least one of the clustering of the generated document indexes into document index clusters and the clustering of the layout blocks into layout block clusters comprises using one of the following algorithms:

a k-means clustering algorithm, and

a hierarchical clustering algorithm.

4. The method of claim 1, wherein each representative document index is computed by using an averaging function on all the document indexes in the document index cluster for which the representative document index is computed.

5. The method of claim 1, wherein the extracting of layout blocks from the provided documents comprises extracting location information which defines a size and a location of each layout block on a document page.

6. The method of claim 1, wherein each layout block is rectangular and has a height and width of a minimum size to bound a block of text or an image in the document.

7. The method of claim 1, wherein the computing of the representative block for each of the layout block clusters comprises computing a first point and a second point which together define a location and a shape of the representative block, the representative block'"'"'s first point being computed as a function of a first point of each layout block in the cluster, the representative block'"'"'s second point being computed as a function of a second point of each layout block in the cluster, the first point and the second point of each layout block together defining a location and shape of the layout block.

8. The method of claim 1, wherein the generating of a document index comprises:

computing a similarity between each layout block in the provided document and each representative block; and

generating a document index for each provided document based on the computed similarities.

9. The method of claim 8, wherein the generating of the document index based on the computed similarities comprises using one of the following functions:

10. The method of claim 9, further comprising:

weighting the values in the document index as a function of the relative number of blocks associated with each representative block

11. The method of claim 8, wherein the computing of the similarity between a layout block in a provided document and a representative block comprises computing a distance measure between the layout block and the representative block.

12. The method of claim 11, wherein the computing of the distance measure comprises computing a function of the Manhattan distances between:

a) a first point defining the layout block and a corresponding first point defining the representative block; and

b) a second point defining the layout block and a corresponding second point defining the representative block.

13. The method of claim 8, wherein the computing of the similarity between each layout block in a provided document and each representative block comprises determining an extent of overlap between the layout block and the representative block.

14. The method of claim 8, wherein the computing of the similarity between each layout block in a provided document and each representative block comprises:

generating a tuple for each layout block and a tuple for each representative block, each of the tuples comprising location information for the respective block and at least one attribute value for the respective block; and

computing a distance measure between the layout block tuple and the representative block tuple.

15. The method of claim 14, wherein the attribute value is selected from a first attribute value based on a shape ratio of the layout block, a second attribute value based on an overlap distance between the layout block and the representative block, a third attribute based on a block type, and combinations thereof.

16. The method of claim 1, further comprising input document layout query, extracting layout blocks from the input layout query and retrieving responsive documents from the collection using the generated document indexes, representative blocks, document index clusters, and representative cluster indexes.

21. A computer-based system for performing the method of claim 1, comprising:

(i) a block extraction module configured to extract layout blocks from the provided documents;

(ii) a block clustering module configured to cluster the layout blocks into layout block clusters;

(iii) a representative block computation module configured to compute a representative block for each of the layout block clusters;

(iv) a document indexing module configured to generate an index for each provided document with respect to the layout blocks of the document and the computed representative blocks; and

(v) an index clustering module configured to;

cluster the created indexes into document index clusters; and

generate a representative document index for each of the document index clusters.

17. A computer-implemented method for querying a collection of documents according to document layout, comprising:

providing in computer memory;

a set of representative blocks, each representative block being representative of a respective cluster of layout blocks extracted from documents in the collection,

a set of document indexes, each document index being representative of layout blocks of a respective document in the collection, each of the document indexes being assigned to a respective one of a set of document index clusters, and

a representative document index for each document index cluster, each representative document index being derived from the document indexes assigned to the document index cluster;

extracting layout blocks from an input document layout query;

projecting the extracted layout blocks from the document layout query onto the set of representative blocks to generate a query document index;

with a computer processor, computing a measure of similarity between the query document index and each of the representative document indexes in the set of representative document indexes;

identifying a top document index cluster which includes the representative document index determined to have the greatest similarity to the query document index;

computing a measure of similarity between each document index in the top document index cluster and the query index to identify a set of most similar documents; and

outputting information on the documents in the set of most similar documents.

18. The method of claim 17, wherein the query index comprises a vector and further including at least one of a) and b):

a) each of the representative document indexes comprises a vector and wherein the computation of the similarity measure between the query index and each of the representative document indexes comprises assigning a first rank based on a cosine of the angle between the query vector and the representative document index vector; and

b) each of the document indexes comprises a vector and wherein the computation of the similarity measure between the query index and each of the document indexes comprises assigning a second rank based on a cosine of the angle between the query vector and the document index vector.

19. The method of claim 18, wherein at least one of:

the first rank is a function of the cosine of the query vector and the representative document index vector and also of the number of the representative blocks; and

the second rank is a function of the cosine of the query vector and the document index vector and also of the number of the representative blocks.

20. The method of claim 18, wherein at least one of the first and second ranks is defined by one of rank₁(Q,D), rank₂(Q,D) and rank₃(Q,D), as follows:

22. A computer-based system for querying a collection of documents according to a document layout, comprising:

(i) a data input module configured to receive into memory;

a set of document indexes,

a set of representative blocks,

a set of document index clusters,

a set of representative indexes, and

a document layout query;

(ii) a document query module configured to;

extract layout blocks from the document layout query,

project the extracted layout blocks from the document layout query onto the set of representative blocks to generate a query index,

compute the similarity between the query index and each of the representative indexes in the set of document index clusters by using a ranking function,

identify the document index cluster containing the representative index having the greatest similarity as the top document index cluster, and

compute the similarity between each document index in the top document index cluster and the query index by using the ranking function; and

(iii) a document ranking module configured to;

maintain an ordered list of the top k documents based on the computed similarity between each document index in the top document index cluster and the query index, and

output the ordered list.

23. The system of claim 22, wherein the system outputs the ordered list to an associated client terminal.

24. The system of claim 23, wherein when the client terminal identifies to the system at least one document to retrieve from the ordered list, the system provides the at least one document to the client terminal.

25. The system of claim 23, further comprising a touchscreen, and wherein the document layout query is generated through the use of the touchscreen.