微观交通仿真系统的近邻查询算法

doi:10.11772/j.issn.1001-9081.2015.02.0572

计算机应用 ›› 2015, Vol. 35 ›› Issue (2): 572-577.DOI: 10.11772/j.issn.1001-9081.2015.02.0572

微观交通仿真系统的近邻查询算法

宋竹, 秦志光, 邓伟伟, 赵玉平

电子科技大学计算机科学与工程学院, 成都 611731

收稿日期:2014-09-03 修回日期:2014-10-28 出版日期:2015-02-10 发布日期:2015-02-12
通讯作者: 宋竹
作者简介:宋竹(1983-),男,四川成都人,博士研究生,CCF会员,主要研究方向:数据挖掘、交通仿真; 秦志光(1956-),男,四川隆昌人,教授,博士生导师,博士,主要研究方向:信息安全; 邓伟伟(1990-),男,安徽芜湖人,硕士研究生,主要研究方向:数据挖掘; 赵玉平(1987-),男,四川广元人,硕士,主要研究方向:交通仿真。
基金资助:
国家863计划项目(2011AA010706);国家自然科学基金资助项目(61170041)。

Nearest neighbor query algorithm in microscopic traffic simulation system

SONG Zhu, QIN Zhiguang, DENG Weiwei, ZHAO Yuping

School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China

Received:2014-09-03 Revised:2014-10-28 Online:2015-02-10 Published:2015-02-12

摘要/Abstract

摘要：

为解决现有微观交通仿真系统中,由于采用基于链表的方法处理近邻查询导致的查询效率和可扩展性不高的问题,提出了一种基于B+树的近邻查询算法。该算法借鉴了数据库中近邻查询算法的思想并结合了链表结构的优点,在叶子节点维护了其存储的数据单元(即车辆)关系的索引结构,以达到快速查询车辆所在车道的前后车的目的。同时,在假设车辆随机分布的前提下,构建了一个数学模型,根据道路的属性和道路中车辆的数量,计算查询目标车辆的邻近车辆所需的最短平均查询长度,并通过此最短查询长度推导算法参数的最优值。理论分析和对比仿真实验显示,衡量该算法的主要指标:即仿真每个车辆的平均时间消耗,在三类常见的交通参数设置(正常的、较拥堵的和拥堵的)下较链表和B+树分别降低了64.2%和12.8%。仿真结果表明该算法具有良好的可扩展性,更适用于大规模微观交通仿真系统。

关键词: 微观交通仿真, B+树, 链表, 近邻查询, 参数优化

Abstract:

Since methods based on linked list in existing microscopic traffic simulation systems are not efficient and scalable to process Nearest Neighbor (NN) queries, a variation of B+ tree based method was proposed to resolve these problems. This method combined ideas from NN queries in database with advantages of linked list. By maintaining indices of nearby vehicles of each vehicle in the local lane, the performance of NN queries in that lane could be largely improved. Under the assumption of randomly distribution of vehicles, a mathematical model was also proposed to optimize the parameter setting according to multiple parameters for lanes and the amount of vehicles. This model calculated the minimized average query length of each NN query to optimize the parameter setting. The results of theoretical analysis and simulations showed that in common traffic conditions including sparse, normal and congestion, the main indicator, namely the average simulation time cost of each vehicle, could be reduced by 64.2% and 12.8% compared with linked list and B+ tree respectively. The results prove that the proposed method is suitable for larges-cale microscopic traffic simulation systems.

Key words: microscopic traffic simulation system, B+ tree, linked list, nearest neighbor query, parameter optimization

中图分类号:

TP391.9

宋竹, 秦志光, 邓伟伟, 赵玉平. 微观交通仿真系统的近邻查询算法[J]. 计算机应用, 2015, 35(2): 572-577.

SONG Zhu, QIN Zhiguang, DENG Weiwei, ZHAO Yuping. Nearest neighbor query algorithm in microscopic traffic simulation system[J]. Journal of Computer Applications, 2015, 35(2): 572-577.

参考文献

