Efficient Retrieval of Top-k Weighted Triangles on Static and Dynamic Spatial Data

Taniguchi, Ryosuke; Amagata, Daichi; Hara, Takahiro

doi:https://doi.org/10.1109/ACCESS.2022.3177620

Efficient Retrieval of Top-k Weighted Triangles on Static and Dynamic Spatial Data

Taniguchi, Ryosuke; Amagata, Daichi; Hara, Takahiro

IEEE Access, 2022, 10, 55298-55307

Number of Access:605（2025-10-07 07:33 Counts）

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

Link to primary information

File	Format	Terms of use	Size	Views	Date.Available	Description	information
IEEEAccess_10_55298	pdf	None	774 KB	53	2023.10.17

Creative Commons : Attribution

Item Information

Output File Export EndNote Basic Export Mendeley

Title	Efficient Retrieval of Top-k Weighted Triangles on Static and Dynamic Spatial Data
Creator	CreatorName Taniguchi, Ryosuke
	NRID 1000040770649 1000040770649 researchmap permalink amgt amgt Scopus Author ID 55811167300 55811167300 CreatorName 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 CreatorName Hara, Takahiro
Subject	Dynamic data
	Spatial points
	Top-k retrieval
	Weighted graph
Description	Taniguchi R., Amagata D., Hara T.. Efficient Retrieval of Top-k Weighted Triangles on Static and Dynamic Spatial Data. IEEE Access 10, 55298 (2022); https://doi.org/10.1109/ACCESS.2022.3177620.
Abstract	Due to the proliferation of location-based services, spatial data analysis becomes more and more important. We consider 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, as they have been receiving attention as spatial data analysis tools. We focus on triangles in such graphs and address the problem of retrieving the top- $k$ weighted spatial triangles. 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 overcome this challenge, we propose an algorithm that returns the exact result efficiently. We moreover consider two dynamic data models: (i) fully dynamic data that allow arbitrary point insertions and deletions and (ii) streaming data in a sliding-window model. They often appear in location-based services. The results of our experiments on real datasets show the efficiency of our algorithms for static and dynamic data.
Publisher	Institute of Electrical and Electronics Engineers Inc.
Source Title	IEEE Access
Volume (Issue)	10
Page	55298-55307
Date of Issued	2022-01-01
Language	English
Handle URL	https://hdl.handle.net/11094/92777
eISSN	21693536
Relation.isVersionOf	DOI (Publisher Version) https://doi.org/10.1109/ACCESS.2022.3177620
Access Rights	open access
CopyRight	This article is licensed under a Creative Commons Attribution 4.0 International License.
oaire:version	Version of Record
Category	学術雑誌論文 Journal Article

Resource Type	journal article
Local Type	Journal Article
DCMI Type	Text
DCTERMS.bibliographicCitation	IEEE Access. 2022, 10, p. 55298-55307
DC.title	Efficient Retrieval of Top-k Weighted Triangles on Static and Dynamic Spatial Data
DC.creator	Taniguchi, Ryosuke
	Amagata, Daichi
	Hara, Takahiro
DC.publisher	Institute of Electrical and Electronics Engineers Inc.
DC.language' scheme='DCTERMS.RFC1766	English
DC.type' scheme='DCTERMS.DCMIType	Text
DCTERMS.issued' scheme='DCTERMS.W3CDTF	2022-01-01
DC.identifier	https://doi.org/10.1109/ACCESS.2022.3177620
DC.subject	Dynamic data
	Spatial points
	Top-k retrieval
	Weighted graph
DC.description	Taniguchi R., Amagata D., Hara T.. Efficient Retrieval of Top-k Weighted Triangles on Static and Dynamic Spatial Data. IEEE Access 10, 55298 (2022); https://doi.org/10.1109/ACCESS.2022.3177620.
DCTERMS.abstract	Due to the proliferation of location-based services, spatial data analysis becomes more and more important. We consider 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, as they have been receiving attention as spatial data analysis tools. We focus on triangles in such graphs and address the problem of retrieving the top- $k$ weighted spatial triangles. 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 overcome this challenge, we propose an algorithm that returns the exact result efficiently. We moreover consider two dynamic data models: (i) fully dynamic data that allow arbitrary point insertions and deletions and (ii) streaming data in a sliding-window model. They often appear in location-based services. The results of our experiments on real datasets show the efficiency of our algorithms for static and dynamic data.
DC.rights	This article is licensed under a Creative Commons Attribution 4.0 International License.
DC.format	92777
citation_title	Efficient Retrieval of Top-k Weighted Triangles on Static and Dynamic Spatial Data
citation_author	Taniguchi, Ryosuke
	Amagata, Daichi
	Hara, Takahiro
citation_publisher	Institute of Electrical and Electronics Engineers Inc.
citation_language	English
citation_date	2022-01-01
citation_journal_title	IEEE Access
citation_volume	10
citation_firstpage	55298
citation_lastpage	55307
citation_doi	https://doi.org/10.1109/ACCESS.2022.3177620
citation_public_url	https://hdl.handle.net/11094/92777

Efficient Retrieval of Top-k Weighted Triangles on Static and Dynamic Spatial Data

Link to primary information

Item Information

Show details