# US 2013/0159315 A1 · Methods for prefix indexing

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

- Number: US 2013/0159315 A1
- Document ID: US20130159315A1
- Status: Published application
- Kind: A1
- Application number: 13/746,837
- Filed: 2013-01-22
- Published: 2013-06-20
- Earliest claimed: 2010-10-27
- Assignees: Apple Inc.
- Inventors: John M. Hornkvist; Erie R. Koebler
- Web page: https://patentgrep.com/patent/US20130159315A1

## CPC

- G06F 16/901: Indexing; Data structures therefor; Storage structures (for retrieval from the web G06F16/951)
- G06F 16/316: {Indexing structures}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

According to one aspect of the invention, in response to one or more terms to be indexed, each of the terms is indexed in a regular index. In addition, for each of the terms having multiple characters, at least one prefix portion of the term is indexed in a prefix index, where the regular index is used for regular searches and the prefix index is used for prefix searches without having to combine a plurality of postings lists of the regular index at the point in time.

## Claims

### Claim 1

A computer-implemented method for indexing one or more terms, comprising:
in response to one or more terms to be indexed, indexing each of the one or more terms in a regular index, the regular index having a plurality of postings lists and each postings list corresponding to a string containing one of the one or more terms;
for each of the one or more terms having a plurality of characters, indexing at least one prefix portion of each term in a prefix index that is processed separately from the regular index, wherein the regular index is used for regular searches, and wherein the prefix index is used for prefix searches without having to combine the plurality of postings lists of the regular index in response to a search query;
receiving a search query having a search term for searching files that contain the search term from a client;
determining whether a search to be performed is a regular search or a prefix search;
if the search is a regular search,
searching in the regular index to identify a plurality of postings lists, each containing the search term, and
returning to the client, a list of item identifiers from the plurality of postings lists obtained from the regular index; and
if the search is a prefix search,
searching in the prefix index to identify a single postings list that exactly matches the search term, and
returning to the client, a list of item identifiers from the single postings list.

### Claim 2 (depends on 1)

The method of claim 1, wherein the prefix portion of a term comprises a leading character and at least one adjacent character of the term.

### Claim 3 (depends on 1)

The method of claim 1, wherein each of the terms in the regular index and the prefix index is associated with a postings list having one or more items identifiers identifying one or more files that contain the associated term.

### Claim 4 (depends on 1)

The method of claim 1, wherein the one or more terms to be indexed are extracted from at least one of a content data file and metadata of the content data file.

### Claim 5 (depends on 1)

The method of claim 1, wherein the regular index and the prefix index are inverted indexes.

### Claim 6 (depends on 1)

The method of claim 1, wherein the regular index and the prefix index are stored in the same file, and wherein each prefix entry of the prefix index is tagged with a marker indicating that the corresponding prefix entry is part of prefix index.

### Claim 7 (depends on 1)

The method of claim 1, wherein the search term for the prefix search is captured and received as a user is typing in a search field.

### Claim 8

A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a computer, cause the computer to perform a method for indexing one or more terms, the method comprising:
in response to one or more terms to be indexed, indexing each of the one or more terms in a regular index, the regular index having a plurality of postings lists and each postings list corresponding to a string containing one of the one or more terms;
for each of the one or more terms having a plurality of characters, indexing at least one prefix portion of each term in a prefix index that is processed separately from the regular index, wherein the regular index is used for regular searches, and wherein the prefix index is used for prefix searches without having to combine a plurality of postings lists of the regular index in response to a search query;
receiving a search query having a search term for searching files that contain the search term from a client;
determining whether a search to be performed is a regular search or a prefix search; if the search is a regular search,
searching in the regular index to identify a plurality of postings lists, each containing the search term, and
returning to the client, a list of item identifiers from the plurality of postings lists obtained from the regular index; and
if the search is a prefix search,
searching in the prefix index to identify a single postings list that exactly matches the search term, and
returning to the client, a list of item identifiers from the single postings list,

### Claim 9 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the prefix portion of a term comprises a leading character and at least one adjacent character of the term.

### Claim 10 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein each of the terms in the regular index and the prefix index is associated with a postings list having one or more item identifiers identifying one or more files that contain the associated term.

### Claim 11 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the one or more terms to be indexed are extracted from at least one of a content data file and metadata of the content data file.

### Claim 12 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the regular index and the prefix index are inverted indexes.

### Claim 13 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the regular index and the prefix index are stored in the same file, and wherein each prefix entry of the prefix index is tagged with a marker indicating that the corresponding prefix entry is part of prefix index.

### Claim 14 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the search term for the prefix search is captured and received as a user is typing in a search field.

### Claim 15

A data processing system, comprising:
a processor; and
a memory coupled to the processor for storing instructions, which when executed by
the processor, cause the processor to perform a method, the method including
in response to one or more terms to be indexed, indexing each of the one or more terms in a regular index, the regular index having a plurality of postings lists and each postings list corresponding to a string containing one of the one or more terms,
for each of the one or more terms having a plurality of characters, indexing at least one prefix portion of each term in a prefix index that is processed separately from the regular index, wherein the regular index is used for regular searches, and wherein the prefix index is used for prefix searches without having to combine the plurality of postings lists of the regular index in response to a search query,
receiving a search query having a search term for searching tiles that contain the search term from a client,
determining whether a search to be performed is a regular search or a prefix search,
if the search is a regular search,
searching in the regular index to identify a plurality of postings lists, each containing the search term, and
returning to the client, a list of item identifiers from the plurality of postings lists obtained from the regular index, and
if the search is a prefix search,
searching in the prefix index to identify a single postings list that exactly matches the search term, and
returning to the client, a list of item identifiers from the single postings list.

### Claim 16 (depends on 15)

The system of claim 15, wherein the prefix portion of a term comprises a leading character and at least one adjacent character of the term.

### Claim 17 (depends on 15)

The system of claim 15, wherein each of the terms in the regular index and the prefix index is associated with a postings list having one or more items identifiers identifying one or more files that contain the associated term.

### Claim 18 (depends on 15)

The system of claim 15, wherein the one or more terms to be indexed are extracted from at least one of a content data file and metadata of the content data file.

### Claim 19 (depends on 15)

The system of claim 15, wherein the regular index and the prefix index are inverted indexes.

### Claim 20 (depends on 15)

The system of claim 15, wherein the regular index and the prefix index are stored in the same file, and wherein each prefix entry of the prefix index is tagged with a marker indicating that the corresponding prefix entry is part of prefix index.
