Search and Indexing on a User Device

• US 20080243828A1
• Filed: 06/14/2007
• Published: 10/02/2008
• 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: Lattyak, John, Reztlaff, James R.
• Granted Patent: US 7,716,224 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• 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 items; and

a search module executable on the processor to search text of the collection of electronic items in the memory in response to user input of a search query.

2. The handheld electronic book reader device of claim 1, wherein the collection comprises a subset of electronic items stored in the memory.

3. The handheld electronic book reader device of claim 1, wherein the collection comprises all electronic items stored in the memory.

4. The handheld electronic book reader device of claim 1, the memory further storing one or more searchable indices of terms in the one or more electronic items in the collection.

5. The handheld electronic book reader device of claim 4, wherein for each electronic item, the memory includes an item index of the terms in the respective electronic item, and wherein the memory further comprises a master index of terms in all of the electronic items in the collection.

6. The handheld electronic book reader device of claim 4, further comprising second memory comprising a second collection of one or more electronic items and one or more searchable indices of terms in the one or more electronic items in the second collection.

7. The handheld electronic book reader device of claim 6, wherein the memory comprises a master index of terms in all of the electronic items in the collection and the second memory includes a master index of terms in all of the electronic items in the second collection.

8. The handheld electronic book reader device of claim 6, wherein one or both of the memory and the second memory is removable from the handheld electronic book reader device.

9. The handheld electronic book reader device of claim 1, further comprising a user interface usable to enter a search query.

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

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

12. The handheld electronic book reader device of claim 1, further comprising an index module configured to generate indices corresponding to electronic items, the indices being usable by the search module to search for text of the one or more electronic items.

13. A method comprising:

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

searching the text of a collection of electronic items stored in memory of the electronic book reader device for the queried term; and

returning search results identifying locations in the electronic items at which the queried term appears.

14. The method of claim 13, wherein the collection comprises a subset of electronic items stored in memory of the electronic book reader device.

15. The method of claim 13, further comprising displaying a list identifying locations in the electronic items at which the queried term appears.

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

17. The method of claim 13, further comprising jumping to a location in an electronic item at which the queried term appears.

18. The method of claim 13, wherein searching the full text of the collection of electronic items comprises looking up the queried term in a master index of terms contained in the collection of electronic items.

19. The method of claim 13, wherein if the search query is input while a single electronic item is being displayed and the single electronic item contains the search query term, the single electronic item is displayed as a first entry of the search results.

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

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

textual media, image media, video media, audio media, application programs, annotations, or combinations thereof.

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

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

24. The method of claim 23, 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.

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

26. An apparatus comprising:

a processor; and

memory storing one or more electronic items and instructions executable on the processor to implement the method of claim 13.

27. A method comprising full text searching a collection of electronic items stored in memory of an electronic book reader device.

28. The method of claim 27, wherein the electronic items comprise textual media.

29. The method of claim 27, wherein the electronic items comprise an application program executable on the electronic book reader device.

30. An electronic book reader device comprising:

a processor;

memory storing one or more electronic items; and

an index module executable on the processor to generate searchable indices of the one or more electronic items.

31. The electronic book reader device of claim 30, further comprising one or more searchable indices stored in the memory.

32. The electronic book reader device of claim 31, wherein the one or more searchable indices consist of a single master index of all electronic items stored in the memory.

33. The electronic book reader device of claim 31, wherein the one or more indices searchable consist of an item index for each electronic item stored in the memory.

34. The electronic book reader device of claim 31, wherein the one or more searchable indices comprise a master index of terms in electronic items stored in the memory and at least one item index of terms in an electronic item.

35. A method, implemented at least partially by an electronic book reader device, the method comprising:

receiving one or more electronic items;

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

generating one or more searchable indices of the electronic item, the generating being performed by the electronic book reader device.

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

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

38. The method of claim 35, wherein generating the one or more searchable indices comprises generating a master index of terms in electronic items stored in the memory and generating at least one item index of terms in an electronic item.

39. A method comprising:

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 a device.

40. The method of claim 39, 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.

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

42. The method of claim 41, wherein each location identifier comprises an invariant location reference identifier.

43. The method of claim 41, 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.

44. The method of claim 39, wherein the master index comprises a list of terms used in electronic items in the collection and, for each term, a reference to each item index entry for the respective term.

45. The method of claim 44, 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 an item index for the respective electronic item.

46. The method of claim 39, wherein the item index of terms is organized alphabetically.

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

48. The method of claim 39, wherein the master index of terms is organized alphabetically.

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

50. The method of claim 39, 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.

51. The method of claim 39, 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.

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

playing an audio file or executing an application program.

53. The method of claim 39, wherein terms include one or more of the following:

words, phrases, numbers, and symbols.

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

55. A handheld electronic book reader device comprising:

a processor; and

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

56. A method comprising:

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

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

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

58. The method of claim 57, wherein each location identifier comprises an invariant location reference identifier.

59. The method of claim 57, 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.

60. The method of claim 56, wherein the item-specific master index comprises a list of terms used in the electronic item and, for each term, a reference to each item index entry for the respective term.

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

62. The method of claim 60, 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 an item index for the respective electronic item.

63. The method of claim 56, further comprising storing the item index and the item-specific master index in memory.

64. The method of claim 56, 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.

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

