Query generation using structural similarity between documents

• US 9,092,479 B1
• Filed: 09/14/2012
• Issued: 07/28/2015
• Est. Priority Date: 11/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baker, Steven D., Flaster, Michael, Gupta, Nitin, Haahr, Paul G., Venkatachary, Srinivasan, Wu, Yonghui
• Primary Examiner(s): Hasan, Syed
• Application Number:
  US13/620,500
• Time in Patent Office: 1,047 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/186 Templates

Abstract

Methods, systems, and apparatus, including computer program products, for generating synthetic queries using seed queries and structural similarity between documents are described. In one aspect, a method includes identifying embedded coding fragments (e.g., HTML tag) from a structured document and a seed query; generating one or more query templates, each query template corresponding to at least one coding fragment, the query template including a generative rule to be used in generating candidate synthetic queries; generating the candidate synthetic queries by applying the query templates to other documents that are hosted on the same web site as the document; identifying terms that match structure of the query templates as candidate synthetic queries; measuring a performance for each of the candidate synthetic queries; and designating as synthetic queries the candidate synthetic queries that have performance measurements exceeding a performance threshold.

Claims

1. A method executed by a data processing apparatus, comprising:

identifying a seed query for a structured document based on a performance of the seed query with respect to the structured document;

identifying, by the one or more computers, one or more embedded coding fragments for the structured document using the seed query, each identified embedded coding fragment specifying a structure of a portion of the structured document that includes at least one term of the seed query;

generating, by the one or more computers, one or more query templates, each query template corresponding to at least one of the identified embedded coding fragments, the query template including the structure of the corresponding at least one embedded coding fragment and a generative rule to be used in generating one or more synthetic queries;

generating, by the one or more computers, the one or more synthetic queries using the one or more query templates and other structured documents, the generating comprising, for each query template;

identifying a portion of a particular structured document that includes the structure specified by the corresponding embedded coding fragment; and

generating a synthetic query using text contained in the portion of the particular structured document and specified by the generative rule; and

storing, by the one or more computers, at least one of the one or more synthetic queries in a query store.

2. The method of claim 1, wherein the seed query has been identified as a seed query based on a performance of the query, the method further comprising identifying the structured document by determining that search results that reference the structured document have been selected at least a threshold number of times.

3. The method of claim 1, wherein identifying the one or more embedded coding fragments comprises:

identifying, in the structured document, a pair of structured document tags that enclose at least one term of the seed query; and

identifying a structure for the pair of structured document tags, the structure including the pair of structured document tags and at least a portion of content enclosed by the pair of structured document tags.

4. The method of claim 3, wherein generating one or more query templates comprises generating a query template that includes:

the pair of structured document tags;

a wild card for the at least one term of the seed query that is enclosed by the pair of structured document tags; and

a portion of the content enclosed by the pair of structured document tags that does not match a term of the seed query.

5. The method of claim 1, further comprising:

performing an augmented search operation using a particular synthetic query to identify one or more search results; and

providing the one or more search results.

6. The method of claim 1, wherein the seed query is a machine-generated query.

7. The method of claim 1, wherein storing at least one of the one or more synthetic queries comprises:

measuring a performance in a search operation of each of the one or more synthetic queries;

identifying each of the one or more synthetic queries that has a performance measure that exceeds a performance threshold; and

storing each identified synthetic query in the query store.

8. A system, comprising:

a data processing apparatus; and

a memory storage apparatus in data communication with the data processing apparatus, the memory storage apparatus storing instructions executable by the data processing apparatus and that upon such execution cause the data processing apparatus to perform operations comprising;

identifying a seed query for a structured document based on a performance of the seed query with respect to the structured document;

identifying one or more embedded coding fragments for the structured document using the seed query, each identified embedded coding fragment specifying a structure of a portion of the structured document that includes at least one term of the seed query;

generating one or more query templates, each query template corresponding to at least one of the identified embedded coding fragments, the query template including the structure of the corresponding at least one embedded coding fragment and a generative rule to be used in generating one or more synthetic queries;

