Location-Aware Query Recommendation for Search Engines at Scale

Query recommendation is a popular add-on feature of search engines, which provides related and helpful reformulations of a keyword query. Due to the dropping prices of smartphones and the increasing coverage and bandwidth of mobile networks, a large percentage of search engine queries are issued from mobile devices. This makes it possible to provide better query recommendations by considering the physical locations of the query issuers. However, limited research has been done on location-aware query recommendation for search engines. In this paper, we propose an effective spatial proximity measure between a query issuer and a query with a location distribution obtained from its clicked URLs in the query history. Based on this, we extend two popular query recommendation approaches to our location-aware setting, which provides recommendations that are semantically relevant to the original query and their results are spatially close to the query issuer. In addition, we extend the bookmark coloring algorithm for graph proximity search to support our proposed approaches online, with a spatial partitioning based approximation that accelerates the computation of our proposed spatial proximity. We conduct experiments using a real query log, which show that our query recommendation approaches significantly outperform previous work in terms of quality, and they can be efficiently applied online.