Location Aware Keyword Query Suggestion Based on Document Proximity

• Published in: IEEE transactions on knowledge and data engineering 2016-01, Vol.28 (1), p.82-97
• Main Authors: Shuyao Qi, Dingming Wu, Mamoulis, Nikos
• Format: Article
• Language: English
• Subjects: Bipartite graph; Computer science; Ink; Marine animals; Mobile radio mobility management; Partitioning algorithms; Semantics
• ISSN: 1041-4347; 1558-2191
• DOI: 10.1109/TKDE.2015.2465391

Keyword suggestion in web search helps users to access relevant information without having to know how to precisely express their queries. Existing keyword suggestion techniques do not consider the locations of the users and the query results; i.e., the spatial proximity of a user to the retrieved results is not taken as a factor in the recommendation. However, the relevance of search results in many applications (e.g., location-based services) is known to be correlated with their spatial proximity to the query issuer. In this paper, we design a location-aware keyword query suggestion framework. We propose a weighted keyword-document graph, which captures both the semantic relevance between keyword queries and the spatial distance between the resulting documents and the user location. The graph is browsed in a random-walk-with-restart fashion, to select the keyword queries with the highest scores as suggestions. To make our framework scalable, we propose a partition-based approach that outperforms the baseline algorithm by up to an order of magnitude. The appropriateness of our framework and the performance of the algorithms are evaluated using real data.