Moving kNN query processing in metric space based on influential sets. (July 2019)

• Record Type: Journal Article
• Authors: Li, Chuanwen; Gu, Yu; Qi, Jianzhong; Zhang, Rui; Yu, Ge
• Is Part Of: Information systems. Volume 83(2019)
• Page Start: 126
• Page End: 144
• Publication Date: 2019-07
• Subjects: Moving kNN query -- k nearest neighbors -- Influential set -- Safe region; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2019.03.008
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: The moving k nearest neighbor query computes one's k nearest neighbor set and maintains it while at move. This query is gaining importance due to the prevalent use of smart mobile devices and location-based services. Safe region is a popular technique for processing the query. It is a region where the movement of the query object does not cause the query answer to change. Processing a moving k nearest neighbor query is a continuing process of validating the safe region and recomputing it if invalidated. The size of the safe region largely decides the recomputation frequency and hence query efficiency. Existing algorithms lack efficiency due to either computing too small safe regions frequently or computing larger but expensive safe regions. We propose to replace safe regions in metric space (e.g., Euclidean space and spatial networks) with safe guarding objects which have low cost to compute.We prove that, the k nearest neighbors stay valid as long as they are closer to the query object than the safe guarding objects are. We hence avoid the high cost of safe region recomputation. We also prove that, the region defined by the safe guarding objects is the largest possible safe region. Thus, the recomputation frequency of the proposed method is also minimized. We conduct extensive experiments comparing the proposed method with the state-of-the-art methods on both real and synthetic data. The results confirm the superiority of the proposed method. Highlights: Introduce the concept of the influential object in metric space. Use it to formulate the influential neighbor set in metric space. Extend the theorems previously used to the metric space. Propose an algorithm for moving kNN query processing in spatial networks. Analyze the complexity of the newly proposed algorithm.