时间依赖路网上的移动对象K近邻查询算法

随着基于位置服务的广泛应用,时间依赖路网上的对象查询逐渐成为研究热点。以往研究大多只针对时间依赖路网上的静态对象(如加油站、餐厅等),未考虑到移动对象(如出租车)的情况,而移动对象的查询在日常生活中有着非常广泛的应用场景。因此,文中提出了一种针对时间依赖路网上的移动对象K近邻查询算法TD-MOKNN,该算法分为预处理阶段和查询阶段。在预处理阶段,通过建立路网和网格索引,提出了一种新的移动对象到路网的映射方法,解除了以往研究假设移动对象恰好在路网顶点上的限制;在查询阶段,采用启发式搜索,借助倒排网格索引计算了一种新的高效启发值,通过预处理信息和启发值设计了高效K近邻查询算法,并给出了算法的正确性证明和时间复杂度分析。实验验证了所提算法的有效性,相比现有算法,TD-MOKNN算法在遍历顶点数和响应时间上分别减少了55.91%和54.57%,查询效率平均提升了55.2%。     

时间依赖路网中反向k近邻查询

在现存的反向k近邻查询方案中,比较高效的研究大多集中在欧氏空间或者静态路网,对时间依赖路网中的反向k近邻查询的研究相对较少。已有算法在兴趣点密度稀疏或者k值较大时,查询效率较低。对此,提出了基于子网划分的反向k近邻查询算法mTD-SubG。首先,将整个路网划分为大小相同的子网,通过子网的边界节点向其他子网进行扩展,加快对路网中兴趣点的查找速度;其次,利用剪枝技术缩小路网的扩展范围;最后, 利用已有时间依赖路网下的近邻查询算法,判定查找到的兴趣点是否为反向k近邻结果。实验中将mTD-SubG算法与已有算法mTD-Eager进行对比,结果表明mTD-SubG算法的响应时间比mTD-Eager算法减少了85.05%,遍历节点个数比mTD-Eager算法减少了51.40%。     

面向时间依赖路网的连续k近邻查询

连续k近邻查询(continuous k-nearest neighor,Ck NN)定义为查找指定路径上每个点的k个最小代价数据对象。目前关于Ck NN的研究都是在欧式空间与静态路网中实现的,这些算法不能直接应用到边权值变化的时间依赖路网中。定义并解决了时间依赖路网中的Ck NN问题,利用积分的性质以及通过对权值代价函数合并的方式提出了两阶段的基于分割点的Ck NN查询算法。过滤阶段提出了计算节点到达时间的方法,再利用到达时间查询出多个候选k近邻结果;求精阶段将查询点到候选结果的权值函数合并,通过计算函数交点得到分割点,进而为查询返回若干个分割点以及相应区间内的k近邻结果。实验结果表明,与进行多次快照k近邻查询相比,所提算法在响应时间上减少了近一个数量级。     

面向不确定移动对象的连续K近邻查询算法*

近年来,位置服务等领域急需解决的一个难点问题是不确定移动对象连续K近邻查询.基于此情况,文中提出高效的面向不确定移动对象的连续K近邻查询算法.首先提出2种预测移动对象可能区域算法MaxMin与Rate,利用最近一段时间窗口内的位置采样、速度和方向预测移动对象在查询时刻到未来I区间可能的位置区域.同时使用最小距离与最大距离区间描述移动对象到查询对象的距离.然后采用优化的基于模糊可能度判定的排序方法查找查询对象的K近邻.最后在真实和合成的大规模移动对象数据集上验证文中方法的有效性.     

基于路由机制的时变路网k近邻算法

针对现实生活中动态路网的地理信息查询问题,提出了一种基于路由机制的动态路网中k近邻查询的算法。其主导思想是利用空间换时间,用路由表保存历史查询结果,用查询路由表的方法代替传统的最短路径计算,通过历史数据减少系统重复计算并对车辆行驶路径进行规划,用更新路由表的方法适应路况的变化。围绕路由表这一核心,改进相应的k近邻算法的过滤、精炼过程。通过路由表对动态路网进行少量的预处理,减少系统在k近邻搜索中的候选点数量,缩小查询范围,提高搜索效率。     

