A parametric approximation algorithm for spatial group keyword queries
| Autor: | Ming Xu, Jincao Li |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Artificial Intelligence
Computer science Group (mathematics) 020204 information systems 0202 electrical engineering electronic engineering information engineering Approximation algorithm 020201 artificial intelligence & image processing 02 engineering and technology Computer Vision and Pattern Recognition Algorithm Computer Science::Databases Theoretical Computer Science Parametric statistics |
| Zdroj: | Intelligent Data Analysis. 25:305-319 |
| ISSN: | 1571-4128 1088-467X |
| DOI: | 10.3233/ida-195071 |
| Popis: | With the application of big data, various queries arise for information retrieval. Spatial group keyword queries aim to find a set of spatial objects that cover the query keywords and minimize a goal function such as the total distance between the objects and the query point. This problem is widely found in database applications and is known to be NP-hard. Efficient algorithms for solving this problem can only provide approximate solutions, and most of these algorithms achieve a fixed approximation ratio (the upper bound of the ratio of an approximate goal value to the optimal goal value). Thus, to obtain a self-adjusting algorithm, we propose an approximation algorithm for achieving a parametric approximation ratio. The algorithm makes a trade-off between the approximation ratio and time consumption enabling the users to assign arbitrary query accuracy. Additionally, it runs in an on-the-fly manner, making it scalable to large-scale applications. The efficiency and scalability of the algorithm were further validated using benchmark datasets. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|