generating the one or more synthetic queries using the one or more query templates and other structured documents, the generating comprising, for each query template;

identifying a portion of a particular structured document that includes the structure specified by the corresponding embedded coding fragment; and

generating a synthetic query using text contained in the portion of the particular structured document and specified by the generative rule; and

storing at least one of the one or more synthetic queries in a query store.

9. The system of claim 8, wherein:

the seed query has been identified as a seed query based on a performance of the query; and

the instructions cause the data processing apparatus to perform further operations comprising identifying the structured document by determining that search results that reference the structured document have been selected at least a threshold number of times.

10. The system of claim 8, wherein identifying the one or more embedded coding fragments comprises:

identifying, in the structured document, a pair of structured document tags that enclose at least one term of the seed query; and

identifying a structure for the pair of structured document tags, the structure including the pair of structured document tags and at least a portion of content enclosed by the pair of structured document tags.

11. The system of claim 10, wherein generating one or more query templates comprises generating a query template that includes:

the pair of structured document tags;

a wild card for the at least one term of the seed query that is enclosed by the pair of structured document tags; and

a portion of the content enclosed by the pair of structured document tags that does not match a term of the seed query.

12. The system of claim 8, wherein the instructions cause the data processing apparatus to perform further operations comprising:

performing an augmented search operation using a particular synthetic query to identify one or more search results; and

providing the one or more search results.

13. The system of claim 8, wherein the seed query is a machine-generated query.

14. The system of claim 8, wherein storing at least one of the one or more synthetic queries comprises:

measuring a performance in a search operation of each of the one or more synthetic queries;

identifying each of the one or more synthetic queries that has a performance measure that exceeds a performance threshold; and

storing each identified synthetic query in the query store.

15. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by a data processing apparatus cause the data processing apparatus to perform operations comprising:

identifying a seed query for a structured document based on a performance of the seed query with respect to the structured document;

identifying one or more embedded coding fragments for the structured document using the seed query, each identified embedded coding fragment specifying a structure of a portion of the structured document that includes at least one term of the seed query;

generating one or more query templates, each query template corresponding to at least one of the identified embedded coding fragments, the query template including the structure of the corresponding at least one embedded coding fragment and a generative rule to be used in generating one or more synthetic queries;

generating the one or more synthetic queries using the one or more query templates and other structured documents, the generating comprising, for each query template;

identifying a portion of a particular structured document that includes the structure specified by the corresponding embedded coding fragment; and

generating a synthetic query using text contained in the portion of the particular structured document and specified by the generative rule; and

storing, at least one of the one or more synthetic queries in a query store.

16. The non-transitory computer storage medium of claim 15, wherein:

the query has been identified as a seed query based on a performance of the query; and

the instructions cause the data processing apparatus to perform further operations comprising identifying the structured document by determining that search results that reference the structured document have been selected at least a threshold number of times.

17. The non-transitory computer storage medium of claim 15, wherein identifying the one or more embedded coding fragments comprises:

identifying, in the structured document, a pair of structured document tags that enclose at least one term of the seed query; and

identifying a structure for the pair of structured document tags, the structure including the pair of structured document tags and at least a portion of content enclosed by the pair of structured document tags.

18. The non-transitory computer storage medium of claim 17, wherein generating one or more query templates comprises generating a query template that includes:

the pair of structured document tags;

a wild card for the at least one term of the seed query that is enclosed by the pair of structured document tags; and

a portion of the content enclosed by the pair of structured document tags that does not match a term of the seed query.

19. The non-transitory computer storage medium of claim 15, wherein the instructions cause the data processing apparatus to perform further operations comprising:

performing an augmented search operation using a particular synthetic query to identify one or more search results; and

providing the one or more search results.

20. The non-transitory computer storage medium of claim 15, wherein storing at least one of the one or more synthetic queries comprises:

measuring a performance in a search operation of each of the one or more synthetic queries;

identifying each of the one or more synthetic queries that has a performance measure that exceeds a performance threshold; and

storing each identified synthetic query in the query store.