面向时间依赖路网的空间索引方法

在兴趣点(POI)呈稀疏分布时,现有时间依赖路网中的k近邻查询方法效率较低,且无法高效支持多类型的POI查询。为此,建立基于POI分布的空间索引结构TDG。根据路径权值上、下界对预计算路径进行剪枝优化,在此基础上,提出一种索引更新策略与基于TDG的k近邻查询算法。实验结果表明,与启发式查询算法相比,该算法的扩展节点数量平均减少87.5%,查询响应时间平均缩短33%～66%。     

基于参考节点嵌入的图可达性查询

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试。相较于K-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92%和78.6%,其查询时间大大缩短,分别降低了95.5%和92%。实验结果表明：所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。     

面向非平衡类问题的k近邻分类算法

针对k近邻（kNN）方法不能很好地解决非平衡类问题,提出一种新的面向非平衡类问题的k近邻分类算法。与传统k近邻方法不同,在学习阶段,该算法首先使用划分算法（如K-Means）将多数类数据集划分为多个簇,然后将每个簇与少数类数据集合并成一个新的训练集用于训练一个k近邻模型,即该算法构建了一个包含多个k近邻模型的分类器库。在预测阶段,使用划分算法（如K-Means）从分类器库中选择一个模型用于预测样本类别。通过这种方法,提出的算法有效地保证了k近邻模型既能有效发现数据局部特征,又能充分考虑数据的非平衡性对分类器性能的影响。另外,该算法也有效地提升了k近邻的预测效率。为了进一步提高该算法的性能,将合成少数类过抽样技术（SMOTE）应用到该算法中。KEEL数据集上的实验结果表明,即使对采用随机划分策略划分的多数类数据集,所提算法也能有效地提高k近邻方法在评价指标recall、g-mean、f-measure和AUC上的泛化性能;另外,过抽样技术能进一步提高该算法在非平衡类问题上的性能,并明显优于其他高级非平衡类处理方法。     

路网中基于地理位置和区域封闭性的最短路径的查询算法

针对大规模城市路网寻找最短路径的问题,提出了一种基于边的聚类树(ECT)和最小封闭格(MCL)的算法来达到路网中快速查询的目的。首先对给定的城市路网进行预处理,即利用封闭格的定义对路网进行划分;其次利用ECT树对划分出的MCL格进行存储;最后利用虚拟路径的思想(两点之间直线距离最短)并结合MCL格的性质和路网的平面性的特点,利用ECT树存储的优势,在查询中大大减少了无用节点的访问数量,降低了时间复杂度,从而达到了快速寻找最短路径的目的。理论分析和仿真实验表明,在大规模的城市路网中ECT树的存储空间相比PCPD算法减少了约45.56%,相比TNR算法减少了24.35%,其在存储方面略优于较为完备的SILC算法。MCL算法在查找过程中的搜索效率比SPB算法快15.6%。实验结果表明基于ECT存储的MCL算法在实际查询过程中能提高查询的效率。     

多样性感知的时空文本信息的KNN查询处理方法*

如何在互联网上大量的带有地理位置标签和时间标签的信息中查找满足用户需求的信息十分重要.文中针对带有地理位置和时间标签的文本信息,提出多样性感知的时空文本信息的k近邻查询处理方法.首先,归一化处理数据对象的时空变量,并建立三维Rtree索引,有效融合数据对象的时间变量和空间变量.然后,提出多样性感知的k近邻查询算法(DST-KNN)和改进的DST-KNN(IDST-KNN).最后,通过基于大量数据集的实验验证文中查询处理方法的高效性和准确性.     

基于肌电信号和加速度信号的动态手势识别方法

