US6502091B1 — Apparatus and method for discovering context grou…

Claim 1

Independent Claim 138 words

An apparatus for relating user queries and documents, comprising: a client configured to enable a user to submit user queries to locate documents; a server having a data mining mechanism configured to receive the user queries and generate information retrieval sessions; a communications pathway extending between the client and the server; and a database provided in communication with the client and the server, the database storing data in the form of usage logs generated from the information retrieval sessions generated by a user at the client; wherein the data mining mechanism includes a clustering algorithm identifying context groups and usage categories, and operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs.

Claim 2

Independent Claim 138 words

An apparatus for relating user queries and documents, comprising: a client configured to enable a user to submit user queries to locate documents; a server having a data mining mechanism configured to receive the user queries and generate information retrieval sessions; a communications pathway extending between the client and the server; and a database provided in communication with the client and the server, the database storing data in the form of usage logs generated from the information retrieval sessions generated by a user at the client; wherein the data mining mechanism includes a clustering algorithm identifying context groups and usage categories, and operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs.

Claim 3

Dependent Claim 40 words

The apparatus of claim 1 wherein each query context comprises a set of all queries that belong to a connected component of G, wherein G is an undirected query graph with a vertex for each query in a usage log.

Claim 4

Dependent Claim 36 words

The apparatus of claim 1 wherein individual context groups comprise one or more query contexts, wherein queries are grouped solely based on corresponding sets of opened document ids, with a query comprising at least one keyword.

Claim 5

Dependent Claim 18 words

The apparatus of claim 1 wherein the clustering algorithm clusters together query contexts to form the context groups.

Claim 6

Dependent Claim 36 words

The apparatus of claim 1 wherein each context group is represented as a directed acyclic graph (DAG) comprising a multi-level context DAG having at least one query context node and at least one general context node.

Claim 7

Dependent Claim 18 words

The apparatus of claim 5 wherein individual documents are attached to individual nodes of the multi-level context DAG.

Claim 8

Dependent Claim 32 words

The apparatus of claim 6 wherein a relevant document set, rel-doc (Q), that is associated with a query context, Q, comprises a group of individual documents attached to a query context node.

Claim 9

Dependent Claim 22 words

The apparatus of claim 1 wherein individual queries are grouped based on corresponding sets of opened document ids from the usage logs.

Claim 10

Dependent Claim 14 words

The apparatus of claim 1 wherein each query is an individual user retrieval session.

Claim 11

Independent Claim 92 words

A method for relating user queries and documents using usage logs from retrieval sessions from a text retrieval system, comprising: identifying contexts associated with a user query comprising at least one specific query keyword; identifying user queries having similar query contexts; partitioning user queries into groups based upon similarity of the query contexts; merging the groups to compute multiple contexts associated with specific query keywords; and applying a clustering algorithm to identify similar query contexts based upon the query keywords to generate context groups that associate keywords with documents accessed by users.

Claim 12

Independent Claim 92 words

A method for relating user queries and documents using usage logs from retrieval sessions from a text retrieval system, comprising: identifying contexts associated with a user query comprising at least one specific query keyword; identifying user queries having similar query contexts; partitioning user queries into groups based upon similarity of the query contexts; merging the groups to compute multiple contexts associated with specific query keywords; and applying a clustering algorithm to identify similar query contexts based upon the query keywords to generate context groups that associate keywords with documents accessed by users.

Claim 13

Dependent Claim 13 words

The method claim 10 wherein each query context is identified as a vector.

Claim 14

Dependent Claim 32 words

The method of claim 11 wherein the clustering algorithm comprises a self-organizing map (SOM) clustering algorithm configured to order the vectors onto a map such that similar vectors lie proximate each other.

Claim 15

Dependent Claim 38 words

The method of claim 11 wherein the map comprises a regular grid of units, with each unit being assigned a model vector, wherein each vector is mapped to the unit whose model vector best represents the input vector.

Claim 16

Dependent Claim 27 words

The method of claim 10 wherein the step of partitioning comprises representing each context group as a directed acyclic graph, with each context group containing query contexts.

Claim 17

Dependent Claim 17 words

The method of claim 14 wherein the acyclic graph comprises a multi-level context directed acyclic graph (DAG).

Claim 18

Independent Claim 122 words

A method for associating user queries in the form of keywords and documents accessed from usage logs in response to submission of the user queries during user retrieval sessions from a text retrieval system, comprising: identifying contexts associated with a user query comprising at least one specific query keyword; identifying similar query contexts from individual user queries; partitioning the user queries into groups based upon the identified similar query contexts; associating the groups to identify at least one query context associated with each specific query keyword; clustering similar query contexts based upon the query keywords to generate context groups that associate the keywords with documents accessed by users; and graphically depicting the contexts associated with documents from most general to most specific.

