Clustering web queries

• US 20030144994A1
• Filed: 10/12/2001
• Published: 07/31/2003
• Est. Priority Date: 10/12/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Hong-Jiang, Wen, Ji-Rong, Nie, Jian-Yun, Li, Ming-Jing
• Granted Patent: US 7,149,732 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

The described subject matter provides systems and procedures to make query similarity determinations, wherein the queries are used in information retrieval operations. A same document and/or multiple similar documents are identified that have been selected by a user in response to multiple queries. Responsive to identifying the same document and/or the similar documents, a query cluster is generated that indicates that the queries used to obtain the same and/or similar documents. This is accomplished in a manner that is independent of whether individual ones of the queries are compositionally similar with respect to other ones of the queries.

Claims

1. A method for clustering queries, the method comprising:

identifying a same document and/or a plurality of similar documents selected by a user in response to a plurality of queries; and

responsive to identifying the same document and/or the similar documents, generating a query cluster to indicate that the queries are similar independent of whether individual ones of the queries comprise similar composition with respect to other ones of the queries.

2. A method as recited in claim 1, wherein the queries comprise a well formed natural language question, a keyword, or a phrase.

3. A method as recited in claim 1, wherein the query cluster is used to disambiguate a word or phrase in a query of the queries.

4. A method as recited in claim 1, further comprising determining that the queries are similar based on similar keyword or phrase composition.

5. A method as recited in claim 1, wherein identifying the same document and/or the similar documents further comprises:

determining the similar documents by evaluating a set of selected similar documents chosen responsive to queries p and q of the queries, wherein documents D_C(.) is a subset of a result list D(.) according to the following;

D_—

C(p)={d_p1, d_p2, . . . , d_pi}⊂

D(p) D_—

C(q)={d_q1, d_q2, . . . , d_qj}⊂

D(q);

wherein similarity based on selection of documents is based on;

If D_C(p)∩

D_C(q)={d_pq1, d_pq2, . . . , d_pqk}≠

Ø

, then documents d_pq1, d_pq2, . . . , d_pqk represent a set of common topics of queries p and q, and,

whereby the similar documents between queries p and q is determined by D_C(p)∩

D_C(q).

6. A method as recited in claim 1, further comprising constructing a thesaurus comprising a plurality of synsets, wherein each synset comprises one or more query clusters.

7. A method as recited in claim 1, wherein identifying the same document and/or the similar documents further comprises determining the similar documents based on a proportionality of commonly selected individual documents.

8. A method as recited in claim 7, wherein identifying the same document and/or the similar documents further comprises:

determining the similar documents based on a proportionality of commonly selected individual documents, such that;

${\mathrm{similarity}}_{\mathrm{single\_doc}}<br><br>\left(p,q\right)=\frac{\mathrm{RD}<br><br>\left(p,q\right)}{\mathrm{Max}<br><br>\left(\mathrm{rd}<br><br>\left(p\right),\mathrm{rd}<br><br>\left(q\right)\right)},$

wherein rd(.) is the number of clicked documents for a query of the queries, and wherein RD(p, q) is the number of document selections in common.

9. A method as recited in claim 1, wherein identifying the same document and/or the similar documents further comprises:

determining the similar documents based on a hierarchical positioning between individual ones of a plurality of documents commonly selected across the queries.

10. A method as recited in claim 9:

wherein F(d_i, d_j) is a lowest common parent node for documents d_i and d_j;

wherein L(x) is a level of a node x;

wherein L_Total identifies a total number of levels in a hierarchy; and

wherein a similarity between two documents is defined as follows;

$s<br><br>\left(d_i,d_j\right)=\frac{L<br><br>\left(F<br><br>\left(d_i,d_j\right)\right)-1}{\mathrm{L\_Total}-1},$

such that

s(d_i, d_i)=1; and

s(d_i, d_j)=0 if F(d_i, d_j)=root; and

the method further comprises;

incorporating s(d_i, d_j) into a calculation of query similarity, wherein. d_i(1≦

i≦

m) and d_j(1≦

j≦

n) be a set of selected documents for queries p and q respectively such that;

${\mathrm{similarity}}_{\mathrm{hierarchy}}<br><br>\left(p,q\right)=\frac{1}{2}\times <br><br>\left(\frac{\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>\left(\underset{j=1}{\stackrel{n}{\max }}<br><br>\text{\hspace{1em}<br><br>}<br><br>s<br><br>\left(d_i,d_j\right)\right)}{\mathrm{rd}<br><br>\left(p\right)}+\frac{\underset{j=1}{\overset{m}{\sum <br><br>}}<br><br>\left(\underset{i=1}{\stackrel{n}{\max }}<br><br>\text{\hspace{1em}<br><br>}<br><br>s<br><br>\left(d_i,d_j\right)\right)}{\mathrm{rd}<br><br>\left(q\right)}\right)$

