QUERY LOG MINING FOR DETECTING SPAM HOSTS

• US 20100082752A1
• Filed: 09/30/2008
• Published: 04/01/2010
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Gionis, Aristides, Donato, Debora, Corsi, Claudio, Ferragina, Paolo
• Granted Patent: US 8,996,622 B2
• Time in Patent Office: Days
• US Class Current: 709/206
• CPC Class Codes: G06F 16/95 Retrieval from the web
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

Disclosed are methods and apparatus for detecting spam hosts. In one embodiment, one or more graphs are generated using data obtained from a query log, where the one or more graphs include at least one of an anticlick graph or a view graph. Values of one or more syntactic features of the one or more graphs are ascertained. Values of one or more semantic features of the one or more graphs are determined by propagating categories from a web directory among nodes in each of the one or more graphs. Spam hosts are then detected based upon the values of the syntactic features and the semantic features.

Claims

1. A method, comprising:

generating one or more graphs using data obtained from a query log, the one or more graphs including at least one of an anticlick graph or a view graph;

ascertaining values of one or more syntactic features of the one or more graphs;

determining values of one or more semantic features of the one or more graphs by propagating categories from a web directory among nodes in each of the one or more graphs; and

detecting spam hosts based upon the values of the syntactic features and the semantic features.

2. The method as recited in claim 1, wherein the one or more graphs include a set of one or more host-based graphs, and wherein the nodes of the one or more host-based graphs include one or more host nodes.

3. The method as recited in claim 2, wherein the one or more semantic features include one or more measures of dispersion of each of the host nodes in the one or more graphs.

4. The method as recited in claim 1, wherein the one or more graphs include a set of one or more document-based graphs, and wherein the nodes of the one or more document-based graphs include one or more document nodes.

5. The method as recited in claim 4, wherein the one or more semantic features include one or more measures of dispersion of each of the document nodes in the one or more graphs.

6. The method as recited in claim 1, wherein the one or more graphs further include a click graph.

7. The method as recited in claim 1, wherein the one or more graphs includes an anticlick graph, a click graph, and a view graph.

8. The method as recited in claim 1, wherein the one or more syntactic features of the one or more graphs includes at least one of topQx or topTy.

9. The method as recited in claim 8, wherein x is 1 and y is 1.

10. The method as recited in claim 8, wherein x is 100 and y is 100.

11. The method as recited in claim 1, wherein propagating is performed using a tree-based propagation by weighted average.

12. The method as recited in claim 1, wherein propagating is performed by random walk.

13. The method as recited in claim 1, wherein the web directory is DMOZ.

14. The method as recited in claim 1, wherein determining values of the one or more semantic features of one of the one or more graphs further comprises:

categorizing a subset of hosts in the graph that can found in a web directory that includes a plurality of categories such that each of the subset of hosts is associated with one or more of the plurality of categories; and

propagating the one or more of the plurality of categories to other host nodes and query nodes in the graph such that each node in the graph has an associated category tree.

15. The method as recited in claim 1, wherein determining values of the one or more semantic features of one of the one or more graphs further comprises:

categorizing a subset of documents in the graph that can found in a web directory that includes a plurality of categories such that each of the subset of documents is associated with one or more of the plurality of categories; and

propagating the one or more of the plurality of categories to other document nodes and query nodes in the graph such that each node in the graph has an associated category tree.

16. The method as recited in claim 15, further comprising:

associating a score with each category tree, wherein the category tree indicates a semantic spread of the corresponding node.

17. A computer-readable medium storing thereon computer-readable instructions, comprising:

instructions for generating one or more graphs using data obtained from a query log, the one or more graphs including at least one of an anticlick graph or a view graph;

instructions for propagating categories from a web directory among nodes in each of the one or more graphs;

instructions for determining values of one or more semantic features of the one or more graphs after propagating categories among the nodes; and

instructions for detecting spam hosts based upon the values of the semantic features.

18. An apparatus, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

generating one or more graphs using data obtained from a query log, the one or more graphs including at least one of an anticlick graph or a view graph;

ascertaining values of one or more syntactic features of the one or more graphs;

propagating categories from a web directory among nodes in each of the one or more graphs;

determining values of one or more semantic features of the one or more graphs; and

detecting spam hosts using the values of the syntactic features and the semantic features.

19. The apparatus as recited in claim 18, wherein the one or more semantic features include one or more measures of dispersion of each document node or host node in the one or more graphs.

20. The apparatus as recited in claim 18, wherein the one or more syntactic features of the one or more graphs includes at least one of topQx or topTy.