Probabilistic Association Based Method and System for Determining Topical Relatedness of Domain Names

• US 20090282038A1
• Filed: 05/02/2009
• Published: 11/12/2009
• Est. Priority Date: 09/23/2008
• Status: Abandoned Application

• Current Assignee: Paxfire, Inc.
• Original Assignee: Paxfire, Inc.
• Inventors: Sullivan, Alan, Subotin, Michael
• Application Number:
  US12/434,625
• Publication Number:
  US 20090282038A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]

Abstract

Systems, computer software and methods for calculating relatedness scores which are indicative of relatedness of pairs of domain names requested by clients are described. The method includes receiving DNS traffic data, wherein the DNS traffic data includes at least domain names requested by clients and identities of the clients requesting the domain names, generating sequences of the domain names based on the received DNS traffic data, collecting co-occurrence counts for queried pairs of domain names, applying a probabilistic association estimate to the collected counts to determine the relatedness scores of the queried pairs of domain names, and storing the determined relatedness scores.

Claims

1. A method for calculating relatedness scores, which are indicative of relatedness of pairs of domain names requested by clients, the method comprising:

receiving domain name system (DNS) traffic data, wherein the DNS traffic data includes at least domain names requested by clients and identities of the clients requesting the domain names;

generating sequences of the domain names based on the received DNS traffic data;

collecting co-occurrence counts for queried pairs of domain names;

applying a probabilistic association estimate to the collected counts to determine the relatedness scores of the queried pairs of domain names; and

storing the determined relatedness scores.

2. The method of claim 1, wherein the probabilistic association estimate includes at least one of pointwise mutual information (PMI), probability-weighted pointwise mutual information (PWPMI), likelihood ratio or information gain.

3. The method of claim 2, wherein the PWPMI is calculated by

estimating the PMI for co-occurrence of queries of a pair of domain names in a predefined window of a corresponding sequence, wherein the predefined window includes fewer domain names than the corresponding sequence;

and

calculating the PWPMI of the pair of domain names by multiplying the PMI by a probability that both domain names of the pair of domain names co-occur in the predefined window.

4. The method of claim 3, wherein the estimating step comprises:

calculating the PWPMI as

$\begin{array}{cc}\mathrm{PWPMI}<br><br>\left(d_A,d_B\right)=p<br><br>\left(d_A,d_B\right)·<br><br>\ln <br><br>\frac{p<br><br>\left(d_A,d_B\right)}{p<br><br>\left(d_A\right)·<br><br>p<br><br>\left(d_B\right)},& \end{array}$

where probability p(d_A) is a ratio of a number of client sessions in which domain name d_A occurs and a total number of client sessions,

p(d_B) is a ratio of a number of client sessions in which domain name d_B occurs and the total number of client sessions,

p(d_A, d_B) is a ratio of a number of client sessions in which domain names d_A and d_B co-occur and the total number of client sessions, and

a client session includes a sequence of domain names requested by a client during a predetermined period of time.

5. The method of claim 3, wherein the predefined window includes between 3 and 10 different domain names.

6. The method of claim 3, wherein the predefined window is time based and includes a predefined amount of time between two queries.

7. The method of claim 1, further comprising:

receiving a time stamp for each domain name requested by the clients; and

calculating the relatedness score by taking into account an order in time of the requested domain names.

8. The method of claim 1, further comprising:

calculating the relatedness score for all pairs of available domain names in the Internet service provider; and

generating a database that stores the calculated relatedness scores for the available domain names.

9. A server for calculating relatedness scores, which are indicative of a relatedness of pairs of domain names requested by clients, the server comprising:

an input/output interface configured to receive domain name system (DNS) traffic data, wherein the DNS traffic data includes at least domain names requested by clients and identities of the clients requesting the domain names;

a processor connected to the input/output interface and configured to,

generate sequences of the domain names based on the received DNS traffic data,

collect co-occurrence counts for queried pairs of domain names, and

apply a probabilistic association estimate to the collected counts to determine the relatedness scores of the queried pairs of domain names; and

