# US 2008/0306949 A1 · Inverted index processing

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0306949 A1
- Document ID: US20080306949A1
- Status: Published application
- Kind: A1
- Application number: 11/760,673
- Filed: 2007-06-08
- Published: 2008-12-11
- Earliest claimed: 2007-06-08
- Inventors: John Martin Hoernkvist; Eric Richard Koebler; Wayne Loofbourrow
- Web page: https://patentgrep.com/patent/US20080306949A1

## CPC

- G06F 16/319: {Inverted lists}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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

### Claim 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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 6)

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

### Claim 9 (depends on 8)

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.

### Claim 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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 10)

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.

### Claim 13 (depends on 12)

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.