66. The method of claim 56, further comprising transmitting the item index and the master index to a handheld electronic book reader device.

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

68. A method comprising:

receiving an electronic item;

receiving a searchable item index of terms in the electronic item;

receiving a searchable item-specific master index of terms in the electronic item;

storing the electronic item and the item index in memory; and

merging the item-specific master index into an existing master index of terms in a collection of electronic items stored in memory.

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

70. The method of claim 69, wherein each location identifier comprises an invariant location reference identifier.

71. The method of claim 69, 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.

72. The method of claim 68, wherein the item-specific master index comprises a list of terms used in the electronic item and, for each term, a reference to each item index entry for the respective term.

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

74. One or more computer-readable media having stored thereon a data structure comprising:

a master-index data field comprising data representing a master index of terms, the master index field including;

a list of terms used in one or more electronic items, and

for each term in the list, a reference to one or more item index entries for the respective term, which indicate where the respective term is used in the one or more electronic items.

75. The one or more computer-readable media of claim 74, 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 appeared in the respective electronic item, and a position at which the term is indexed in an item index for the respective electronic item.

76. The one or more computer-readable media of claim 74, wherein master-index data field corresponds to an item-specific master index, such that:

the list of terms consists of terms used in a specific electronic item, and

the references to one or more item index entries for each term are limited to entries from an item index corresponding to the specific electronic item.

77. The one or more computer-readable media of claim 74, wherein master-index data field corresponds to a master index of a collection of electronic items, such that:

the list of terms comprises a list of terms used in each electronic item of the collection of electronic items, and

the references to one or more item index entries comprise references to item index entries from each electronic item in the collection of electronic items.

78. An apparatus comprising:

a processor; and

memory comprising a collection of one or more electronic items, a searchable item index of terms for each electronic item in the collection, and a master index of terms in all electronic items in the collection.

79. The apparatus of claim 78, wherein the collection consists of a single electronic item.

80. The apparatus of claim 79, further comprising second memory comprising a second collection of one or more electronic items, a searchable item index of terms for each electronic item in the second collection, and a master index of terms in all electronic items in the second collection.

81. The apparatus of claim 79, wherein the searchable item index comprises a list of location identifiers indicating a location at which each term appears within the electronic item.

82. The apparatus of claim 81, wherein each location identifier comprises an invariant location reference identifier.

83. The apparatus of claim 81, 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.

84. The apparatus of claim 79, wherein the master index comprises a list of terms used in electronic items in the collection and, for each term, a reference to each item index entry for the respective term.

85. The apparatus of claim 84, 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 an item index for the respective electronic item.

86. The apparatus of claim 79, wherein terms include one or more of the following:

words, phrases, numbers, and symbols.

87. A method comprising:

receiving an electronic item;

calling an application programming interface (API) to expose terms contained in the electronic item and a location of each term within the electronic item; and

indexing the terms exposed using the API.

88. The method of claim 91, wherein indexing the terms exposed using the API comprises generating a searchable item index of terms in the electronic item, and updating a searchable master index of terms in a collection of available electronic items to include the terms exposed using the API.

89. The method of claim 88, wherein indexing the terms exposed using the API comprises generating a searchable item index of terms in the electronic item, and generating an item-specific searchable master index of terms in the electronic item.

90. The method of claim 89, further comprising transmitting the item index and the item-specific master index to a handheld electronic reader device.

91. The method of claim 87, wherein the electronic item comprises an application program.

92. The method of claim 87, wherein the electronic item comprises an e-book.

93. The method of claim 87, wherein the electronic item comprises web data.

94. One or more computer-readable media comprising:

an electronic item executable on a processor; and

an indexing application programming interface (API) callable by the processor to expose terms contained in the electronic item and a location of each term within the electronic item.

95. The one or more computer-readable media of claim 94, further comprising an index module configured to receive the exposed terms contained in the electronic item and the location of each term within the electronic item and, based on the exposed terms and locations, indexing the electronic item.

96. The one or more computer-readable media of claim 95, wherein indexing the electronic item comprises generating a searchable item index of terms in the electronic item, and updating a searchable master index of terms in a collection of available electronic items to include the terms in the electronic item.

97. The one or more computer-readable media of claim 94, wherein the electronic item comprises an application program.

98. The one or more computer-readable media of claim 94, wherein the electronic item comprises an e-book.

99. The one or more computer-readable media of claim 94, wherein the electronic item comprises web data.

100. One or more computer-readable media comprising:

an electronic item executable on a processor; and

a search application programming interface (API) callable by the processor to expose terms contained in the electronic item, in response to entry of a location within the electronic item.

101. The one or more computer-readable media of claim 100, further comprising:

an electronic item executable on a processor; and

a navigation application programming interface (API) callable by the processor to cause an electronic book reader to jump to a location corresponding to the location within the electronic item.

102. The one or more computer-readable media of claim 100, further comprising a search module configured to receive the exposed terms in the electronic item, and to search the exposed terms for one or more queried terms.

103. The one or more computer-readable media of claim 102, wherein the search module is further configured to list the electronic item as an entry in search results if the electronic item is found to have the one or more queried terms.

104. The one or more computer-readable media of claim 100, wherein the electronic item comprises an application program.

105. The one or more computer-readable media of claim 100, wherein the electronic item comprises an e-book.

106. The one or more computer-readable media of claim 100, wherein the electronic item comprises web data.