[1] CAMERON G D B, DUNCAN G I D. PARAMICS — Parallel microscopic simulation of road traffic [J]. The Journal of Supercomputing, 1996, 10(1): 25-53.
[2] FELLENDORF M. VISSIM: a microscopic simulation tool to evaluate actuated signal control including bus priority [C]//Proceedings of the 64th Institute of Transportation Engineers Annual Meeting. [S.l.]: ITE, 1994: 1-9.
[3] YANG Q, KOUTSOPOULOS H N. A microscopic traffic simulator for evaluation of dynamic traffic management systems [J]. Transportation Research Part C: Emerging Technologies, 1996, 4(3): 113-129.
[4] KRAJZEWICZ D, BONERT M, WAGNER P. The open source traffic simulation package SUMO [C]//RoboCup 2006: Proceedings of the 2006 Infrastructure Simulation Competition. [S.l.]: RoboCup Federation, 2006, 1: 1-5.
[5] ROUSSOPOULOS N, KELLEY S, VINCENT F. Nearest neighbor queries [C]//SIGMOD '95: Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1995: 71-79.
[6] HU H, LEE D L. Range nearestn-eighbor query [J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(1): 78-91.
[7] JAGADISH H V, OOI B C, TAN K-L, et al. iDistance: an adaptive B⁺-tree based indexing method for nearest neighbor search [J]. ACM Transactions on Database Systems, 2005, 30(2): 364-397.
[8] HJALTASON G R, SAMET H. Index-driven similarity search in metric spaces (survey article) [J]. ACM Transactions on Database Systems, 2003, 28(4): 517-580.
[9] ARYA S, MOUNT D M. Approximate nearest neighbor queries in fixed dimensions [C]//SODA '93: Proceedings of the Fourth Annual ACMS-IAM Symposium on Discrete algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 1993: 271-280.
[10] HU L, JING Y, KU W-S, et al. Enforcing k nearest neighbor query integrity on road networks [C]//SIGSPATIAL '12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York: ACM, 2012: 422-425.
[11] SEIDL T, KRIEGEL H-P. Optimal multi-step k-nearest neighbor search [C]//SIGMOD '98: Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1998: 154-165.
[12] ELMASRI R, NAVATHE S B. Fundamentals of database systems [M]. 5th ed. Upper Saddle River: Pearson Education, 2008: 652-660.
[13] COMER D. Ubiquitous B-tree [J]. ACM Computing Surveys, 1979, 11(2): 121-137.

[1]	张豪, 朱睿, 宋栿尧, 方鹏, 夏秀峰. 距离-关键字相似度约束的双色反k近邻查询方法[J]. 计算机应用, 2021, 41(6): 1686-1693.
[2]	金波, 张志勇, 赵婷. 基于差分隐私的社交网络位置近邻查询方法[J]. 计算机应用, 2020, 40(8): 2340-2344.
[3]	金滔, 董秀成, 李亦宁, 任磊, 范佩佩. 改进的粒子群优化算法优化分数阶PID控制器参数[J]. 计算机应用, 2019, 39(3): 796-801.
[4]	李佳佳, 刘晓静, 刘向宇, 夏秀峰, 朱睿. 基于动态选择启发值的改进TD-FTT算法[J]. 计算机应用, 2018, 38(1): 120-125.
[5]	李校林, 杜托, 刘彪. 基于B-list的快速频繁模式挖掘算法[J]. 计算机应用, 2017, 37(8): 2357-2361.
[6]	李方伟, 李骐, 朱江. 改进的基于隐马尔可夫模型的态势评估方法[J]. 计算机应用, 2017, 37(5): 1331-1334.
[7]	张进, 丁胜, 李波. 改进的基于粒子群优化的支持向量机特征选择和参数联合优化算法[J]. 计算机应用, 2016, 36(5): 1330-1335.
[8]	徐永秀, 刘旭敏, 徐维祥. 基于间隔链表改进的频繁项集挖掘算法[J]. 计算机应用, 2016, 36(4): 997-1001.
[9]	杨鹏, 赵辉, 鲍忠贵. 基于双十字链表存储的共享资源矩阵方法特性研究[J]. 计算机应用, 2016, 36(3): 653-656.
[10]	郭洪帅, 孙殿柱, 李延瑞, 李聪. 支持STL数据源的网格曲面动态空间索引[J]. 计算机应用, 2015, 35(9): 2611-2615.
[11]	吴宗谕, 罗文彩. 基于空间分解的参数优化径向基函数近似模型构造方法[J]. 计算机应用, 2015, 35(1): 179-182.
[12]	张华伟魏萌. 基于云免疫算法的认知无线网络参数优化[J]. 计算机应用, 2014, 34(3): 628-631.
[13]	张丽平李松赵纪桥郝晓红. 受限区域内的单纯型连续近邻链查询方法[J]. 计算机应用, 2014, 34(2): 406-410.
[14]	李书玲刘蓉张鎏钦刘红. 基于改进型SVM算法的语音情感识别[J]. 计算机应用, 2013, 33(07): 1938-1941.
[15]	刘德高李晓宇. 基于道路网的连续k近邻查询算法[J]. 计算机应用, 2013, 33(07): 1964-1968.

微观交通仿真系统的近邻查询算法

Nearest neighbor query algorithm in microscopic traffic simulation system

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics