公路网上移动对象连续k近邻查询的一种方法

公路网上移动对象连续k近邻查询是最近时空数据库查询中的一个研究热点,它是在一个时间段内找到离查询点最近的K个移动对象.我们分析了现有查询方法,存在的问题主要是运动对象位置随时间而频繁变化以至于不能及时更新运动对象的信息而导致返回KNN结果不正确.为了解决这些问题,采用一种距离预计算方法,使计算量减少,从而为更新通讯获得更多时间.通过实验证明,我们提出的方法是有效的.     

空间k近邻查询的新策略

有效执行空间k近邻查询是地理信息系统尤其关心的问题,空间近邻查询是基于空间索引的树的遍历过程,苦测量距离和剪枝策略选取适当,可以极大地减少搜索空间所需访问的事点数,基于Rousspoulos等提出的测量距离,提出2个新的近邻搜索剪枝策略,用于空间k近邻查询,给出了搜索算法,并用算例表明该策略具有更好的剪枝效果,提高了空间k近邻查询的效率。     

GRkNN:一种组反k近邻查询方法

针对传统查询方法在查询点有多个对象时,对每个查询点逐个执行查询导致运行时间较长的问题,提出一种组反k近邻查询(GRkNN)方法.该方法将多个查询点视为一个整体考虑,并采用剪枝和核实两阶段策略.实验表明,该方法能更有效地实现数据库更新操作,缩短了运行时间.     

无线数据广播环境下k近邻查询研究

近邻查询问题是基于位置的查询的重要问题之一,是要找到距离查询点最近的k个对象的集合。无线数据广播技术能够有效地避免C/S模式在处理海量数据时的弊端,也能够对用户的位置信息进行隐私保护。将无线数据广播技术应用到k近邻查询中,利用Hilbert曲线组织空间结构,结合无线数据广播技术具有线性的特性,通过过滤和剪枝两个步骤,最终找到查询点的k个最近邻集合。     

路网中速度不确定移动对象的K范围近邻查询方法

K范围近邻查询是指查找给定范围区域内所有点的近邻对象。现有工作主要考虑对象固定不动情况下的K范围近邻查询,实际上对象不但可能移动,而且由于外界环境和自身情况等不确定性因素的影响,移动对象运动速度的不确定性也是客观存在的。基于此,本文考虑了速度不确定移动对象的K范围近邻查询,提出路网中速度不确定的移动对象的K范围近邻查询的处理算法,利用共享查询的思想减少了冗余查询的代价,最后,通过实验验证了所提算法的有效性。     

Spark环境下基于网格索引的轨迹k近邻查询方法

移动对象轨迹的k近邻(k nearest neighbor trajectories,kNNT)查询是一种重要的空间信息服务,主要用于寻找与给定轨迹最近邻的k条轨迹,被广泛地应用于智能交通、信息推荐等领域。随着轨迹数据量的快速增长,由于单机计算资源的限制,传统集中式环境下的kNNT查询效率和可扩展性无法满足实际要求。为了解决这个问题,设计了轨迹数据的分布式网格索引结构,该索引在Spark环境下将轨迹切分并映射到网格中,并引入轨迹还原表以保留查询时候选子轨迹段间的连续性。基于此索引,提出了Spark环境下的轨迹k近邻查询方法kNNT-Grid。实验结果表明,kNNT-Grid方法在分布式环境下实现了良好的查询效率和可扩展性,能够应对海量轨迹数据的k近邻查询需求。     

一种并发高效的连续时空查询处理算法

分析了SINA在查询结果上的完整性,发现和解决了其在消极更新结果完整性上的一点不足.为了进一步提高SINA的查询效率,将并发机制引入递增计算算法中,并给出了实施并发控制的策略及其在结果正确性上的证明.实验表明,并发运行后的算法,随着时空数据集的增大,查询计算的平均时间有了明显下降,内存和CPU的利用率有了明显提高.     

空间多样化约束下的移动k近邻查询

考虑为移动中的查询对象连续返回k个距离近并且满足空间多样化约束的对象,提出了空间多样化约束下的移动k近邻(SDC-MkNN)查询.在此,满足空间多样化约束代表对象之间的相互距离大于距离阈值.为了高效处理SDC-MkNN查询问题,提出了两种基于安全区域技术的算法.算法均通过减少重新计算查询结果的次数来提高查询效率.其中一种为精确算法EA,可连续返回精确的查询结果;另一种为近似算法ρAA,可连续返回具有近似率保障的近似查询结果.采用真实数据集验证了所提出算法的有效性.     

范围最近邻查询方法研究

范围最近邻(RNN)查询检索到一个区域内每个点的最近邻(NN),它是点和连续最近邻查询的推广.本文将范围看作矩形,分析了二维空间中范围最近邻查询的性质,描述了算法处理过程,并对提出的算法进行了性能分析.     

分布式网络中 CKNN 查询的 BORA 优化汇聚

针对时空数据库中,移动对象轨迹的连续K近邻查询(continuous K nearest neighbor query,CKNN)的查询效率较低的问题,以及在分布式的移动对象数据库(moving objects databases,MOD)环境下,提升对应查询结果的数据汇聚效率问题进行了研究.在CKNN查询中,设计优化了查询海滩线的更新算法,通过在轨迹数据结构中增加更新标志位,减少了轨迹线段参与的判定运算;同时在假设的类网格覆盖的分布式空间环境下,利用基于Bresenham覆盖的路由汇聚(Bresenham-based overlay for routing and aggregation,BORA)方法,进行查询结果的汇聚;并针对不同近邻参数、轨迹数目、移动对象速度、汇聚方式等对查询时间的影响进行了仿真实验;仿真结果表明,不同参数数值的增加延长了处理时间,基于BORA的汇聚方式比一般的汇聚方式节省了更多的处理时间,提高了系统查询及处理的效率.     

