Efficient mutual nearest neighbor query processing for moving object trajectories

S. Arumugam, C. Jermaine, Closest-point-of-approach join for moving object histories, in: Proceedings of the 22nd International Conference on Data Engineering (ICDE), 2006, p. 86. P. Bakalov, M. Hadjieleftheriou, E. Keogh, V.J. Tsotras, Efficient trajectory joins using symbolic representations, in: Proceedings of the Sixth International Conference on Mobile Data Management (MDM), 2005, pp. 86–93. P. Bakalov, M. Hadjieleftheriou, V.J. Tsotras, Time relaxed spatiotemporal trajectory joins, in: Proceedings of the 13th Annual ACM International Workshop on Geographic Information Systems (GIS), 2005, pp. 182–191. P. Bakalov, V.J. Tsotras, Continuous spatiotemporal trajectory joins, in: Proceedings of the Second International Conference on GeoSensor Networks (GSN), 2006, pp. 109–128. Benetis, 2006, Nearest and reverse nearest neighbor queries for moving objects, International Journal on Very Large Data Bases, 15, 229, 10.1007/s00778-005-0166-4 Brito, 1997, Connectivity of the mutual k-nearest neighbor graph in clustering and outlier detection, Statistics and Probability Letters, 35, 33, 10.1016/S0167-7152(96)00213-1 L. Chen, M.T. Ozsu, V. Oria, Robust and fast similarity search for moving object trajectories, in: Proceedings of ACM International Conference on Management of Data (SIGMOD), 2005, pp. 491–502. Cheung, 1998, Enhanced nearest neighbour search on the R-tree, SIGMOD Record, 27, 16, 10.1145/290593.290596 Corral, 2007, A performance comparison of distance-based query algorithms using R-trees in spatial databases, Information Science, 177, 2207, 10.1016/j.ins.2006.12.012 C.H.Q. Ding, X. He, K-nearest neighbor consistency in data clustering: Incorporating local information into global optimization, in: Proceedings of ACM Symposium on Applied Computing (SAC), 2004, pp. 584–589. Francis, 2008, A scalable constraint-based Q-hash indexing for moving objects, Information Science, 178, 1442, 10.1016/j.ins.2007.11.004 Frentzos, 2007, Algorithms for nearest neighbor search on moving object trajectories, GeoInformatica, 11, 159, 10.1007/s10707-006-0007-7 E. Frentzos, K. Gratsias, Y. Theodoridis, Index-based most similar trajectory search, in: Proceedings of 23rd International Conference on Data Engineering (ICDE), 2007, pp. 816–825. Y. Gao, G. Chen, Q. Li, B. Zheng, C. Li, Processing mutual nearest neighbor queries for moving object trajectories, in: Proceedings of the Ninth International Conference on Mobile Data Management (MDM), 2008, pp. 116–123. Gao, 2007, Efficient k-nearest neighbor search algorithms for historical moving object trajectories, Journal of Computer Science and Technology, 22, 232, 10.1007/s11390-007-9030-x Y. Gao, C. Li, G. Chen, Q. Li, C. Chen, Efficient algorithms for historical continuous kNN query processing over moving object trajectories, in: Proceedings of the Joint Ninth Asia-Pacific Web Conference on Advances in Data and Web Management and the Eighth International Conference on Web-Age Information Management (APWeb/WAIM), 2007, pp. 188–199. Gao, 2009, On efficient mutual nearest neighbor query processing in spatial databases, Data and Knowledge Engineering, 68, 705, 10.1016/j.datak.2009.04.004 Y. Gao, B. Zheng, G. Chen, Q. Li, Algorithms for constrained k-nearest neighbor queries over moving object trajectories, GeoInformatica, in press, doi: 10.1007/s10707-009-0084-5. Gowda, 1978, Agglomerative clustering using the concept of mutual nearest neighborhood, Pattern Recognition, 10, 105, 10.1016/0031-3203(78)90018-3 Gowda, 1979, The condensed nearest neighbor rule using the concept of mutual nearest neighborhood, IEEE Transactions on Information Theory, 25, 488, 10.1109/TIT.1979.1056066 J. Gudmundsson, M. van Kreveld, Computing longest duration flocks in trajectory data, in: Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems (GIS), 2006, pp. 35–42. D. Harel, Y. Koren, Clustering spatial data using random walks, in: Proceedings of the Seventh ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), 2001, pp. 281–286. Hjaltason, 1999, Distance browsing in spatial databases, ACM Transactions on Database Systems, 24, 265, 10.1145/320248.320255 S. Iwerks, H. Samet, K. Smith, Continuous k-nearest neighbor queries for continuously moving points with updates, in: Proceedings of the 29th International Conference on Very Large Data Base (VLDB), 2003, pp. 512–523. Jeung, 2008, Discovery of convoys in trajectory databases, Proceedings of the VLDB Endowment, 1, 1068, 10.14778/1453856.1453971 W. Jin, Anthony K.H. Tung, J. Han, W. Wang, Ranking outliers using symmetric neighborhood relationship, in: Proceedings of the 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2006, pp. 577–593. G. Kollios, D. Gunopoulos, V. Tsotras, On indexing mobile objects, in: Proceedings of the Eighth ACM Symposium on Principles of Database Systems (PODS), 1999, pp. 261–272. Lee, 2009, Mining frequent trajectory patterns in spatial-temporal databases, Information Science, 179, 2218, 10.1016/j.ins.2009.02.016 J. Lee, J. Han, X. Li, Trajectory outlier detection: a partition-and-detect framework, in: Proceedings of 24th International Conference on Data Engineering (ICDE), 2008, pp. 140–149. Lee, 2008, TraClass: Trajectory classification using hierarchical region-based and trajectory-based clustering, Proceedings of the VLDB Endowment, 1, 1081, 10.14778/1453856.1453972 J. Lee, J. Han, K. Whang, Trajectory clustering: a partition-and-group framework, in: Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2007, pp. 593–604. E.-J. Lee, K.H. Ryu, K.W. Nam, Indexing for efficient managing current and past trajectory of moving object, in: Proceedings of the Sixth Asia-Pacific Web Conference on Web Technologies Research and Development (APWeb), 2004, pp. 782–787. Lin, 2008, One way distance: for shape based similarity search of moving object trajectories, GeoInformatica, 12, 117, 10.1007/s10707-007-0027-y Mokbel, 2003, Spatio-temporal access methods, IEEE Data Engineering Bulletin, 26, 40 H.M.O. Mokhtar, J. Su, Universal trajectory queries for moving object databases, in: Proceedings of the Fifth International Conference on Mobile Data Management (MDM), 2004, pp. 133–144. K. Mouratidis, M. Hadjieleftheriou, D. Papadias, Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring, in: Proceedings of ACM International Conference on Management of Data (SIGMOD), 2005, pp. 634–645. A. Papadopoulos, Y. Manolopoulos, Performance of nearest neighbor queries in R-trees, in: Proceedings of the Sixth International Conference on Database Theory (ICDT), 1997, pp. 394–408. D. Pfoser, C.S. Jensen, Y. Theodoridis, Novel approaches in query processing for moving object trajectories, in: Proceedings of the 26th International Conference on Very Large Data Base (VLDB), 2000, pp. 395–406. Y. Qian, K. Zhang, Discovering spatial patterns accurately with effective noise removal, in: Proceedings of the Ninth ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD), 2004, pp. 43–50. Raptopoulou, 2003, Fast nearest neighbor query processing in moving object databases, GeoInformatica, 7, 113, 10.1023/A:1023403908170 N. Roussopoulos, S. Kelley, F. Vincent, Nearest neighbor queries, in: Proceedings of ACM International Conference on Management of Data (SIGMOD), 1995, pp. 71–79. Z. Song, N. Roussopoulos, K-nearest neighbor search for moving query point, in: Proceedings of the Seventh International Symposium on Advances in Spatial and Temporal Databases (SSTD), 2001, pp. 79–96. Sozer, 2008, Modeling and querying fuzzy spatiotemporal databases, Information Science, 178, 3665, 10.1016/j.ins.2008.05.034 Y. Tao, D. Papadias, The MV3R-Tree: a spatiotemporal access method for timestamp and interval queries, in: Proceedings of the 27th International Conference on Very Large Data Base (VLDB), 2001, pp. 431–440. Y. Tao, D. Papadias, Time parameterized queries in spatiotemporal databases, in: Proceedings of ACM International Conference on Management of Data (SIGMOD), 2002, pp. 334–345. Tao, 2007, Multidimensional reverse kNN search, International Journal on Very Large Data Bases, 16, 293, 10.1007/s00778-005-0168-2 Y. Tao, D. Papadias, Q. Shen, Continuous nearest neighbor search, in: Proceedings of the 28th International Conference on Very Large Data Base (VLDB), 2002, pp. 287–298. Y. Theodoridis, J.R.O. Silva, M.A. Nascimento, On the generation of spatiotemporal datasets, in: Proceedings of the Sixth International Symposium on Advances in Spatial Databases (SSD), 1999, pp. 147–164. Y. Theodoridis, M. Vazirgiannis, T.K. Sellis, Spatio-temporal indexing for large multimedia applications, in: Proceedings of the International Conference on Multimedia Computing and Systems (ICMCS), (1996) pp. 441–448. G. Trajcevski, R. Tamassia, H. Ding, P. Scheuermann, I.F. Cruz, Continuous probabilistic nearest neighbor queries for uncertain trajectories, in: Proceedings of the 12th International Conference on Extending Database Technology (EDBT), 2009, pp. 874–885. M. Vlachos, G. Kollios, D. Gunopulos, Discovering similar multidimensional trajectories, in: Proceedings of the 18th International Conference on Data Engineering (ICDE), 2002, pp. 673–684. R.C.-W. Wong, Y. Tao, A.W.-C. Fu, X. Xiao, On efficient spatial matching, in: Proceedings of the 33rd International Conference on Very Large Data Base (VLDB), 2007, pp. 579–590. X. Xiong, M.F. Mokbel, W. Aref, SEA-CNN: Scalable processing of continuous k-nearest neighbor queries in spatiotemporal databases, in: Proceedings of the 21st International Conference on Data Engineering (ICDE), 2005, pp. 643–654. Y. Yanagisawa, J. Akahani, T. Satoh, Shape-based similarity query for trajectory of mobile objects, in: Proceedings of the Fourth International Conference on Mobile Data Management (MDM), 2003, pp. 63–77. X. Yu, K. Pu, N. Koudas, Monitoring k-nearest neighbor queries over moving objects, in: Proceedings of the 21st International Conference on Data Engineering (ICDE), 2005, pp. 631–642. Y. Zhang, C. Zhang, S. Wang, Clustering in knowledge embedded space, in: Proceedings of the 14th European Conference on Machine Learning (ECML), 2003, pp. 480–491.