Query expansion

[0001] This application claims the benefit of U.S. Provisional Patent Application No. 61/049,381 filed on Apr. 30, 2008, which is hereby incorporated by reference in its entirety.

[0002] The described technology is directed to the field of search queries.

[0003] Online advertising is sometimes targeted using segments, each a groups of users determined to share an interest that tends to make these users good candidates for receiving advertising for a particular cause. It is possible to define a segment of users to include those users that submitted one of a group of queries to a web site. It is typical for this group of queries to be manually defined, by a person such as an editor or a merchandising specialist.

[0016] The inventors have recognized that manually-defined query groups can be under-inclusive, unnecessarily excluding from a segment users that share the common interest that is ultimately the basis for the segment.

[0017] Accordingly, a software facility for query expansion (“the facility”) is described that automatically selects queries to include in the group specified for a particular segment definition. A human user enters a few seed queries intended to be representative of those typically entered by users desired to be included in the segment. For example, for a segment of users interested in travel, the human user might enter the queries “travel”, “expedia”, and “plane ticket”. The facility relies on a set of actual queries recently received by the web site. The facility uses each of these actual queries to augment both a “behavioral index” and a “contextual index”. The behavioral index identifies actual queries that users issue within a short time of one another; the facility augments the behavioral index with the current query by storing indications of other queries issued within a short time of the current query by the same user. The contextual index contains publicly-available information relating to each actual query; the facility updates the contextual index for the current query by submitting the current query to a number of publicly-available information sources, and storing the results provided by the publicly-available information sources together with the actual query in the contextual index.

[0018] When the facility receives a set of seed queries for a segment, the facility uses both the behavioral index and contextual index to identify the actual queries that most closely relate to the seed queries in aggregate, and selects these actual queries as expanded queries for use in the segment definition.

[0019] By performing in some or all of the manners described above, the group of queries used in the segment definition to include in the segment users who would have otherwise been excluded.

[0020] FIG. 1 is a block diagram showing some of the components typically incorporated in at least some of the computer systems and other devices on which the facility executes. These computer systems and devices 100 may include one or more central processing units (“CPUs”) 101 for executing computer programs; a computer memory 102 for storing programs and data—including data structures, database tables, other data tables, etc.—while they are being used; a persistent storage device 103, such as a hard drive, for persistently storing programs and data; a computer-readable media drive 104, such as a CD-ROM drive, for reading programs and data stored on a computer-readable medium; and a network connection 105 for connecting the computer system to other computer systems, such as via the Internet, to exchange programs and/or data—including data structures. In various embodiments, the facility can be accessed by any suitable user interface including Web services calls to suitable APIs. While computer systems configured as described above are typically used to support the operation of the facility, one of ordinary skill in the art will appreciate that the facility may be implemented using devices of various types and configurations, and having various components, such as wireless telephones and similar devices.

[0021] FIG. 2 is a flow diagrams showing interactions performed in accordance with the facility. A user client 200 issues an actual user query 201 to a search engine 210. The search engine returns a query result 211 to the user client. The search engine also passes the actual user query to a query post processor 220. The query post processor uses accumulated actual user queries to generate both a behavioral index 230 and a contextual index 240, both of which are used by a query expander 260 as discussed below. A user of a merchandiser client 250 generates a set 251 of seed queries to be used in defining a segment. The query expander uses the behavioral index and contextual index to generate a set of expanded queries 161 from the set of seed queries. The merchandiser client then generates a segment definition that is based upon the expanded queries (and in some cases the seed queries) 252. This new segment definition is stored among a set of segment definitions 270. Each of the segment definitions 270 is used to generate a population, i.e., a list of qualifying users, for the segment definition. These segment populations can then be used by an ad selector 290 to select advertising messages to present to users based upon their membership in different segment populations.

