Method for automatic discovery of query language features of web sites

• US 7,007,017 B2
• Filed: 02/10/2003
• Issued: 02/28/2006
• Est. Priority Date: 02/10/2003
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chidlovskii, Boris, Bergholz, Andre
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Hicks, Michael J.
• Application Number:
  US10/361,955
• Publication Number:
  US 20040162814A1
• Time in Patent Office: 1,114 Days
• Field of Search: 707/100, 707/5, 707/3, 707/2, 707/1, 707/103.R, 707/4, 715/700
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• 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

Abstract

A method for automatically determining query language operators of a Web information source, includes providing a set of known query operators, each known query operator in the set operating according to at least one syntax, wherein for a test query comprising a query operator and a test key word, each syntax of the operator produces a different number of document matches for the test query at a known Web information source; performing the test query on the Web information source, wherein the test query produces a number of document matches on the Web information source; comparing the number of document matches produced by the Web information source with the number of document matches produced by the known operator'"'"'s different syntaxes; and using an established criteria for determining if comparing results indicate the Web information source supports the known query operator according its matching syntax.

Claims

1. A computer-implemented method for automatically determining query language operators of a Web information source, comprising:

providing a search interface for submitting a query, for retrieving documents from a Web information source and for reporting the number of document matches for the query;

providing a set of known query operators, each known query operator in the set operating according to at least one syntax, wherein for a test query comprising a query operator and a test key word, each syntax of the operator produces a different number of document matches for the test query at a known Web information source;

performing the test query on the Web information source, wherein the test query produces a number of document matches on the Web information source;

wherein the set of known operators comprises the operators of case sensitivity and stemming, Boolean operators, AND, OR, NOT and phrases having more than one key word

comparing the number of document matches produced by the Web information source with the number of document matches produced by the known operator'"'"'s different syntaxes; and

using an established criteria for determining if comparing results indicate the Web information source supports the known query operator according its matching syntax.

2. The method of claim 1, further comprising generating a wrapper for the Web information source, wherein the wrapper supports the set of known query operators according to their corresponding matching syntax.

3. The method of claim 1, wherein the test query comprises one syntax for the query operator and one key word, wherein the query operator comprises a unary operator.

4. The method of claim 3 wherein the unary operator comprises one of case sensitivity and stemming.

5. The method of claim 1, wherein the test query comprises one syntax for the query operator and two key words, wherein the query operator comprises a binary operator.

6. The method of claim 5, wherein the binary operator comprises one of a Boolean operator and a phrase.

7. The method of claim 1, further comprising

providing a set of known query operators, each known query operator in the set operating according to at least one syntax, wherein for a plurality of test queries, each test query comprising one syntax for a query operator and at least one key word;

and

performing the plurality of test queries on the Web information source, wherein each test query in the plurality of test queries produces a different number of document matches on the Web information source.

8. The method of claim 7, wherein the established criteria comprises a set of classification rules established using the document matches for the plurality of test queries at the known Web information sources and generated using a machine learning technique.

9. The method of claim 8, wherein generating the set of classification rules further includes normalizing document matches by the maximum number of matches for the first and second test queries.

10. The method of claim 1, wherein the established criteria comprises a set of classification rules for the set of known query operators and their syntaxes generated by:

identifying a set of known Web information sources;

performing the plurality of test queries on each of the known Web information sources, wherein each test query produces a different number of matches for each of the known Web information sources; and

transforming the number of matches into features used by a machine learning techniques to generate the classification rules for the known query operators and their syntaxes.

11. The method of claim 10, wherein the key word comprises key word pairs selected from known domains resulting in non-zero matches.

12. The method of claim 10, wherein the key word comprises words that are capable of forming a phrase.

13. The method of claim 10, wherein the key word comprises words likely to occur in the same document.

14. The method of claim 10, wherein the key word comprises words that are unrelated.

15. The method of claim 10, wherein the set of classification rules for determining syntax of a query operator further includes building operator-based classification rules where any classification rule is associated with an operator from the known operator syntax set.

16. The method of claim 10, wherein the set of classification rules for determining syntax of a query operator further includes building syntax-based classification rules where any classification rule is associated with a syntax from the known set.

17. The method of claim 1, where the established criteria comprise a set of classification rules built using a known machine learning technique and wherein the known machine learning technique is one of a decision tree, a k-nearest neighbor algorithm and a Support Vector Machine algorithm.

18. The method of claim 1, wherein the established criteria comprises applying an equal less more relationship between the number of document matches produced by the Web information source with the number of document matches produced by the known operator'"'"'s different syntaxes.