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

Number of Access:901（2025-10-07 04:02 Counts）

Identifier to cite or link to this item: https://hdl.handle.net/11094/92846

Link to primary information 

File Format Terms of use Size Views Date.Available Description information
GISProcACMIntSympAdvGeogrInfSyst_15 pdf None 1.40 MB 112 2023.10.30  

Item Information

Output File Export EndNote Basic Export Mendeley

Title
Feat-SKSJ: Fast and Exact Algorithm for Top-k Spatial-Keyword Similarity Join
Creator
NRID
1000040770649 1000040770649
researchmap permalink
amgt amgt
Scopus Author ID
55811167300 55811167300
CreatorName
Amagata, Daichi
CreatorName
Tsuruoka, Shohei
CreatorName
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
CreatorName
Hara, Takahiro
Subject
similarity join
spatial-keyword data
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.
Conference Information
Conference Name
International Conference on Advances in Geographic Information Systems
Conference Sequence
29
Conference Date
November 2nd to November 5th, 2021
Conference Place
New York
Conference Country
United States of America
Publisher
Association for Computing Machinery
Source Title
GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
Page
15-24
Date of Issued
2021-11-04
Language
English
Handle URL
https://hdl.handle.net/11094/92846
Relation.isVersionOf
DOI (Publisher Version)
https://doi.org/10.1145/3474717.3483629
Relation.isPartOf
ISBN
9781450384582
Access Rights
open access
CopyRight
© 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.
oaire:version
Accepted Manuscript
Category
会議発表論文 Conference Paper