Techniques for improved searching of electronically stored information

• US 6,778,980 B1
• Filed: 09/27/2001
• Issued: 08/17/2004
• Est. Priority Date: 02/22/2001
• Status: Expired due to Term

• Current Assignee: Walgreen Co. (Walgreens Boots Alliance Incorporated)
• Original Assignee: Drugstore.com Incorporated (Walgreens Boots Alliance Incorporated)
• Inventors: Madan, Umesh, Eppley, Geary
• Primary Examiner(s): Rones, Charles
• Application Number:
  US09/966,850
• Time in Patent Office: 1,055 Days
• Field of Search: 707/2, 707/3, 707/5, 707/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Methods and apparatuses for searching electronically-stored information are described. Specifically, in a network providing for electronic commerce, a computer system provides a user with access to a set of electronic commerce pages, category pages and databases for locating products electronically. To locate products electronically, the user performs a search using multiple words. Different forms of the words in the search request are used to generate search hits, and hit vectors containing bits corresponding to the words comprising each search hit are used to indicate the search hits.

Claims

1. A method of electronic searching comprising:

performing an OR search based on a search request having one or more search terms;

generating a hit for each of one or more OR search results that match a corresponding search term;

using the hits and combinations of the hits to generate a hit vector, wherein the hit vector includes one or more bits, each of the one or more bits respectively representing a search result for each of the one or more search terms;

sorting the hit vectors; and

providing search results based, at least in part, on the sorted hit vectors.

2. The method of claim 1, wherein performing the OR search further comprises stemming at least one of the one or more search terms.

3. The method of claim 1, wherein a logical value of one of a bit in the hit vector represents a hit and a logical value of zero of a bit in the hit vector represents a miss with respect to the search term represented by the respective bit.

4. The method of claim 1, wherein providing search results comprises:

sorting the search results in a descending order according to values represented by the bits of the hit vector; and

generating an indication of the descending order.

5. The method of claim 4, wherein sorting the search results comprises:

determining a number of the one or more search terms that are included in each combination of the one or more search terms for which the search is performed; and

sorting the search results based, at least in part, on the number of the, one or more search terms included in a corresponding combination of the one or more search terms.

6. The method of claim 4, further comprising:

grouping the search results of the one or more terms having the same value represented by the bits of the hit vector; and

displaying the number of search results corresponding to the hit vector representing the grouped search results.

7. The method of claim 4, wherein

the hits of the one or more search terms are represented by the corresponding bits of the hit vector starting from the least significant bit of the hit vector.

8. The method of claim 7, wherein

the hit vector includes a number of bits that is greater than or equals to the number of search terms, unused bits of the hit vector having a logical value of zero.

9. A machine-readable medium having stored thereon sequences of instructions that, when executed, cause one or more electronic systems to:

perform an OR search based on a search request having one or more search terms;

generate a hit for each of one or more OR search results that matches a corresponding search term;

use the hits and combinations of the hits to generate a hit vector, wherein the hit vector includes one or more bits, each of the one or more bits respectively representing a search result for each of the one or more search term;

sort the hit vectors; and

provide search results based, at least in part, on the sorted hit vectors.

10. The machine-readable medium of claim 9, wherein the sequences of instructions that, when executed, cause one or more electronic systems to perform OR the search comprise sequences of instructions that, when executed, cause the one or more electronic systems to stem at least one of the one or more search terms.

11. The machine-readable medium of claim 9, wherein a logical value of one of a bit in the hit vector represents a hit and a logical value of zero of a bit in the hit vector represents a miss with respect to the search term represented by the respective bit.

12. The machine-readable medium of claim 9, wherein the sequences of instructions that cause the one or more electronic systems to provide search results comprise sequences of instructions that, when executed, cause the one or more electronic systems to:

sort the search results in a descending order according to values represented by the bits of the hit vector; and

generate an indication of the descending order.

13. The machine-readable medium of claim 12, wherein the sequences of instructions that cause the one or more electronic systems to sort the search results comprise sequences of instructions that, when executed, cause the one or more electronic systems to:

determine a number of the one or more search terms that are included in each combination of the one or more search terms for which the search is performed; and

sort the search results based, at least in part, on the number of the one or more search terms included in a corresponding combination of the, one or more search terms.

14. The machine-readable medium of claim 12, further comprising sequences of instructions that, when executed, cause the one or more electronic systems to

group the search results of the one or more terms having the same value represented by the bits of the hit vector, and

display the number of the search results corresponding to the hit vector representing the grouped search results.

15. The machine-readable medium of claim 12, wherein

