SYSTEMS, METHODS AND COMPUTER PROGRAM PRODUCTS FOR DISCOVERING A TEXT QUERY FROM EXAMPLE DOCUMENTS

• US 20130132418A1
• Filed: 11/18/2011
• Published: 05/23/2013
• Est. Priority Date: 11/18/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Spangler, William S.
• Granted Patent: US 8,862,605 B2
• Time in Patent Office: Days
• US Class Current: 707/759
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries

Abstract

Discovering a keyword query corresponding to an input collection of documents taken from a candidate pool includes selecting a document from a working set as the input set, and extracting a list of snippets in the selected document. For each snippet, executing a set of proximity queries based on selected terms in that snippet, and finding all possible proximity queries that return less than N query results from the candidate pool. A query is selected from said proximity queries, based on the selected query returning the greatest number of working set documents, and returning the smallest number of documents not in the working set. Documents returned by the selected query are removed from the working set, and the above steps are repeated until no documents remain in the working set. The disjunction of selected queries is returned as the discovered query.

Claims

1. A method for discovering a keyword query corresponding to an input collection of documents taken from a candidate pool, the method comprising:

(a) initializing a working set to be an input set;

(b) processing the working set until no documents remain in the working set, wherein said processing comprises;

selecting a document from the working set and extracting a list of snippets in the selected document;

for each snippet, executing a set of proximity queries based on selected terms in that snippet, and finding all possible proximity queries that return less than N query results from the candidate pool;

selecting a query from said proximity queries, based on;

a first criterion for the selected query returning the greatest number of working set documents, and a second criterion for the selected query returning the smallest number of documents not in the working set; and

removing, from the working set, documents returned by the selected query; and

(c) returning, as the discovered query, the disjunction of selected queries.

2. The method of claim 1, wherein the selected document is selected in view of most typical sorting based on a dictionary vector space similarity.

3. The method of claim 1, wherein selecting a document from the working set comprises:

generating a vector space model over a collection of snippets;

finding the centroid of the working set; and

selecting a document in the working set that is closest to said centroid.

4. The method of claim 1, wherein the discovered query returns as results the input collection along with additional related documents from the candidate pool.

5. The method of claim 1, wherein extracting a list of snippets in the selected document comprises extracting a list of all the snippets in the selected document.

6. The method of claim 5, comprising:

for each said snippet, generating a set of proximity queries from selected terms found in the snippet and executing a set of proximity queries,

such that all possible proximity queries are found that return less than N query results from the candidate pool.

7. The method of claim 5, wherein:

at least one snippet comprises a sentence; and

N is a pre-specified threshold.

8. A system for discovering a keyword query corresponding to an input collection of documents taken from a candidate pool, the system comprising:

a document selection module that selects a document from a working set of documents;

an extraction module that extracts a list of snippets in the selected document;

a query execution module that, for each snippet, executes a set of proximity queries based on selected terms in that snippet, wherein all possible proximity queries that return less than N query results from the candidate pool are found;

a query selection module that selects a query from said proximity queries, based on;

a first criterion for the selected query returning the greatest number of working set documents, and a second criterion for the selected query returning the smallest number of documents not in the working set;

a removal module that removes, from the working set, documents returned by the selected query, and feeds back the working set to the document selection module until no documents remain in the working set; and

an output module that returns, as the discovered query, the disjunction of selected queries.

9. The system of claim 8, comprising:

a query generating module that, for each said snippet, generates a set of proximity queries from selected terms found in the snippet and executing a set of proximity queries;

a determination module that finds all possible proximity queries that return less than N query results from the candidate pool;

wherein the document selection module selects the selected document in view of most typical sorting based on a dictionary vector space similarity; and

wherein the discovered query returns as results the input collection along with additional related documents from the candidate pool.

10. The system of claim 8, wherein the document selection module generates a vector space model over a collection of snippets, finds the centroid of the working set, and selects a document in the working set that is closest to said centroid, as the selected document.

11. A method for discovering a query, the method comprising:

iteratively processing a working set comprising a collection of documents from a candidate pool, for discovering a corresponding keyword query, wherein iteratively processing comprises;

for each snippet in a document selected from the working set, executing a set of proximity queries based on that snippet, and finding proximity queries that return less than a predefined number of query results from the candidate pool;

selecting a query from said proximity queries, wherein the selected query returns the greatest number of working set documents and the smallest number of documents not in the working set; and

removing, from the working set, documents returned by the selected query.

12. The method of claim 11, comprising:

iteratively processing the working set until no documents remain in the working set; and

returning, as the discovered query, the disjunction of selected queries;

wherein the discovered query returns as results the input collection along with additional related documents from the candidate pool.

13. The method of claim 12, wherein:

the selected document is selected in view of most typical sorting based on a dictionary vector space similarity; and

extracting snippets in the selected comprises extracting a list of all snippets in the selected document.

14. The method of claim 12, wherein selecting a document from the working set comprises:

generating a vector space model over a collection of snippets;

finding the centroid of the working set; and

selecting a document in the working set that is closest to said centroid.

15. A computer program product for discovering a keyword query corresponding to an input collection of documents taken from a candidate pool, the computer program product comprising:

a tangible storage medium readable by a computer system and storing instructions for execution by the computer system for performing a method comprising;

(a) initializing a working set to be an input set;

(b) selecting a document from the working set and extracting a list of sentences in the selected document;

(c) for each sentence, executing a set of proximity queries based on selected terms in that sentence, and finding all possible proximity queries that return less than N query results from the candidate pool;

(d) selecting a query from said proximity queries, based on;

a first criterion for the selected query returning the greatest number of working set documents, and a second criterion for the selected query returning the smallest number of documents not in the working set;

(e) removing, from the working set, documents returned by the selected query;

(f) repeating steps (b)-(e) until no documents remain in the working set; and

(g) returning, as the discovered query, the disjunction of selected queries.

16. The computer program product of claim 15, wherein the selected document is selected in view of most typical sorting based on a dictionary vector space similarity.

17. The computer program product of claim 15, wherein a document is selected from the working by:

generating a vector space model over a collection of sentences;

finding the centroid of the working set; and

selecting a document in the working set that is closest to said centroid.

18. The computer program product of claim 15, wherein:

the discovered query returns as results the input collection along with additional related documents from the candidate pool.

19. The computer program product of claim 15, wherein:

a list of all the sentences in the selected document is extracted.

20. The computer program product of claim 19, wherein:

for each said sentence, a set of proximity queries from selected terms found in the sentence is generated and a set of proximity queries is executed,

such that all possible proximity queries are found that return less than N query results from the candidate pool.