计算机科学 ›› 2017, Vol. 44 ›› Issue (3): 16-19.doi: 10.11896/j.issn.1002-137X.2017.03.004
薛忠斌,白利光,何宁,周烜,周歆,王珊
XUE Zhong-bin, BAI Li-guang, HE Ning, ZHOU Xuan, ZHOU Xin and WANG Shan
摘要: 随着无线通信技术、空间定位技术和移动计算技术的快速发展,基于位置的查询成为数据库领域的一个重要研究问题。研究了路网中移动对象的KNN查询,一系列的算法被提出用于解决移动对象的KNN查询问题。然而,这些算法关注于查询的快速响应问题或者专注于解决移动对象的快速更新问题。随着移动对象数量的不断增加,当查询和更新大量涌入时,吞吐量成为一个更重要的问题。针对移动对象的更新数据流和查询数据流,提出了一种基于内存的高吞吐量移动对象KNN查询算法——DSRNKNN算法,用于处理路网中移动对象的KNN查询。DSRNKNN算法采用了基于快照的模式。在每个快照中,DSRNKNN算法通过重新构建索引的方式避免了复杂的索引维护操作,充分发挥了硬件的性能;通过每次执行一组查询的方式,充分利用查询内和查询间的并行,增加了数据的局部性,提高了算法的效率。在基于实际路网生成的数据集上对算法进行了测试,实验验证了DSRNKNN算法具有很好的性能表现。
[1] CHO H J,CHUNG C W.An efficient and scalable approach to CNN queries in a road network[C]∥Proceedings of the 31st International Conference on Very Large Data Bases.VLDB Endowment,2005:865-876. [2] MOURATIDIS K,YIU M L,PAPADIAS D,et al.Continuousnearest neighbor monitoring in road networks[C]∥Proceedings of the 32nd International Conference on Very large Data Bases.VLDB Endowment,2006:43-54. [3] LEE K C K,LEE W C,ZHENG B,et al.ROAD:a new spatial object search framework for road networks[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(3):547-560. [4] CHEN Y J,CHUANG K T,CHEN M S.Coupling or decoupling for KNN search on road networks?:a hybrid framework on user query patterns[C]∥Proceedings of the 20th ACM International Conference on Information and Knowledge Management.ACM,2011:795-804. [5] CHEN Y J,CHUANG K T,CHEN M S.Spatial-temporal query homogeneity for KNN object search on road networks[C]∥ Proceedings of the 22nd ACM International Conference on Conference on Information & Knowledge Management.ACM,2013:1019-1028. [6] BALKESEN C,TEUBNER J,ALONSO G,et al.Main-Memory Hash Joins on Modern Processor Architectures[J].IEEE Transactions on Knowledge & Data Engineering,2015,27(7):1754-1766. [7] TEUBNER J,ALONSO G,BALKESEN C,et al.Main-memory hash joins on multi-core CPUs:Tuning to the underlying hardware[C]∥ 2013 IEEE 29th International Conference on Data Engineering (ICDE).IEEE,2013:362-373. [8] KIM C,KALDEWEY T,LEE V W,et al.Sort vs.Hash revisited:fast join implementation on modern multi-core CPUs[J].Proceedings of the Vldb Endowment,2009,2(2):1378-1389. [9] SIDLAUSKAS D,SALTENIS S,JENSEN C S.Processing ofextreme moving-object update and query workloads in main memory[J].The Vldb Journal,2014,23(5):817-841. [10] LI F,CHENG D,HADJIELEFTHERIOU M,et al.On tripplanning queries in spatial databases[M]∥Advances in Spatial and Temporal Databases.Springer Berlin Heidelberg,2005:273-290. [11] LI F.Real Datasets for Spatial Databases:Road Networks and Points of Interest.http://www.cs.fsu.edu/ lifeifei/SpatialDataset.htm.2004 [12] LEE K C K,LEE W C,ZHENG B.Fast object search on road networks[C]∥Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology.ACM,2009:1018-1029. [13] DITTRICH J,BLUNSCHI L,SALLES M A V.Indexing mo-ving objects using short-lived throwaway indexes[M]∥Advances in Spatial and Temporal Databases.Springer Berlin Heidelberg,2009:189-207. [14] BRINKHOFF T.A framework for generating network-basedmoving objects[J].GeoInformatica,2002,6(2):153-180 |
No related articles found! |
|