conference paper

Conference Paper

Text

Proceedings - 2022 IEEE International Conference on Big Data, Big Data 2022. 2022, p. 4952-4961

Retrieving Top-N Weighted Spatial k-cliques

Institute of Electrical and Electronics Engineers Inc.

English

Text

2022-12-17

https://doi.org/10.1109/BigData55660.2022.10021071

Taniguchi R., Amagata D., Hara T.. Retrieving Top-N Weighted Spatial k-cliques. Proceedings - 2022 IEEE International Conference on Big Data, Big Data 2022 , 4952 (2022); https://doi.org/10.1109/BigData55660.2022.10021071.

Spatial data analysis is a classic yet important topic because of its wide range of applications. Recently, as a spatial data analysis approach, a neighbor graph of a set P of spatial points has often been employed. This paper also considers a spatial neighbor graph and addresses a new problem, namely top-N weighted spatial k-clique retrieval. This problem searches for the N minimum weighted cliques consisting of k points in P, and it has important applications, such as community detection and co-location pattern mining. Recent spatial datasets have many points, and efficiently dealing with such big datasets is one of the main requirements of applications. A straightforward approach to solving our problem is to try to enumerate all k-cliques, which incurs O(nkk2) time. Since k ≥ 3, this approach cannot achieve the main requirement, so computing the result without enumerating unnecessary k-cliques is required. This paper achieves this challenging task and proposes a simple practically-efficient algorithm that returns the exact answer. We conduct experiments using two real spatial datasets consisting of million points, and the results show the efficiency of our algorithm, e.g., it can return the exact top-N result within 1 second when N ≤ 1000 and k ≤ 7.

© 2022 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.

92857

Retrieving Top-N Weighted Spatial k-cliques

Institute of Electrical and Electronics Engineers Inc.

English

2022-12-17

Proceedings - 2022 IEEE International Conference on Big Data, Big Data 2022

4952

4961

https://doi.org/10.1109/BigData55660.2022.10021071

https://hdl.handle.net/11094/92857