Efficient algorithms for solving aggregate keyword routing problems

• Main Authors: JIANG, Qize, SUN, Weiwei, ZHENG, Baihua, CHEN, Kunjie
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Aggregate keyword query; Query processing; Route planning; Databases and Information Systems; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/4390; https://ink.library.smu.edu.sg/context/sis_research/article/5393/viewcontent/EfficientAlgorithmsForSolvingAKRP_2019_afv.pdf
• Institution: Singapore Management University

With the emergence of smart phones and the popularity of GPS, the number of point of interest (POIs) is growing rapidly and spatial keyword search based on POIs has attracted significant attention. In this paper, we study a more sophistic type of spatial keyword searches that considers multiple query points and multiple query keywords, namely Aggregate Keyword Routing (AKR). AKR looks for an aggregate point m together with routes from each query point to m. The aggregate point has to satisfy the aggregate keywords, the routes from query points to the aggregate point have to pass POIs in order to complete the tasks specified by the task keywords, and the result route is expected to be the optimal one among all the potential results. In order to process AKR queries efficiently, we propose effective search algorithms, which support different aggregate functions. A comprehensive evaluation has been conducted to evaluate the performance of these algorithms with real datasets.