the hits of the one or more search terms are represented by the corresponding bits of the hit vector starting from the least significant bit of the hit vector.

16. The machine-readable medium of claim 15 wherein the hit vector includes a number of bits that is greater than or equals to the number of search terms, unused bits of the hit vector having a logical value of zero.

17. An apparatus comprising:

a processor; and

a memory coupled to the processor, the memory to store sequences of instructions that, when executed, cause one or more electronic systems to perform an OR search based on a search request having one or more search terms,

generate a hit for each of one or more OR search results that matches a corresponding search term,

use the hits and combinations of the hits to generate a hit vector, wherein the hit vector includes one or more bits, each of the one or more bits respectively representing a search result for each of the one or more search term,

sort the hit vectors, and provide search results based, at least in part, on the sorted hit vectors.

18. The apparatus of claim 17 wherein the sequences of instructions that, when executed, cause one or more electronic systems to perform the OR search comprise sequences of instructions that, when executed, cause the one or more electronic systems to stem at least one of the one or more search terms.

19. The apparatus of claim 17, wherein a logical value of one of a bit in the hit vector represents a hit and a logical value of zero of a bit in the hit vector represents a miss with respect to the search term represented by the respective bit.

20. The apparatus of claim 17, wherein the sequences of instructions that cause the one or more electronic systems to provide search results comprise sequences of instructions that, when executed, cause the one or more electronic systems to

sort the search results in a descending order according to values represented by the bits of the hit vector, and

generate an indication of the descending order.

21. The apparatus of claim 20, wherein the sequences of instructions that cause the one or more electronic systems to sort the search results comprise sequences of instructions that, when executed, cause the one or more electronic systems to

determine a number of the one or more search terms that are included in each combination of the one or more search terms for which the search is performed, and

sort the search results based, at least in part, on the number of the one or more search terms included in a corresponding combination of the one or more search terms.

22. The apparatus of claim 20, further comprising sequences of instructions that, when executed, cause the one or more electronic systems to

group the search results of the one or more terms having the same value represented by the bits of the hit vector, and

display the number of the search results corresponding to the hit vector representing the grouped search results.

23. The apparatus of claim 20, wherein hits of the one or more search terms are represented by the corresponding bits of the hit vector starting from the least significant bit of the hit vector.

24. The apparatus of claim 23, wherein the hit vector includes a number of bits that is greater than or equals to the number of search terms, unused bits of the hit vector having a logical value of zero.

25. A computer data signal embodied in a data communications medium shared among a plurality of network devices comprising sequences of instructions that, when executed, cause one or more electronic systems to:

perform an OR search based on a search request having one or more search terms;

generate a hit for each of one or more OR search results that matches a corresponding search term;

use the hits and combinations of the hits to generate a hit vector, wherein the hit vector includes one or more bits, each of the one or more bits respectively representing a search result for each of the one or more search term;

sort the hit vectors; and

provide search results based, at least in part, on the sorted hit vectors.

26. The computer data signal of claim 25, wherein the sequences of instructions that, when executed, cause one or more electronic systems to perform the OR search comprise sequences of instructions that, when executed, cause the one or more electronic systems to stem at least one of the one or more search terms.

27. The computer data signal of claim 25, wherein a logical value of one of a bit in the hit vector represents a hit and a logical value of zero of a bit in the hit vector represents a miss with respect to the search term represented by the respective bit.

28. The computer data signal of claim 25 wherein the sequences of instructions that cause the one or more electronic systems to provide search results comprise sequences of instructions that, when executed, cause the one or more electronic systems to:

sort the search results in a descending order according to values represented by the bits of the hit vector; and

generate an indication of the descending order.

29. The computer data signal of claim 28 wherein the sequences of instructions that cause the one or more electronic systems to sort the search results comprise sequences of instructions that, when executed, cause the one or more electronic systems to:

determine a number of the one or more search terms that are included in each combination of the one or more search terms for which the search is performed; and

sort the search results based, at least in part, on the number of the one or more search terms included in the corresponding combination of the one or more search terms.

30. The computer data signal of claim 28 further comprising sequences of instructions that, when executed, cause the one or more electronic systems to

group the search results of the one or more terms having the same value represented by the bits of the hit vector, and

display the number of the search results corresponding to the hit vector representing the grouped search results.

31. The computer data signal of claim 28 wherein the hits of the one or more search terms are represented by the corresponding bits of the hit vector starting from the least significant bit of the hit vector.

32. The computer data signal of claim 25 wherein the hit vector includes a number of bits that is greater than or equals to the number of search terms, unused bits of the hit vector having a logical value of zero.