LAUSR

Abstract In abundant location-based service applications, it is necessary to process continuous spatial keyword queries over geo-textual data streaming. As an important spatial keyword query, the collective spatial keyword (CSK) query aims to find a set of objects such that it covers all the given keywords collectively, the objects within the set are nearest to the query point, and it has the minimum distance between different objects. The existing approaches for the CSK query are mostly index-based algorithms. Although these approaches gain superior performance, their applicability is significantly limited by the necessity to create an index to organize the dataset. Therefore, these index-based approaches cannot be utilized to process data streaming that prevalently exists in most location-based service applications. In addition, the existing algorithms have much room for improvement as the distances between different objects are overlooked when generating feasible candidate sets. Moreover, the results returned by the proposed algorithms could be further refined to offer better decision support for users. In this paper, a greedy algorithm and an approximate algorithm with a provable approximate bound are proposed for the CSK query. Our approaches are appropriate to the CSK queries where the datasets are not suitable to be organized by indexes and can get better query results with less objects and smaller function scores. To boost the query performance, new pruning strategies and heuristic rules are developed. The experimental results demonstrate scalability, efficiency, and effectiveness of the proposed algorithms.