[0022] FIG. 3 is a flow diagram showing steps typically performed by the facility in order to process actual queries. In step 301, the facility receives a history of actual queries submitted by all users, or all users in a particular group. In step 302, the facility filters and normalizes the received query history. In some embodiments, this involves removing queries that are too short (such as less than 2 characters long) or too long (such as more than 50 characters long). In some embodiments, step 302 involves generating a lemma for each search term in the query, such as by applying an analyzer such as the Snowball analyzer available from Snowball.tartarus.org or otherwise stemming or homogenizing different forms of the same word. In step 303, the facility frequency-counts the filtered and normalized queries. That is, it determines the number of occurrences of each unique query in this set. In step 304, the facility generates a contextual index for the top m most frequent filtered and normalized queries. In various embodiments, m takes on a variety of values. In some embodiments, m is set at or about 70,000 queries. Step 304 is discussed in greater detail below in connection with FIG. 4. In step 305, the facility generates a behavioral index for the top n most frequent and normalized queries. In various embodiments, different values of n are used. In some embodiments, the value for n is set at or near 200,000 queries. Step 305 is discussed in additional detail below in connection with FIG. 6. After step 305, the facility continues in step 301 to receive the next query history. In some embodiments, this process is repeated periodically, such as daily, weekly, or monthly.

[0023] Those skilled in the art will appreciate that the steps shown in FIG. 3 and in each of the flow diagrams discussed below may be altered in a variety of ways. For example, the order of the steps may be rearranged; some steps may be performed in parallel; shown steps may be omitted, or other steps may be included; etc.

[0024] FIG. 4 is a flow diagram showing steps typically performed by the facility in order to generate the contextual index. In steps 401-409, the facility loops though each unique query selected for inclusion in the contextual index. In step 402, the facility creates an entry in the contextual index for the query.

[0025] FIG. 5 is a table diagram showing sample contents of the contextual index. The contextual index 500 contains an entry for each query selected for inclusion in the contextual index, such as entry 501. For each entry, column 511 contains the query. In some embodiments, the query is the normalized version of the query generated in step 302 discussed above.

[0026] Returning to FIG. 4, in steps 403-408, the facility loops through each of a number of different publicly-available information sources. These can include on-line dictionaries, thesauruses, encyclopedias, search engines, product and/or service databases, news services, etc. In step 404, the facility submits the current query as a query to the current information source. In step 405, the facility receives a result from the information source in response to the submitted query. In step 406, the facility stores the result received in step 405 in a per-source field for the current source in the entry created in step 402. In step 407, the facility appends the result received in step 405 to an all-source field of the entry created in step 402.

[0027] Returning to FIG. 5, each of columns 512-521 is a per-source field. It can be seen that, in row 501, text from a first information source has been stored in column 512, while text from a second information source has been stored in column 513. Further, column 522 contains a concatenated version of the responses from all information sources.

[0028] While FIG. 5 and each of the table diagrams discussed below show a table whose contents and organization are designed to make them more comprehensible by a human reader, those skilled in the art will appreciate that actual data structures used by the facility to store this information may differ from the table shown, in that they, for example, may be organized in a different manner; may contain more or less information than shown; may be compressed and/or encrypted; etc.

[0029] Returning to FIG. 4, in step 408, if additional sources remain to be processed, then the facility continues in step 403 to process the next source. In step 409, if additional queries remain to be processed, then the facility continues in step 401 to process the next query. After step 409, these steps conclude.

[0030] FIG. 6 is a flow diagram typically performed by the facility to generate the behavioral index. In step 601, the facility sorts all of the individual query occurrences selected for inclusion in the behavioral index first by user, then by time. In steps 602-611, the facility loops through each of these queries. The index of this loop is called the “earlier query”. In steps 603-610, the facility loops through each query that is by the same user as the earlier query, that occurred later than the earlier query, and that occurred no more than a window size later than the earlier query. This window size is set in order to capture queries that occurred relatively closely in time, and that are likely to correspond to a single effort to locate information on a subject. The index of this loop is called the “ladder query”. In step 604, if the behavioral index contains an entry for the earlier query, then the facility continues in step 606, else the facility continues in step 605. In step 605, the facility creates an entry in the behavioral index for the earlier query. After step 605, the facility continues in step 606. In step 606, the facility adds a copy of the later query to the entry for the earlier query. In step 607, if the behavioral index creates an entry for the later query, then the facility continues in step 609, else the facility continues in step 608. In step 608, the facility creates an entry in the behavioral index for the later query. After step 608, the facility continues in step 609. In step 609, the facility adds a copy of the earlier query to the entry for the later query. In step 610, if additional later queries remain for processing, then the facility continues in step 603 to process the next later query, else the facility continues in step 611. In step 611, if additional earlier queries remain for processing, then the facility continues in step 602 to process the next earlier query, else these steps conclude. In some embodiments, steps 606 and 609 can be performed without steps 605 and 608, respectively. In such embodiments, steps 604-605 and 607-608 are omitted.

