INVERTED INDEX PROCESSING

• US 20080306949A1
• Filed: 06/08/2007
• Published: 12/11/2008
• Est. Priority Date: 06/08/2007
• Status: Abandoned Application

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Loofbourrow, Wayne, Hoernkvist, John Martin, Koebler, Eric Richard
• Application Number:
  US11/760,673
• Publication Number:
  US 20080306949A1
• Time in Patent Office: Days
• US Class Current: 707/7
• CPC Class Codes: G06F 16/319 Inverted lists

Abstract

Systems and methods for processing an index are described. In one exemplary method, a 2-level term table and postings table is used to generate postings lists. The postings lists are optimally stored in a postings file. Update sets for an index are optimally processed to update a index to a storage medium using flushing.

Claims

1. A machine implemented method of indexing, the method comprising:

storing more frequently occurring terms in a first table of an inverted index, the first table optimized for updating;

storing less frequently occurring terms in a second table, the second table not optimized for updating;

posting an item in which a more frequently occurring term occurs in the first table;

copying a previously posted item from the first table to a postings table; and

updating the posted item to point to the previously posted item in the postings table.

2. The method of claim 1, wherein posting to the first table is optimized for updating using a posting format that substantially minimizes an amount of memory used to post an item.

3. The method of claim 2, wherein the posting format that substantially minimizes the amount of memory used to post an item comprises:

allocating a space having a number of slots; and

storing each item in a next available slot in reverse order.

4. The method of claim 1, further comprising:

calculating a frequency of a term; and

determining whether the term is a less frequently occurring term or a more frequently occurring term based on the calculated frequency.

5. The method of claim 1, wherein the terms occur in at least one item of a corpus of items.

6. A machine-implemented method of indexing, the method comprising:

allocating a first space on a storage medium for storing a postings file, the postings file containing data representing at least one list of items containing a term;

writing the data to the allocated space in reverse order; and

allocating a second space on a storage medium for storing the postings file, when writing the data would cause the postings file to exceed the amount of space allocated thus far.

7. The machine-implemented method in claim 6, further comprising:

appending new data to old data; and

updating a pointer in the appended new data to point to the old data.

8. The machine-implemented method in claim 6, further comprising storing the data in term order.

9. The machine-implemented method in claim 8, further comprising storing a term identifier with each entry in the list of items containing the term, wherein storing the data in term order includes storing entries in term identifier order.

10. A machine-implemented method of improving indexing, the method comprising:

storing an inverted index on a storage medium, the inverted index mapping a term to an item containing the term;

sorting strings in an update set of strings representing items containing the term in a first order, the first order by a relative location of the term as mapped in the stored inverted index; and

inserting strings from the update set of strings into the stored inverted index in accordance with the first order.

11. The machine-implemented method of claim 10, wherein the relative location of the term as mapped in the inverted index is an offset to a page of the storage medium on which the inverted index has been stored.

12. The machine-implemented method of claim 10, further comprising:

sorting strings in the update set of strings in a second order within the first order, the second order by string order; and

inserting strings from the update set of strings into the stored inverted index in accordance with the second order within the first order.

13. The machine-implemented method of claim 12, wherein inserting strings from the update set of strings into the stored inverted index in accordance with the second order within the first order comprises:

storing a pointer to a last accessed location associated with the relative location of the term as mapped in the stored inverted index; and

inserting strings from the update set of strings using the last accessed location stored in the pointer.