Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/Sub

Tsuruoka, Shohei; Amagata, Daichi; Nishio, Shunya; Hara, Takahiro

doi:https://doi.org/10.1145/3397536.3422199

Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/Sub

Tsuruoka, Shohei; Amagata, Daichi; Nishio, Shunya et al.

GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2020, 111-114

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

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

閲覧可能ファイル

ファイル	フォーマット	利用条件	サイズ	閲覧回数	利用開始日	説明	information
GISProcACMIntSympAdvGeogrInfSyst_111	pdf	なし	983 KB	114	2023.10.31

論文情報

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

タイトル	Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/Sub
著者	著者名 Tsuruoka, Shohei
	NRID 1000040770649 1000040770649 researchmap permalink amgt amgt Scopus Author ID 55811167300 55811167300 著者名 Amagata, Daichi
	著者名 Nishio, Shunya
	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
キーワード等	kNN queries
キーワード等	location-aware Pub/Sub
抄録	Recent applications employ publish/subscribe (Pub/Sub) systems so that publishers can easily receive attentions of customers and subscribers can monitor useful information generated by publishers. Due to the prevalence of smart devices and social networking services, a large number of objects that contain both spatial and keyword information have been generated continuously, and the number of subscribers also continues to increase. This poses a challenge to Pub/Sub systems: they need to continuously extract useful information from massive objects for each subscriber in real time. In this paper, we address the problem of k nearest neighbor monitoring on a spatial-keyword data stream for a large number of subscriptions. To scale well to massive objects and subscriptions, we propose a distributed solution. Given m workers, we divide a set of subscriptions into m disjoint subsets based on a cost model so that each worker has almost the same kNN-update cost, to maintain load balancing. We allow an arbitrary approach to updating kNN of each subscription, so with a suitable in-memory index, our solution can accelerate update efficiency by pruning irrelevant subscriptions for a given new object. We conduct experiments on real datasets, and the results demonstrate the efficiency and scalability of our solution.
会議情報	会議名 28th International Conference on Advances in Geographic Information Systems 回次 28 開催期間 November 3rd to November 6th, 2020 開催地 Seattle 開催国アメリカ合衆国
出版者	Association for Computing Machinery
収録物名	GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
ページ	111-114
刊行年月	2020-11-03
言語	英語
ハンドルURL	https://hdl.handle.net/11094/92859
関連情報 (isVersionOf)	DOI (出版社版) https://doi.org/10.1145/3397536.3422199
関連情報 (isPartOf)	ISBN 9781450380195
アクセス権	open access
権利情報	© 2020 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 Tsuruoka S., Amagata D., Nishio S., et al. Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/Sub. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 111 (2020); https://doi.org/10.1145/3397536.3422199.
出版タイプ	Accepted Manuscript
カテゴリ	会議発表論文 Conference Paper

資源タイプ	会議発表論文
ローカル資源タイプ	会議発表論文
DCMI資源タイプ	text
DCTERMS.bibliographicCitation	GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems. 2020, p. 111-114
DC.title	Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/Sub
DC.creator	Tsuruoka, Shohei
	Amagata, Daichi
	Nishio, Shunya
	Hara, Takahiro
DC.publisher	Association for Computing Machinery
DC.language' scheme='DCTERMS.RFC1766	英語
DC.type' scheme='DCTERMS.DCMIType	text
DCTERMS.issued' scheme='DCTERMS.W3CDTF	2020-11-03
DC.identifier	https://doi.org/10.1145/3397536.3422199
DC.subject	kNN queries
DC.subject	location-aware Pub/Sub
DCTERMS.abstract	Recent applications employ publish/subscribe (Pub/Sub) systems so that publishers can easily receive attentions of customers and subscribers can monitor useful information generated by publishers. Due to the prevalence of smart devices and social networking services, a large number of objects that contain both spatial and keyword information have been generated continuously, and the number of subscribers also continues to increase. This poses a challenge to Pub/Sub systems: they need to continuously extract useful information from massive objects for each subscriber in real time. In this paper, we address the problem of k nearest neighbor monitoring on a spatial-keyword data stream for a large number of subscriptions. To scale well to massive objects and subscriptions, we propose a distributed solution. Given m workers, we divide a set of subscriptions into m disjoint subsets based on a cost model so that each worker has almost the same kNN-update cost, to maintain load balancing. We allow an arbitrary approach to updating kNN of each subscription, so with a suitable in-memory index, our solution can accelerate update efficiency by pruning irrelevant subscriptions for a given new object. We conduct experiments on real datasets, and the results demonstrate the efficiency and scalability of our solution.
DC.rights	© 2020 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 Tsuruoka S., Amagata D., Nishio S., et al. Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/Sub. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 111 (2020); https://doi.org/10.1145/3397536.3422199.
DC.format	92859
citation_title	Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/Sub
citation_author	Tsuruoka, Shohei
	Amagata, Daichi
	Nishio, Shunya
	Hara, Takahiro
citation_publisher	Association for Computing Machinery
citation_language	英語
citation_date	2020-11-03
citation_journal_title	GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
citation_firstpage	111
citation_lastpage	114
citation_doi	https://doi.org/10.1145/3397536.3422199
citation_public_url	https://hdl.handle.net/11094/92859

Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/Sub

閲覧可能ファイル

論文情報

論文詳細を表示