Cost-aware and distance-constrained Collective Spatial Keyword Query

With the proliferation of location-based services, geo-textual data is becoming ubiquitous. Objects involved in geo-textual data include geospatial locations, textual descriptions or keywords, and various attributes (e.g., a point-of-interest has its expenses and users' ratings). Many types of spatial keyword queries have been proposed on geo-textual data. Among them, one prominent type is to find, for a query consisting of a query location and some query keywords, a set of multiple objects such that the objects in the set collectively cover all the query keywords and the object set is of good quality according to some criteria. Existing studies define the criteria either based on the geospatial information of the objects solely or simply treat the geospatial information and the attribute information of the objects together without differentiation though they may have different semantics and scales. As a result, they cannot provide users flexibility to express finer grained preferences on the objects. In this paper, we propose a new criterion which is to find a set of objects where the distance (defined based on the geospatial information) is at most a threshold specified by users and the cost (defined based on the attribute information) is optimized. We develop a suite of two algorithms including an exact algorithm and an approximation algorithm with provable guarantees for the problem. We conducted extensive experiments on real datasets which verified the efficiency and effectiveness of proposed algorithms.Ministry of Education (MOE)Nanyang Technological UniversitySubmitted/Accepted versionWe thank anonymous reviewers for their helpful comments. This research is supported by the Nanyang Technological University Start-Up Grant from the College of Engineering under Grant M4082302 and by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG20/19 (S)). The research of the HKUST side is supported by IRS17EG25