INDEXING VERSIONED DOCUMENT SEQUENCES

• US 20080270396A1
• Filed: 04/25/2007
• Published: 10/30/2008
• Est. Priority Date: 04/25/2007
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yogev, Sivan, Lempel, Ronny, Herscovici, Michael
• Application Number:
  US11/739,700
• Publication Number:
  US 20080270396A1
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing

Abstract

A method includes indexing text is repeated in multiple edited versions of a document, a single time, thereby generating a compact index, and conducting text searches in the compact index.

Claims

1. A method comprising:

for at least one document, indexing a single time, text which is repeated in multiple edited versions of said document thereby generating a compact index; and

conducting text searches in said compact index.

2. The method according to claim 1 wherein said versions of each said at least one document form a group and wherein said indexing comprises:

generating a set of virtual documents for each said group;

indexing said virtual documents; and

recording mapping data correlating said virtual documents to said versions.

3. The method according to claim 2 and comprising associating each instance of repetition of said text in at least two successive said versions with a single appearance of said text in one of said virtual documents.

4. The method according to claim 2 and wherein said generating comprises:

defining an alignment for each said group; and

deriving said set of virtual documents from said alignment.

5. The method according to claim 4 and wherein said defining comprises building a matrix whose first row is a supersequence of the entirety of text in each said group and each of whose subsequent rows is a binary representation of each of said versions.

6. The method according to claim 5 and wherein said building comprises assigning a column in said matrix for each unit of text in said entirety of text.

7. The method according to claim 6 and comprising:

assigning a first value in each cell of said matrix when said column associated with said cell is associated with a particular said unit of text which appears in said version associated with said row associated with said cell; and

otherwise assigning a second value in said cell.

8. The method according to claim 5 and wherein said deriving comprises associating one combination of contiguous said rows of said matrix with one said virtual document.

9. The method according to claim 8 and wherein textual content of each said virtual document associated with a particular said combination comprises each said unit of text associated with each said column in said matrix in which there is a maximal run of said first value in said particular combination.

10. The method according to claim 5 and comprising ordering said versions in said subsequent rows according to their time of creation when said versions evolve in a linear manner.

11. The method according to claim 5 and comprising ordering said versions in said subsequent rows using DFS (Depth First Search) traversal when said versions evolve in a treelike manner.

12. The method according to claim 6 and wherein each said unit of text is one of the following:

a word, a sentence and a paragraph.

13. A search engine comprising:

an indexer to index a single time, text which is repeated in multiple edited versions of at least one document thereby generating a compact index; and

a query manager to conduct text searches in said compact index.

14. The search engine according to claim 13 wherein said versions of each said at least one document form a group and wherein said indexer comprises an aligner to generate a set of virtual documents for each said group and a predicate calculator to calculate mapping data correlating said virtual documents to said versions.

15. The search engine according to claim 14 and wherein said aligner associates each instance of repeating of said text in at least two successive said versions with a single appearance of said text in one of said virtual documents.

16. The search engine according to claim 15 and wherein said each instance comprises the repetition of a unit of said text wherein said unit is one of the following:

a word, a sentence, and a paragraph.

17. A computer product readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps, said method steps comprising:

for at least one document, indexing a single time, text which is repeated in multiple edited versions of said document thereby generating a compact index; and

conducting text searches in said compact index.

18. The computer product according to claim 17 and wherein said versions of each said at least one document form a group and wherein said indexing comprises:

generating a set of virtual documents for each said group;

indexing said virtual documents; and

recording mapping data correlating said virtual documents to said versions.

19. The computer product according to claim 18 and comprising associating and each instance of repetition of said text in at least two successive said versions with a single appearance of said text in one of said virtual documents.

20. The computer product according to claim 18 and wherein said generating comprises:

defining an alignment for each said group; and

deriving said set of virtual documents from said alignment.