Search and indexing on a user device

• US 8,954,444 B1
• Filed: 04/14/2010
• Issued: 02/10/2015
• Est. Priority Date: 03/29/2007
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Retzlaff, James R. II, Lattyak, John
• Primary Examiner(s): Fan, Shiow-Jy
• Application Number:
  US12/759,828
• Time in Patent Office: 1,763 Days
• Field of Search: 707/741, 707/E17.014, 707/E17.069, 707/E17.083, 707/711
• US Class Current: 707/741
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3331 Query processing

Abstract

Search may be performed on a user device, such as a handheld electronic book reader device. A search query term may be received. Text of a collection of electronic items stored in memory of the user device may be searched, using an item index and/or a master index, for the queried term. Search results may be returned identifying locations in the electronic items at which the queried term appears.

Claims

1. A handheld electronic book reader device comprising:

a processor and memory arranged in the handheld electronic book reader device, the memory storing;

a collection of a plurality of electronic books;

a plurality of item indexes, each item index including a plurality of terms used in a corresponding electronic book in the collection, each term having a position entry at which the term is indexed in the corresponding item index for each corresponding electronic book;

a master index of a plurality of terms used in the collection, each term associated with a pointer to an entry of a corresponding item index for a corresponding electronic book, each pointer comprising an identifier for the corresponding item index in which the term appears, a number of times the term appears in the corresponding item index, and the position entry at which the term is indexed in the corresponding item index; and

a search module executable on the processor to search the plurality of item indexes and the master index in response to user input of a search query entered via a user interface of the handheld electronic book reader device, to return search results identifying locations in one or more of the electronic books at which the search query appears and to cause display of the search results.

2. The handheld electronic book reader device of claim 1, wherein the memory is removable from the handheld electronic book reader device.

3. The handheld electronic book reader device of claim 1, wherein the user interface comprises a keypad.

4. The handheld electronic book reader device of claim 1, wherein the user interface comprises a pointing device.

5. The handheld electronic book reader device of claim 1, further comprising an index module configured to generate the plurality of item indexes.

6. The handheld electronic book reader device of claim 1, the memory further storing executable instructions that, when executed, cause the processor to reconstruct the master index from the plurality of item indexes when the master index is corrupted or lost.

7. The handheld electronic book reader device of claim 1, the memory further storing executable instructions that, when executed, cause the processor to re-index the plurality of item indexes when at least one item index of the plurality of item indexes is corrupted or lost, without regenerating the master index.

8. A method comprising;

under control of an electronic book reader device comprising a display screen;

receiving a search query for a queried term input via a user interface of an electronic book reader device;

searching for the queried term in a master index of a collection of electronic books stored in memory of the electronic book reader device;

providing a pointer to an item index for each electronic book that includes the queried term, each pointer comprising an identifier for a respective item index for a respective electronic book, a number of times the queried term appears in the respective item index for the respective electronic book, and a position entry at which the queried term is indexed in the respective item index for the respective electronic book, wherein each item index includes a plurality of terms used in a respective electronic book, each term having a position entry at which the term is indexed in the respective item index for the respective electronic book;

returning search results identifying locations in one or more of the electronic books at which the queried term appears; and

causing display of the search results on the display screen.

9. The method of claim 8, wherein the collection comprises a subset of electronic books stored in memory of the electronic book reader device.

10. The method of claim 8, further comprising displaying excerpts of one or more of the electronic books, each excerpt comprising at least one instance of the queried term in context with text surrounding the queried term.

11. The method of claim 8, further comprising jumping to a location in an electronic book at which the queried term appears.

12. The method of claim 8, further comprising prompting a user to set a scope of the search to full text of all electronic books stored in memory of the electronic book reader device or to full text of a subset of the electronic books stored in memory of the electronic book reader device.

13. The method of claim 8, wherein electronic books include one or more of the following:

audio media, annotations, or combinations thereof.

14. The method of claim 8, further comprising stemming the search query prior to searching for the queried term.

15. The method of claim 14, wherein stemming comprises expanding the queried term to include variations of the queried term including one or more of the following:

plural forms, singular forms, other verb tenses, common misspellings, translations in other languages, possessive forms, or domain names.

16. The method of claim 14, wherein stemming comprises expanding the queried term to include variations of the queried term including plural forms, singular forms, and domain names.

17. One or more non-transitory computer-readable media in a handheld electronic book reader device having instructions stored thereon for performing a method, the method comprising:

storing a plurality of item indexes, each item index including a plurality of terms used in a respective electronic book in a collection of electronic books, each term having a position entry at which the term is indexed in the respective item index for the respective electronic book;

storing a master-index comprising data representing a master index of a plurality of terms for the collection of electronic books, the master-index including;

a list of terms used in one or more electronic books, wherein each term in the list having been indexed by an index module of the handheld electronic book reader device, and

each term in the list comprising a reference to one or more book index entries for the respective term, the reference comprising an identifier for a respective electronic book in which the term appears, a number of times the term appears in the respective electronic book, and the position entry at which the term is indexed in the item index for the respective electronic book;

receiving a search query for a queried term input via a user interface of the handheld electronic book reader device;

returning search results identifying locations in one or more of the collection of electronic books at which the queried term appears; and

causing display of the search results.

18. The one or more non-transitory computer-readable media of claim 17, wherein the method further comprises merging an item-specific master index with the master index.