Nearest Neighbor Search on Moving Object Trajectories

Autor:	Nikos Pelekis, Kostas Gratsias, Yannis Theodoridis, Elias Frentzos
Rok vydání:	2005
Předmět:	Computer science Nearest neighbor search Spatial database Scalability R-tree Data mining Pruning (decision trees) Object (computer science) computer.software_genre Algorithm computer Search tree
Zdroj:	Advances in Spatial and Temporal Databases ISBN: 9783540281276 SSTD
DOI:	10.1007/11535331_19
Popis:	With the increasing number of Mobile Location Services (MLS), the need for effective k-NN query processing over historical trajectory data has become the vehicle for data analysis, thus improving existing or even proposing new services. In this paper, we investigate mechanisms to perform NN search on R-tree-like structures storing historical information about moving object trajectories. The proposed branch-and-bound algorithms vary with respect to the type of the query object (stationary or moving point) as well as the type of the query result (continuous or not). We also propose novel metrics to support our search ordering and pruning strategies. Using the implementation of the proposed algorithms on a member of the R-tree family for trajectory data (the TB-tree), we demonstrate their scalability and efficiency through an extensive experimental study using synthetic and real datasets.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c2dc9cac6af253b0f8035b9cda724d77 https://doi.org/10.1007/11535331_19 Zobrazit plný text záznamu