Retrieving Top-N Weighted Spatial k-cliques

Taniguchi, Ryosuke; Amagata, Daichi; Hara, Takahiro

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

Retrieving Top-N Weighted Spatial k-cliques

Taniguchi, Ryosuke; Amagata, Daichi; Hara, Takahiro

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

アクセス数:618件（2025-08-26 02:06 集計）

固定URL: https://hdl.handle.net/11094/92857

閲覧可能ファイル

ファイル	フォーマット	利用条件	サイズ	閲覧回数	利用開始日	説明	information
Proc-IEEEIntConfBigData_4952	pdf	なし	687 KB	88	2023.10.31

論文情報

ファイル出力 EndNote Basic出力 Mendeley出力

タイトル	Retrieving Top-N Weighted Spatial k-cliques
著者	著者名 Taniguchi, Ryosuke
	NRID 1000040770649 1000040770649 researchmap permalink amgt amgt Scopus Author ID 55811167300 55811167300 著者名 Amagata, Daichi
	NRID 1000020294043 1000020294043 ORCID 0000-0003-4807-3156 0000-0003-4807-3156 researchmap permalink hara-osakau hara-osakau Scopus Author ID 7404213547 7404213547 著者名 Hara, Takahiro
キーワード等	algorithm
	k-clique
	spatial data
	top- N retrieval
内容	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 International Conference on Big Data (Big Data) 回次 2022 開催期間 December 17th to December 20th, 2022 開催会場 International Convention Center 開催地 Osaka 開催国日本
出版者	Institute of Electrical and Electronics Engineers Inc.
収録物名	Proceedings - 2022 IEEE International Conference on Big Data, Big Data 2022
ページ	4952-4961
刊行年月	2022-12-17
言語	英語
ハンドルURL	https://hdl.handle.net/11094/92857
関連情報 (isVersionOf)	DOI (出版社版) https://doi.org/10.1109/BigData55660.2022.10021071
関連情報 (isPartOf)	ISBN 9781665480451
関連情報 (isPartOf)	ISBN 9781665480468
アクセス権	open access
権利情報	© 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.
出版タイプ	Accepted Manuscript
カテゴリ	会議発表論文 Conference Paper

資源タイプ	会議発表論文
ローカル資源タイプ	会議発表論文
DCMI資源タイプ	text
DCTERMS.bibliographicCitation	Proceedings - 2022 IEEE International Conference on Big Data, Big Data 2022. 2022, p. 4952-4961
DC.title	Retrieving Top-N Weighted Spatial k-cliques
DC.creator	Taniguchi, Ryosuke
	Amagata, Daichi
	Hara, Takahiro
DC.publisher	Institute of Electrical and Electronics Engineers Inc.
DC.language' scheme='DCTERMS.RFC1766	英語
DC.type' scheme='DCTERMS.DCMIType	text
DCTERMS.issued' scheme='DCTERMS.W3CDTF	2022-12-17
DC.identifier	https://doi.org/10.1109/BigData55660.2022.10021071
DC.subject	algorithm
	k-clique
	spatial data
	top- N retrieval
DC.description	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.
DCTERMS.abstract	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.
DC.rights	© 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.
DC.format	92857
citation_title	Retrieving Top-N Weighted Spatial k-cliques
citation_author	Taniguchi, Ryosuke
	Amagata, Daichi
	Hara, Takahiro
citation_publisher	Institute of Electrical and Electronics Engineers Inc.
citation_language	英語
citation_date	2022-12-17
citation_journal_title	Proceedings - 2022 IEEE International Conference on Big Data, Big Data 2022
citation_firstpage	4952
citation_lastpage	4961
citation_doi	https://doi.org/10.1109/BigData55660.2022.10021071
citation_public_url	https://hdl.handle.net/11094/92857

Retrieving Top-N Weighted Spatial k-cliques

閲覧可能ファイル

論文情報

論文詳細を表示