A class of search queries which contain abstract concepts are studied in this paper. These queries cannot be correctly interpreted by traditional keyword-based search engines. This paper presents a simple framework that detects and instantiates the abstract concepts by their concrete entities or meanings to produce alternate queries that yield better search results. 3
The quality of search results largely depend on the specificity of the keywords they put in search engine, for modern search engine are mostly keyword-based. When user queries do not general good results, search engine may suggest a list of alternate queries for the user to select and re-submit.
Traditionally, the function of query suggestion is implemented by
keywordbased methods and partially depends on the information from search log [
This paper focuses on a class of difficult queries which include abstract concepts, e.g., “hurricane in US state”. The likely intention of this query is to look for a specific instance of a hurricane that happened to a US state, e.g., Katrina in Louisiana. Here both hurricane and state are used as abstract concepts which contain many specific entities. The reason for such an abstract query may be because the user has forgotten the name of the hurricane or the state.
Search engines today return pages about these abstract concepts, and that usually means a list of huricanes in the US history for the above example (see Figure 1). It takes the user at least a few more clicks and scanning through the pages to find the information needed. Our objectives is to return a list of suggested queries such as: Katrina in Lousiana, Sandy in Connecticut, Dolly in Texas. 3 Kenny Q. Zhu (corresponding author) is partially supported by NSFC grants 61100050 and 61033002.
To this end, our main approach utilizes a comprehensive, probabilistic
taxonomy and a search log with access statistics (click-through rate, etc.). The
probabilistic taxonomy, called Probase[
Our system is divided into two parts, an offline part which creates an index on
all historical search queries from the search log and an online runtime system
which retrieves a number of relevant queries to an input concept-based query
and ranks them according to a scoring function. The architecture of the system
is shown in Figure 2. Next, we briefly discuss the two key components in the
architecture.
First, we parse each historical query in the search log and identify all noun-phrase
terms which exist as entities in Probase. Entities are those terms which appear
as the instance in at least one is-a pair in the taxonomy, e.g., katrina, louisina,
etc. Then, we conceptualize these instances into their most likely concepts by
considering the neighboring instances in the same query, using the technique
by Song et al.[
Rank Candidates Given a query, our system first parses the query and recognizes the concepts in it and then fetch a number of historical queries which are indexed by these concepts as candidate suggestions. Ranking the candidate is the main challenge in this work. We apply a hybrid method to calculate the ranking score. This score takes three factors into consideration, i.e. semantic similarity, context similarity and quality of suggestion query.
The context similarity, CScore, is measured by the edit distance between the input query and the candidate in terms of the number of insertion, deletion or replacement of words. Matched instances in the candidate and the matched concepts in the input queries which represent semantic information are removed before calculating the edit distance.
The semantic similarity between a candidate query and an input query is the combined distance between the instances in the candidate and the corresponding concept in the input. The distance between an instance and a concept is measured by the typicality score between these two terms in Probase. Because typicality score is a value between 0 and 1 and can be dense in some range (around 0.01 in practice), we take logistic function on the typical value to expand the range into something more distinguishable. We also use a scalar to make it linear comparable with CScore according to statistics. That is,
SScore(t) = (
1 1 + e t + 1) where t is the typicality value and is the factor to locate the dense range and is a scalar factor. Both factors are learned from some training examples.
We also utilize the click-through rate from the search log, in order to measure the quality or effectiveness of candidate suggestion. In this paper, we use a simple measure defined as
Num clicks(q) QScore(q) =
Frequency(q) where q is a candidate suggestion query. Besides the click-through rate, the quality score can be extended to include other information from search log.
Currently, the overall score (the lower, the better) is defined as:
OverallScore = [CScore + SScore] + e QScore We take 1/10 of a 6-month worth of Bing search log as our experimental data source. To evaluate the system, we arbitrarily select 10 concept-based queries related to the events happening during the 6-month time span. All suggested queries from the system are given to 3 human judges who would grade the suggestion on the scale of 1-5, 1 being the least helpful and 5 being the most helpful. The averaged normalized precision score of of these results with different size of search log and the suggestions of two example queries are shown in Figure 3. The results show that having more search log is helpful but the effect saturates at some point. Complete data set as well as evaluation results can be found at http://adapt.seiee.sjtu.edu.cn/~jack/query/.