Feat-SKSJ: Fast and Exact Algorithm for Top-k Spatial-Keyword Similarity Join

Amagata, Daichi; Tsuruoka, Shohei; Arai, Yusuke; Hara, Takahiro

doi:https://doi.org/10.1145/3474717.3483629

Feat-SKSJ: Fast and Exact Algorithm for Top-k Spatial-Keyword Similarity Join

Amagata, Daichi; Tsuruoka, Shohei; Arai, Yusuke et al.

GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2021, 15-24

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

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

閲覧可能ファイル

ファイル	フォーマット	利用条件	サイズ	閲覧回数	利用開始日	説明	information
GISProcACMIntSympAdvGeogrInfSyst_15	pdf	なし	1.40 MB	104	2023.10.30

論文情報

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

タイトル	Feat-SKSJ: Fast and Exact Algorithm for Top-k Spatial-Keyword Similarity Join
著者	NRID 1000040770649 1000040770649 researchmap permalink amgt amgt Scopus Author ID 55811167300 55811167300 著者名 Amagata, Daichi
	著者名 Tsuruoka, Shohei
	著者名 Arai, Yusuke
	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
キーワード等	similarity join
キーワード等	spatial-keyword data
抄録	Due to the proliferation of GPS-enabled mobile devices and IoT environments, location-based services are generating a large number of objects that contain both spatial and keyword information, and spatial-keyword databases are receiving much attention. This paper addresses the problem of top-k spatial-keyword similarity join, which outputs k object pairs with the highest similarity. This query is a primitive operator for important applications, including duplicate detection, recommendation, and clustering. The main bottleneck of the top-k spatial-keyword similarity join is to compute the similarity of a given object pair. To avoid this computation as much as possible, a state-of-the-art algorithm utilizes a filter that can skip the exact similarity computation of a given pair. However, this algorithm suffers from a loose threshold at the first stage, a high filtering cost, and the impossibility of filtering many pairs in a batch. We propose Feat-SKSJ, which removes these drawbacks and quickly outputs the exact result. Extensive experiments on real datasets show that Feat-SKSJ is significantly faster than the state-of-the-art algorithm.
会議情報	会議名 International Conference on Advances in Geographic Information Systems 回次 29 開催期間 November 2nd to November 5th, 2021 開催地 New York 開催国アメリカ合衆国
出版者	Association for Computing Machinery
収録物名	GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
ページ	15-24
刊行年月	2021-11-04
言語	英語
ハンドルURL	https://hdl.handle.net/11094/92846
関連情報 (isVersionOf)	DOI (出版社版) https://doi.org/10.1145/3474717.3483629
関連情報 (isPartOf)	ISBN 9781450384582
アクセス権	open access
権利情報	© 2021 ACM.This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Amagata D., Tsuruoka S., Arai Y., et al. Feat-SKSJ: Fast and Exact Algorithm for Top-k Spatial-Keyword Similarity Join. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 15 (2021); https://doi.org/10.1145/3474717.3483629.
出版タイプ	Accepted Manuscript
カテゴリ	会議発表論文 Conference Paper

資源タイプ	会議発表論文
ローカル資源タイプ	会議発表論文
DCMI資源タイプ	text
DCTERMS.bibliographicCitation	GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems. 2021, p. 15-24
DC.title	Feat-SKSJ: Fast and Exact Algorithm for Top-k Spatial-Keyword Similarity Join
DC.creator	Amagata, Daichi
	Tsuruoka, Shohei
	Arai, Yusuke
	Hara, Takahiro
DC.publisher	Association for Computing Machinery
DC.language' scheme='DCTERMS.RFC1766	英語
DC.type' scheme='DCTERMS.DCMIType	text
DCTERMS.issued' scheme='DCTERMS.W3CDTF	2021-11-04
DC.identifier	https://doi.org/10.1145/3474717.3483629
DC.subject	similarity join
DC.subject	spatial-keyword data
DCTERMS.abstract	Due to the proliferation of GPS-enabled mobile devices and IoT environments, location-based services are generating a large number of objects that contain both spatial and keyword information, and spatial-keyword databases are receiving much attention. This paper addresses the problem of top-k spatial-keyword similarity join, which outputs k object pairs with the highest similarity. This query is a primitive operator for important applications, including duplicate detection, recommendation, and clustering. The main bottleneck of the top-k spatial-keyword similarity join is to compute the similarity of a given object pair. To avoid this computation as much as possible, a state-of-the-art algorithm utilizes a filter that can skip the exact similarity computation of a given pair. However, this algorithm suffers from a loose threshold at the first stage, a high filtering cost, and the impossibility of filtering many pairs in a batch. We propose Feat-SKSJ, which removes these drawbacks and quickly outputs the exact result. Extensive experiments on real datasets show that Feat-SKSJ is significantly faster than the state-of-the-art algorithm.
DC.rights	© 2021 ACM.This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Amagata D., Tsuruoka S., Arai Y., et al. Feat-SKSJ: Fast and Exact Algorithm for Top-k Spatial-Keyword Similarity Join. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 15 (2021); https://doi.org/10.1145/3474717.3483629.
DC.format	92846
citation_title	Feat-SKSJ: Fast and Exact Algorithm for Top-k Spatial-Keyword Similarity Join
citation_author	Amagata, Daichi
	Tsuruoka, Shohei
	Arai, Yusuke
	Hara, Takahiro
citation_publisher	Association for Computing Machinery
citation_language	英語
citation_date	2021-11-04
citation_journal_title	GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
citation_firstpage	15
citation_lastpage	24
citation_doi	https://doi.org/10.1145/3474717.3483629
citation_public_url	https://hdl.handle.net/11094/92846

Feat-SKSJ: Fast and Exact Algorithm for Top-k Spatial-Keyword Similarity Join

閲覧可能ファイル

論文情報

論文詳細を表示