Claim 19

Independent Claim 122 words

A method for associating user queries in the form of keywords and documents accessed from usage logs in response to submission of the user queries during user retrieval sessions from a text retrieval system, comprising: identifying contexts associated with a user query comprising at least one specific query keyword; identifying similar query contexts from individual user queries; partitioning the user queries into groups based upon the identified similar query contexts; associating the groups to identify at least one query context associated with each specific query keyword; clustering similar query contexts based upon the query keywords to generate context groups that associate the keywords with documents accessed by users; and graphically depicting the contexts associated with documents from most general to most specific.

Claim 20

Dependent Claim 25 words

The method of claim 16 wherein multi-level context directed acyclic graphs (DAGs) are used to display to a user the contexts associated with individual documents.

Claim 21

Dependent Claim 30 words

The method of claim 16 wherein the step of graphically depicting the contexts comprises displaying a multi-level context directed acyclic graph (DAG) to a user via a graphical user interface.

Claim 22

Dependent Claim 17 words

The method of claim 18 wherein the displayed DAG comprises query context nodes and general context nodes.

Claim 23

Dependent Claim 49 words

The method of claim 19 wherein the query context nodes identify a document set comprising a relevant document set, rel-doc (Q), associated with a query context, Q, where the query context is a set of all the queries that belong to a connected component of a query graph, G.

Claim 24

Independent Claim 174 words

An apparatus for relating user queries and documents, comprising: a client configured to enable a user to submit user queries to locate documents; a server having a data mining mechanism configured to receive the user queries and generate information retrieval sessions; a communications pathway extending between the client and the server; and a database provided in communication with the client and the server, the database storing data in the form of usage logs generated from the information retrieval sessions generated by a user at the client, wherein the data mining mechanism includes a clustering algorithm identifying context groups and usage categories, and operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs, and wherein each query context comprises a set of all queries that belong to a connected component of G, wherein G is an undirected query graph with a vertex for each query in a usage log.

Claim 25

Independent Claim 174 words

An apparatus for relating user queries and documents, comprising: a client configured to enable a user to submit user queries to locate documents; a server having a data mining mechanism configured to receive the user queries and generate information retrieval sessions; a communications pathway extending between the client and the server; and a database provided in communication with the client and the server, the database storing data in the form of usage logs generated from the information retrieval sessions generated by a user at the client, wherein the data mining mechanism includes a clustering algorithm identifying context groups and usage categories, and operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs, and wherein each query context comprises a set of all queries that belong to a connected component of G, wherein G is an undirected query graph with a vertex for each query in a usage log.

Claim 26

Independent Claim 170 words

An apparatus for relating user queries and documents, comprising: a client configured to enable a user to submit user queries to locate documents; a server having a data mining mechanism configured to receive the user queries and generate information retrieval sessions; a communications pathway extending between the client and the server; and a database provided in communication with the client and the server, the database storing data in the form of usage logs generated from the information retrieval sessions generated by a user at the client, wherein the data mining mechanism includes a clustering algorithm identifying context groups and usage categories, and operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs, and wherein individual context groups comprise one or more query contexts, wherein queries are grouped solely based on corresponding sets of opened document IDs, with a query comprising at least one keyword.

Claim 27

Independent Claim 170 words

An apparatus for relating user queries and documents, comprising: a client configured to enable a user to submit user queries to locate documents; a server having a data mining mechanism configured to receive the user queries and generate information retrieval sessions; a communications pathway extending between the client and the server; and a database provided in communication with the client and the server, the database storing data in the form of usage logs generated from the information retrieval sessions generated by a user at the client, wherein the data mining mechanism includes a clustering algorithm identifying context groups and usage categories, and operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs, and wherein individual context groups comprise one or more query contexts, wherein queries are grouped solely based on corresponding sets of opened document IDs, with a query comprising at least one keyword.

Claim 28

Independent Claim 170 words

An apparatus for relating user queries and documents, comprising: a client configured to enable a user to submit user queries to locate documents; a server having a data mining mechanism configured to receive the user queries and generate information retrieval sessions; a communications pathway extending between the client and the server; and a database provided in communication with the client and the server, the database storing data in the form of usage logs generated from the information retrieval sessions generated by a user at the client, wherein the data mining mechanism includes a clustering algorithm identifying context groups and usage categories, and operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs, and wherein each context group is represented as a directed acyclic graph (DAG) comprising a multi-level context DAG having at least one query context node and at least one general context node.

Claim 29

Independent Claim 170 words

An apparatus for relating user queries and documents, comprising: a client configured to enable a user to submit user queries to locate documents; a server having a data mining mechanism configured to receive the user queries and generate information retrieval sessions; a communications pathway extending between the client and the server; and a database provided in communication with the client and the server, the database storing data in the form of usage logs generated from the information retrieval sessions generated by a user at the client, wherein the data mining mechanism includes a clustering algorithm identifying context groups and usage categories, and operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs, and wherein each context group is represented as a directed acyclic graph (DAG) comprising a multi-level context DAG having at least one query context node and at least one general context node.

