论文研究-基于动态创建局部Voronoi图的连续近邻查询.pdf

所需积分/C币:7 2019-07-22 18:14:48 185KB .PDF

在充分认识到k阶Voronoi图在解决连续k个近邻查询优越性和现实不可行性的基础上,用分支限界的思想去界定预创建Voronoi图生成点范围的上界,提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。该方法只是在给定查询段上所有点的k个近邻范围上界内创建一个局部的k阶Voronoi图,这样大大降低了基于Voronoi图的连续k近邻查询的代价。
第9期 王淼,等:基于动态创建局部 orono图的连续近邻查询 2773 {归[sb1]》;P[b1,b2]),,[b2,日》}。 阶 Varanoi图 定理2算法。 CNN-SEO()算法是可终止的并且能止确求 )求查询段与第三步生成的orna图的交点,输出查询 出给定查询段连续最近邻分点列表。吋间复杂度为O(ln+结果。 36)(为查询轨迹穿过 Varona单元的个数)。 山以上论述可得出基于动态创建局部k阶ˇrono图的 证明可终止性。本算法调用的过程NN_SEC()其可终ACNN查询算法如下: 止性在定理1已证明。佘下部分的循环操作仅有Whie…d诰 句,其结束的条件为e∈VP(T),其内嵌的双重fa循环诰句可 人,FND(m5/求由定坦3确定的[se]上所有点的k近邻泡 界点集*/ 自行结束。故该算法是可终止的 输入:R树节点类型数据冂,査询段的始点S终点已 翰出:[se上所有点k近邻所在范围的一个上界点集Q 正确性。首先执行NNSC(n,S找到杳询段始氐S的最 begin 近邻, while…do语句以找到的最近邻为循环的起点查找[s cllT← NN SEC(n,s);//查找S的最近邻 e穿过的所有 Vorono单元,每次循环查找一个沿S→e方向的 S-s №hile(eVP(T))do vα ranoi单元并将连续最近邻列表的一个元组存入旦。循环结 /继续寻找查询段穿过的下一个 orono多边形 宋后伣存着连续最近邻分点列表,所以该算法实现了查找 tfor Vorond edge(VP(T)do 交点并存储近邻信息的过程。枚该算法是止确的。 if(Varonoi edge[S,e]=o)then 时间复杂度分析。执行NN王C(n,S)过程的时间复杂度 edger[S,e]氵 for P( AG(T)do 为∝agn)级。由一阶orn图的性质4知每个 orana单 if(VP(t)nVp(P)=edge)then 元平均有6条边,嵌套的fo语句最多执行6×6=36次。最外 T←P; 层的whie…do语旬要循坏f(i为查询轨迹穿过 orona单元 QQU AG,(T)U.UAGK-1(T)iy 的个数)次。所以该算法的时间复杂度为(lqgn+36)。 Q·QAG1(T)U…UAGk1(T return Q 3基于动态创建局部k阶∨ orono图的连续k近邻 KCNN-SEC(n, s,e,k) 查询算法 输入:R树节点类型数捆η查询軌迹始点S终点e查询近邻的 个数k k阶√αrα图能有效地解决给定査询段的连续k近邻杏 输出:分其列表S 询,但构造一个全局的k阶van图代价太大。不文提出了 eaIn 种动态地创建局部k阶∨ orono图的办法解决连续k近邻查 Q=,S=;//SL为分点列表 询问题。该方法仅在给定杳询段上所有点的k个近邻范围上 calk←FIND(ns,e)//求预生成k价 Vornoi图的生成点 call VDk(K)+ge kv orona (Q, k) 内创建一个局部的k阶Ⅴ orana图,实现迕续k近邻查询 //生成局部k阶 Voronoi图(文献[6]) (kCNN)。下面给出由一阶 Orana图的性质得出的一个定 cal. KNN SEC(n,S);//查找S的k近邻 理,它为确定给定查询段上所有点的k个近邻氾围的一个上界 . si 提供了理论依据 以下部分为[s,e]基丁动态创建的局部k阶 Voronoi VDK P),求连续k近邻分点列表的过程* 定理3对」整个数据空间P={p1P2,…/Dn}的 Varanoi thile(el VPk (t))do 图M(P)和一给定查询轨迹[se,若Ⅶ(P∩[S已≠C,则 for Varonoi edg∈∨Pk(T)do [se]每一点的前k个近邻必在{AG1(P)…UAG(P)|vP if(varonoi edge[S,e]=o then (P)∩[se≠}中。 SL←,[S,egen[se] s← edge[s,e]; 证明V(P)∩[se]≠,则[se]被(P分成一线 forp∈AG(T)do 段集{L;P(P)n[se=L,}由定理1知vP(P)内任 /生成元点集T的邻接生成元点集简记为AG(T) qq的第k个近邻pAG(P)…UAG1(P)(k≥1),那么q if((VPk(t)nvP( p)=edge)then T←P;}/继续寻找下一个分点 前k个近邻都在AG(p)…∪AGk1(p)内,故L,上每点的前k sL←T[s,e] 个近邻都在AG1(p)…UAG.1(。故{L,VP(p)∩[Se]= return sL L},即S上每一点的前k个近邻必在{AG2(p)…∪AG-1 (P)VP(p)∩[se≠}中。证毕 定理4算法KCNN-SEC()算法是可终止的并且能正确 山定理3知,对于给定询轨迹[se]上所有点的k近邻地求出给定查询段连续k近邻分点列表,时间复杂度为 必在[s日穿过的所有一阶Vao多边形生成点的前k-1阶O(2n+36+36+de+e)级(n为全局数据点的数 邻接生成点中。本算法的某本思想是:出定理3确定∫给定查目、j分别为查询轨迹[S穿过一阶、k阶 Norma单元的 询段上所有点k个近邻所在范围的一个上界集合。那么以这数月,e为局部k阶voon图牛成点的数目)。 个上界集合为牛成点生成一个局部的k阶 Voronoi图是足以能 证明可终止性。本算法调用的子过程FIND()与CNN 够通过求查询段与该k阶Vod图的交点,正确地得到连续SC()语句结构一样,QNC()可终止,放FND()也可终 k近邻查询分点列表。因为查洵轨迹上每一点k近邻都在止。余下的部分循坏操作仅有We…d语们,其结束的条件 该局部的k阶Wao图的生成点之中。 为ePk(T),其内嵌的双重for循环语句,可白行结束。故该算 整个查询过程步骤如下 法是可终止的。 a)求出由定理3确定的给定查询轨迹上所有点的k近邻 正确性。FIND()过程首先执行NN王C(nS)找到查询 范围中限点集。 轨迹的始点的最近邻,并将最近邻的前k-1阶邻接生成点存 b)以第二步査找到的点集合为生成点,生成一个局部的 kA Q; while…Φo诰句以査找到的最近邻为循环的起点实现了 2774 计算机应用研究 第25卷 查找[$e穿过的所有 Varanoi单元,每次循环查找到一个沿查询得出移动点的连续最近邻,它解决问题的思想筲单明晰 S→e方向上Ⅴαrono单元并将它的生成点的前k-1阶邻接生但由于时空数据库巾数掃庞大,要对仝局数据构造一个高阶 成点存人Q。执行FIND()实现了第一步的要求:求出由定理 arnol图厶实现连续k个近邻査询,代价太人没有实现可行 7确定的给定査询段所有点k近邻范围上界点集。执行g性。本文提出了一种动态地创建局部∨ arnol图的办法。该方 Aaron(Qk生成了以上限点集合为生成点的局韶k阶法不是以整个数据空间而是以某些特定的点为生成元创建 Varanoi图。 while…do语句,它以起点s所在的k阶νoronσ单^足以实现绐定徳询段迕续k近邻耷洵的局部Ⅴαonoi图。该 元为循环的起点査找[s母穿过的所有k阶 Voronoi单元,每次方法大大降低了查询的时间复杂度。本文的主要贡献就是提 循环查找一个沿S→~e方向的k阶 Vorona单元并将迕续近邻岀∫基于创建局部 Vorono图解决迕续近邻查询的思想。那 分点列表的一个元组存入皇。循环结束后S保存着分点列寻找新的1更行之有效的限界方法将预生成roo图生成点 表,所以该算法实现了查找[Se与局部k阶 arno图交点并的范围上限界定在尽可能小的范围内将是木课题未来研究的 存储连续k近邻分点列表的过程。故该算法是正确的 重点。 时间复杂度分析。对有刀个点的数据空间执行NEC参考文献: ()过程的时间复杂度为O(|am)级;调用的子过程FIND()与 [1] ONG Z, ROUSSOPOULOS N. k-NN search for moving query point CNN SEC()语句结构一样,故它们时间复杂度均为O(lan+ [C//Proc of the 7th SSTD Symposium. Redondo Beac, CA: Sprin- 36)级;荇执行FIND()得到点的数日为e那么执行ge ga,2001:79-96 hanoi(Q)过程的时间复杂度为O(elge+e)级。对 [2 TAO Yu-fei, PAPA DIAS D. Time-parameterzied queries in spatio-temr 余下的部分,由性质5推论知每个k阶 Varonoi单元平均 oral databases[ C]//Proc of SIGMOD Conference 2002: 334-345 最多有6条边,所以嵌套的fα语句最多循环36k次。最外 层的 while…d语句要循坏jj为[Se穿过k阶Ⅴaoni单元 [3 BESPAMYATNIKH S, SNOEYINK J. Queries with segments in Voro 的数目)次。所以该部分至多循环36次。故该算法的时间 noi diagrams[ J]. SoDA, 1999: 122-129. 复杂度为(2gn+35+36+elge+a()级(n为全局数[41pr. n k-nearest neighbor Vaona diagrams in the planel 据点的数日,、j分别为[S穿过一阶1k阶∨ arenal单元的 IEEE Trans on Computers, 1998, 31: 478-487 数日,e为局部k阶arno图生成点的数目) [5 KOLAHDOUZAN M, SHAHABI C. Voronoi-based k-nearest nei ghbor 本算法利用一阶∨ aono图中各级邻接生成点和近邻的关 search for spatial network databases[c]//Proc of VLDB. Toronto, 系,确定了给定査询轨迹上所有点的k近邻所在的范围的一个 Canada: S.n., 2004. 上界。基」这个上界内的点构造一个局部的k阶 Voronoi图而[6] MEYERHENK H. Canstructing higher-order Vornoi diagrams in p 不是仝局的Ⅴ aono冬,故基于∨oron图的连续k近邻査洵算 rallel[ c] //Proc of EWCG. [S1.]: Eindhoven, 2005: 56-60. 法的时间复杂度降低 [7] GUTTMAN A. R-trees: a dynamic index structure for spatial sear- ching[ C]//Proc of ACM SIGMOD Conf Ann Meeting. 1984: 47-57. 4结束语 8 TAO Y u-fei, PAPADIAs D, SHEN Qiong-mao. Continuous nearest k阶 aono图在解决连续k近令査询间题中有其优越 neighbor search[ c]//Proc of the 28th VLDB Conference 2002: 287- 性。基于k阶αonoi图的连续近邻查询可以有效地通过一次 (上接第2750页)大大增强,能够通过构件插拔迅速地适应快[2]段作义,吴威,赵沁平·基于构件的分布式虚拟现实应用系统 速变化的业务需求,维护成显著降低。 [].软件学报,2006,17(3):546-558 [3] BROWN A W, SHORT K. On components and objects the founda 4结束语 tians of component based devel opment c]//Proc of the 5th Interna- tinal Symposium on assessment of Software Tools. Washington DC 木文依据农业部有关规泥,开了面向构件的测十:配方施 IEEE Camputer Society Press, 1997: 112-121 肥辅助决策技术体系的研究,为快遽搭建淸矬不同需求的测上 [4 COX P T, SONG 配方施肥辅助决策系统提供了技术支撑。作为在此技术体系 a formal mode for component - base ftware[ c]//Prmc of IEEE 2001 Symposium on Visual Multimedia 下开发构件化应用系统的一个例子,顺义区测土配方施肥辅助 Approaches to Programming and Software Engineering. Washington 决策系统展现了构件化技术的优势,即开发周期短、系统稳定 DC: IEEE Computer Society Press, 2001: 342-350 向件技术作为一种先进的软件果物技术,是设可在全国花(5明个+机,于的经5⑤肉 围推广的开放式测土配方施肥辅助决策系统的必然选择;下 [6]马亮,孙艳春.软件构件概念的变迁[].计算机科学,2002,29 步将在测土配方施肥辅助决策的业务需求分析、业务单元划 分、业务构件接口定义、行业数据规范化等方面开展更加深入[刀杨芙清软件工程技术发展思索[].软件学报,20051(1-7) 的研究 21-26 参考文献 [8] LARUFA JM, RAUN WR, PHILLIPS B, Et al. Opti mum fied ele- [1]农业部农业技术推广中心,测土配方施肥专家咨询系统编制规 ment size for maxmum yields in winter wheat using variabl e nitmgen 范(试行)[S].北京:中国农业出版社,;200 rates[ J] Journal of P lant Nutrient, 2001, 24(2): 313-325.

...展开详情
试读 4P 论文研究-基于动态创建局部Voronoi图的连续近邻查询.pdf
img

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于动态创建局部Voronoi图的连续近邻查询.pdf 7积分/C币 立即下载
    1/4
    论文研究-基于动态创建局部Voronoi图的连续近邻查询.pdf第1页
    论文研究-基于动态创建局部Voronoi图的连续近邻查询.pdf第2页

    试读已结束,剩余2页未读...

    7积分/C币 立即下载 >