基于Voronoi图的最近邻查询的索引结构的研究

基于Voronoi图的最近邻查询在计算几何中已被研究了相当长一段时间。但在以往的研究中,基于Voronoi图的最近邻查询究竟是基于何种具体的索引结构去实现对查询空间的搜索的,却很少被提及。本文把传统的R树和Voronoi图在解决最近邻查询问题中的优越性相结合,提出了一种新的索引结构:VR树。进而提出了基于VR树索引结构的NN查询算法并对这该算法进行分析,在理论上证明了这个算法较基于R树索引结构的最近邻查询算法优。     

时空数据库中反向最近邻查询的方法研究

随着无线通讯及连续移动对象寻轨技术的高速发展,迫切需要提出解决大量移动对象查询的有效方法。本文提出了一个解决连续移动点反向最近邻查询的算法,同时也提出了解决连续移动点的最近邻查询算法。     

基于共享最近邻密度的演化数据流聚类算法

现有的基于密度的数据流聚类算法难于发现密度不同的簇,难于区分由若干数据对象桥接的簇和离群点.本文提出了一种基于共享最近邻密度的演化数据流聚类算法.在此算法中,基于共享最近邻图定义了共享最近邻密度,结合数据对象被类似的最近邻对象包围的程度和被其周围对象需要的程度这两个环境因素,使聚类结果不受密度变化的影响.定义了数据对象的平均距离和簇密度,以识别离群点和簇间的桥接.设计了滑动窗口模型下数据流更新算法,维护共享最近邻图中簇的更新.理论分析和实验结果验证了算法的聚类效果和聚类质量.     

Theoretical analysis of the confidence metrics for nearest neighbor classifier

Confidence value plays a vital role in the decision of rejection threshold and the integration of multiple classifiers. Nearest neighbor (NN) classifier is the most traditional and most common nonparameter statistical pattern classifier. However, so far there is no explicate theoretical analysis of the connection between nearest distance and confidence value. An analytical insight into different approximations is presented and one formula is pointed out that it is optimal in the sense of mathematical expectation. Practice in handwritten numeral recognition strongly supports the conclusion.     

最近邻搜索用于分类问题的一种改进

最近邻搜索广泛应用于分类问题,其最显著的优点是分类准确率高、泛化性能好.但现有最近邻分类算法都存在着一个弱点——样本集增大分类计算量也显著增大.为了克服这一不足,本文基于一个新的思路,提出了最近邻分类方法的一种改进方法.该方法在进行最近邻分类时,不一定要找到待分类点的最近邻点,而只要知道最近邻点的类别即可,大大地减少了最近邻搜索时的计算量.用经典的分类问题双螺线问题(TSP)以及其他几个例子,就该改进方法的分类效果、分类速度和学习性能等3个方面进行了测试,并与经典的K维双叉树(KD树)最近邻搜索法以及压缩近邻法进行了比较.结果表明,就综合性能而言,本文改进方法是有竞争力的.     

一种新的基于伪最近邻算法的降水预报方法

分析北京地区日降雨量资料,相较于其他降雨事件,大雨或暴雨事件发生的次数较少,因此该地区的降水量预报属于样本不均衡问题。在样本不平衡的情况下,K最近邻(PNN)算法的分类误差率将会大大提高,这也就使传统的基于K最近邻算法的降水量预报方法的应用受到了限制。针对北京地区降水量预报这一样本不均衡问题,应用伪最近邻算法构建了北京市的降水量预报模型。该方法利用北京地区日降雨量资料和美国国家环境预报中心全球格点资料,将降雨量作为类,将美国国家环境预报中心全球格点资料的各种因子场作为天气样本特征,通过决策规则实现最优分类。利用提出的降水预报模型对北京地区2010年6~8月进行了24 h降水预报,实验结果表明,提出的预报方法对于降水等级预报的预报准确率以及晴雨预报的TS评分、正样本概括率和漏报率均优于传统的K最近邻预报方法,该方法具有较好的预报效果。     

一维双原子链晶格振动中的次近邻

目的研究一维双原子链的色散关系,并与最近邻近似下的结果进行比较。方法以一维离子晶体为例,分别考虑次近邻原子和所有原子的作用,利用数值模拟的方法。结果得到了一维双原子链的色散关系的一般表达式,即ω2=2m11m2{-x(m1 m2)±[x2(m1 m2)2-4m1m2(x2-y2)]}。结论对一维双原子链来说,次近邻对色散关系的贡献也是比较大的。     

t′次近邻跃迁对角分析光电子谱的影响

以SDW波模拟赝能隙,基于具有自旋密度波(SDW)和d-波超导对称性(DSC)的Hub bard唯象模型,同时考虑近邻、次近邻跃迁效应,在平均场近似下计算谱函数及态密度,研究赝能隙和次近邻跃迁(t′)对ARPES的影响。发现考虑次近邻跃迁后得到的结果与铜氧化物高温超导体的性质符合的更好。     

ND序列下最近邻密度估计的强相合速度

在ND(negatively dependent)样本下研究最近邻密度估计的强相合速度,利用ND序列的指数不等式以及ND序列的性质,给出了最近邻密度估计强相合速度的充分条件。     

考虑次近邻作用原子链的热传导研究

运用Ford—Kac—Mazur（FKM）方法和数值模拟对考虑次近邻作用的一维介电原子链进行了研究。在一定的条件下得到了热流的具体表达式，给出了不同条件下热流随体系大小的变化趋势，分析了次近邻相互作用和质量梯度对热流的影响。结果表明次近邻作用对于热流的调节不明显，而构建材料的不对称结构（质量梯度调节）可作为热传导控制的有效手段。