Claim 30

Dependent Claim 18 words

The apparatus of claim 23 wherein individual documents are attached to individual nodes of the multi-level context DAG.

Claim 31

Dependent Claim 32 words

The apparatus of claim 24 wherein a relevant document set, rel-doc (Q), that is associated with a query context, Q, comprises a group of individual documents attached to a query context node.

Claim 32

Independent Claim 156 words

An apparatus for relating user queries and documents, comprising: a client configured to enable a user to submit user queries to locate documents; a server having a data mining mechanism configured to receive the user queries and generate information retrieval sessions; a communications pathway extending between the client and the server; and a database provided in communication with the client and the server, the database storing data in the form of usage logs generated from the information retrieval sessions generated by a user at the client, wherein the data mining mechanism includes a clustering algorithm identifying context groups and usage categories, and operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs, and wherein individual queries are grouped based on corresponding sets of opened document IDs from the usage logs.

Claim 33

Independent Claim 156 words

An apparatus for relating user queries and documents, comprising: a client configured to enable a user to submit user queries to locate documents; a server having a data mining mechanism configured to receive the user queries and generate information retrieval sessions; a communications pathway extending between the client and the server; and a database provided in communication with the client and the server, the database storing data in the form of usage logs generated from the information retrieval sessions generated by a user at the client, wherein the data mining mechanism includes a clustering algorithm identifying context groups and usage categories, and operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs, and wherein individual queries are grouped based on corresponding sets of opened document IDs from the usage logs.

Claim 34

Independent Claim 101 words

A method for relating user queries and documents using usage logs from retrieval sessions from a text retrieval system, comprising: identifying contexts associated with a user query comprising at least one specific query keyword; identifying user queries having similar query contexts; partitioning user queries into groups based upon similarity of the query contexts; merging the groups to compute multiple contexts associated with specific query keywords; and applying a clustering algorithm to identify similar query contexts based upon the query keywords to generate context groups that associate keywords with documents accessed by users, wherein each query context is identified as a vector.

Claim 35

Independent Claim 101 words

A method for relating user queries and documents using usage logs from retrieval sessions from a text retrieval system, comprising: identifying contexts associated with a user query comprising at least one specific query keyword; identifying user queries having similar query contexts; partitioning user queries into groups based upon similarity of the query contexts; merging the groups to compute multiple contexts associated with specific query keywords; and applying a clustering algorithm to identify similar query contexts based upon the query keywords to generate context groups that associate keywords with documents accessed by users, wherein each query context is identified as a vector.

Claim 36

Dependent Claim 32 words

The method of claim 27 wherein the clustering algorithm comprises a self-organizing map (SOM) clustering algorithm configured to order the vectors onto a map such that similar vectors lie proximate each other.

Claim 37

Dependent Claim 38 words

The method of claim 27 wherein the map comprises a regular grid of units, with each unit being assigned a model vector, wherein each vector is mapped to the unit whose model vector best represents the input vector.

Claim 38

Independent Claim 114 words

A method for relating user queries and documents using usage logs from retrieval sessions from a text retrieval system, comprising: identifying contexts associated with a user query comprising at least one specific query keyword; identifying user queries having similar query contexts; partitioning user queries into groups based upon similarity of the query contexts; merging the groups to compute multiple contexts associated with specific query keywords; and applying a clustering algorithm to identify similar query contexts based upon the query keywords to generate context groups that associate keywords with documents accessed by users, wherein the step of partitioning comprises representing each context group as a directed acyclic graph, with each context group containing query contexts.

Claim 39

Independent Claim 114 words

A method for relating user queries and documents using usage logs from retrieval sessions from a text retrieval system, comprising: identifying contexts associated with a user query comprising at least one specific query keyword; identifying user queries having similar query contexts; partitioning user queries into groups based upon similarity of the query contexts; merging the groups to compute multiple contexts associated with specific query keywords; and applying a clustering algorithm to identify similar query contexts based upon the query keywords to generate context groups that associate keywords with documents accessed by users, wherein the step of partitioning comprises representing each context group as a directed acyclic graph, with each context group containing query contexts.

Claim 40

Dependent Claim 17 words

The method of claim 30 wherein the acyclic graph comprises a multi-level context directed acyclic graph (DAG).

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2005-12-30	2006-07-01	2006-12-31	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2009-12-30	2010-07-01	2010-12-31	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2013-12-30	2014-07-01	2014-12-31	$7700.00	Window Closed / Lapsed

Apparatus and method for discovering context groups and document categories by mining usage logs

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag