Techniques for navigational query identification

• US 20080059508A1
• Filed: 08/30/2006
• Published: 03/06/2008
• Est. Priority Date: 08/30/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Peng, Fuchun, Lu, Yumao, Li, Xin, Ahmed, Nawaaz
• Granted Patent: US 7,693,865 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 18/2113 by ranking or filtering the set of features, e.g. using a measure of variance or of feature cross-correlation
• CPC Class Codes: G06F 18/24155 Bayesian classification

Abstract

To accurately classify a query as navigational, thousands of available features are explored, extracted from major commercial search engine results, user Web search click data, query log, and the whole Web'"'"'s relational content. To obtain the most useful features for navigational query identification, a three level system is used which integrates feature generation, feature integration, and feature selection in a pipeline. Because feature selection plays a key role in classification methodologies, the best feature selection method is coupled with the best classification approach to achieve the best performance for identifying navigational queries. According to one embodiment, linear Support Vector Machine (SVM) is used to rank features and the top ranked features are fed into a Stochastic Gradient Boosting Tree (SGBT) classification method for identifying whether or not a particular query is a navigational query.

Claims

1. A method comprising performing a machine-executed operation involving instructions for identifying a navigational query, wherein the machine-executed operation is at least one of:

A) sending said instructions over transmission media;

B) receiving said instructions over transmission media;

C) storing said instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein said instructions are instructions which, when executed by one or more processors, cause performance of;

determining whether a query is a navigational query by

receiving a set of query-URL pair-wise features based at least in part on said query in conjunction with an associated query result set;

integrating subsets of said set of query-URL pair-wise features to generate a set of query-based features;

automatically selecting, from said set of query-based features, a subset of most effective features for identifying navigational queries, wherein said selecting is based on a machine learning feature selection method;

based on said subset of most effective features, using a machine learning classification method to determine whether said query is a navigational query.

2. The method of claim 1, wherein said machine learning feature selection method is a linear support vector machine method.

3. The method of claim 1, wherein said machine learning classification method is a stochastic gradient boosting tree method.

4. The method of claim 1, wherein said machine learning feature selection method is a linear support vector machine method and said machine learning classification method is a stochastic gradient boosting tree method.

5. The method of claim 1, wherein said receiving comprises receiving a set of query-URL pair-wise features based on information from a click engine, a Web-map, and a query log.

6. The method of claim 1, wherein said receiving comprises receiving a set of query-URL pair-wise features comprising click features, URL features, and anchor text features.

7. The method of claim 1, wherein said integrating comprises generating said set of query-based features based on statistics associated with said subsets of said set of query-URL pair-wise features.

8. The method of claim 1, wherein said integrating comprises generating said set of query-based features based in part on statistics associated with a click-based subset of said set of query-URL pair-wise features.

9. The method of claim 1, wherein said integrating comprises generating said set of query-based features based in part on statistics associated with a URL-based subset of said set of query-URL pair-wise features.

10. The method of claim 1, wherein said integrating comprises generating said set of query-based features based in part on statistics associated with an anchor text-based subset of said set of query-URL pair-wise features.

11. The method of claim 1, wherein said integrating comprises generating said set of query-based features based in part on a normalized ratio operator defined as r_k(f_i)=[max(f_j)−

f_jk]/[max(f_j)−

min(f_j)] where k=2, 5, 10, 20.

12. The method of claim 1, wherein said selecting comprises selecting, from said set of query-based features, a subset of approximately fifty most effective features for identifying navigational queries.

13. The method of claim 1, wherein said instructions are instructions which, when executed by one or more processors, cause performance of:

in response to determining that said query is a navigational query, returning only a subset of said query result set.

14. The method of claim 1, wherein said machine learning feature selection method is an information gain method.

15. The method of claim 1, wherein said machine learning feature selection method is a gradient boosting tree method.

16. The method of claim 1, wherein said machine learning classification method is a naive Bayes method.

17. The method of claim 1, wherein said machine learning classification method is a maximum entropy method.

18. The method of claim 1, wherein said machine learning classification method is a support vector machine method.