路网环境中关于模糊组最近邻问题的研究  

Flexible group nearest neighbor queries in road networks

作　　者：陈舒[1] 蒋志会[1] 陆恒[2] 缪天翔 

机构地区：[1]上海交通大学计算机科学与工程系,上海201100 [2]上海交通大学软件学院,上海201100

出　　处：《计算机应用研究》2016年第2期343-346,355,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61373156)

摘　　要：为了解决路网环境中传统的组最近邻查询无法支持用户不确定搜索的问题,在组最近邻查询的基础上引入了模糊因子来描述用户查询的不确定性,并提出了四种不同的算法。其中朴素的全局搜索算法利用了Dijkstra算法的特性来处理不确定性,在此基础上利用多维向量算法和V-tree算法通过缩小搜索空间进一步优化,最后提出的近似算法,在牺牲了一定正确率的前提下进一步提高了查询效率。通过在真实路网数据集上的大量实验总结归纳了不同算法的优势,并充分验证了各个算法的合理性与实用性。In road networks, traditional group nearest neighbor algorithms cannot support the queries with uncertainty. To solve this problem, this paper introduced a flexibility factor to describe the query uncertainty and proposed four algorithms. The global search algorithm took advantage of Dijkstra algorithm to handle the uncertainty, and the multidimensional vector al- gorithm and the V-tree algorithm further optimized it with some pruning techniques in search space, the approximate algorithm further improved the performanee by sacrifieing some accuracy. The advantages of these algorithms, and their effeteness and efficiency, are fully coneluded in a comprehensive experimental evaluation on real road network datasets.

关 键 词：组最近邻查询 空间数据库 路网 近似算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]