为了增强手势识别的多样性和简便性,提出了一种基于肌电信号（EMG）和加速度（ACC）信息融合的方法来识别动态手势。首先,利用MYO传感器采集EMG和ACC的手势动作信息;然后分别对ACC和EMG信号作特征降维和预处理;最后,为减少训练样本数,提出用协作稀疏表示分类器来识别基于ACC信号的姿态手势,用动态时间规整（DTW）算法和K-最邻近分类器（KNN）来分类EMG信号的手形手势。其中在利用协作稀疏表示分类器识别ACC姿态信号时,通过对创建字典最佳样本个数以及特征降维的维数进行研究来降低手势识别的复杂度。实验结果表明,手形手势的平均识别率达到了99.17%,对于向上向下、向左向右4种姿态手势平均识别率达到 96.88%,而且计算速度快;对于总体的12个动态手势,其平均识别率达到96.11%。该方法对动态手势的识别率较高,计算速度快。     

Efficient algorithms for shortest distance queries on special classes of polygons

The problem of finding a rectilinear minimum bend path (RMBP) between two designated points inside a rectilinear polygon has applications in robotics and motion planning. In this paper, we present efficient algorithms to solve the query version of the RMBP problem for special classes of rectilinear polygons given their visibility graphs. Specifically, we show that given an unweighted graph G = (V, E), with ¦V¦ = N and ¦E¦ = M, algorithms to preprocess G in linear space and time such that the shortest distance queries — queries asking for the distance between any pair of nodes in the graph — can be answered in constant time and space are presented in this paper. For the case of a chordal graph G, our algorithms give a distance which is at most one away from the actual shortest distance. When G is a K-chordal graph, our algorithm produces an exact shortest distance in O(K) time. We also present a non-trivial parallel implementation of the sequential preprocessing algorithm for the CREW-PRAM model which runs in O(log² N) time using O(N + M) processors. After the preprocessing, we can answer the queries in constant time using a single processor.     

基于Spark框架的高效KNN中文文本分类算法

针对K-最近邻（KNN）分类算法时间复杂度与训练样本数量成正比而导致的计算量大的问题以及当前大数据背景下面临的传统架构处理速度慢的问题,提出了一种基于Spark框架与聚类优化的高效KNN分类算法。该算法首先利用引入收缩因子的优化K-medoids聚类算法对训练集进行两次裁剪;然后在分类过程中迭代K值获得分类结果,并在计算过程中结合Spark计算框架对数据进行分区迭代实现并行化。实验结果表明,在不同数据集中传统K-最近邻算法、基于K-medoids的K-最近邻算法所耗费时间是所提Spark框架下的K-最近邻算法的3.92~31.90倍,所提算法具有较高的计算效率,相较于Hadoop平台有较好的加速比,可有效地对大数据进行分类处理。     

基于改进AP选择和K最近邻法算法的室内定位技术

针对复杂的室内环境和在传统K最近邻法（KNN）算法中认为信号差相等时物理距离就相等两个问题,提出了一种新的接入点（AP）选择方法和基于缩放权重的KNN室内定位算法。首先,改进AP的选择方法,使用箱形图过滤接收信号强度（RSS）的异常值,初步建立指纹库,剔除指纹库中丢失率高的AP,使用标准偏差分析RSS的变化,选择干扰较小的前n个AP;其次,在传统的KNN算法中引入缩放权重,构建一个基于RSS的缩放权重模型;最后,计算出获得最小有效信号距离的前K个参考点坐标,得到未知位置坐标。定位仿真实验中,仅对AP选择方法进行改进的算法平均定位误差比传统的KNN算法降低了21.9%,引入缩放权重算法的平均定位误差为1.82 m,比传统KNN降低了53.6%。     

不确定环境下轨迹k-匿名隐私保护

综合考虑不确定环境下移动对象的影响因素,提出了对船舶自动导航系统所记录的轨迹进行k-匿名的隐私保护方法。该方法首先建立一个不确定空间索引,并将不确定空间用四叉树结构存储,然后通过使用连续近邻查询方法找出与当前轨迹相似区域的轨迹,并将这些轨迹加入匿名候选集。由于考虑到路网规模影响匿名信息的有效性以及攻击者对轨迹的攻击概率,采用启发式算法生成匿名轨迹最佳利用链,从而加大对轨迹隐私保护的力度。最后实验结果表明,所提出的方法比传统方法信息丢失率降低了20%~50%,信息扭曲度随着查询范围的增大能保持在50%以下,代价损失相比传统方法降低了10%~30%。该方法可以有效防止恶意者对轨迹进行攻击获取信息,应用于公务船艇海上执勤执法。     

