article · 2023

Skyline Micro-Cluster Query: A Novel and Practical Spatial Query

Jing Lu, Yuhai Zhao, Zhengkui Wang, Guoren Wang

Cited by 0Abstract and details only

Abstract

This paper presents a novel spatial query, skyline micro-cluster (SMC) query. Given a set of data points P, a query point q, a radius γ and a density parameter k, the SMC query returns the skyline micro-clusters (MCs), where MC is a set of points in P that can be covered by a circle with radius γ and the number of points in MC is at least k. In this paper, we formally define the SMC query. As the brute-force approach to solving the SMC query in massive datasets has high computation and memory costs, we propose a basic skyline micro-cluster query algorithm, BSMC, which can reduce the time complexity from O(2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</sup>) to O(N<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup>). Furthermore, on top of BSMC, we propose an efficient skyline micro-cluster query algorithm (ESMC). In ESMC, we use the z-value index and propose a filter to remove the invalid micro-clusters, which reduces significant computation overhead. To reduce the memory overhead, we propose an incremental skyline query method. A comprehensive performance study is conducted on real datasets and the experimental results show that our proposed method, ESMC, can significantly improve the SMC query performance.

Cite this paper

APA 7

Lu, J., Zhao, Y., Wang, Z., & Wang, G. (2023). Skyline Micro-Cluster Query: A Novel and Practical Spatial Query. https://doi.org/10.1109/icde55515.2023.00206

MLA 9

Lu, Jing, et al. “Skyline Micro-Cluster Query: A Novel and Practical Spatial Query.” vol. 5, 2023, pp. 2686–98, https://doi.org/10.1109/icde55515.2023.00206.

Chicago

Lu, Jing, Yuhai Zhao, Zhengkui Wang, and Guoren Wang. 2023. “Skyline Micro-Cluster Query: A Novel and Practical Spatial Query.” https://doi.org/10.1109/icde55515.2023.00206.

Harvard

Lu, J. et al. (2023) ‘Skyline Micro-Cluster Query: A Novel and Practical Spatial Query’. Available at: https://doi.org/10.1109/icde55515.2023.00206.

BibTeX

@article{lu2023skyline,
  title = {{Skyline Micro-Cluster Query: A Novel and Practical Spatial Query}},
  author = {Lu, Jing and Zhao, Yuhai and Wang, Zhengkui and Wang, Guoren},
  volume = {5},
  pages = {2686--2698},
  year = {2023},
  doi = {10.1109/icde55515.2023.00206}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.