学術雑誌論文

学術雑誌論文

text

IEEE Access. 2022, 10, p. 55298-55307

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

Institute of Electrical and Electronics Engineers Inc.

英語

text

2022-01-01

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

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.

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.

This article is licensed under a Creative Commons Attribution 4.0 International License.

92777

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

Institute of Electrical and Electronics Engineers Inc.

英語

2022-01-01

IEEE Access

10

55298

55307

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

https://hdl.handle.net/11094/92777