a memory connected to the processor and configured to store the determined relatedness scores.

10. The server of claim 9, wherein the probabilistic association estimate includes at least one of pointwise mutual information (PMI), probability-weighted pointwise mutual information (PWPMI), likelihood ratio or information gain.

11. The server of claim 10, wherein the processor is further configured to calculate the PWPMI as

$\mathrm{PWPMI}$

( d A , d B ) = p 

( d A , d B ) ·

ln 

p 

( d A , d B ) p 

( d A ) ·

p 

( d B ) ,

where probability p(d_A) is a ratio of a number of client sessions in which domain name h_A occurs and a total number of client sessions,

p(d_B) is a ratio of a number of client sessions in which domain name d_B occurs and the total number of client sessions,

p(d_A, d_B) is a ratio of a number of client sessions in which domain names d_A and d_B co-occur and the total number of client sessions, and

a client session includes a sequence of domain names requested by a client during a predetermined period of time.

12. The server of claim 9, wherein the processor input/output interface is further configured to receive a time stamp for each domain name requested by the clients, and the processor is configured to calculate the relatedness score by taking into account an order in time of the requested domain names.

13. The server of claim 9, wherein the processor is further configured to,

calculate the relatedness score for all pairs of available domain names in the Internet service provider;

and

generate a database that stores the calculated probabilistic association scores for the available domain names.

14. A computer readable medium storing computer executable instructions, wherein the instructions, when executed, implement a method for calculating relatedness scores, which are indicative of a relatedness of pairs of domain names requested by clients, the method comprising:

providing a system comprising distinct software modules, wherein the distinct software modules comprise a domain name system (DNS) traffic module, a sequence module, a co-occurrence module, and a probabilistic association estimate module;

receiving at the DNS traffic module DNS traffic data, wherein the DNS traffic data includes at least domain names requested by clients and identities of the clients requesting the domain names;

generating by the sequence module sequences of the domain names based on the received DNS traffic data;

collecting co-occurrence counts for queried pairs of domain names in the co-occurrence module;

applying, in the probabilistic association estimate module, a probabilistic association estimate to the collected counts to determine the relatedness scores of the queried pairs of domain names; and

storing the determined relatedness scores.

15. The medium of claim 14, wherein the probabilistic association estimate includes at least one of pointwise mutual information (PMI), probability-weighted pointwise mutual information (PWPMI), a likelihood ratio or information gain.

16. The medium of claim 15, wherein PWPMI is calculated by

estimating the PMI for co-occurrence of queries of a pair of domain names in a predefined window of a corresponding sequence, wherein the predefined window includes fewer domain names than the corresponding sequence;

and

calculating the PWPMI of the pair of domain names by multiplying the PMI by a probability that both domain names of the pair of domain names co-occur in the predefined window.

17. The medium of claim 16, wherein the estimating step comprises:

calculating the PWPMI as

$\mathrm{PWPMI}<br><br>\left(d_A,d_B\right)=p<br><br>\left(d_A,d_B\right)·<br><br>\ln <br><br>\frac{p<br><br>\left(d_A,d_B\right)}{p<br><br>\left(d_A\right)·<br><br>p<br><br>\left(d_B\right)},$

where probability p(d_A) is a ratio of a number of client sessions in which domain name d_A occurs and a total number of client sessions,

p(d_B) is a ratio of a number of client sessions in which domain name d_B occurs and the total number of client sessions,

p(d_A, d_B) is a ratio of a number of client sessions in which domain names d_A and d_B co-occur and the total number of client sessions, and

a client session includes a sequence of domain names requested by a client during a predetermined period of time.

18. The medium of claim 14, further comprising:

receiving a time stamp for each domain name requested by the clients; and

calculating the relatedness score by taking into account an order in time of the requested domain names.

19. The medium of claim 14, further comprising:

calculating the relatedness score for all pairs of available domain names in the Internet service provider; and

generating a database that stores the calculated relatedness scores for the available domain names.