2. 麻省理工学院 计算机科学与人工智能实验室, 马萨诸塞州 剑桥 02139
2. CSAIL, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
海量轨迹数据包含了丰富的时空特征信息,记录了人、物或事件的移动轨迹信息,体现了各类移动对象的位置变化,正在深刻地影响着人们的日常生活,在城市规划、智能交通等领域发挥了极大的作用[1-2].时空查询技术作为位置信息服务的重要技术支撑之一,已经在实际应用中发挥了重要作用,典型的k近邻查询[3]是时空数据领域广泛应用的查询类型之一,一直是学术界与工业界共同关注的研究热点[4].
面向移动对象的k近邻查询算法旨在查找距离给定位置或对象最近的k个移动对象.连续k近邻查询是将k近邻算法应用到动态实时环境下,对移动对象进行连续查询以实现实时动态更新.笔者等[5]面向不确定移动对象,提出针对不确定移动对象的连续k近邻查询处理方法,利用最近一段时间的位置数据预测移动对象在未来Ⅰ时间区间内的可能区域,采用距离区间表示查询对象与可能区域的距离,利用基于模糊可能度判定的排序方法查找k近邻.在面向海量用户查询的实际应用系统中,需要应对高并发量的查询请求需求,串行算法所带来的延迟往往是不能忍受的.另外,针对当前常用计算平台的性能配置,传统单线程查询方案难以充分利用多核处理器的计算优势.基于多核多线程的不确定移动对象连续k近邻查询处理是当前解决这一问题的主要方法.
在实际环境下常常存在一部分邻近的用户同时查询附近的移动对象,这使得查询对象在地理位置上具有较大的空间相关性.将相距较近的查询对象分到相同组别,组内其他用户的查询请求结果往往与邻近用户的结果一致.利用空间相关性对邻近查询对象的结果进行有效复用,可以提升大规模并发查询请求时的处理效率.
在确定数据下的k近邻查询方面,已有较多的研究工作[6-15].目前,针对确定数据的并行k近邻查询算法已经有所发展[13-15].赵亮等[14-15]结合多核多线程技术,提出在道路网下的移动对象连续k近邻查询算法,使用任务并行和数据并行的方法优化连续查询过程,该算法实现了1.51~1.7的加速比.上述算法都是针对确定的移动对象数据,查询的是当前时刻下的k近邻,针对未来一小段时间内的预测问题,没有相应的解决方案.
在不确定数据下的k近邻查询方面,Huang等[16]考虑不确定速度的移动对象连续k近邻查询问题,提出有效代价的P2KNN (probability-based possible-KNN)算法,在给定的查询时间区间内找出每个时刻上的k近邻对象. Fan等[21]提出基于道路网的模糊连续k近邻查询算法,处理速度不确定的移动对象查询问题;该方法考虑了移动对象的运动状态,利用基于路网的距离区间模型计算移动对象与查询对象间的最大和最小距离,采用vague模糊集计算k近邻.在传统的单线程环境下,对于大量位置邻近的查询请求都进行k近邻的计算,会造成重复查询,导致响应延迟问题.
本文针对不确定移动对象,提出高效的基于多核多线程的连续k近邻并行查询处理方法.本文的主要贡献如下:1)提出面向不确定移动对象的k近邻查询复用方法,根据临近查询对象之间的运动速度与相对位置确定是否采用查询复用,并确定两查询对象采用复用时的距离边界. 2)提出基于密度网格扩展的多线程负载均衡数据分发方法,利用网格密度对查询请求进行划分, 解决多线程并行条件下的负载均衡问题;将空间位置相邻的查询请求尽量划分到同一线程,提高查询复用率. 3)实现了多线程间的内存共享机制,对计算过移动对象的预测区域通过建立内存共享区来避免重复计算,以实现计算复用. 4)采用Oldenburg城市上模拟的大规模交通数据集,设计综合实验评估,验证了所提算法的有效性与查询性能.
1 问题定义给出一些重要的定义和表示,对不确定数据的连续k近邻并行查询问题进行描述.
定义1(移动对象) 一个移动对象由唯一的标识符表示,记为oi.oi的移动轨迹数据是一个多维时空位置点序列,每个位置点为五元组(t, x, y, vx, vy)表示,其中t为采样时间,x、y分别为oi在t时刻的位置坐标,vx、vy分别为oi在该位置时x和y方向上的速度分量.
对于采样频率不固定的移动对象oi,轨迹数据可以表示为轨迹序列si= {(t1, x1, y1, vx1, vy1), (tj, xj, yj, vxj, vyj), …(tk, xk, yk, vxk, vyk)}.其中,si, j为移动目标oi在时刻tj时的位置,相应地,用si, (j, k)表示oi从时刻tj到时刻tk区间上所采集的轨迹序列.包含n个移动对象的集合表示为DBo= {o1, o2, …, on},不确定轨迹数据集表示为S={s1, s2, …, sn}.
采用基于时间的滑动窗口W来处理移动对象实时的位置数据,窗口长度标记为w,将最小的时间刻度单位定义为一个时间点,则W包含的时间点数|W| = w.
针对基于时间的滑动窗口W的不确定k近邻查询Query(q, I),于彦伟等[5]提出基于速度变化率的k近邻预测查询方法Rate,给定一个查询点q,通过预测周围移动对象在I时间区间内可能到达的区域,然后结合vague模糊集对q在下一时刻的k近邻进行排序.如图 1所示,si为移动对象oi的轨迹数据,包含4个位置点.当q查询预测t=18(当前时间tc=17,I=1)时的k近邻时,首先根据下式预测oi在t=18时可能到达的区域si, 18.
$ \left. \begin{array}{l} {s_{i, {\rm{ }}{t_{\rm{c}}} + I}} = {s_{i, {t_j}}} + {v_{i, j}}(I + {t_{\rm{c}}} - {t_j}) + \frac{1}{2}a{(I + {t_{\rm{c}}} - {t_j})^2}, \\ {a_{i, j}} = \frac{{\Delta v}}{{\Delta t}} = {\rm{ }}{v_{i, j + 1}} - {v_{i, j}}{t_{j + 1}} - {t_j}. \end{array} \right\} $ | (1) |
![]() |
图 1 基于速度变化率的预测 Fig. 1 Position predicting based onrate |
当采用与当前时间临近的多个以往时间点上的速率变化时,可得一块可能到达的区域,如图 1的阴影部分所示. Rate方法既考虑了最近一个时刻的位置与速度的权重,又考虑了最近一段时间速度与采样时刻的变化情况.采用多速率变化的Rate方法获取的可能到达区域有效刻画了不确定移动对象在tc+I区间内可能存在的位置.
使用最近距离与最远距离的区间[d, D]为查询对象到移动对象间的距离.对于查询对象q到两个移动对象o1、o2的距离区间,分别设为[d1, D1]和[d2, D2].若要获得q的k近邻,则需要比较q到不同移动对象的距离区间,Rate采用vague模糊集方法,利用模糊可能度判定的方法排序k近邻.如性质1所述,若q到o1距离相比q到o2的距离更近的概率p(o1<o2)大于等于0.5,则满足D2-d1≥ D1-d2.通过验证D2-d1≥ D1-d2是否成立,可以判断查询对象q到o1是否更近于o2.若o1与除o1之外的移动对象oi都计算一遍p(o1<oi),则可以确定o1是查询对象q的第几近邻.对所有移动对象检查一遍,可以获取到查询对象q的k近邻.与Huang等[16]提出的P2KNN方法相比,Rate方法的查询正确率平均提高18%,效率平均提升66%.
性质1 p(o1<o2) ≥ 0.5当且仅当D2-d1≥ D1-d2.
问题定义(不确定移动对象k近邻多线程查询Multi-Query(Q, I)).给定移动对象集合DBo、不确定轨迹数据序列S、时间窗口W、当前查询时刻tc、查询请求集合Q、近邻数量k和线程数M,Multi-Query(Q, I)查询从M个线程并行返回Q中所有查询对象q在接下来时间I内最可能的k个最近邻移动对象.
涉及到的符号及相应含义如表 1所示.
![]() |
表 1 涉及的重要符号名称及解释 Table 1 Symbolsand descriptors |
针对不确定移动对象,给出基于多核多线程的连续k近邻并行查询Multi-Query(Q, I)算法的框架,如算法1所示.
算法1 Multi-Query(Q, I)
Inputs:DBo, S, W, Q, k, M;
Outputs:k-NNs for each query object in Q;
01:Qi=1, ..., M gridPartition(Q, M);
02:FOR i← 1 to M PAR-DO
03:QueryThread(Qi, I).
采用基于密度网格扩展的多线程数据分发方法,将查询请求根据地理空间划分成数量大致相等的M份;M个线程并行执行使用数据复用优化的k近邻查询算法来获取查询对象的前k近邻. 2.2与2.3节将分别介绍查询复用优化和基于密度网格扩展的数据分发方法.
2.2 邻近查询对象间的查询复用考虑到用户在进行k近邻查询时当前位置是已知的并且查询的是在未来很小一段时间I内的大致位置,使用匀速运动方式对查询对象在I时间区间的位置进行预测.
对于同一时刻发起请求的多个查询对象,若相距较近,则考虑是否可以复用已查询到的结果来减少冗余的k近邻查询过程.如图 2所示,设定已对qi查询完毕,并返回qi的k近邻集合Oki.当qj进行查询时,为了能够复用qi的查询结果,需要考虑qj与qi之间的距离d(qi, qj)可以直接复用qi的查询结果时的条件.若使得qj的k近邻刚好为qi的k近邻,如图 2的虚线圆圈,即qj的第k近邻刚好覆盖到oki,不超出ok+1i,则需要满足2Rqj+d(qi, ok+1i) -d (qi, oki)=2d (qi, ok+1i).Rqj=d(qi, qj) +d(qi, oki),可以得出d(qi, qj)=[d(qi, ok+1i)-d (qi, oki)]/2.为了使得qj的k近邻刚好包含oki, 而不包括ok+1i,所以d(qi, qj)应该满足[0, (d (qi, ok+1i)-d (qi, oki))/2), 才能直接复用qi的计算结果.
![]() |
图 2 查询点间查询复用示例 Fig. 2 Query reuse between two query points |
针对移动对象的k近邻查询预测问题,在复用查询结果时需要考虑查询对象之间的速度方向关系.比如两个查询对象相背而行,则在未来I时刻内对查询结果进行复用,将会导致查询准确率降低.利用两查询对象的余弦相似度来判定是否采用查询复用.如图 3所示,设定当前qi已经查询完毕,继续对qj进行查询,根据式(2)的余弦相似度,利用两查询对象的速度向量 v i与 v j计算相似度sim(qi, qj).在实际情况下,同向运动的查询对象之间的距离较近较小,相似度越高,因此考虑速度方向夹角α∈[0, π/6]时对查询点进行查询复用,即当余弦相似度区间满足[
![]() |
图 3 查询点之间的速度关系 Fig. 3 Velocity relations between query points |
$ {\rm{sim}}({q_i}, {q_j}) = {\rm{cos}}\alpha = \frac{{\mathit{\boldsymbol{v}}{_i}\cdot{\rm{ }}\mathit{\boldsymbol{v}}{_j}}}{{\left| {{\rm{ }}\mathit{\boldsymbol{v}}{_i}} \right||\mathit{\boldsymbol{v}}{_j}|}}. $ | (2) |
算法2 QueryThread(Q, I)
Inputs:DBo, S, W, Q, k;
Outputs:k-NNs for each query object in Q;
01:FOR qi∈Q DO
02:IF QRs=
03:Cani←PR-Tree(S, MAX_HITS, qi);
04:ELSE
05:index ← reuseQuery(qi, QRs);
06:IF index ≥ 0 THEN
07:QRi ← QRs.get(index);
08:QRi.isReuse ← TRUE; Goto line 12;
09:ELSE
10:Cani←PR-Tree(S, MAX_HITS, qi);
11:QRi←Query(qi, Cani, I);
12:QRs←QRs ∪ QRi;
13:RETURN QRs;
reuseQuery(qi, QRs)
14:FOR QRj in QRs DO
15:IF!QRj. isReuse THEN
16:IF sim(qi, qj)∈[
d (qi, qj) < (d(qj, ok+1) -d(qj, ok))/2
17:THEN RETURN j;
18:RETURN -1;
Query(qi, Cani, I)
19:mutex ← 1;
20:FOR oj∈ Cani DO
21:sj ←get(S, oj);
22:IFsj, tc+I
23:P(mutex);
24:compute sj, tc+I;
25:MStc+I ←MStc+I ∪ {sj, tc+I};
26:V(mutex);
27:QRi←queryKNN(qi, S{Can}i, tc+I);
28:RETURN QRi;
算法2描述多线程下考虑查询复用时的k近邻查询算法.若当前查询为第一个查询对象qi(i=1),则采用PRTree索引获取在当前时刻tc下qi周围MAX_HITS个移动对象集合Cani作为qi的k近邻的候选项集合. 04~09行描述的是对查询点qi检查是否可以采用查询复用的过程.使用reuseQuery()函数从已查询过的查询点中检查是否满足复用条件,即速度相似度与距离是否在复用范围以内;如果满足条件,则返回复用结果,否则,回退到最原始的计算方法,即对查询点的临近对象使用PR-Tree进行过滤(第10行).为了避免查询复用的漂移,每次查询复用只针对真实计算过的k近邻查询,不会对复用结果再次复用,因此使用QR.isReuse进行区分,如第15行所示.第11行表示采用不确定k近邻查询方法Rate返回qi的前k近邻.为了共享已经计算的移动对象区域预测结果,建立内存共享区MStc+I用于暂存已经计算过的sj, tc+I的信息,如第20~27行所示.对于qi的每个候选邻近对象oj,首先在共享内存区MStc+I中查找在tc+I时刻的预测区域sj, tc+I,若不存在,则计算出oj在tc+I时刻的预测区域sj, tc+I.第27行描述的是针对qi对已经计算出的候选区域集合S{Cani}, tc+I查找qi的前k近邻.有关MStc+I共享内存区的计算复用详细实现方法见2.3节的计算复用.考虑到多线程操作,因此采用加锁操作,避免重复计算(第23、26行).
2.3 负载均衡的多线程k近邻查询针对多线程并行k近邻查询,对移动对象计算过的预测区域进行共享是需要考虑的关键问题.为了使得更多相邻查询对象复用查询的计算结果,需要对查询对象集合Q在地理空间上进行划分.引入计算复用与密度网格扩展划分的概念来解决以上两个关键问题.
计算复用.在同一线程内,只有当两查询对象满足复用距离时才能直接复用查询结果.针对不确定移动对象的k近邻查询,对查询对象周围的移动对象可能到达区域的计算占据较大的时间开销.对于互相之间距离较近的查询对象,查询范围通常存在较大的重叠区域,因此,在满足复用条件的前提下,可以直接共享已完成的移动对象可能到达区域的计算结果.在多线程并行计算时,不同线程上的查询对象的查询所涉及到的相关移动对象集合往往存在重叠区域.为了使得不同线程上查询对象能够共享已完成的移动对象可能到达区域的计算结果,实现多线程内存共享将有效加大查询过程中的计算复用.为了避免重复计算,通过建立计算结果内存共享区MSfuture来暂存已计算的移动对象集合在未来时间future = tc+I时刻可能到达的区域,以实现计算复用.
密度网格扩展划分.在实际应用中,大部分查询对象的分布是不均匀,例如在城市中,人口密集区域、商场商业区以及交通站点等位置查询请求往往过于密集,住宅区、公园、工厂等区域查询比较稀少.在多线程数据分发时,采用随机方式虽然能够保证负载均衡,但会导致查询对象间的数据复用率降低.网格划分是目前为止公认较高效的空间划分方法.为了提升算法整体效率,即尽量增加查询复用率,又保证负载均衡,本文结合查询对象在位置上的相关性,提出基于密度网格扩展的数据分发策略.
为了方便描述,定义查询对象集合Q = {qi | i = 1, 2, …, n },划分集合为QM = {Qi | i = 1, 2, …, M },|
算法3. gridPartition(Q, M)
Inputs:Q, M;
Outputs:QM = {Qi | i = 1, 2, …, M};
01:G← mapping(Q); /*Mapping Q into Grid*/
02:Lgrid←density(G);
03:WHILE |Lgrid|≠0 DO
04:g←Lgrid.getfirst();
05:Qi←expendCell(g); i++;
06:IF i = M THEN break;
07:Q←fetchQi(Q, Lgrid);
08:Q←balanceMParts(Q);
09:RETURN Q;
balanceMParts(Q)
10:FOR i ← M to 1 DO
11:IF |Qi| < 0.8
12:Qj=max{|Qj| | j=1, 2, …, M};
13:move q from Qj to Qi;
算法3描述了基于密度网扩展的数据分发策略.首先将所有查询对象映射到网格,得到按照网格密度降序排列的列表Lgrid,如01、02行所示.然后循环从Lgrid取出第一个网格,对该网格进行扩展,直到获取M个划分(如03~06行所示).扩展过程按照所述的2点扩展原则进行扩展,每次扩展后网格从Lgrid中删除.之后,将剩余Lgrid分配到较少的划分中(第07行).最后,根据M个划分的查询数量,使用平衡原则对Q的M个划分进行平衡操作,如balanceMParts(Q)函数.
如图 4所示,假设当前线程数M=4,|Q|=40,此时每个线程应当大致分得
![]() |
图 4 基于密度网格的划分示例 Fig. 4 Grid-based partition |
实验平台采用Intel Xeon E5-2660处理器,8核,48 GB内存,Windows Server 2012操作系统,所有算法全部由Java实现.
实验数据.数据集Oldenburg由Thomas Brinkhoff实现的基于网络的移动对象生成器,该生成器可以生成德国奥尔登堡城市的交通数据[23].使用的数据包含5 000个移动对象、905 000个位置采样点;根据生成器的参数设置,生成的移动对象的速度类型包含6类(类似于行人、自行车、机动车等不同的速度).为了模拟不确定数据,将该数据集分为3个版本,分别为全部数据Full、随机删除10%采样点的数据集Full-10%以及随机删除20%采样点的数据Full-20%.
评估方法.采用准确率评估方法,Precision=(R∩D)/R,其中D为查询时刻从完整数据中查询的真实k近邻结果,R为所提算法在删除数据之后获得的k近邻预测结果.对于效率评估,通过变化各重要参数,测量单次查询所执行的CPU时间来评估算法的性能.
对比方法.对提出优化方法的组合策略及Rate方法进行综合对比分析.组合方案如下:不考虑数据复用、随机分发查询请求、无共享内存的多线程查询方法(basic random no-shared memory, BRN);不考虑数据复用、随机分发查询、共享内存的多线程查询方法(basic random shared memory, BRS);考虑数据复用、随机分发查询、共享内存的多线程查询方法(optimized random shared memory, ORS); 考虑数据复用、密度网格分发查询、共享内存的多线程查询处理方法(optimized grid shared memory, OGS).所有方法的实现都采用PR-Tree索引[24].
3.2 实验和结果正确性评估.首先,在Oldenburg三组数据集上验证了所提方法的正确率,并与串行算法Rate进行对比分析.参数设置如下:W=10,查询对象数量Q=1 500,I=1,查询时间间隔Δt=2,k=40.如图 5所示为Rate与OGS方法分别在2、4、6、8个线程上并行查询的正确率P.图中, Full为所有样本,Full-10%表示在原有数据的基础上删除了10%,Full-20%表示在原有数据的基础上删除了20%.可以看出,在3个数据集上,OGS方法在多个线程上的并发查询结果几乎都与Rate方法的查询结果完全一致,验证了OGS方法的有效性.随着删除数据的增多,不确定移动对象的数量增加,导致所有算法的正确率都下降,但在Full-20%数据集上仍能达到近80%的正确率.
![]() |
图 5 不同数据集上的正确率对比 Fig. 5 Precision comparison on different datasets |
性能评估.下面在Full-20%数据集上评估重要参数对所提算法查询效率的影响.在没有明确指定参数变化下的默认参数设置如下:W=10,查询请求数量Q=500,I=1,查询时间间隔Δt=2,k=40,线程数M=8.
首先,通过变化M评估并行线程数量对4种组合算法性能的影响.如图 6(a)所示,采用数据复用与密度网格分发的OGS方法所消耗的时间最少,采用数据复用与随机分发的ORS次之,BRN使用最多的CPU时间.随着M的增加,单次查询的平均时间不断降低,但是当M≥10以后,所有算法趋于平稳.这是由于该实验平台CPU为八核,当线程数超过该数量后,不能进一步提升并行度;当线程过多时,单核上线程之间的切换将带来一定的开销.当M=10时,OGS方法相对于串行Rate的加速比已达16.59.通过对比OGS、ORS与BRS、BRN方法可以发现,采用查询复用方法对算法效率有很大的提升.通过对比OGS与ORS方法可以发现,利用密度网格分发策略进一步提升了数据复用率.
![]() |
图 6 OGS、ORS、BRS、BRN、Rate算法的效率对比 Fig. 6 Efficiency comparison on OGS, ORS, BRS, BRN, Rate |
图 6(b)描述了Q对算法性能的影响.随着Q的不断增加,虽然算法消耗的总时间是上升的,但是单次查询的平均时间呈下降趋势.这是因为Q越多,相近的查询请求越多,数据复用率越高.同样,OGS方法使用了最少的CPU时间,当Q=2 500时,OGS方法的效率相比于BRN提高了5.27倍.这证明了所提的OGS方法相对于Q具有较高的可扩展性.
图 6(c)描述了参数k对算法效率的影响,当k增大时,单次查询的平均消耗时间都上升,这是因为当增大k时,PRTree索引需要搜索的临近移动对象数量相应增加,需要计算的可能到达的区域与排序邻居数量增加,导致平均消耗时间增加.从总体上来看,OGS消耗最少的时间,并且增长缓慢.与BRN、BRS和ORS相比,OGS分别平均提升了536%、481%和200%的效率.这验证了OGS相对参数k具有较好的可扩展性.
为了进一步考查OGS算法的扩展性能,分别通过变化M、k、Q对算法进行评估.首先,评估了M对不同查询请求数量下OGS算法性能的影响.如图 7(a)所示,当增大M时,OGS算法处理每次查询请求所消耗的时间不断降低,当线程数达到10之后算法性能趋于平稳,这是由硬件平台的限制导致的.当Q增多时,单次查询请求的平均消耗时间降低.与Rate算法相比,当M=8,Q=2 500时,并行后的加速比最高可达28.27.
![]() |
图 7 线程数量M与参数k对OGS算法的影响 Fig. 7 Efficiency of OGS w.r.t M and k |
图 7(b)给出参数k对各线程数下OGS算法效率的影响.可以发现:相对于参数k,OGS算法在多线程环境下展现了更好的扩展性.随着k的增大,单次查询的平均响应时间都上升,但线程数越多,上升越缓慢.这说明所提的复用策略在多线程下有效提升了算法效率.当M=8时,与Rate算法相比,效率平均提升了37倍.
4 结语本文提出多核多线程环境下面向不确定移动对象的连续k近邻并行查询算法.针对不确定移动对象已计算的可能到达区域,设置内存共享区用于不同线程之间的计算复用.针对空间位置邻近的查询请求,设计查询复用的方法,确定了复用条件.利用密度网格扩展的方法,实现了负载均衡的多线程数据分发.实验结果表明,提出的多线程方法与串行算法相比,加速比达到16.5以上.下一步将考虑引入路网和城市兴趣点,进一步研究有效的不确定移动对象连续k近邻并行查询策略.
[1] |
ZHENG Y, CAPRA L, WOLFSON O, et al. Urban computing:concepts, methodologies, and applications[J]. ACM Transactions on Intelligent Systems and Technology, 2014, 5(3): 38. |
[2] |
周傲英, 杨彬, 金澈清, 等. 基于位置的服务:架构与进展[J]. 计算机学报, 2011, 34(7): 1155-1171. ZHOU Ao-ying, YANG Bin, JIN Che-qing, et al. Location-based services:architecture and progress[J]. Chinese Journal of Computers, 2011, 34(7): 1155-1171. |
[3] |
TAO Y, PAPADIAS D, SHEN Q. Continuous nearest neighbor search[C]//International Conference on Very Large Data Bases. Hong Kong:VLDB Endowment, 2002:287-298. http://dl.acm.org/citation.cfm?id=1287369.1287395
|
[4] |
ZHENG Yu. Trajectorydata mining:an overview[J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3): 1-41. |
[5] |
于彦伟, 齐建鹏, 宋鹏, 等. 面向不确定移动对象的连续K近邻查询算法[J]. 模式识别与人工智能, 2016, 29(11): 1048-1056. YU Yan-wei, QI Jian-peng, SONG Peng, et al. Continuous K-nearest neighbor queries for uncertain moving objects[J]. Pattern Recognition and Artificial Intelligence, 2016, 29(11): 1048-1056. |
[6] |
KOLAHDOUZAN M R, SHAHABI C. Alternativesolutions for continuous K nearest neighbor queries in spatial network databases[J]. Geoinformatica, 2005, 9(4): 321-341. DOI:10.1007/s10707-005-4575-8 |
[7] |
YU X, PU K Q, KOUDAS N. Monitoring k-nearest neighbor queries over moving objects[C]//IEEE International Conference on Data Engineering (ICDE). Tokyo, Japan:IEEE, 2005:631-642. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=1410180
|
[8] |
XIONG X, MOKBEL M F, AREF W G. SEA-CNN:scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases[C]//IEEE International Conference on Data Engineering (ICDE). Tokyo:IEEE, 2005:643-654. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1410181
|
[9] |
郝兴, 王凌, 孟小峰. 一种道路网络中移动对象的k近邻多查询处理算法[C]//中国数据库学术会议. 海口: 中国计算机学会, 2007: 113-118. HAO Xing, WANG Ling, MENG Xiao-feng. Multiple KNN queries processing for moving objects in road networks[C]//National Database Conference. Haikou:CCF, 2007:113-118. http://www.cqvip.com/QK/94913X/2007z3/1001097190.html |
[10] |
孙圣力, 林硕. 一个高效的连续k近邻查询改进算法[J]. 计算机研究与发展, 2013(增1): 80-89. |
[11] |
MOURATIDIS K, YIU M L, PAPADIAS D, et al. Continuousnearest neighbor monitoring in road networks[C]//Proceedings of the 32nd Very Large Data Bases Conference (VLDB). Seoul:VLDB, 2006:43-54. http://dl.acm.org/citation.cfm?id=1164133
|
[12] |
HUANG Y K, CHEN Z W, LEE C. Continuous K-nearest neighbor query over moving objects in road networks[C]//Advances in Data and Web Management, Joint International Conferences. Suzhou:[s.n.], 2009:27-38. http://dl.acm.org/citation.cfm?id=1532366.1532373
|
[13] |
廖巍, 吴晓平, 严承华, 等. 多用户连续k近邻查询多线程处理技术研究[J]. 计算机应用, 2009, 29(7): 1861-1864. LIAO Wei, WU Xiao-ping, YAN Cheng-hua, et al. Research on multi-threading processing of concurrent multiple continuous k-nearest neighbor queries[J]. Journal of Computer Applications, 2009, 29(7): 1861-1864. |
[14] |
赵亮, 陈荦, 景宁, 等. 道路网中的移动对象连续K近邻查询[J]. 计算机学报, 2010, 33(8): 1396-1404. ZHAO Liang, CHEN Luo, JING Ning, et al. Continuous K nearest neighbor queries of moving objects in road networks[J]. Chinese Journal of Computers, 2010, 33(8): 1396-1404. |
[15] |
赵亮, 景宁, 陈荦, 等. 面向多核多线程的移动对象连续K近邻查询[J]. 软件学报, 2011, 22(8): 1805-1815. ZHAO Liang, JING Ning, CHEN Luo, et al. Continuous K nearest neighbor queries over moving objects based on multi-core and multi-threading[J]. Journal of Software, 2011, 22(8): 1805-1815. |
[16] |
HUANG Y K, CHEN C C, LEE C. Continuous K-nearest neighbor query for moving objects with uncertain velocity[J]. Geoinformatica, 2009, 13(1): 1-25. DOI:10.1007/s10707-007-0041-0 |
[17] |
王艳秋, 徐传飞, 于戈, 等. 一种面向不确定对象的可见k近邻查询算法[J]. 计算机学报, 2010, 33(10): 1943-1952. WANG Yan-qiu, XU Chuan-fei, YU Ge, et al. Visible k nearest neighbor queries over uncertain data[J]. Chinese Journal of Computers, 2010, 33(10): 1943-1952. |
[18] |
陈子军, 任彩平, 刘文远. 路网中查询点速度不确定的连续k近邻查询方法[J]. 小型微型计算机系统, 2011, 32(3): 430-434. CHEN Zi-jun, REN Cai-ping, LIU Wen-yuan. Continuous K-nearest neighbor query for query points with uncertain velocity[J]. Journal of Chinese Computer Systems, 2011, 32(3): 430-434. |
[19] |
王宝文, 胡云, 陈子军, 等. 路网中速度不确定移动对象的k近邻查询[J]. 小型微型计算机系统, 2012, 33(8): 1756-1760. WANG Bao-wen, HU Yun, CHEN Zi-jun, et al. k-nearest neighbor query for moving objects with uncertain velocity in road network[J]. Journal of Chinese Computer Systems, 2012, 33(8): 1756-1760. |
[20] |
LI G, LI Y, SHU L C, et al. CkNNquery processing over moving objects with uncertain speeds in road networks[C]//Proceedings of the 13th Asia-Pacific Web Conference on Web Technologies and Applications. Beijing, China:Springer, 2011:65-76. http://www.springerlink.com/content/13312760726j305t/
|
[21] |
FAN P, LI G, YUAN L, et al. Vague continuous K-nearest neighbor queries over moving objects with uncertain velocity in road networks[J]. Information Systems, 2012, 37(1): 13-32. DOI:10.1016/j.is.2011.08.002 |
[22] |
SISTLA A P, WOLFSON O, XU B. Continuous nearest-neighbor queries with location uncertainty[J]. VLDB Journal, 2015, 24(1): 25-50. DOI:10.1007/s00778-014-0361-2 |
[23] |
BRINKHOFF T. Generatingnetwork-based moving objects[C]//International Conference on Scientific and Statistical Database Management. Washington, DC:IEEE, 2000:253-255. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=869794
|
[24] |
ARGE L, BERG M D, HAVERKORT H, et al. The priority R-tree:a practically efficient and worst-case optimal R-tree[J]. ACM Transactions on Algorithms, 2008, 4(1): 9. |