Methods and apparatus for query formulation

• US 9,075,799 B1
• Filed: 10/24/2011
• Issued: 07/07/2015
• Est. Priority Date: 10/24/2011
• Status: Active Grant

• Current Assignee: Netbase Solutions, Inc.
• Original Assignee: Netbase Solutions, Inc.
• Inventors: Tellefsen, Jens Erik, Bhatia, Ranjeet Singh
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US13/280,294
• Time in Patent Office: 1,352 Days
• Field of Search: 707600-899
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/332 Query formulation

Abstract

To the standard inverted index database, a new “To” operator is added. The “To” operator treats the standard single-level linear collection of records as being organized into localized clusters. Techniques for hierarchical clusters are presented. During indexing, hierarchical clusters are serialized according to a uniform visitation procedure. Serialization produces bit maps, one for each hierarchical level, that preserve the hierarchical level of each record and its location in the serialization sequence. Also presented are techniques, when searching for an Object-of-Interest, for greatly improving the process by which Exclude Terms are identified. Exclude Terms are particularly useful when the lexical units, representing an Object-of-Interest, are ambiguous. When in the mode of searching for Exclude Terms, the Object-of-Interest can match anywhere in a snippet, rather than just in the focus sentence. Using the “To” operator, the focus sentences thus found are converted into role values, from which are identified candidate Exclude Terms.

Claims

1. A method for query formulation, comprising:

searching, performed at least in part with a configuration of computing hardware and programmable memory, a corpus, to produce a first collection of records, by testing for appearances of a lexical unit that can be indicative of an object-of-interest;

identifying, performed at least in part with a configuration of computing hardware and programmable memory, a first collection of role values corresponding to the first collection of records;

performing, performed at least in part with a configuration of computing hardware and programmable memory, frequency analysis of sets of one or more lexical units, contained within the first collection of role values, to produce a first candidate list of exclude terms; and

wherein each role value is part of a frame instance, each instance produced by application of a frame extraction rule to a record of the corpus.

2. The method of claim 1, further comprising:

performing cluster analysis, of the sets of one or more lexical units, to produce a first candidate list of grouped exclude terms.

3. The method of claim 1, wherein the identifying is performed by use of an operator that identifies a cluster, for each record of the first collection of records, and maps the record to another hierarchical level.

4. The method of claim 1, wherein the searching is performed by testing for appearances of the lexical unit in snippets.

5. The method of claim 1, wherein each record, of the first collection of records, represents a focus sentence.

6. The method of claim 1, further comprising:

reducing a number of role values, contained in the first collection of role values, by obtaining a sample of the first collection of role values.

7. The method of claim 1, further comprising:

selecting one or more exclude terms, from the first candidate list of exclude terms.

8. The method of claim 7, further comprising:

searching a corpus, to produce a second collection of records, by testing for appearances of the lexical unit and excluding any record that contains a member of the first candidate list of exclude terms.

9. The method of claim 8, wherein the searching, for both the second first and second collection of records, is performed by testing for appearances of the lexical unit in snippets.

10. The method of claim 8, wherein the searching, for the first collection of records, is performed by testing for appearances of the lexical unit in snippets, and the searching, for the second collection of records, is performed by testing for appearances of the lexical unit in focus sentences.

11. The method of claim 1, wherein the first collection of roles values is collected from a role that is indicative of an object.

12. A system for query formulation, comprising:

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish searching a corpus, to produce a first collection of records, by testing for appearances of a lexical unit that can be indicative of an object-of-interest;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish identifying a first collection of role values corresponding to the first collection of records;

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish performing frequency analysis of sets of one or more lexical units, contained within the first collection of role values, to produce a first candidate list of exclude terms; and

wherein each role value is part of a frame instance, each instance produced by application of a frame extraction rule to a record of the corpus.

13. The system of claim 12, further comprising:

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish performing cluster analysis, of the sets of one or more lexical units, to produce a first candidate list of grouped exclude terms.

14. The system of claim 12, wherein the identifying is performed by use of an operator that identifies a cluster, for each record of the first collection of records, and maps the record to another hierarchical level.

15. The system of claim 12, wherein the searching is performed by testing for appearances of the lexical unit in snippets.

16. The system of claim 12, wherein each record, of the first collection of records, represents a focus sentence.

17. The system of claim 12, further comprising:

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish reducing a number of role values, contained in the first collection of role values, by obtaining a sample of the first collection of role values.

18. The system of claim 12, further comprising:

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish selecting one or more exclude terms, from the first candidate list of exclude terms.

19. The system of claim 18, further comprising:

a sub-system configured, as a result of the computing hardware and programmable memory, to accomplish searching a corpus, to produce a second collection of records, by testing for appearances of the lexical unit and excluding any record that contains a member of the first candidate list of exclude terms.

20. The system of claim 19, wherein the searching, for both the second first and second collection of records, is performed by testing for appearances of the lexical unit in snippets.

21. The system of claim 19, wherein the searching, for the first collection of records, is performed by testing for appearances of the lexical unit in snippets, and the searching, for the second collection of records, is performed by testing for appearances of the lexical unit in focus sentences.

22. The system of claim 12, wherein the first collection of roles values is collected from a role that is indicative of an object.