Best Paper Award

An Efficient Algorithm for Location-Aware Query Autocompletion

Sheng HU, Chuan XIAO, Yoshiharu ISHIKAWA


  This paper presented a novel method that can be applied to realize efficient and scalable `location-aware' searching such as ``looking for a shop near here whose name starts with "star..."''. To do this, a fast and scalable completion of the actual name of the target from the given very short `hint' should be done while also considering their spatial context. The proposed algorithm aims at answering `range queries', which could find some values that are in the specified range, and `top-k queries', which could only return the k-most appropriate results to be retrieved. In the proposed method, the authors prepared a way to efficiently index data objects in a trie, and several pruning techniques have also been applied for the further improvement of the query processing performance. The proposed method also included an extension to error-tolerant searching for both types of queries. The shown experimental results demonstrated the efficiency of the proposed method by comparing it with other existing methods.
The impact of this achievement is so huge since the method already has a concrete application domain to be applied to as shown in this paper, and we could have further potential application areas. Because of these great contributions, this paper has been selected for the IEICE Best Paper Award.