Approximate aggregate nearest neighbor search on moving objects trajectories

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.

Keywords

Approximate aggregate k nearest neighbor (AAkNN) / scalable and efficient trajectory index (SETI) / trajectory indexing / moving objects / query processing

References

[1] ZhengY, ZhouX-fangComputing with spatial trajectories [M], 2011New YorkSpringer3-60

[2] ParentC, SpaccapietraS, RensoC, AndrienkoG, AndrienkoN, BogornyV, DamianiM L, GkoulalasdivanisA, MacedoJ, PelekisN, TheodoridisY, YanZ. Semantic trajectories modeling and analysis [J]. ACM Computing Surveys (CSUR), 2013, 45: 1-32

[3] RensoC, SpaccapietraS, ZimÁNyiE. Mobility data modeling management and understanding [M]. Cambridge University Press, 20135-10

[4] ChakkaV P, EverspaughA C, PatelJ MIndexing large trajectory data sets with SETI [C]// The Conference on Innovative Data Systems Research (CIDR 2003), 2003

[5] AbbasifardM R, GhahremaniB, NaderiH. A survey on nearest neighbor search methods [J]. International Journal of Computer Applications, 2014, 95: 39-52

[6] DhanabalS, ChandramathiS. A Review of various k-nearest neighbor query processing techniques [J]. Computer Applications, 2011, 31: 14-22

[7] BhatiaN, AshevV. Survey of nearest neighbor techniques [J]. International Journal of Computer Science and Information Security, 2010, 8: 1-4

[8] PapadiasD, ShenQ, TaoY, MouratidisKGroup nearest neighbor queries [C]// 20th International Conference on Data Engineering, Massachusetts, Boston, 2004301-312

[9] PapadiasD, TaoY, MouratidisK, HuiC K. Aggregate nearest neighbor queries in spatial databases [J]. ACM Transactions on Database Systems, 2005, 30: 529-576

[10] YiuM L, MamoulisN, PapadiasD. Aggregate nearest neighbor queries in road networks [J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17: 820-833

[11] FengJ, WatanabeT. Index and query methods in road networks [M]. Springer International Publishing, 201511-39

[12] MokbelM F, GhanemT M, ArefW G. Spatio-temporal access methods [J]. IEEE Data Engineering Bulletin, 2003, 26: 40-49

[13] Nguyen-DinhL, ArefW G, MokbelM F. Spatio-temporal access methods: Part 2 (2003-2010) [J]. IEEE Data Engineering Bulletin, 2010, 33: 46-55

[14] GuttmanA. R-trees: A dynamic index structure for spatial searching [J]. ACM SIGMOD Record, 1984, 14: 47-57

[15] ManolopoulosY, NanopoulosA, PapadopoulosA N, TheodoridisYR-Trees: Theory and applications [M], 2005New YorkSpringer3-20

[16] TaoY, PapadiasD. 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, 2001431-440

[17] NascimentoM A, SilvaJ R O, TheodoridisY. Evaluation of access structures for discretely moving points [C]// The International Workshop on Spatio-Temporal Database Management (STDBM'99). Edinburgh, 1999171-188

[18] TheodoridisY, VazirgiannisM, SellisT. Spatio-temporal indexing for large multimedia applications [C]// The Third IEEE International Conference on Multimedia Computing and Systems (ICMCS '96). Hiroshima, 1996441-448

[19] PfoserD, JensenC S, TheodoridisY. Novel Approaches in query processing for moving object trajectories [C]// 26th International Conference on Very Large Data Bases (VLDB '00). Cairo, Egypt, 2000395-406

[20] XuX, HanJ, LuW. RT-tree: An improved R-tree indexing structure for temporal spatial databases [C]// The International Symposium on Spatial Data Handling (SDH). Zurich, 19901040-1049

[21] NascimentoM A, SilvaJ R O. Towards historical R-trees [C]// The 1998 ACM symposium on Applied Computing (SAC '98). Atlanta, 1998235-240

[22] TaoY, PapadiasD. Efficient historical R-trees [C]// 13th International Conference on Scientific and Statistical Database Management (SSDBM '01). Fairfax, 2001223

[23] ChaC-i, KimS-w, WonJ-i, LeeJ, BaeD-ho. Efficient indexing in trajectory databases [J]. International Journal of Database Theory and Application, 2008, 1(1): 21-28

[24] SongR, SunW, ZhengB, ZhengYPRESS: A novel framework of trajectory compression in road networks [C]// Proceedings of the VLDB Endowment, 2014661-672

[25] FerhatosmanogluH, AgrawalD, Egecioglu, ElA, BbadiA. Optimal data-space partitioning of spatial data for parallel I/O [J]. Distributed and Parallel Databases, 2005, 17(1): 75-101

[26] GrunbaumB, ShephardG C. Tilings by regular polygons [J]. Mathematics Magazine, 1977, 50: 227-247

[27] SahrK, WhiteD, KimerlingA J. Geodesic discrete global grid systems [J]. Cartography and Geographic Information Science, 2003, 30: 121-134

[28] AntoineE, RamamohanaraoK, ShaoJ, ZhangR. Recursive partitioning method for trajectory indexing [C]// The Twenty-First Australasian Conference on Database Technologies-Volume 104 (ADC '10). Darlinghurst, Australia, 201037-46

[29] GreulichF E. Accurate polygon centroid computation using ARC/INFO GIS [J]. Journal of Computing in Civil Engineering, 1993, 7: 388-392

[30] ChenZ, ShenH T, ZhouX, ZhengY, XieXSearching trajectories by locations–An efficiency study [C]// The 2010 ACM SIGMOD International Conference on Management of data (SIGMOD '10), 2010255-266