[0031] FIG. 7 is a table diagram showing sample initial contents of a behavioral index constructed in accordance with steps shown in FIG. 6. The behavioral index contains rows each corresponding to a query, such as rows 701-702. Each row is divided into a query column 711 containing an actual query and a co-occurring query is column 712 containing all of the queries that co-occur with the query contained in the query column. For example, row 701 indicates that the “travel” query co-occurs with the “airfare” query.

[0032] FIG. 8 is a table diagram showing a set of sample queries sorted in accordance with step 601. The table 800 contains rows, such as rows 801-803, each corresponding to a query submitted by a user. Each row is divided into the following columns: a user column 811 containing an identifier that uniquely identifies the user submitting the query; a time column 812 that indicates the time at which the query was submitted; and a query column 813 containing the submitted query. For example, row 801 indicates that user 55956 submitted the “travel” query at 1:03 p.m. on Jan. 1, 2008. Suppose that the behavioral index has the contents shown on FIG. 7 and the facility is performing the steps shown in FIG. 6.

[0033] FIG. 9 is a table diagram showing sample subsequent contents of the behavioral index shown in FIG. 7 after the facility has processed the queries shown in FIG. 8. When the early query was “travel” and the later query was “airfare”, the facility added a second occurrence of “travel” to the “airfare” entry 901 and added a second occurrence of “airfare” to the “travel” entry 902. When the earlier query was “travel” and the later query was “hotel”, the facility added an occurrence of “hotel” to the “travel” entry 902; added the “hotel” entry 903; and added to the new “hotel” entry 903 an occurrence of “travel”. When the earlier query was “airfare” and the later query was “hotel”, the facility added an occurrence of “hotel” to the “airfare” entry 901, and added an occurrence of “airfare” to the “hotel” entry 903.

[0034] FIG. 10 is a flow diagram showing steps typically performed by the facility to generate a set of expanded queries for a set of seed queries. In step 1001, the facility receives a set of seed queries to be expanded. In step 1002, if the seed queries are adequately represented in the contextual and behavioral indices, then the facility continues in step 1003, else the facility continues in step 1007. In step 1003, the facility applies the contextual index generated in accordance with FIG. 4 to the seed queries received in step 1001 to identify and score expanded queries that are based on the seed queries. Step 1003 is described in greater detail below in connection with FIG. 11. In step 1004, the facility applies the behavioral index generated in accordance with FIG. 6. Step 1004 is described in additional detail below in connection with FIG. 12. In step 1005, the facility combines scores produced by both the contextual and behavioral indices for the expanded queries to obtain a master score for each expanded query. In some embodiments, this combination of contextual and behavioral scores for an expanded query involves summing the contextual score, the behavioral score, and the lower of the contextual score and the behavioral score. In some embodiments, the combination weights the contextual and behavioral scores based upon the amount of information contained by each the contextual and the behavioral index that is relevant to the expanded queries, the seed queries, or both. In step 1006, the facility selects the expanded queries having the largest master scores, such as the expanded queries having scores exceeding a minimum threshold, or a fixed number of the expanded queries having the highest scores. After step 1006, the facility continues in step 1001 to receive the next set of seed queries.

[0035] In step 1007, where the seed queries are determined to be inadequately represented in the indices, the facility applies the contextual index to the seed queries in a manner similar to that of step 1003 to obtain expanded queries. In step 1008, the facility augments the seed queries received in step 1001 with the expanded queries obtained in step 1007. After step 1008, the facility continues in step 1003 using the augmented set of seed queries.

