Efficient Retrieval of Top-k Weighted Spatial Triangles

Taniguchi, Ryosuke; Amagata, Daichi; Hara, Takahiro

doi:https://doi.org/10.1007/978-3-031-00123-9_17

Efficient Retrieval of Top-k Weighted Spatial Triangles

Taniguchi, Ryosuke; Amagata, Daichi; Hara, Takahiro

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2022, 13245, 224-231

アクセス数:744件（2025-08-25 23:40 集計）

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

閲覧可能ファイル

ファイル	フォーマット	利用条件	サイズ	閲覧回数	利用開始日	説明	information
LectNotesComputSci_13245 LNCS_224	pdf	なし	292 KB	83	2023.10.30

論文情報

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

タイトル	Efficient Retrieval of Top-k Weighted Spatial Triangles
著者	著者名 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
キーワード等	Spatial points
	Top-k retrieval
	Weighted graph
内容	This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-031-00123-9_17.
抄録	Due to the proliferation of location-based services and IoT devices, a lot of spatial points are being generated. Spatial data analysis is well known to be an important task. As spatial data analysis tools, graphs consisting of spatial points, where each point has edges to its nearby points and the weight of each edge is the distance between the corresponding points, have been receiving much attention. We focus on triangles (one of the simplest sub-graph patterns) in such graphs and address the problem of retrieving the top-k weighted spatial triangles. This problem has important real-life applications, e.g., group search, urban planning, and co-location pattern mining. However, this problem is computationally challenging, because the number of triangles in a graph is generally huge and enumerating all of them is not feasible. To solve this challenge, we propose an efficient algorithm that returns the exact result. Our experimental results on real datasets show the efficiency of our algorithm.
会議情報	会議名 International Conference on Database Systems for Advanced Applications 回次 27 開催期間 April 11th 2022 to April 14th, 2022 開催会場 Online 開催地 Hyderabad 開催国
出版者	Springer Science and Business Media Deutschland GmbH
収録物名	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
巻(号)	13245
ページ	224-231
刊行年月	2022-04-08
言語	英語
ハンドルURL	https://hdl.handle.net/11094/92844
関連情報 (isVersionOf)	DOI (出版社版) https://doi.org/10.1007/978-3-031-00123-9_17
関連情報 (isPartOf)	ISBN 9783031001222
アクセス権	open access
権利情報	© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
出版タイプ	Accepted Manuscript
カテゴリ	会議発表論文 Conference Paper

資源タイプ	会議発表論文
ローカル資源タイプ	会議発表論文
DCMI資源タイプ	text
DCTERMS.bibliographicCitation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2022, 13245, p. 224-231
DC.title	Efficient Retrieval of Top-k Weighted Spatial Triangles
DC.creator	Taniguchi, Ryosuke
	Amagata, Daichi
	Hara, Takahiro
DC.publisher	Springer Science and Business Media Deutschland GmbH
DC.language' scheme='DCTERMS.RFC1766	英語
DC.type' scheme='DCTERMS.DCMIType	text
DCTERMS.issued' scheme='DCTERMS.W3CDTF	2022-04-08
DC.identifier	https://doi.org/10.1007/978-3-031-00123-9_17
DC.subject	Spatial points
	Top-k retrieval
	Weighted graph
DC.description	This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-031-00123-9_17.
DCTERMS.abstract	Due to the proliferation of location-based services and IoT devices, a lot of spatial points are being generated. Spatial data analysis is well known to be an important task. As spatial data analysis tools, graphs consisting of spatial points, where each point has edges to its nearby points and the weight of each edge is the distance between the corresponding points, have been receiving much attention. We focus on triangles (one of the simplest sub-graph patterns) in such graphs and address the problem of retrieving the top-k weighted spatial triangles. This problem has important real-life applications, e.g., group search, urban planning, and co-location pattern mining. However, this problem is computationally challenging, because the number of triangles in a graph is generally huge and enumerating all of them is not feasible. To solve this challenge, we propose an efficient algorithm that returns the exact result. Our experimental results on real datasets show the efficiency of our algorithm.
DC.rights	© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
DC.format	92844
citation_title	Efficient Retrieval of Top-k Weighted Spatial Triangles
citation_author	Taniguchi, Ryosuke
	Amagata, Daichi
	Hara, Takahiro
citation_publisher	Springer Science and Business Media Deutschland GmbH
citation_language	英語
citation_date	2022-04-08
citation_journal_title	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
citation_volume	13245
citation_firstpage	224
citation_lastpage	231
citation_doi	https://doi.org/10.1007/978-3-031-00123-9_17
citation_public_url	https://hdl.handle.net/11094/92844

Efficient Retrieval of Top-k Weighted Spatial Triangles

閲覧可能ファイル

論文情報

論文詳細を表示