Search and indexing on a user device

• US 7,716,224 B2
• Filed: 06/14/2007
• Issued: 05/11/2010
• 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: Reztlaff, James R. II, Lattyak, John
• Primary Examiner(s): Wong; Leslie
• Assistant Examiner(s): Fan; Shiow-Jy
• Application Number:
  US11/763,349
• Publication Number:
  US 20080243828A1
• Time in Patent Office: 1,062 Days
• Field of Search: 707/5, 707/100, 707/E17.014, 707/E17.069, 707/E17.083, 707/2
• 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 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;

memory storing a collection of one or more electronic books;

an index module stored in the memory and executable on the processor of the handheld electronic book reader device to generate searchable indices of the one or more electronic books at the handheld electronic book reader device; and

searchable indices stored in the memory and comprising a searchable item index of terms in one of the electronic books and a searchable master index of terms in the collection of one or more electronic books,

wherein the master index comprises a list of terms used in electronic books in the collection and, for each term, a reference to one or more item index entries for the respective term, and

wherein each reference to an item index entry comprises an identifier of the electronic book in which the term appears, a number of times the term appears in the respective electronic book, and a position at which the term is indexed in the item index for the respective electronic book.

29. The handheld electronic book reader device of claim 1, the index module further configured to display a status of index generation for one or more electronic books in the collection of electronic books.

30. The handheld electronic book reader device of claim 1, the index module further configured to present a priority interface, by which a user may set an order in which indexes are to be generated for electronic books in the collection of electronic books.

31. The handheld electronic book reader device of claim 1, the index module further configured to pause index generation in response to one or more of the following:

operation of a button of the device, insertion of memory into the device, receipt of a new electronic item, or updating software of the device.

32. The handheld electronic book reader device of claim 1, to index module further configured to slow index generation in response to one or more of the following:

playing an audio file or executing an application program.

2. A method, implemented at least partially by a handheld electronic book reader device, the method comprising:

under control of one or more systems of the handheld electronic book reader device configured with executable instructions,

receiving one or more electronic books;

storing the one or more electronic books in memory of the handheld electronic book reader device; and

generating one or more searchable indices of the one or more electronic books, the one or more searchable indices comprising a searchable item index of terms in one of the electronic books or a searchable master index of terms in a collection of one or more electronic books stored in the memory of the handheld electronic book reader device, the generating being performed by the electronic book reader device.

3. The method of claim 2, wherein generating the one or more searchable indices consists of generating a single master index of all electronic books stored in the memory.

4. The method of claim 2, wherein generating the one or more searchable indices consists of generating an item index for each electronic book stored in the memory.

5. The method of claim 2, wherein generating the one or more searchable indices comprises generating the master index of terms in the collection of electronic books stored in the memory and generating at least one item index of terms in an electronic book.

6. A method, implemented at least partially by a handheld electronic book reader device, the method comprising:

under control of one or more systems of the handheld electronic book reader device configured with executable instructions,

generating a searchable item index of terms in an electronic item; and

generating a searchable master index of terms in the electronic item and other electronic items in a collection of electronic items stored in memory of the handheld electronic book reader device,

wherein the master index comprises a list of terms used in electronic items in the collection and, for each term, a reference to one or more item index entries for the respective term, and

wherein each reference to an item index entry comprises an identifier of the electronic item in which the term appears, a number of times the term appears in the respective electronic item, and a position at which the term is indexed in the item index for the respective electronic item.

7. The method of claim 6, further comprising adding an electronic item to the collection of electronic items, generating a searchable item index of terms in the added electronic item, and updating the master index of terms to include terms in the added electronic item.

8. The method of claim 6, wherein the searchable item index comprises a list of location identifiers indicating a location at which each term appears within the electronic item.

9. The method of claim 8, wherein each location identifier comprises an invariant location reference identifier.

10. The method of claim 8, wherein each location identifier comprises a byte offset, a word count, a character count, or a defined region within the electronic item, corresponding to the location of the term in the electronic item.

11. The method of claim 6, wherein the item index of terms is organized alphabetically.

12. The method of claim 6, wherein the item index of terms is organized in order of a number of occurrences of each term in the electronic item.

13. The method of claim 6, wherein the master index of terms is organized alphabetically.

14. The method of claim 6, further comprising displaying a status of index generation for one or more electronic items in the collection of electronic items.

15. The method of claim 6, further comprising presenting a priority interface, by which a user may set an order in which indexes are to be generated for electronic items in the collection of electronic items.

16. The method of claim 6, further comprising pausing index generation in response to one or more of the following:

operation of a button of the device, insertion of memory into the device, receipt of a new electronic item, or updating software of the device.

17. The method of claim 6, further comprising slowing index generation in response to one or more of the following:

playing an audio file or executing an application program.

18. The method of claim 6, wherein terms include one or more of the following:

words, phrases, numbers, and symbols.

19. One or more computer-readable media comprising computer-executable instructions for implementing the method of claim 6.

20. A handheld electronic book reader device comprising:

a processor; and

memory storing instructions executable on the processor to implement the method of claim 6.

21. A method comprising:

under control of one or more computing systems configured with executable instructions,

generating a searchable item index of terms in an electronic item, the searchable item index comprising a list of location identifiers indicating a location at which each term appears within the electronic item;

generating a searchable item-specific master index of terms in the electronic item,

the item-specific master index comprising a list of terms used in the electronic item and, for each term, a reference to an item index entry for the respective term,

the reference to an item index entry comprising an identifier of the electronic item in which the term appears, a number of times the term appears in the respective electronic item, and a position at which the term is indexed in the item index for the respective electronic item; and

transmitting the item index and the master index to a handheld electronic book reader device.

22. The method of claim 21, wherein each location identifier comprises an invariant location reference identifier.

23. The method of claim 21, wherein each location identifier comprises a byte offset, a word count, a character count, or a defined region within the electronic item, corresponding to the location of the term in the electronic item.

24. The method of claim 21, wherein the list of terms in the item-specific master index consists of terms in the electronic item.

25. The method of claim 21, further comprising storing the item index and the item-specific master index in memory of the one or more computing systems.

26. The method of claim 21, further comprising generating a searchable item index of terms for plural electronic items, and for each of the plural electronic items, generating a searchable item-specific master index of terms in the respective electronic item.

27. The method of claim 21, further comprising compressing the item index, the item-specific master index, or both.

28. One or more computer-readable media comprising computer-executable instructions for implementing the method of claim 21.