Abstract:Nearest neighbor query, as one of the building blocks of location-based service, has become a hot research topic in recent years. Compared with Euclidean space, road network is a more practical model in real applications; hence, nearest neighbor query in road network has received broader research efforts. In road network, tremendous data are generated along with sophisticated data structure, making nearest neighbor query computationally expensive. This poses a major challenge to spatial database community on its effort to effectively improve the query processing efficiency for nearest neighbor query. This work summarizes existing nearest neighbor query techniques in road network, and conducts analysis and comparison among them, from various perspectives including indexing structure and algorithm implementation. Additionally, several variants of nearest neighbor query are also summarized in this work. Finally, future research focus and trend for nearest neighbor query in road network are discussed.