Implicit links search enhancement system and method for search engines using implicit links generated by mining user access patterns

• US 7,584,181 B2
• Filed: 09/30/2003
• Issued: 09/01/2009
• Est. Priority Date: 09/30/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Zeng, Hua-Jun, Xue, Gui-Rong
• Primary Examiner(s): Fleurantin; Jean B
• Application Number:
  US10/676,794
• Publication Number:
  US 20050071465A1
• Time in Patent Office: 2,163 Days
• Field of Search: 707 1- 10, 707100-1041, 715/513, 715206-208, 715/738, 715/741, 715/815, 709/224
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

An implicit links enhancement system and method for search engines that generates implicit links obtained from mining user access logs to facilitate enhanced local searching of web sites and intranets. The implicit links search enhancement system and method includes extracting implicit links by mining users'"'"' access patterns and then using a modified link analysis algorithm to re-rank search results obtained from traditional search engines. More specifically, the implicit links search enhancement method includes extracting implicit links from a user access log, generating an implicit links graph from the extracted implicit links, and computing page rankings using the implicit links graph. The implicit links are extracted from the log using a two-item sequential pattern mining technique. Search results obtained from a search engine are re-ranked based on an implicit links analysis performed using an updated implicit links graph, a modified re-ranking formula, and at least one re-ranking technique.

Claims

1. A computer-readable storage medium having stored and encoded thereon computer-executable instructions for performing on a computing device an enhanced local search of web sites and intranets by mining user access logs, comprising:

segmenting the user access log into different browsing sessions;

generating ordered pairs of pages from the browsing sessions to find implicit links by using a gliding window to move over explicit paths of the browsing sessions to generate the ordered pairs of pages;

determining a frequency of each of the ordered pairs;

defining a minimum support threshold;

applying the minimum support threshold to the frequency of each of the ordered pairs;

filtering the ordered pairs to remove any ordered pairs that are infrequently occurring;

constructing an implicit links graph from the implicit links;

generating two-item sequential patterns from the ordered pairs;

updating the implicit links graph using the two-item sequential patterns;

re-ranking search results obtained from a search engine to enhance the local searching to produce updated search results; and

displaying the updated search results to a user.

2. The computer-readable storage medium of claim 1, further comprising pre-processing the user access log using at least one of:

(a) data cleaning;

(b) browsing session identification;

(c) consecutive repetition elimination.

3. The computer-readable storage medium of claim 1, further comprising identifying each individual ones of the browsing sessions.

4. The computer-readable storage medium of claim 3, further comprising identifying in terms of a user identification and a chronological order of pages.

5. The computer-readable storage medium of claim 1, further comprising defining the gliding window size, wherein the size represents a maximum interval a user clicks between a source page and a target page.

6. The computer-readable storage medium of claim 1, further comprising discarding an ordered pair if its frequency is below the minimum support threshold.

7. The computer-readable storage medium of claim 1, further comprising keeping an ordered pair if its frequency is above the minimum support threshold.

8. A computer-implemented method contained on computer-readable storage media having stored and encoded thereon computer-executable instructions for execution on a general-purpose computing device for enhancing initial search results of a search engine performing a local search of a web sub-space using a user access log, comprising:

using the general-purpose computing device to perform the following process actions;

pre-processing the user access log;

segmenting the log into browsing sessions;

generating ordered pairs of implicit links from the browsing sessions;

filtering the ordered pairs using a minimum support threshold to remove any infrequently occurring ordered pairs to generate two-item sequential patterns;

updating an implicit links graph using the two-item sequential patterns;

defining an adjacency matrix to describe the updated implicit links graph;

defining a modified re-ranking formula in terms of the adjacency matrix;

modifying the re-ranking formula using a random walk technique;

re-ranking the initial search results using the updated implicit links graph to generate enhanced search results; and

displaying the enhanced search results to a user.

9. The computer-implemented method as set forth in claim 8, further comprising discarding any ordered pairs having a frequency below the minimum support threshold.

10. The computer-implemented method as set forth in claim 8, further comprising keeping any ordered pairs having a frequency above the minimum support threshold.

11. The computer-implemented method as set forth in claim 8, further comprising computing a page rank using the adjacency matrix.

12. The computer-implemented method as set forth in claim 8, further comprising discarding any ordered pairs having a frequency below the minimum support threshold.

13. The computer-implemented method as set forth in claim 12, wherein the random walk technique further comprises a probability parameter.

14. The computer-implemented method as set forth in claim 8, wherein re-ranking further comprises using an order-based re-ranking technique.

15. The computer-implemented method as set forth in claim 14, wherein the order-based re-ranking technique further comprises using a linear combination of page positions contained on two lists.

16. The computer-implemented method as set forth in claim 15, wherein one of the two lists is sorted by similarity scores.

17. The computer-implemented method as set forth in claim 15, wherein one of the lists is sorted by PageRank values.

18. The computer-implemented method as set forth in claim 8, wherein re-ranking further comprises using an score-based re-ranking technique.

19. The computer-implemented method as set forth in claim 18, wherein the score-based re-ranking technique further comprises using a linear combination of a content-based similarity score and a PageRank value of all pages.