RNDLP: A Distributed Framework for Supporting Continuous k-Similarity Trajectories Search over Road Network

Hong Jiang, Sainan Tong, Rui Zhu () and Baoze Wei
Additional contact information
Hong Jiang: School of Management, Shenyang University of Technology, Shenyang 110870, China
Sainan Tong: School of Computer Science, Shenyang Aerospace University, Shenyang 110136, China
Rui Zhu: School of Computer Science, Shenyang Aerospace University, Shenyang 110136, China
Baoze Wei: Department of Energy Technology, Aalborg University, 9220 Aalborg, Denmark

Mathematics, 2024, vol. 12, issue 2, 1-16

Abstract: Continuous k -similarity trajectories search over a data stream is an important problem in the domain of spatio-temporal databases. Given a set of trajectories T and a query trajectory T q over road network G , the system monitors trajectories within T , reporting k trajectories that are the most similar to T q whenever one time unit is passed. Some existing works study k -similarity trajectories search over trajectory data, but they cannot work in a road network environment, especially when the trajectory set scale is large. In this paper, we propose a novel framework named RNDLP (Road Network-based Distance Lower-bound-based Prediction) to support CKTRN over trajectory data. It is a distributed framework based on the following observation. That is, given a trajectory T i and the query trajectory T q , when we have knowledge of D ( T i ), we can compute the lower-bound and upper-bound distances between T q and T i , which enables us to predict the scores of trajectories in T and employ these predictions to assess the significance of trajectories within T . Accordingly, we can form a mathematical model to evaluate the excepted running cost of each trajectory we should spend. Based on the model, we propose a partition algorithm to partition trajectories into a group of servers so as to guarantee that the workload of each server is as the same as possible. In each server, we propose a pair-based algorithm to predict the earliest time T i could become a query result, and use the predicted result to organize these trajectories. Our proposed algorithm helps us support query processing via accessing a few points of a small number of trajectories whenever trajectories are updated. Finally, we conduct extensive performance studies on large, real, and synthetic datasets, which demonstrate that our new framework could efficiently support CKST over a data stream.

Keywords: trajectory stream; k-similarity trajectories search; distributed; continuous query (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/2/270/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/2/270/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:2:p:270-:d:1318917

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().