11. Computer-readable media comprising computer-executable instructions for identifying similar queries, the computer-executable instructions comprising instructions for:

identifying a same document and/or a plurality of similar documents selected by a user in response to a plurality of queries; and

responsive to identifying the same document and/or the similar documents, generating a query cluster to indicate that the queries are similar independent of whether individual ones of the queries comprise similar composition with respect to other ones of the queries.

12. Computer-readable media as recited in claim 11, wherein the queries comprise a well formed natural language question, a keyword, or a phrase.

13. Computer-readable media as recited in claim 11, wherein the query cluster is used to disambiguate a word or phrase in a query of the queries.

14. Computer-readable media as recited in claim 11, wherein the computer-executable instructions further comprise instructions for determining that the queries are similar based on similar keyword or phrase composition.

15. Computer-readable media as recited in claim 11, wherein the instructions for identifying the same document and/or the similar documents further comprise instructions for:

determining the similar documents by evaluating a set of selected similar documents chosen responsive to queries p and q of the queries, wherein documents D_C(.) is a subset of a result list D(.) according to the following;

D_—

C(p)={d_p1, d_p2, . . . , d_pi}⊂

D(p) D_—

C(q)={d_q1, d_q2, . . . , d_qj}⊂

D(q);

wherein similarity based on selection of documents is based on;

If D_C(p)∩

D_C(q)={d_pq1, d_pq2, . . . , d_pqk}≠

Ø

then documents d_pq1, d_pq2, . . . , d_pqk represent a set of common topics of queries p and q, and,

whereby the similar documents between queries p and q is determined by D_C(p)∩

D_C(q).

16. Computer-readable media as recited in claim 11, wherein the computer-executable instructions further comprise instructions for constructing a thesaurus comprising a plurality of synsets, wherein each synset comprises one or more query clusters.

17. Computer-readable media as recited in claim 11, wherein the instructions for identifying the same document and/or the similar documents further comprise instructions for determining the similar documents based on a proportionality of commonly selected individual documents.

18. Computer-readable media as recited in claim 17, wherein the instructions for identifying the same document and/or the similar documents further comprise instructions for:

determining the similar documents based on a proportionality of commonly selected individual documents, such that;

${\mathrm{similarity}}_{\mathrm{single\_doc}}<br><br>\left(p,q\right)=\frac{\mathrm{RD}<br><br>\left(p,q\right)}{\mathrm{Max}<br><br>\left(\mathrm{rd}<br><br>\left(p\right),\mathrm{rd}<br><br>\left(q\right)\right)},$

wherein rd(.) is the number of clicked documents for a query of the queries, and wherein RD(p, q) is the number of document selections in common.

19. Computer-readable media as recited in claim 11, wherein the instructions for identifying the same document and/or the similar documents further comprise instructions for:

determining the similar documents based on a hierarchical positioning between individual ones of a plurality of documents commonly selected across the queries.

20. Computer-readable media as recited in claim 19:

wherein F(d_i, d_j) is a lowest common parent node for documents d_i and d_j;

wherein L(x) is a level of a node x;

wherein L_Total identifies a total number of levels in a hierarchy; and

wherein a similarity between two documents is defined as follows;

$s<br><br>\left(d_i,d_j\right)=\frac{L<br><br>\left(F<br><br>\left(d_i,d_j\right)\right)-1}{\mathrm{L\_Total}-1},$

such that

s(d_i, d_i=1; and

s(d_i, d_j)=0 if F(d_i, d_j)=root; and

wherein the computer-executable instructions further comprise instructions for;

incorporating s(d_i, d_j) into a calculation of query similarity, wherein. d_i(1≦

i≦

m) and d_j(1≦

j≦

n) be a set of selected documents for queries p and q respectively such that;

${\mathrm{similarity}}_{\mathrm{hierarchy}}<br><br>\left(p,q\right)=\frac{1}{2}\times <br><br>\left(\frac{\underset{l=1}{\overset{m}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\underset{j=1}{\stackrel{n}{\max }}<br><br>s<br><br>\left(d_i,d_j\right)\right)}{r<br><br>\text{\hspace{1em}<br><br>}<br><br>d<br><br>\left(p\right)}+\frac{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\underset{l=1}{\stackrel{m}{\max }}<br><br>s<br><br>\left(d_i,d_j\right)\right)}{r<br><br>\text{\hspace{1em}<br><br>}<br><br>d<br><br>\left(q\right)}\right)$