Heuristics for the time dependent team orienteering problem: Application to tourist route planning

The Time Dependent Team Orienteering Problem with Time Windows (TDTOPTW) can be used to model several real life problems. Among them, the route planning problem for tourists interested in visiting multiple points of interest (POIs) using public transportation. The main objective of this problem is to select POIs that match tourist preferences, taking into account a multitude of parameters and constraints while respecting the time available for sightseeing in a daily basis and integrating public transportation to travel between POIs (Tourist Trip Design Problem, TTDP). TDTOPTW is NP-hard while almost the whole body of the related literature addresses the non-time dependent version of the problem. The only TDTOPTW heuristic proposed so far is based on the assumption of periodic transit service schedules. Herein, we propose efficient cluster-based heuristics for the TDTOPTW which yield high quality solutions, take into account time dependency in calculating travel times between POIs and make no assumption on periodic service schedules. The validation scenario for our prototyped algorithms involved the transit network and real POI datasets compiled from the metropolitan area of Athens (Greece). Our TTDP algorithms handle arbitrary (i.e. determined at query time) rather than fixed start/end locations for derived tourist itineraries.     

基于云平台的任务性能采集和分类方法

由于用户在实际使用云平台时,很难确定云平台的云主机类型,所以造成了云平台资源利用率低下的问题。许多典型的解决资源利用率低下的方法,都是从云提供商的角度优化放置算法,而用户选择将限制资源利用率增加;也有一些方法采用云平台下的任务性能短时间采集并预测,但会降低任务分类的准确性。为了达到提高云平台资源利用率、简化用户操作的目的,首先提出一种多属性的任务性能采集工具Lbenchmark,全面采集任务的性能特征,和Ganglia相比负载降低了50%以上。然后,利用该性能数据,提出一种基于权值可配的多KD树-K最近邻（KNN）应用性能分类算法,挑选适合参数建立多个基于KD树的KNN分类器,通过交叉验证方法调整每个属性在不同分类器的权重,进行选举分类。实验结果表明,所提算法与传统的KNN相比,计算量明显提高了约10倍以上,而准确性平均提高约10%。该算法可利用数据特征映射将资源建议提供给用户和云提供商,进而提高云平台整体的利用率。     

基于主成分分析和K近邻的文件类型识别算法

为解决基于文件后缀名和文件特征标识识别文件类型误判率较高的问题,在基于文件内容识别文件类型的算法基础上,提出主成分分析（PCA）和K近邻（KNN）算法相结合的文件类型识别算法。首先,使用PCA方法对样本预处理以降低样本空间的维数;然后,对降维后的训练样本集进行聚类处理,即用聚类质心代表每种类型的文件;最后,针对训练样本分布不均匀可能造成的分类误差,提出基于距离加权的KNN算法。实验结果表明,改进算法在样本数较多的情况下,能降低分类的计算复杂度,并保持了较高的识别正确率;而且该算法不依赖文件类型的特征标识,应用范围更为广泛。     

基于滑动时间窗口的IPv6地址跳变主动防御模型

针对IPv6恢复端到端通信,IPv6节点易被攻击者探测攻击等问题,提出一种基于滑动时间窗口的IPv6地址跳变（AHSTW）主动防御模型。首先通过共享密钥进行地址跳变间隔等会话参数的协商,之后引入收发时间窗口的概念,通信双方仅发送或接收处于时间窗口内的数据包,通过时间窗口自适应调整（TWAA）算法,依据网络时延的变化及时调整时间窗口大小以适应网络环境的变化。理论分析证明,该模型能够有效抵抗攻击者对目标IPv6节点的数据截获分析攻击和拒绝服务攻击（DoS）。实验结果表明,在传输相同数据包大小时,AHSTW的额外CPU开销在2~5个百分点,并无显著提高,通信效率并无显著下降;在通信过程中,通信双方地址与端口呈随机、分散、无序等特点,极大增加了攻击者的开销与攻击难度,保护了IPv6网络安全。