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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/164236 |
| _version_ | 1811696137342550016 |
|---|---|
| author | Chan, Harry Kai-Ho Liu, Shengxin Long, Cheng Wong, Raymond Chi-Wing |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Chan, Harry Kai-Ho Liu, Shengxin Long, Cheng Wong, Raymond Chi-Wing |
| author_sort | Chan, Harry Kai-Ho |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T07:34:35Z |
| format | Journal Article |
| id | ntu-10356/164236 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:34:35Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | ntu-10356/1642362023-01-13T00:54:50Z Cost-aware and distance-constrained Collective Spatial Keyword Query Chan, Harry Kai-Ho Liu, Shengxin Long, Cheng Wong, Raymond Chi-Wing School of Computer Science and Engineering Engineering::Computer science and engineering::Information systems::Information systems applications Spatial Keyword Queries Query Processing 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 University Submitted/Accepted version We 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. 2023-01-13T00:54:50Z 2023-01-13T00:54:50Z 2021 Journal Article Chan, H. K., Liu, S., Long, C. & Wong, R. C. (2021). Cost-aware and distance-constrained Collective Spatial Keyword Query. IEEE Transactions On Knowledge and Data Engineering, 1-1. https://dx.doi.org/10.1109/TKDE.2021.3095388 1041-4347 https://hdl.handle.net/10356/164236 10.1109/TKDE.2021.3095388 2-s2.0-85124701248 1 1 en RG20/19 (S) M4082302 IEEE Transactions on Knowledge and Data Engineering © 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/ 10.1109/TKDE.2021.3095388. application/pdf |
| spellingShingle | Engineering::Computer science and engineering::Information systems::Information systems applications Spatial Keyword Queries Query Processing Chan, Harry Kai-Ho Liu, Shengxin Long, Cheng Wong, Raymond Chi-Wing Cost-aware and distance-constrained Collective Spatial Keyword Query |
| title | Cost-aware and distance-constrained Collective Spatial Keyword Query |
| title_full | Cost-aware and distance-constrained Collective Spatial Keyword Query |
| title_fullStr | Cost-aware and distance-constrained Collective Spatial Keyword Query |
| title_full_unstemmed | Cost-aware and distance-constrained Collective Spatial Keyword Query |
| title_short | Cost-aware and distance-constrained Collective Spatial Keyword Query |
| title_sort | cost aware and distance constrained collective spatial keyword query |
| topic | Engineering::Computer science and engineering::Information systems::Information systems applications Spatial Keyword Queries Query Processing |
| url | https://hdl.handle.net/10356/164236 |
| work_keys_str_mv | AT chanharrykaiho costawareanddistanceconstrainedcollectivespatialkeywordquery AT liushengxin costawareanddistanceconstrainedcollectivespatialkeywordquery AT longcheng costawareanddistanceconstrainedcollectivespatialkeywordquery AT wongraymondchiwing costawareanddistanceconstrainedcollectivespatialkeywordquery |