PATTERN TREE-BASED RULE LEARNING

• US 20110307436A1
• Filed: 06/10/2010
• Published: 12/15/2011
• Est. Priority Date: 06/10/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cai, Rui, Zhang, Lei, Yang, Jiang-Ming, Ke, Yan, Fan, Xiaodong, Ma, Wei-Ying
• Granted Patent: US 8,429,110 B2
• Time in Patent Office: Days
• US Class Current: 706/48
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A pattern tree is constructed based on a plurality of key-value pairs representing portions of a data set. In some implementations, the pattern tree may be used for learning one or more rules for interacting with a source of the data set.

Claims

1. A method comprising:

obtaining a set of Uniform Resource Locators (URLs) and corresponding content from a targeted website;

decomposing each URL into a group of key-value pairs;

constructing, by a processor, a tree having a plurality of nodes, each node of the tree representing a group of URLs having a common pattern;

identifying one or more pairs of nodes corresponding to duplicate content in which a first node in a pair of nodes corresponds to first content that substantively matches second content corresponding to a second node in the pair of nodes;

generating a candidate rule for each of the one or more pairs of nodes, the candidate rule relating a URL of the first node to a URL of the second node; and

selecting one or more of the candidate rules as one or more deployable rules.

2. The method according to claim 1, the constructing the tree further comprising:

creating a root node for the URLs of the set of URLs;

choosing a particular key having a smallest distribution of values;

splitting the URLs into multiple subgroups according to the values of the particular key identified as having the smallest distribution of values to generate additional nodes of a next hierarchical level; and

recursively repeating the choosing and splitting, wherein each node on the tree comprises a set of the URLs.

3. The method according to claim 2, the choosing the particular key having a smallest distribution of values being based on an entropy value determined for the particular key, the entropy values being determined by comparing a number of values under the particular key with a total number of the URLs.

4. The method according to claim 1, the identifying one or more pairs of nodes further comprising:

identifying, as duplicate clusters, a plurality of groups of URLs having duplicate content;

determining an overlap between the nodes in the tree for identifying the one or more pairs of nodes, the overlap being determined based on the number of duplicate clusters corresponding to each node.

5. The method according to claim 4, the determining the overlap further comprising:

initializing an index list with the duplicate clusters; and

determining whether a particular pair of nodes is a member of one or more duplicate clusters in the index list.

6. The method according to claim 1, the generating the candidate rule further comprising determining a mapping relationship between the keys of the first and second nodes in each of the pairs of nodes by estimating a rate of common values shared by the keys in comparison with a predetermined threshold, the mapping relationship being used for generating a URL rewrite operation of the candidate rule.

7. The method according to claim 1, further comprising:

testing the one or more candidate rules against the set of URLs to determine a false positive rate for each rule; and

removing a candidate rule having a false positive rate above a predetermined threshold.

8. The method according to claim 1, the selecting one or more of the candidate rules as one or more deployable rules further comprising:

determining a popularity for each node having a candidate rule associated therewith, the popularity being determined based on a number of URLs covered by each node having a candidate rule associated therewith;

identifying conflicting or redundant candidate rules; and

discarding conflicting or redundant candidate rules originating at popular nodes.

9. A computer-implemented method comprising:

obtaining a set of data from a source;

generating a plurality of key-value pairs from the set of data, the key-value pairs representing data portions of the set of data; and

constructing a pattern tree by;

creating a root node for the set of data;

choosing a particular key having a smallest distribution of values;

splitting the data into multiple subgroups according to the values of the particular key identified as having the smallest distribution of values to generate additional nodes of a next hierarchical level.

10. The method according to claim 9, further comprising generating a candidate rule by determining a first node and a second node that correspond to duplicate content in the set of data, the candidate rule relating a pattern of the first node to a pattern of the second node.

11. The method according to claim 10, the generating the candidate rule further comprising determining a key-to-key mapping relationship between the first node and the second node for use in generating the candidate rule.

12. The method according to claim 10, wherein a plurality of candidate rules are generated and further comprising selecting one or more rules from the plurality of candidate rules for use during interaction with the source based on a popularity determined for nodes associated with the plurality of candidate rules.

13. Computer-readable storage media containing processor-executable instructions to be executed by a processor for carrying out the method according to claim 9.

14. A computing device comprising:

a processor coupled to computer-readable storage media containing instructions executable by the processor;

tree construction component implemented by the processor to construct a pattern tree based on a plurality of key-value pairs, the key-value pairs representing portions of a plurality of Uniform Resource Locators (URLs); and

a rule generation component implemented to identify a pair of nodes of the tree relating to duplicate content for generating a rule.

15. The computing device according to claim 14, the tree construction component being implemented to create nodes of the pattern tree by choosing a particular key having a smallest distribution of values and splitting the URLs into multiple subgroups according to the values of the particular key chosen as having the smallest distribution of values to generate additional nodes of a next hierarchical level, wherein each node on the pattern tree comprises a set of the URLs.

16. The computing device according to claim 14, the rule generation component being implemented to generate the rule for rewriting a portion of a URL of a first node of the pair of nodes to a format of a URL of a second node of the pair of nodes.

17. The computing device according to claim 15, the rule generation component being implemented to determine a mapping relationship between the keys of the first node and second node in the pair of nodes by estimating a rate of common values shared by the keys of the first node and second node in comparison with a predetermined threshold, the mapping relationship being used for generating the rule for rewriting.

18. The computing device according to claim 14, the rule generation component being implemented to generate a plurality of rules for a plurality of pairs of nodes, further comprising a rule selection component to select deployable rules from the plurality of rules, the rule selection component selecting the deployable rules based at least in part on a popularity determined for each node of the plurality of pairs of nodes.

19. The computing device according to claim 14, further comprising a search engine maintained on the computer storage media and implemented by the processor the search engine comprising a web crawler that obtains a set of sample URLs from a targeted website, the set of sample URLs being decomposed by the tree construction component into the key-value pairs, each key-value pair representing a portion of URL syntax of a URL of the set of sample URLs.

20. The computing device according to claim 19, further comprising the search engine being implemented to apply the rule during crawling of the targeted website for normalizing one or more URLs a first format to a second format according to the rule from to avoid downloading duplicate content during the crawling of the targeted website.