Indexing

• US 20080033909A1
• Filed: 08/04/2006
• Published: 02/07/2008
• Est. Priority Date: 08/04/2006
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Loofbourrow, Wayne, Li, Yun-chih S., Koebler, Eric Richard, Arrouye, Yan, Hornkvist, John Martin
• Granted Patent: US 7,783,589 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/3331 Query processing

Abstract

Systems and methods for improving indexing are described. In one exemplary method, a 2-level table is used to improve performance when searching an index. A first table contains a subset of more frequently occurring terms and a second and larger table contains terms that occur rarely, with the first table optimized for updating and the second table optimized for searching. The second table is searched only when a search of the first table is unsuccessful. Other methods are described and data processing systems and machine readable media are also described.

Claims

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

storing a subset of 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 optimized for searching;

searching for a term in the first table; and

searching for a term in the second table only when searching for the term in the first table was unsuccessful.