Abstract
Aggregate nearest neighbor (ANN) search retrieves for two spatial datasets T and Q, segment(s) of one or more trajectories from the set T having minimum aggregate distance to points in Q. When interacting with large amounts of trajectories, this process would be very time-consuming due to consecutive page loads. An approximate method for finding segments with minimum aggregate distance is proposed which can improve the response time. In order to index large volumes of trajectories, scalable and efficient trajectory index (SETI) structure is used. But some refinements are provided to temporal index of SETI to improve the performance of proposed method. The experiments were performed with different number of query points and percentages of dataset. It is shown that proposed method besides having an acceptable precision, can reduce the computation time significantly. It is also shown that the main fraction of search time among load time, ANN and computing convex and centroid, is related to ANN.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
ZHENG Yu, ZHOU Xiao-fang. Computing with spatial trajectories [M]. New York: Springer, 2011: 3–60.
PARENT C, SPACCAPIETRA S, RENSO C, ANDRIENKO G, ANDRIENKO N, BOGORNY V, DAMIANI M L, GKOULALASDIVANIS A, MACEDO J, PELEKIS N, THEODORIDIS Y, YAN Z. Semantic trajectories modeling and analysis [J]. ACM Computing Surveys (CSUR), 2013, 45: 1–32.
RENSO C, SPACCAPIETRA S, ZIMÁNYI E. Mobility data modeling management and understanding [M]. Cambridge University Press, 2013: 5–10.
CHAKKA V P, EVERSPAUGH A C, PATEL J M. Indexing large trajectory data sets with SETI [C]// The Conference on Innovative Data Systems Research (CIDR 2003). USA, 2003.
ABBASIFARD M R, GHAHREMANI B, NADERI H. A survey on nearest neighbor search methods [J]. International Journal of Computer Applications, 2014, 95: 39–52.
DHANABAL S, CHANDRAMATHI S. A Review of various k-nearest neighbor query processing techniques [J]. Computer Applications, 2011, 31: 14–22.
BHATIA N, ASHEV V. Survey of nearest neighbor techniques [J]. International Journal of Computer Science and Information Security, 2010, 8: 1–4.
PAPADIAS D, SHEN Q, TAO Y, MOURATIDIS K. Group nearest neighbor queries [C]// 20th International Conference on Data Engineering, Massachusetts, Boston, USA, 2004: 301–312.
PAPADIAS D, TAO Y, MOURATIDIS K, HUI C K. Aggregate nearest neighbor queries in spatial databases [J]. ACM Transactions on Database Systems, 2005, 30: 529–576.
YIU M L, MAMOULIS N, PAPADIAS D. Aggregate nearest neighbor queries in road networks [J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17: 820–833.
FENG J, WATANABE T. Index and query methods in road networks [M]. Springer International Publishing, 2015: 11–39.
MOKBEL M F, GHANEM T M, AREF W G. Spatio-temporal access methods [J]. IEEE Data Engineering Bulletin, 2003, 26: 40–49.
NGUYEN-DINH L, AREF W G, MOKBEL M F. Spatio-temporal access methods: Part 2 (2003-2010) [J]. IEEE Data Engineering Bulletin, 2010, 33: 46–55.
GUTTMAN A. R-trees: A dynamic index structure for spatial searching [J]. ACM SIGMOD Record, 1984, 14: 47–57.
MANOLOPOULOS Y, NANOPOULOS A, PAPADOPOULOS A N, THEODORIDIS Y. R-Trees: Theory and applications [M]. New York: Springer, 2005: 3–20.
TAO Y, PAPADIAS D. MV3R-Tree: A spatio-temporal access method for timestamp and interval queries [C]// The 27th International Conference on Very Large Data Bases (VLDB '01). Rome, 2001: 431–440.
NASCIMENTO M A, SILVA J R O, THEODORIDIS Y. Evaluation of access structures for discretely moving points [C]// The International Workshop on Spatio-Temporal Database Management (STDBM'99). Edinburgh, 1999: 171–188.
THEODORIDIS Y, VAZIRGIANNIS M, SELLIS T. Spatio-temporal indexing for large multimedia applications [C]// The Third IEEE International Conference on Multimedia Computing and Systems (ICMCS '96). Hiroshima, 1996: 441–448.
PFOSER D, JENSEN C S, THEODORIDIS Y. Novel Approaches in query processing for moving object trajectories [C]// 26th International Conference on Very Large Data Bases (VLDB '00). Cairo, Egypt, 2000: 395–406.
XU X, HAN J, LU W. RT-tree: An improved R-tree indexing structure for temporal spatial databases [C]// The International Symposium on Spatial Data Handling (SDH). Zurich, 1990: 1040–1049.
NASCIMENTO M A, SILVA J R O. Towards historical R-trees [C]// The 1998 ACM symposium on Applied Computing (SAC '98). Atlanta, 1998: 235–240.
TAO Y, PAPADIAS D. Efficient historical R-trees [C]// 13th International Conference on Scientific and Statistical Database Management (SSDBM '01). Fairfax, 2001: 223.
CHA Chang-il, KIM Sang-wook, WON Jung-im, LEE Junghoon, BAE Duck-ho. Efficient indexing in trajectory databases [J]. International Journal of Database Theory and Application, 2008, 1(1): 21–28.
SONG R, SUN W, ZHENG B, ZHENG Y. PRESS: A novel framework of trajectory compression in road networks [C]// Proceedings of the VLDB Endowment. Hangzhou, 2014: 661–672.
FERHATOSMANOGLU H, AGRAWAL D, EGECIOGLU Ö, EL A BBADI A. Optimal data-space partitioning of spatial data for parallel I/O [J]. Distributed and Parallel Databases, 2005, 17(1): 75–101.
GRUNBAUM B, SHEPHARD G C. Tilings by regular polygons [J]. Mathematics Magazine, 1977, 50: 227–247.
SAHR K, WHITE D, KIMERLING A J. Geodesic discrete global grid systems [J]. Cartography and Geographic Information Science, 2003, 30: 121–134.
ANTOINE E, RAMAMOHANARAO K, SHAO J, ZHANG R. Recursive partitioning method for trajectory indexing [C]// The Twenty-First Australasian Conference on Database Technologies-Volume 104 (ADC '10). Darlinghurst, Australia, 2010: 37–46.
GREULICH F E. Accurate polygon centroid computation using ARC/INFO GIS [J]. Journal of Computing in Civil Engineering, 1993, 7: 388–392.
CHEN Z, SHEN H T, ZHOU X, ZHENG Y, XIE X. Searching trajectories by locations–An efficiency study [C]// The 2010 ACM SIGMOD International Conference on Management of data (SIGMOD '10). Indianapolis, Indiana, USA, 2010: 255–266.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Abbasifard, M.R., Naderi, H., Fallahnejad, Z. et al. Approximate aggregate nearest neighbor search on moving objects trajectories. J. Cent. South Univ. 22, 4246–4253 (2015). https://doi.org/10.1007/s11771-015-2973-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11771-015-2973-0