[0036] FIG. 11 is a flow diagram showing steps typically performed by the facility in order to apply the contextual index to a set of seed queries to identify and score expanded queries. In steps 1101-1109, the facility loops through the seed queries. In step 1102, the facility produces a base score for each query in the contextual index other than the current seed query by using a query engine to perform a query seeking to match the contents of the all documents field of the contextual index entry for the current seed query against contents of the all documents fields of contextual index entries for the other actual queries. If the seed query was “travel”, the facility would compare the text in column 522 for entry 501 to the text in column 522 for each of the other entries of the contextual index. The query result indicates, for each of the other queries in the contextual index, the degree of similarity of its all documents field to the all documents field of the travel entry. In steps 1103-1105, the facility loops through each individual document source. In step 1104, the facility produces a boost score for each other actual query with the current seed query and the current document source by performing a query of the contents of the all documents field of the contextual index entry for the current seed query against the contents of the current individual document fields of the contextual index entries for the other queries. In terms of FIG. 5, for the individual document source corresponding to document 1 column 512, the facility performs a query seeking to match the contents of column 512 for row 501 to the contents of the column 512 for each of the other entries of the contextual index. In step 1105, if additional individual document sources remain to be processed, then the facility continues in step 1103, else the facility continues in step 1106. In steps 1106-1108, the facility loops through each other actual query in the contextual index. In step 1107, the facility obtains a final score for the current seed query with the current actual query by multiplying the base score determined in step 1102 for the current actual query with the current seed query by the sum of the boost scores determined in step 1104 for the current actual query with the current seed query and each document source. This basis for determining the final score for the current seed query with the current actual query tends to favor seed queries that match the text retrieved from a large number of different information sources over those that match text received from only a small number of information sources. In step 1108, if additional other actual queries remain to be processed, then the facility continues in step 1106 to process the next other actual query, else the facility continues in step 1109. Step 1109, if additional seed queries remain to be processed, then the facility continues in step 1101 to process the next seed query, else the facility continues in step 1110. In steps 1110-1112, the facility loops through each actual query in the contextual index that has a final score greater than zero. In step 1111, the facility determines a contextual score for the current actual query by summing the final scores for the current actual query with each seed query determined in step 1107. In step 1112, if additional actual queries remain to be processed, then the facility continues in step 1110 to process the next actual query, else these steps conclude.

[0037] FIG. 12 is a flow diagram showing steps typically performed by the facility in order to apply the behavioral index to the set of seed queries to identify and score expanded queries. In steps 1201-1203, the facility loops through each seed query. In step 1202, the facility determines a score for each other actual query with the seed query by performing a query of the contents of the co-occurring queries field of the behavioral index entry for the current seed query against contents of the co-occurring queries field of behavioral index entries for the other actual queries in the behavioral index. In terms of FIG. 9, if the current seed query is “airfare” then the facility would query the contents of the co-occurring queries column 912 for the “airfare” entry 901 against the contents of that column for the “travel” entry 902 and the “hotel” entry 903. Typically, the facility would attribute a higher score to the “hotel” actual query—whose single occurrence of “travel” matches two of the occurrences of travel in entry 901—than “travel”, which only has a single instance of “hotel” matching a single instance of “hotel” in entry 901. In step 1203, if additional seed queries remain to be processed, then the facility continues in step 1201 to process the next seed query, else the facility continues in step 1204. In steps 1204-1206, the facility loops through each actual query in the behavioral index that has a final score greater than zero. In step 1205, the facility determines the behavioral score for the current actual query by summing the scores for the current actual query with each seed query. In step 1206, if additional actual queries remain to be processed, then the facility continues in step 1204 to process the next actual query, else these steps conclude.

[0038] It will be appreciated by those skilled in the art that the above-described facility may be straightforwardly adapted or extended in various ways. While the foregoing description makes reference to particular embodiments, the scope of the invention is defined solely by the claims that follow and the elements recited therein.