Query expansion

1. A method in a computing system for constructing an index usable to identify expanded queries for a set of seed queries, comprising:

receiving a query history identifying, for each of a plurality of queries received from users, text of the query, a user submitting the query, and a time at which the query was submitted;

for each unique query identified by the query history:

for each user:

for every submission of the unique query by the user:

adding to an entry of the index for the unique query an instance of any query submitted by the user within a predetermined time period of the submission of the unique query by the user;

receiving a set of seed queries;

for each of the seed queries of the set:

identifying an entry of the index corresponding to the seed query;

submitting to a search engine a request to match the query instances added to the identified entry against the query instances added to the entries of the index other than the identified entry;

receiving from the search engine a score for each entry of the index other than the identified entry indicating the extent to which the query instances added to the identified entry matches the query instances added to the entry; and

selecting as expanded queries the queries corresponding to the entries of the index other than the identified entry having the highest scores.

2. The method of claim 1 , further comprising, before the adding, normalizing the text of the queries identified by the query history.

3. The method of claim 1 , further comprising constructing a segment definition based on the selected expanded queries.

4. The method of claim 3 wherein the constructed segment definition is further based on the set of seed queries.

5. A computer-readable medium whose contents cause a computing system to perform a method for constructing an index usable to identify expanded queries for a set of seed queries, the method comprising:

receiving a query history identifying, for each of a plurality of queries received from users, text of the query, a user submitting the query, and a time at which the query was submitted;

for each unique query identified by the query history:

for each of a plurality of publicly-available information sources:

submitting the unique query as a query to the publicly-available information source;

receiving a response to the submitted query; and

storing text contained by the response in an entry of the index for the unique query

receiving a set of seed queries;

for each of the seed queries of the set:

identifying an entry of the index corresponding to the seed query;

submitting to a search engine a request to match the text stored in the identified entry against the text stored in the entries of the index other than the identified entry;

receiving from the search engine a score for each entry of the index other than the identified entry indicating the extent to which the text stored in the identified entry matches the text stored in the entry; and

selecting as expanded queries the queries corresponding to the entries of the index other than the identified entry having the highest scores.

6. The computer-readable medium of claim 5 , the method further comprising, before the adding, normalizing the text of the queries identified by the query history.

7. The computer-readable medium of claim 5 , the method further comprising:

storing in each entry indications of the information source from which different portions of the text stored in the entry was received;

for each query corresponding to the entries of the index other than the identified entry, before the selecting, weighting the score in accordance with the number of information sources from which text matching the text stored in the identified entry was received.

8. The computer-readable medium of claim 5 , the method further comprising constructing a segment definition based on the selected expanded queries.

9. The computer-readable medium of claim 8 wherein the constructed segment definition is further based on the set of seed queries.