Reordering of enriched inverted indices

• US 10,452,693 B2
• Filed: 04/07/2017
• Issued: 10/22/2019
• Est. Priority Date: 04/07/2017
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Transier, Frederik, Lemke, Christian, Seifert, Sebastian
• Primary Examiner(s): Kuddus, Daniel K
• Application Number:
  US15/482,518
• Publication Number:
  US 20180293298A1
• Time in Patent Office: 928 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]

Abstract

A method can include: reordering an enriched inverted index associated with a database, the enriched inverted index including a first inverted list having a first plurality of current document identifiers of records that contain a first data value, the enriched inverted index further including a first data structure storing enrichment data, the reordering of the enriched inverted index comprising: generating an ordinal sequence corresponding to an order of a first plurality of current document identifiers that include a change of at least one of the first plurality of current document identifiers to a new document identifier; determining a reordered ordinal sequence corresponding to a sorted order of the second plurality of document identifiers; separately reordering, based at least on the reordered ordinal sequence, the first plurality of current document identifiers in the first inverted list and the enrichment data in the first data structure.

Claims

1. A computer implemented method, comprising:

reordering an enriched inverted index associated with a database, the enriched inverted index including a first inverted list having a first plurality of current document identifiers of records that contain a first data value, the enriched inverted index being reordered in response to at least one of the first plurality of document identifiers being changed to a different document identifier, the enriched inverted index further including a first data structure storing enrichment data associated with the first inverted list, the reordering of the enriched inverted index comprising;

generating an ordinal sequence corresponding to an order of a second plurality of document identifiers in the first inverted list, the second plurality of document identifiers including the change of the at least one of the first plurality of current document identifiers to the different document identifier;

determining a reordered ordinal sequence, the reordered ordinal sequence corresponding to a sorted order of the second plurality of document identifiers;

first reordering, based at least on the reordered ordinal sequence, the first plurality of current document identifiers in the first inverted list; and

second reordering, based at least on the reordered ordinal sequence, enrichment data stored in the first data structure, the second reordering being performed separately from the first reordering; and

executing, based at least on the reordered enriched inverted index, a query to retrieve, from the database, the records containing the first data value subsequent to the at least one of the first plurality of document identifiers being changed to the different document identifier.

2. The computer-implemented method of claim 1, wherein the enrichment data comprises at least one of a statistic, a language, a part-of-speech, and a location associated with each occurrence of the first data value in a record.

3. The computer-implemented method of claim 1, wherein an order of the enrichment data in the first data structure conforms to an order of the first plurality of current document identifiers in the first inverted list.

4. The computer-implemented method of claim 3, wherein the enrichment data in the first data structure is reordered to have a same order as the sorted order of the second plurality of document identifiers.

5. The computer-implemented method of claim 1, wherein the generating of the ordinal sequence comprises assigning a value from an ascending sequence of values to each document identifier in the second plurality of document identifiers.

6. The computer-implemented method of claim 1, wherein the sorted order of the second plurality of document identifiers comprises an ascending numerical order.

7. The computer-implemented method of claim 1, wherein the enriched inverted index further includes a second inverted list and a second data structure that is associated with the second inverted list, the second inverted list and the second data structure being reordered separately from the first inverted list and the first data structure.

8. The computer-implemented method of claim 1, wherein the first plurality of document identifiers in the first inverted list and the enrichment data stored in the first data structure are reordered in parallel.

9. A system, comprising:

at least one processor; and

at least one memory storing instructions which, when executed by the at least one processor, result in operations comprising;

reordering an enriched inverted index associated with a database, the enriched inverted index including a first inverted list having a first plurality of current document identifiers of records that contain a first data value, the enriched inverted index being reordered in response to at least one of the first plurality of document identifiers being changed to a different document identifier, the enriched inverted index further including a first data structure storing enrichment data associated with the first inverted list, the reordering of the enriched inverted index comprising;

generating an ordinal sequence corresponding to an order of a second plurality of document identifiers in the first inverted list, the second plurality of document identifiers including the change of the at least one of the first plurality of current document identifiers to the different document identifier;

determining a reordered ordinal sequence, the reordered ordinal sequence corresponding to a sorted order of the second plurality of document identifiers;

first reordering, based at least on the reordered ordinal sequence, the first plurality of current document identifiers in the first inverted list; and

second reordering, based at least on the reordered ordinal sequence, enrichment data stored in the first data structure, the second reordering being performed separately from the first reordering; and

executing, based at least on the reordered enriched inverted index, a query to retrieve, from the database, the records containing the first data value subsequent to the at least one of the first plurality of document identifiers being changed to the different document identifier.

10. The system of claim 9, wherein the enrichment data comprises at least one of a statistic, a language, a part-of-speech, and a location associated with each occurrence of the first data value in a record.

11. The system of claim 9, wherein the generating of the ordinal sequence comprises assigning a value from an ascending sequence of values to each document identifier in the second plurality of document identifiers.

12. The system of claim 9, wherein the sorted order of the second plurality of document identifiers comprises an ascending numerical order.

13. The system of claim 9, wherein the enriched inverted index further includes a second inverted list and a second data structure that is associated with the second inverted list, the second inverted list and the second data structure being reordered separately from the first inverted list and the first data structure.

14. The system of claim 9, wherein the first plurality of document identifiers in the first inverted list and the enrichment data stored in the first data structure are reordered in parallel.

15. A non-transitory computer-readable storage medium including program code, which when executed by at least one data processor, cause operations comprising:

reordering an enriched inverted index associated with a database, the enriched inverted index including a first inverted list having a first plurality of current document identifiers of records that contain a first data value, the enriched inverted index being reordered in response to at least one of the first plurality of document identifiers being changed to a different document identifier, the enriched inverted index further including a first data structure storing enrichment data associated with the first inverted list, the reordering of the enriched inverted index comprising;

generating an ordinal sequence corresponding to an order of a second plurality of document identifiers in the first inverted list, the second plurality of document identifiers including the change of the at least one of the first plurality of current document identifiers to the different document identifier;

determining a reordered ordinal sequence, the reordered ordinal sequence corresponding to a sorted order of the second plurality of document identifiers;

first reordering, based at least on the reordered ordinal sequence, the first plurality of current document identifiers in the first inverted list; and

second reordering, based at least on the reordered ordinal sequence, enrichment data stored in the first data structure, the second reordering being performed separately from the first reordering; and

executing, based at least on the reordered enriched inverted index, a query to retrieve, from the database, the records containing the first data value subsequent to the at least one of the first plurality of document identifiers being changed to the different document identifier.

16. The non-transitory computer-readable storage medium of claim 15, wherein the enrichment data comprises at least one of a statistic, a language, a part-of-speech, and a location associated with each occurrence of the first data value in a record.

17. The non-transitory computer-readable storage medium of claim 15, wherein the generating of the ordinal sequence comprises assigning a value from an ascending sequence of values to each document identifier in the second plurality of document identifiers.

18. The non-transitory computer-readable storage medium of claim 15, wherein the sorted order of the second plurality of document identifiers comprises an ascending numerical order.

19. The non-transitory computer-readable storage medium of claim 15, wherein the enriched inverted index further includes a second inverted list and a second data structure that is associated with the second inverted list, the second inverted list and the second data structure being reordered separately from the first inverted list and the first data structure.

20. The non-transitory computer-readable storage medium of claim 15, wherein the first plurality of document identifiers in the first inverted list and the enrichment data stored in the first data structure are reordered in parallel.