关键字 |
| BFS、约束的路线,时间,查询 |
介绍 |
| 一般人希望减少出行距离但他们希望覆盖所有地方和满足约束。传统方法招致大量的重复计算,从而不可伸缩的大型数据集。前路线服务提供商如谷歌城市旅游(citytours.googlelabs.com), Yahoo旅游频道(travel.yahoo.com)规定了用户搜索和分享旅行,不幸的是,不能回答最优路线查询或不能包含用户定义的约束。所以需要新颖有效的方法。 |
| 感兴趣的点(POI)序列也称为路线集合从启用GPS / GIS设备帮助用户获得更快到达目的地集合排序路由信息获得途径。这个排序过程包括路径查询评价大型磁盘频繁更新的路由集合。更新需要添加和删除的路线。路线集合可以非常转换为图;因此,路径查询可以使用标准的图搜索技术评估。这些方法遵循两种方法之一。第一个采用图的遍历方法,如深度优先搜索(DFS)。第二个压缩图的传递闭包,其中包含达到信息的能力,即。,任何一对节点之间的路径是否存在。虽然传递闭包方法是最快的,他们大多是适用于不频繁更新的数据集,或者当局部更新,因为它们需要昂贵的预先估计。另一方面,DFS很容易维护,但较慢,因为他们可能访问图的很大一部分。 |
| 对于一个给定的一组空间点每个分类信息,例如,餐厅,酒吧,等等,最优路径查询发现从查询点的最短路径(例如,一个家庭或酒店),和包括一组指定的类别(例如,酒吧,餐馆,博物馆)。用户还可以指定不同类别之间的偏序约束,比如,一个餐厅之前必须去酒吧。提出系统的查询包含两个参数:一个起点q,和一个有向无环图《GQ》被称为访问顺序图。《GQ》中的每个顶点对应于一个类别和每条边? C;C′?显示的类别C之前必须访问另一个类别C′。方法使用贪婪算法之前回答的最优路线查询。我们使用提出了两种高效的技术向前向后搜索和搜索来找到最优路径查询。第一个计算最优路线从最后一点到第一个,而另一个遵循的,顺序点 |
| 导航服务提供者应该考虑更多复杂的因素如工作时间、类型的服务和可能的限制的订单实体可能访问。我们将时间等因素的限制。合并的时间限制在我们的空间场景中会导致一个新的时空方法路线查询。我们延长批向前搜索算法与一个新方法来处理时间约束的路线查询。结果是有效的和之前相比更多的思考方法和该方法的实现验证我们的索赔要求。 |
| 这个项目的目标是找到一个最优路线查询,考虑所有必要的用户定义的约束。等约束可能任意约束一个ATM机前应该去餐厅或饭店的时间约束,如工作时间 |
相关工作 |
| Bouros Panagiotis,等[1]考虑路径查询频繁更新路线集合了路线收集和两点ns和nt,路径查询返回一个路径,即。一系列的点连接ns nt。这项工作目标路径查询评估大型磁盘上居民频繁更新的路由集合。更新需要添加和删除的路线。路线集合可以非常转换为图;因此,路径查询可以使用标准的图搜索技术评估。这些方法遵循两种模式。第一个采用图的遍历方法,如深度优先搜索(DFS) [3]。第二个压缩图的传递闭包,其中包含达到信息的能力,即。,任何一对节点之间的路径是否存在。两种模式既有优点和缺点。这里像RTS, LTS图遍历技术。路线遍历搜索(RTS)[2],扩展了搜索考虑所有后续节点的路由,而链接遍历搜索(LTS)只考虑下一个链接的节点集合。 Route Traversal Search with Transitions (RTST) uses the T -Index in addition to R-Index to captures transitions among routes allowing earlier termination [1].Link Traversal Search with Transitions (LTST) has a stronger condition based on the T -Index. The LTS-k algorithm forgoes the high storage and maintenance cost of T -Index and features a tunable termination condition. |
| 赵和耿等[4]讨论使用移动网络的路径搜索。在移动环境中信息和查询服务是基于连续移动查询处理或连续k最近邻(CKNN),找到兴趣点的地点或兴趣对象变化而移动手机用户。这些位置被称为“分裂节点。“所有的现有工作CKNN查询路径划分为段,这一段路隔开两个十字路口,然后,这个过程找到分裂节点应用于每一段。处理每一段是不可能的所以我们使用fo CKNN泰森多边形法图。因为它不把道路分成段实现更好的性能。其中最著名的和不断增长的移动信息服务是移动导航的应用[5],由于交通负荷的增加和道路连接的复杂性。最常见的搜索是资讯搜索[6]。资讯的问题也被解决在其他领域,包括数据挖掘和工业电子[7]。为了找到分裂节点,所有现有CKNN方法将查询路径分成部分,找到资讯结果两个终止节点的每一部分,然后对于每个部分,找到分裂节点。 One segment of the path starts from an intersection and ends at another intersection. For every segment, a KNN process is invoked to find split nodes for each segment. |
| 泰森多边形法图是一种特殊的分解的距离度量空间由一组指定的离散的对象空间[8]。给定一组点的年代,将生成相应的泰森多边形法图。每个s点都有自己的泰森多边形法细胞V (s),它包含所有点接近年代比任何其他点。边界点与多边形的集合点之间距离的方程对共享发电机。 |
| 陈和Haiquan等[9]提出一种新颖的空间查询类型,运用多部分测序的路线(MRPSR)查询,这将帮助用户提供好的旅行计划有效地与用户定义的规则。MRPSR查询提供了一个统一的框架,它贯穿了众所周知的旅行计划查询(TPQ)和最优排序查询路线(OSR)。回答MRPSR查询困难在于如何整合多个选择的兴趣点(POI)规则当寻找满意的旅行路线。通过保持旅游规则activity-on-vertex网络,我们利用拓扑排序[10]整合旅游规则有多种POIs的选择和研究MRPSR查询的可解性。 |
| 最近的Neighbor-based部分序列路线查询(NNPSR)算法。NNPSR算法使用activity-on-vertex网络指导搜索来检索算法的路线满足公路网络中的所有旅游规则。这里的图有一个边缘< i, j >当且仅当类别我是立即先决条件类别j的规则。图为命名为活动顶点(自动阀)网络[15]。第一步是列出一个顶点的网络,没有前任。然后第二步是删除这个顶点和边主要从自动阀。重复这两个步骤,直到所有的顶点已经上市。 |
| 整合NNPSR灯最优路线发现者(主)算法[11]创建NNPSR-LORD,进一步减少了出行距离基于NNPSR算法。主是基于阈值的算法,与迪杰斯特拉算法相比需要更少的内存空间。第一步是连续问题最近邻查询来找到遵循给定的POI的贪婪路由序列的起点。保持一个变量阈值(T),其价值降低每次迭代后,丢弃所有POIs的距离超过(T)的起点。 |
| 先进的A *搜索部分序列路线查询(AASPSR (k)算法[12]。AASPSR (k)利用旅行目的地的位置以及规则,生成一个有效的旅行计划在公路网络。这里我们使用成本之和源初始点和目的地的最初兴趣点检索点(POI)的最小成本在所有将被纳入路线列表和更新过程会重复,直到所有用户选择类别列表都包含在旅行计划。 |
| 道和Yufei等[13]讨论连续监测,当利益点或利益对象改变了由于移动用户的移动,移动用户这些更改的通知。这些被称为分裂节点。这种方法着重于有效地识别分割节点CKNN可以被定义为搜索,查询点移动,预定义的移动路径,和一组候选人的兴趣点。目标是找到点的方式,然而,改变。连续的最近邻查询检索(CNN)最近邻(NN)的每一个点在一条线段q = (s、e)。特别是,结果包含一组< R T >元组,其中R(结果)是一个P, R和T是间隔期间的NN q。 |
| 赵和耿等[14]讨论的概念基于路径k近邻(pkNN)介绍。给定一组候选人感兴趣的对象,一个查询点,和对象的数量k, pkNN找到最短路径穿过所有k兴趣对象在所有可能的路径最短的最小距离。pkNN非常有用当用户想要访问所有k兴趣对象从查询点,pkNN将给用户的最短路径。传统空间数据库中查询范围搜索[15]和k近邻(NN)(资讯搜索[16]。范围搜索是找到所有感兴趣的对象在一个预定义的范围内,而资讯搜索找到感兴趣k对象查询最接近点。范围和资讯搜索为用户提供候选人的兴趣点并允许用户选择任何一个组,因为他们已经被用户之前过滤条件 |
算法 |
| 答:算法批向前搜索: |
| InitBFS (q,《GQ》) |
| 输入:q,《GQ》:分别查询起点和访问顺序图 |
| 输出:满足查询的最佳路线 |
| 1:使用贪婪算法来获得一个路线rg |
| 2:初始化阈值长度(rg) |
| 3:检索在距离q CS的点集,其类别出现在《GQ》 |
| 4:初始化路线R1设置为空 |
| 5:初始化所有Ω未知的元素 |
| 6:点CS分割成集群,这样分在同一个集群属于同一类别,和接近对方 |
| 7:调用BFS (q,《GQ》{q}, {q},θ),并返回的结果集的唯一途径。 |
| BFS (q, G, P, R,θ) |
| 输入: |
| •问:查询起点 |
| •G:《GQ》只包含的子图指出既无类别 |
| •P:集群当前cluster-route的尾巴 |
| •R:设置每个点的最短路线q P,只有包括线路长度短于θ |
| •θ:一个已知的路线的长度满足查询 |
| 输出:所有最优路线,从一个点开始,P,在G和涵盖所有类别。 |
| 1:让V在G组类别,类别CP是所有的点P的类别,并设置V′= \ {CP}。 |
| 2:构造新的子图指出G′通过删除从G Cp和所有相关的边缘 |
| 3:如果ΩP;V ? =未知然后返回ΩP;V |
| 4:如果V包含单个类别CP然后返回一组线路,每个包含一个单点P |
| 5:计算P的最小距离其最近的集群的每个类别C∈V,并设置距离这些距离的最大值 |
| 6:如果mindist (q, MBRP) +距离≥θ然后设置ΩP;V无效,并返回无效。 |
| 7:对于每个集群P′∈CS mindist递增的顺序(MBRP, MBRP′) |
| 8:如果添加P′当前集群路由违反G然后继续 |
| 9:调用R′= FSJoin (q, G R P′,θ) |
| 10:递归地调用ΩP′;V′= BFS (q, G′P′, R′,θ) |
|
|
| 11:调用BSJoin (q, G、P′, V′P)和合并结果ΩP;V |
| 12:如果R ? =Φ |
| 13:计算路线r1∈R, r2∈ΩP;V的终点的起点是r1 r2,长度和长度(r1∈R) + (r2)最小化 |
|
|
| 14:如果长度(r1) + (r2) <然后更新θ和CS |
| 然后用地中海BFS算法扩展算法,以满足用户定义的时间约束 |
| b .时间近似: |
|
|
| 地中海((s, t, Q, C, D, ?) |
| 输入:开始位置,目标位置,搜索查询 |
| Q1,。根据C, Qm命令,数据集D,订单< / D |
|
|
| 输出:下一个对象访问 |
| 1:如果Q是空的 |
| 2:返回t |
| 3:计算预期的距离 |
| 4:咕咕叫←年代 |
| 5:因为我= 1 m |
| 6:发现←假 |
| 7:虽然没有找到 |
| 8:如果Ai =Φ |
| 9:返回“路线不能完成” |
| 10:o←argmin (o∈Ai (dist(咕咕叫,o) + E [o]) |
| 11:为用户提供o并获得反馈 |
| 12:咕咕叫←o |
| 13:如果o不满足气 |
| 14:清除o从人工智能 |
| 15:其他 |
| 16:发现←真的 |
| c .描述: |
| 为了克服现有路线查询系统的缺点,提出系统包括用户定义的约束查询。查询包含两个参数:一个起点q,和一个有向无环图《GQ》被称为访问顺序图。《GQ》中的每个顶点对应于一个类别和每条边? C;C′?显示的类别C之前必须访问另一个类别C′。方法使用贪婪算法之前回答的最优路线的最近邻查询第一个发现问这是允许访问后问据《GQ》被添加到路线。我们提出一些有效的解决方案一般情况下最优路线查询。时间的定义是“持续相对较短的时间”。大多数导航应用,如今,只是找到一个点对点的航线,不能处理复杂的搜索场景。我们引入了一个更复杂的导航方法,与有效的复杂查询路线路线搜索在异构环境中,在处理不确定性对地理实体。 |
| 在路径检索,用户指定他们的需求的形式查询,主要任务是找到一个路线,通过地理对象虽然满足了搜索规范。例如,考虑一个游客在一个陌生的城市海德拉巴说想计划从当前位置到目的地的路线,通过四种类型的实体: |
| 吗?一个加油站, |
| 吗?一个自动取款机, |
| 吗?一个素食餐馆。 |
|
|
| 虽然之前制定方法来集成这些任意限制到特定的路线搜索,他们可能不会对用户是有用的,比如路线将会通过一个餐厅,不是真正的素食者。在现实的场景中,导航服务提供者应考虑额外的复杂的因素,如工作时间的实体,这些实体类型的服务迎合和可能限制订单可能访问的实体。我们将时间等因素的限制。合并的时间限制在我们的空间场景中会导致一个新的时空方法路线查询。提出延长批向前搜索算法与时间近似算法在处理时间约束的路线查询路线查询。 |
| 提出的系统实现以下步骤: |
| 1。地方存储库设置:此阶段是积累各种位置信息对经度和纬度(坐标)(坐标)的SQL查询。 |
| 2。路线库设置:此阶段涉及到指定的各种组合内部的位置信息以及距离的范围内边界的SQL查询。 |
| 3所示。查询界面:此阶段包括一个自动选择源和目的地的所有可能的路径估计和最佳途径。 |
| 4所示。数据库数据转换:这个阶段涉及转换数据库以逗号分隔值(CSV)数据集挖掘查询实现最优路线。 |
| 5。地图实体绘图仪c路径要么直接/间接的地方:这个阶段包括策划的地方地图上一个预定义的接口以及与路径权重的形式或它们之间的距离。 |
| 6。现有的模拟图(DFS)随着时间的资源:在这个phasetime比较现有方法的实现。 |
| 7所示。批向前搜索算法实现路径索引和选定的节点:在这个阶段最好的边缘的图遍历实现更多的结果选择任意约束的选择是至关重要的。 |
| 8。查询结果随着时间的资源:时间比较提出的实现方法。 |
| 9。时空关系设置和检索:这一阶段集中于建立语义检索任意约束。,它需要自动检索相关的时态数据从第7步检索任意约束 |
伪代码 |
| 步骤1:最初阈值路径长度值 |
| 第二步:点邻近问排列成集群的类别 |
| 步骤3:创建子图G’,这样所有的边和类别不需要删除 |
| 第四步:计算P的最小距离其最近的集群的每个类别C∈V,并设置距离这些距离的最大值,如果mindist (q, P) +距离≥θ然后d (P, V)设置为无效,并返回无效 |
| 步骤5:为每个集群P′∈C mindist递增的顺序(P, P′)如果添加P′当前集群路由违反G然后返回无效。 |
| 第六步:其他计算路线r1∈R, r2∈d (P, V), r1的终点是r2的起点,和长度(r1∈R) + (r2)最小化。如果长度(r1) + (r2) <然后更新其他θ转到步骤5,重复这个过程 |
仿真结果 |
| 仿真研究涉及到确定的小路由节点集合,如图2所示。提出的节能与NETBEANS算法实现。在选择所需的数据库路径搜索系统将打开,如图2所示。基于他的欲望可以选择使用图2所示的复选框。我们可以选择源和目标点通过选择点地图所示。当选择源和目标点我们可以运行查询界面。源与绿色表示,目标是用红色表示,突出显示的路径查询系统运行时,如图2所示。 |
| 而且,输出将显示在图4中显示或解释了不同的点在地图上选择以及如何找到最优路径。图3显示了信息存在许多点的路径。如果有任何约束,比如餐馆或汽油双层应选择在选择源和目标之间的路线,然后获得其信息如图5所示。如果没有选择约束的路由选择它显示没有确定任意约束。 |
结论和未来的工作 |
| 仿真结果表明,该算法使信息用户定义的约束和有效的最优位置。我们开发了一种新颖的方法来提供搜索引擎查询满足用户定义的约束。这两种算法的结合批向前搜索算法(BFS)和时间近似算法,有效地实现了最优查询系统。用户可以定义自己的约束任意或时间。使用这种新方法,用户不仅得到最优路线但也会根据他们的要求。我们认为,该方法将解决关键问题的路线查询系统的约束。在未来需要开发一个最优路线查询系统,可以处理更多数量的类别访问应该开发。在这个,如果没有类别或地方发现出现在选定的路线显示所需的信息,如没有地方选择的路线。所以需要一个最优路线查询系统给替代之间的最佳路径由选定的路线从源到目的地的路线。 |
数据乍一看 |
|
|
引用 |
- Anjum Sacharidis d;Dalamagas t;Skiadopoulos,美国;Sellis, t . Bouros, p .“评估路径查询频繁更新路线集合”,IEEE知识和数据工程,24卷,2012年7月7号。
- p . Bouros s Skiadopoulos t . Dalamagas d . Sacharidis, tSellis”,评估可达性查询路径集合,“Proc。如您相依之科学和统计数据库管理(SSDBM), 398 - 416年,2009页。
- T.H.科尔曼、石球雷瑟尔森、R.L.莱维斯特和c·斯坦“算法导论”,麻省理工学院出版社和麦格劳-希尔图书公司,第二,2001。
- 4所示。Kefeng宣;Rahayu w;Taniar d;回历2月,m;Gavrilova,马丁;Srinivasan, b”Voronoi-Based连续k近邻搜索在移动导航”,IEEE工业电子、58卷,2011年6月6号。
- k .宣g .赵d Taniar, b . Srinivasan”连续范围搜索在移动导航查询处理,“在Proc。14日IEEE Int。Conf.Parallel Distrib。系统。,pp. 361–368, 2008.
- m .回历2月“K最近邻搜索在导航系统中,“移动Inf。系统。,1卷,不。3,第224 - 207页,2005年8月。
- h . j . Koskimaki p . Laurinen e . Haapalainen l . Tuovinen和j·罗恩,“应用程序扩展资讯的方法对电阻点焊过程识别和处理信息的好处,“IEEE反式。印第安纳州。电子。,vol. 54, no. 5, pp. 2823–2830, Oct. 2007
- 杉原冈,b .靴子,k和s . Nok赵”空间镶嵌:泰森多边形法的概念和应用图”,第二版。奇切斯特,英国:威利,2000年。
- 陈、Haiquan et al。“旅行的部分测序路线查询规则在公路网络。”Geoinformatica 15.3 (2011): 541-569.
- 卡恩AB,“大型网络的拓扑排序”,Commun ACM 5(11): 558 - 562年,1962年
- Sharifzadeh M, Kolahdouzan先生,Shahabi C“最优排序的路线查询”,VLDB、J 17(4): 765 - 787年,2008年。
- 陈,Haiquan。“近似评估查询空间,不确定性和概率数据库。”PhD diss., Auburn University, 2011.
- Dimitris Papadias Yufei道,Qiongmao沈,“连续的最近邻搜索”,28日VLDB会议,香港,中国,2002
- 耿赵,Kefeng宣,大卫Taniar路径“资讯查询处理在移动系统”,IEEE工业电子、60卷,2013年3月3号
- j . Jayaputera和d . Taniar依赖所在查询的数据检索在多单元无线环境中,“移动Inf。系统。,1卷,不。2,页。91 - 108年,2005年4月
/ td > |
菜单