21. A computing device comprising:

a processor coupled to a memory, the memory comprising computer executable instructions, the processor being configured to fetch and execute the computer-executable instructions for;

identifying a same document and/or a plurality of similar documents selected by a user in response to a plurality of queries; and

responsive to identifying the same document and/or the similar documents, generating a query cluster to indicate that the queries are similar independent of whether individual ones of the queries comprise similar composition with respect to other ones of the queries.

22. A computing device as recited in claim 21, wherein the queries comprise a well formed natural language question, a keyword, or a phrase.

23. A computing device as recited in claim 21, wherein the query cluster is used to disambiguate a word or phrase in a query of the queries.

24. A computing device as recited in claim 21, wherein the computer-executable instructions further comprise instructions for determining that the queries are similar based on similar keyword or phrase composition.

25. A computing device as recited in claim 21, wherein the instructions for identifying the same document and/or the similar documents further comprise instructions for:

determining the similar documents by evaluating a set of selected similar documents chosen responsive to queries p and q of the queries, wherein documents D_C(.) is a subset of a result list D(.) according to the following;

D_—

C(p)={d_p1, d_p2, . . . , d_pi}⊂

D(p) D_—

C(q)={d_q1, d_q2, . . . , d_qj}⊂

D(q);

wherein similarity based on selection of documents is based on;

If D_C(p)∩

C(q)={d_pq1, d_pq2, . . . , d_pqk}≠

Ø

then documents d_pq1, d_pq2, d_pqk represent a set of common topics of queries p and q, and,

whereby the similar documents between queries p and q is determined by D_C(p)∩

D_C(q).

26. A computing device as recited in claim 21, wherein the computer-executable instructions further comprise instructions for constructing a thesaurus comprising a plurality of synsets, wherein each synset comprises one or more query clusters.

27. A computing device as recited in claim 21, wherein the instructions for identifying the same document and/or the similar documents further comprise instructions for determining the similar documents based on a proportionality of commonly selected individual documents.

28. A computing device as recited in claim 27, wherein the instructions for identifying the same document and/or the similar documents further comprise instructions for:

determining the similar documents based on a proportionality of commonly selected individual documents, such that;

${\mathrm{similarity}}_{\mathrm{single\_doc}}<br><br>\left(p,q\right)=\frac{R<br><br>\text{\hspace{1em}<br><br>}<br><br>D<br><br>\left(p,q\right)}{\mathrm{Max}<br><br>\left(r<br><br>\text{\hspace{1em}<br><br>}<br><br>d<br><br>\left(p\right),r<br><br>\text{\hspace{1em}<br><br>}<br><br>d<br><br>\left(q\right)\right)},$

wherein rd(.) is the number of clicked documents for a query of the queries, and wherein RD(p, q) is the number of document selections in common.

29. A computing device as recited in claim 21, wherein the instructions for identifying the same document and/or the similar documents further comprise instructions for:

determining the similar documents based on a hierarchical positioning between individual ones of a plurality of documents commonly selected across the queries.

30. A computing device as recited in claim 29:

wherein F(d_i, d_j) is a lowest common parent node for documents d_i and d_j;

wherein L(x) is a level of a node x;

wherein L_Total identifies a total number of levels in a hierarchy; and

wherein a similarity between two documents is defined as follows;

$s<br><br>\left(d_i,d_j\right)=\frac{L<br><br>\left(F<br><br>\left(d_i,d_j\right)\right)-1}{\mathrm{L\_Total}-1},$

such that

s(d_i, d_i)=1; and

s(d_i, d_j)=0 if F(d_i, d_j)=root; and

wherein the computer-executable instructions further comprise instructions for;

incorporating s(d_i, d_j) into a calculation of query similarity, wherein. d_i(1≦

i≦

m) and d_j(1≦

j≦

n) be a set of selected documents for queries p and q respectively such that;

${\mathrm{similarity}}_{\mathrm{hierarchy}}<br><br>\left(p,q\right)=\frac{1}{2}\times <br><br>\left(\frac{\underset{l=1}{\overset{m}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\underset{j=1}{\stackrel{n}{\max }}<br><br>s<br><br>\left(d_i,d_j\right)\right)}{r<br><br>\text{\hspace{1em}<br><br>}<br><br>d<br><br>\left(p\right)}+\frac{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\underset{l=1}{\stackrel{m}{\max }}<br><br>s<br><br>\left(d_i,d_j\right)\right)}{r<br><br>\text{\hspace{1em}<br><br>}<br><br>d<br><br>\left(q\right)}\right)$