Interleaving search results

• US 7,873,633 B2
• Filed: 07/13/2007
• Issued: 01/18/2011
• Est. Priority Date: 07/13/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smolyanskiy, Nikolay
• Primary Examiner(s): Kim; Charles
• Assistant Examiner(s): GIRMA, ANTENEH B
• Application Number:
  US11/777,560
• Publication Number:
  US 20090019030A1
• Time in Patent Office: 1,285 Days
• Field of Search: None
• US Class Current: 707/728
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Search result interleaving may be provided. First, a first list comprising online results may be received. Next, a second list comprising local results may be received. Then a subsequence common to the first list and the second list may be determined using a longest common subsequence algorithm. Next, an interleaved list may be created using the determined subsequence and a smart merge interleave algorithm to interleave the first list and the second list without hurting relevance.

Claims

1. A method for interleaving search results, the method comprising:

receiving a first list comprising at least a first result;

receiving a second list comprising at least a second result and a third result, the third result listed subsequent to the second result in the second list, wherein receiving a second list comprises receiving the second list having;

results obtained from a first database different than a second database used to obtain at least the first result of the first list, and

results obtained using a first algorithm different than a second algorithm used to obtain at least the first result of the first list;

determining that the first result corresponds to the second result; and

creating an interleaved list comprising the first result and the third result, wherein the third result is listed subsequent to the first result and the second result is excluded from the interleaved list, wherein creating the interleaved list comprises comparing a first set of relevance values associated with the first list with a second set of relevance values associated with the second list, the first set of relevance values being dependent on the first algorithm and being different from the second set of relevance values dependent on the second algorithm.

2. The method of claim 1, wherein receiving the first list comprises receiving the first list comprising online results.

3. The method of claim 1, wherein receiving the second list comprises receiving the second list comprising local results.

4. The method of claim 1, wherein receiving the second list comprises receiving the second list wherein the first result is a more current version of the second result received in the second list.

5. The method of claim 1, wherein receiving the second list comprises receiving the second list wherein no version of the third result is available online.

6. The method of claim 1, wherein receiving the second list comprises receiving the second list wherein the third result comprises original equipment manufacturer (OEM) data.

7. The method of claim 1, wherein determining that the first result corresponds to the second result comprises determining that an asset identification associated with the first result corresponds to an asset identification associated with the second result.

8. The method of claim 1, wherein receiving the first list comprises receiving the first list comprising a reference.

9. The method of claim 8, wherein creating the interleaved list comprises creating the interleaved list comprising the reference.

10. The method of claim 1, wherein receiving the first list comprises receiving the first list from a first search engine that used a first search algorithm to create the first list.

11. The method of claim 1, wherein receiving the first list comprises receiving the first list from a first search engine that used a first search algorithm to create the first list, the first search algorithm configured to search a local database on a local computing device.

12. The method of claim 1, wherein receiving the second list comprises receiving the second list from a second search engine that used a second search algorithm to create the second list.

13. The method of claim 1, wherein receiving the second list comprises receiving the second list from a second search engine that used a second search algorithm to create the second list, the second search algorithm configured to search databases not on a local computing device.

14. A computer-readable storage medium which stores a set of instructions which when executed performs a method for interleaving search results, the method executed by the set of instructions comprising:

receiving a first list comprising online results, wherein receiving the first list comprising the online results comprises receiving the first list obtained using a first algorithm, the first algorithm having a first result relevance metric;

receiving a second list comprising local results, wherein receiving the second list comprising the local results comprises receiving the second list obtained using a second algorithm, the second algorithm having a second result relevance metric;

determining a subsequence common to the first list and the second list; and

creating, when a number of elements in the subsequence is greater than a predetermined value, an interleaved list from the first list and the second list, wherein creating the interleaved list further comprises,

placing, in the interleaved list, a first set of references from the first list common to both the first list and the second list, and

placing, in the interleaved list, a second set of references from the second list not common to both the first list and the second list, wherein relevance for the second set of references from the second list not common to both the first list and the second list is preserved in the interleaved list by using a relative location of the second set of references in the second list not common to both the first list and the second list, wherein using the relative location of the second set of references in the second list not common to both the first list and the second list comprises comparing the first result relevance metric with the second result relevance metric.

15. The computer-readable storage medium of claim 14, wherein determining the subsequence common to the first list and the second list comprises using a Longest Common Subsequence algorithm.

16. The computer-readable storage medium of claim 14, wherein receiving the second list comprises receiving the second list wherein the local results comprise original equipment manufacturer (OEM) data.

17. The computer-readable storage medium of claim 14, wherein creating, when the number of elements in the subsequence is greater than the predetermined value, the interleaved list comprises creating, when the number of elements in the subsequence is greater than the predetermined value comprising three.

18. The computer-readable storage medium of claim 14, further comprising creating, when the number of elements in the subsequence is one of less than the predetermined value and equal to the predetermined value, the interleaved list using a one-to-one algorithm to interleave the first list and the second list.

19. A system for interleaving search results, the system comprising:

a memory storage; and

a processing unit coupled to the memory storage, wherein the processing unit is operative to;

receive a first list comprising online results, the first list being obtained using a first algorithm having a first set of relevance metrics;

receive a second list comprising local results, the second list being obtained using a second algorithm having a second set of relevance metrics;

determine a subsequence common to the first list and the second list using a longest common subsequence algorithm; and

create an interleaved list using the determined subsequence and a smart merge interleave algorithm to interleave the first list and the second list, wherein the smart merge interleave algorithm compares the first set of relevance metrics with the second set of relevance metrics.

20. The system of claim 19, wherein the processing unit being operative to receive the second list comprises the processing unit being operative to receive the second list wherein the local results comprise original equipment manufacturer (OEM) data.