Computer-implemented method, computer program product and system for creating an index of a subset of data

• US 8,010,501 B2
• Filed: 09/04/2007
• Issued: 08/30/2011
• Est. Priority Date: 09/19/2006
• Status: Active Grant

• Current Assignee: Dassault Systemes SA
• Original Assignee: Exalead SA (Dassault Systemes SA)
• Inventors: Douetteau, Florian, Donze, Stéphane, Bourdoncle, François
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Gebresenbet; Dinku W
• Application Number:
  US11/849,781
• Publication Number:
  US 20080294597A1
• Time in Patent Office: 1,456 Days
• Field of Search: None
• US Class Current: 707/673
• CPC Class Codes: G06F 16/328 Management therefor

Abstract

A computer implemented method for transforming an inverted index of a collection of documents into a smaller inverted index of documents. The smaller index contains links to all and only to those documents appearing in a subset of the original collection of documents. The method avoids reprocessing the subset to create the smaller inverted index by intersecting each inverted list with the list of document references from the desired subset. If this intersection is empty then the list is removed from the new smaller index, otherwise the list containing only the intersected reference list is included in the new inverted index. The method is also extended to deal with creating multiple smaller inverted indexes and with propagating updates changes in the first collection of documents down into the smaller inverted index or indexes.

Claims

1. A computer-implemented method for creating an inverted index of a subset of data, comprising:

executing in a computer system processor a software component of a computer program product, wherein said executing of the software component configures the computer system to perform;

a first step of receiving from computer storage;

a set of data;

a first inverted index of said set of data; and

identifiers of a subset of data of said set; and

a second step of creating, without reprocessing the data identified by said identifiers, a second inverted index using only the first inverted index and said identifiers, said second inverted index being both an inverted index of said subset of data and a subset of said first inverted index, wherein said second step of creating comprises comparing the first inverted index with said identifiers, and wherein said second step does not make use of data of the set which are not in the subset or identifiers of data of the set which are not in the subset.

2. The method of claim 1, wherein the set of data comprises a plurality of documents, said subset being a subset of said documents.

3. The method of claim 2, wherein the first inverted index created at the first step is an inverted file index storing a mapping from words to said documents.

4. The method of claim 3, wherein said first inverted index comprises a plurality of inverted lists, each of said lists corresponding to a respective word of said words.

5. The method of claim 4, wherein the step of comparing the first inverted index with said identifiers comprises computing, for each said words, an intersection of each respective list with said identifiers.

6. The method of claim 4 wherein each of said inverted lists is sorted and compressed.

7. The method of claim 1, wherein the first step further comprises selecting said subset of data according to the received first inverted index and a criterion.

8. The method of claim 1, wherein:

the first step comprises receiving a plurality of sets of identifiers, each set of identifiers corresponding to a respective subset of data of said set; and

the second step comprises;

creating a plurality of second inverted indexes according to the first inverted index and said sets of identifiers, each of said second inverted indexes being an inverted index of a respective subset of data.

9. The method of claim 1, further comprising:

a third step of updating the first inverted index and storing first residual data, such that the updated first inverted index is computed according to the inverted index as before updating and said first residual data; and

a fourth step of

updating the second inverted index according to said first residual data and identifiers of the subset of data, and

storing second residual data, such that the updated second inverted index is computed according to the second inverted index before updating and second residual data.

10. A computer program product on a computer readable storage medium, the computer program product including a software component executable by a computer system processor to perform the steps of:

a first step of receiving from computer storage;

a set of data;

a first inverted index of said set of data; and

identifiers of a subset of data of said set; and

a second step of creating, without reprocessing the data identified by said identifiers, a second inverted index using only the first inverted index and said identifiers, said second inverted index being both an inverted index of said subset of data and a subset of said first inverted index, wherein said second step of creating comprises comparing the first inverted index with said identifiers, wherein said second step does not make use of data of the set which are not in the subset or identifiers of data of the set which are not in the subset.

11. A computer system comprising:

computer storage; and

a computer program product including a software component executable by a computer system processor to perform the steps of;

a first step of receiving from said computer storage;

a set of data;

a first inverted index of said set of data; and

identifiers of a subset of data of said set; and

a second step of creating, without reprocessing the data identified by said identifiers, a second inverted index using only the first inverted index and said identifiers, said second inverted index being both an inverted index of said subset of data and a subset of said first inverted index, wherein said second step of creating comprises comparing the first inverted index with said identifiers, and wherein said second step does not make use of data of the set which are not in the subset or identifiers of data of the set which are not in the subset.