基于聚集块的多用户连续K最近邻多线程查询

k最近邻分类模型K最近邻（K-Nearest Neighbors，KNN）分类模型是一种基于实例的学习，或者说是局部逼近和将所有的计算推迟到分类之后进行的模型。

在KNN模型中，输出是由输入实例的最近邻的K个训练实例的多数表决来确定的。

具体来说，KNN算法的工作流程如下：准备数据，对数据进行预处理。

这包括数据的清洗、特征的选取和标准化等步骤。

选用合适的数据结构存储训练数据和测试元组。

这通常使用一种称为KD树（KD-tree）的数据结构，它可以帮助我们快速找到样本点的最近邻。

设定参数，如K值。

K值的选择对KNN算法的性能有很大的影响，通常需要通过实验来确定最优的K值。

维护一个大小为K的按距离由大到小的优先级队列，用于存储最近邻训练元组。

随机从训练元组中选取K个元组作为初始的最近邻元组，分别计算测试元组到这K个元组的距离，将训练元组标号和距离存入优先级队列。

遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L与优先级队列中的最大距离Lmax进行比较。

如果L>=Lmax，则舍弃该元组，遍历下一个元组。

否则，将新的元组及其距离加入优先级队列，并删除队列中距离最大的元组。

当所有训练元组都遍历完毕后，优先级队列中的元组就是测试元组的K个最近邻。

根据这K个最近邻的类别，通过多数表决来确定测试元组的类别。

KNN算法的优点是简单易懂，无需参数估计，无需训练。

但是，它的计算量大，尤其是当样本容量大的时候，因为对每个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。

此外，KNN算法对样本的依赖性很大，如果样本不平衡，可能会导致分类结果的不准确。

总的来说，K最近邻分类模型是一种简单而有效的分类方法，适用于各种类型的数据，包括文本、图像等。

但是，它的性能受到数据特性、K值选择以及距离度量方式等因素的影响，需要在实际应用中进行适当的调整和优化。

加权K最近邻（Weighted K-Nearest Neighbors，简称WKNN）是一种在机器学习和数据挖掘中使用的算法，主要用于分类和回归问题。

它是一种基于实例的学习方法，其中最近的邻居被赋予权重，这些权重通常与实例的类别或特征有关。

在WKNN中，我们首先根据距离度量（如欧几里得距离、曼哈顿距离等）找出输入样本在训练数据集中K个最近邻。

然后，对于每个最近邻，我们根据某种规则（如权重函数）赋予它一个权重。

最后，我们根据加权的最近邻的类别或值进行预测。

权重函数通常与样本的类别或特征有关。

例如，如果一个样本属于一个特定的类别，并且它的某些特征比其他样本更显著（例如，在图像分类问题中，边缘或纹理信息可能会比颜色信息更重要），那么这些样本的邻居可能会被赋予更高的权重。

以下是一个简单的WKNN算法的实现步骤：
1. 初始化：为每个训练样本设定一个权重。

2. 对于新的输入样本，使用距离度量找出其K个最近邻。

3. 对每个最近邻，根据权重函数计算其权重。

4. 根据加权的最近邻的类别或值进行预测。

这种算法通常比简单的KNN算法更准确，因为它考虑了不同样本的重要性和影响力。

然而，它的实现和调优可能会更复杂，因为它需要一个适当的权重函数来平衡不同样本的重要性。

需要注意的是，WKNN并不一定比其他分类算法（如支持向量机、决策树、随机森林等）更优越，它可能更适合某些特定的问题和数
据集。

在选择算法时，需要根据具体的问题和数据集进行评估和实验。

kdtree最近邻算法
Kdtree最近邻算法是一种基于树的搜索算法，它可以在密集的空间中找到最近邻（Nearest Neighbor）。

Kdtree最近邻算法使用了一种二叉树的结构，它的特点是每个节点都具有固定的分割轴，并且将其空间分为两个子空间，其中一个在分割轴的左边，另一个在分割轴的右边。

Kdtree最近邻算法是一种基于空间划分的算法，通过划分空间，可以减少搜索范围，从而提高搜索效率。

Kdtree最近邻算法可以用来搜索多维数据集，例如搜索一个二维空间中的最近邻点，或者搜索一个三维空间中的最近邻点。

Kdtree最近邻算法的优点是可以提高搜索的效率，它可以在多维空间中快速搜索最近邻点。

Kdtree最近邻算法也可以用来搜索高维空间中的最近邻点，不过由于高维空间的复杂性，使用Kdtree最近邻算法的效率会受到一定的影响。

Kdtree最近邻算法也可以用于搜索数据库中的最近邻点，它可以搜索出指定数据库中最相似的记录。

Kdtree最近邻算法在搜索数据库中的最近邻点时，能够有效地减少搜索范围，从而提高搜索效率。

Kdtree最近邻算法是一种基于树的搜索算法，它既可以用于搜索多维空间中的最近邻点，也可以用于搜索数据库中的最近邻点，它能够有效地减少搜索范围，从而提高搜索效率。

Kdtree最近邻算法是一种高效的搜索算法，能够有效地解决多维空间中最近邻点搜索的
问题。

多线程join的用法以下是 7 条关于多线程 join 的用法：1. 嘿，你知道吗？多线程 join 就像是让多个小伙伴一起行动，然后等待大家都完成！比如说，你让几个线程去做不同的任务，就像小明去买饮料，小红去拿零食，然后你用 join 就可以在这之后才继续后面的事儿。

为啥要这样啊？不这样万一后面的动作依赖他们没完成的任务咋办呢！2. 多线程 join 啊，那可太重要啦！这就好比一场接力赛跑，前一个线程跑完了，后面的线程才能接着跑呀！比如张三先跑第一段，等他跑完了李四再接着跑第二段。

你不 join 一下，能行吗？这要是乱了套，可就糟糕咯！3. 哇哦，想想多线程 join 呀，其实就像是一列火车，每个车厢都得按顺序连接起来一起前进！假如说有几个线程负责不同的工作，就像不同的车厢装不同的货物，通过 join 让它们协调一致地前进。

这不是很妙吗？4. 多线程 join 真的很神奇呀！可以把它想象成一个团队合作，大家配合好了才能成功呀！就像是王五和赵六一起做一个项目，只有等他们都完成了，整个事情才算结束。

不 join 等着，还能怎么办呢？5. 哎呀呀，多线程 join 呀，不就是确保大家都到齐了才开始下一步嘛！就像是一群朋友约好一起出去玩，得等所有人都到了才出发呀！比如说线程 A 去取车，线程 B 去买门票，这时候就得用 join 等一等咯。

是不是很好理解呀？6. 你看哦，多线程 join 就像是给多个行动排好顺序，一个一个来！好比有线程 C 去做饭，线程 D 去摆餐具，等做饭的完成了再开始吃饭。

这多重要呀，不 join 能行么？7. 多线程 join 简直就是让一切有序进行的法宝啊！就像在一个大工程中，各个部分都得衔接好。

比如线程 E 负责搭建舞台架子，线程 F 负责布置灯光，只有通过 join，等架子搭好了再弄灯光，才不会出乱子呀！总之呀，多线程 join 真的超重要的，一定要用对用好它呀！。

nearestneighbors函数NearestNeighbors函数是机器学习中经常使用的一种方法，它是用来寻找一个样本在样本集中最近的邻居的算法，也可称为K最近邻算法(K-nearest-neighbors algorithm)。

该函数通常用于分类、回归以及异常检测等方面，在实际应用中具有广泛的用途，例如在推荐系统中的用户推荐、医学诊断中的诊断系统等领域。

下面我们将详细介绍NearestNeighbors函数的使用方法：1. 首先导入必要的库和模块，例如numpy、sklearn.neighbors等。

2. 对于一个数据集，首先需要对其进行预处理，包括特征处理、缺失值填充等。

对于特殊类型的数据，例如图像数据，还需要对其进行维度上的转换。

3. 接下来，我们需要进行数据集的划分，通常将一个数据集划分为训练集和测试集。

其中训练集用于模型的训练和参数的调整，测试集用于模型的评估和性能的比较。

4. 对于训练集，我们需要使用NearestNeighbors函数进行模型的训练。

具体而言，我们可以使用sklearn.neighbors模块中的KNeighborsClassifier或KNeighborsRegressor函数进行分类或回归任务。

在这个过程中，我们需要指定K值以及其他参数，例如数据的距离度量方式等。

5. 在模型训练完成之后，我们可以使用该模型进行预测。

对于测试集中的每个样本，我们可以通过查询训练集中的K个最近邻样本，从而预测该样本的输出。

再通过计算该样本的输出与真实值之间的误差，我们可以得到模型的性能指标。

除了上述基本的使用方法，我们还可以对NearestNeighbors函数进行优化和改进。

例如，我们可以使用基于树的K最近邻算法，例如KDTree和BallTree等，以减少查询时间的复杂度；我们还可以进行距离度量的改进，例如使用余弦相似度等。

总之，NearestNeighbors函数是机器学习中的一种重要方法，它具有广泛的应用领域和潜在的优化空间。

k-最近邻算法
1.k-最近邻算法是一种基于实例（Instance-based）的学习方法，也称为惰性学习（Lazy learning）方法或者近似实例学习方法。

它是一种分类方法，它不学习实例及其
之间的关系，而是直接存储数据，当需要进行分类预测时，寻找距离最近的K个点，然后
根据这些点的类别进行预测。

2.k-最近邻算法原理：通过比较未知实例与训练数据库中的实例，测量它们之间的距离，来预测该未知实例的类别。

与距离它最近的K个实例的类别最多的作为该未知实例的
类别。

3.k-近邻算法的优缺点：
优点：
1.简单易行：最近邻算法是计算机最简单的分类算法，直观有效，操作简单易行。

2.可预测性良好：最近邻分类算法可以获得较好的解决方法，并达到较高的预测性能。

3.大规模数据集可以很快地进行分类：kNN算法仅依赖训练数据中出现的模型，而不
用于存储数据，因此它可以在庞大的数据集上进行分类并实现极快的计算性能。

1.计算复杂度高：KNN算法比较复杂，需要调参数，计算复杂度较高且及时性较差。

2.存在样本不平衡问题：由于KNN算法没有考虑数据的内在分布特征，对于样本不平
衡的问题容易出现误分的情况。

3.维数灾难：KNN算法容易陷入维数灾难，即随着维数增加，距离也会不断增加，准
确率越来越低。

数据流滑动窗口上的一种多聚集查询共享策略
于亚新;朱歆华;于戈
【期刊名称】《东北大学学报（自然科学版）》
【年(卷),期】2005(026)011
【摘要】基于如何提高多个聚集查询的查询效率,提出了一种共享链树结构的多查询聚集计算共享策略.利用每个滑动窗口逻辑地将链树划分成若干子树,它们各自根节点中的聚集值恰好就是每个查询对应的结果值.数据流上多个查询可以在同一棵链树上并发执行,避免了每个查询的重复建树.同时,利用链树本身可降低无用的重复比较的性质,使得多个查询在同一棵链树上只需进行少量更新比较就可求得每个查询的新聚集值.实验证明,多个查询共用同一链树结构,可以最大程度地共享资源,减小内存使用量,因此大大提高了数据流上的查询处理效率,加大了数据流上的任务吞吐量,改善了系统性能.
【总页数】4页(P1048-1051)
【作者】于亚新;朱歆华;于戈
【作者单位】东北大学,信息科学与工程学院,辽宁,沈阳,110004;东软集团有限公司,辽宁,沈阳,110179;东北大学,信息科学与工程学院,辽宁,沈阳,110004
【正文语种】中文
【中图分类】TP311.13
【相关文献】
1.一种时空数据流中范围聚集查询共享策略 [J], 左怀玉;靳肖闪;景宁;钟志农
2.时间滑动窗口上数据流极值聚集的空间优化 [J], 丁维龙;韩燕波;王菁;赵卓峰
3.基于滑动窗口的数据流连接聚集查询降载策略 [J], 康伟;李战怀;张龙波
4.滑动窗口数据流上多极值查询资源共享策略研究 [J], 田李;王乐;李爱平;邹鹏;贾焰
5.数据流滑动窗口聚集查询降载策略研究 [J], 郭景峰;贺春亮
因版权原因，仅展示原文概要，查看原文内容请购买。

检索技巧near近邻检索技巧（Near）是一种常用的信息检索方法，它可以帮助我们在海量数据中快速找到与给定查询对象相似或相关的数据。

在本文中，我将介绍近邻检索技巧的原理、应用场景以及常用的算法。

一、近邻检索技巧的原理近邻检索技巧的核心思想是通过计算不同数据对象之间的相似度或距离来衡量它们之间的相关性。

常用的相似度度量方法包括欧氏距离、余弦相似度、曼哈顿距离等。

在实际应用中，我们可以根据具体的需求选择合适的相似度度量方法。

近邻检索技巧的基本步骤包括：首先，我们需要确定一个查询对象，即我们要找到相似数据的参考对象。

然后，我们需要将查询对象与数据集中的每个数据对象进行相似度计算或距离计算。

最后，我们可以根据计算结果对数据对象进行排序，取出与查询对象相似度最高或距离最近的数据。

二、近邻检索技巧的应用场景近邻检索技巧在实际应用中有着广泛的应用场景。

以下是一些常见的应用场景：1. 推荐系统：近邻检索技巧可以帮助推荐系统根据用户的历史行为或偏好找到与之相似的用户或物品，从而为用户提供个性化的推荐服务。

2. 图像搜索：近邻检索技巧可以帮助图像搜索引擎根据用户提供的图像找到与之相似的图像，为用户提供更精准的搜索结果。

3. 文本相似度计算：近邻检索技巧可以帮助文本处理系统根据输入的文本找到与之相似的文本，从而实现文本分类、信息抽取等功能。

4. 音乐推荐：近邻检索技巧可以帮助音乐推荐系统根据用户的听歌记录找到与之相似的歌曲，为用户推荐更符合其口味的音乐。

三、常用的近邻检索算法近邻检索技巧涉及到的算法有很多，下面介绍几种常用的算法：1. K最近邻算法（K-Nearest Neighbors，简称KNN）：KNN算法是一种基本的分类和回归算法，它通过计算查询对象与数据集中最近的K个邻居之间的距离来确定查询对象的类别或预测值。

2. Locality Sensitive Hashing（简称LSH）：LSH是一种高效的近似最近邻搜索算法，它通过将数据对象映射到哈希空间中，使得相似的数据对象具有相似的哈希值，从而加速近邻搜索过程。

第26卷第6期 齐 齐 哈 尔 大 学 学 报 Vol.26,No.6 2010年11月 Journal of Qiqihar University Nov.,2010基于聚集块的多用户连续K最近邻多线程查询夏妍，郝忠孝（齐齐哈尔大学 计算机与控制学院，黑龙江 齐齐哈尔 161006）摘要：当对城市道路网络中的对象进行查询时，已研究出连续的K近邻查询技术，但在一般情况下服务器会同时收到多个查询请求，为了提高查询效率，降低多查询代价，提出一种聚集块的共享查询算法并建立多用户连续查询处理框架，采用流水线处理策略，将查询分为查询预处理、查询执行及查询结果分发3个执行阶段，利用扩展树存储查询结果。

实验结果表明，在目标点分布比较密集的情况下，本算法明显优于其它算法。

关键词：K最近临查询；聚类块；多线程；扩展树；多查询中图分类号：TP311.132.4文献标识码：A 文章编号：1007-984X(2010)06-0016-05Papadias等人[1]首先提出了在道路网络中对空间对象的查询问题，并给出了几个基本查询问题的算法。

Shahabi等人[2]利用空间映射的方法将道路网络映射到高维空间，然后进行最近邻查询处理。

但由于空间的扭曲，其结果将会产生一定的误差。

Feng等人[3]讨论了对多对象最近邻的更新问题。

至今为止，道路网络环境中的多对象最近邻查询问题还没得到很好的解决。

值得注意的是：大部分研究工作中的路径计算都采用了网络扩展[4]的思想：从一点出发，向各个方向进行网络扩展。

该方法可以实时计算道路网络中任意两点的道路网络距离，但其计算代价较大。

单个K最近临查询常使用增量网络扩展（如INE）和预先计算网络距离(如VN3)方法。

文献[4]介绍了增量网络扩展方法，此方法易于更新但查询性能不佳，文献[5]介绍了基于VN3方法的连续K近邻查询，此方法查询性能更好但难以处理对象点和道路网络的频繁更新，对高密度对象的处理效率显著下降，并且需要执行多次查询来查询某物体的K最近邻。

基于多线程的不确定移动对象连续k近邻查询齐建鹏;于彦伟;王创存;曹磊;宋鹏【期刊名称】《浙江大学学报（工学版）》【年(卷),期】2018(052)001【摘要】针对不确定数据下的大规模连续k近邻查询请求,基于不确定移动对象连续k近邻查询的Rate方法,提出高效的基于多核多线程的并行查询处理框架.根据查询对象的运动速度与相对位置确定查询请求间是否采用查询复用,确定查询复用时的距离边界.提出密度网格扩展的多线程数据分发方法,解决了负载均衡问题,将空间位置相邻的查询请求划分到同一线程,提高查询复用率.通过多线程间的内存共享机制,对计算过的移动对象的预测区域实现计算复用.在大规模交通数据集上验证了所提算法的有效性与查询性能,相比传统的Rate方法,所提并行算法的加速比可达37.【总页数】9页(P142-150)【作者】齐建鹏;于彦伟;王创存;曹磊;宋鹏【作者单位】烟台大学计算机与控制工程学院,山东烟台264005;烟台大学计算机与控制工程学院,山东烟台264005;烟台大学计算机与控制工程学院,山东烟台264005;麻省理工学院计算机科学与人工智能实验室,马萨诸塞州剑桥02139;烟台大学计算机与控制工程学院,山东烟台264005【正文语种】中文【中图分类】TP391【相关文献】1.公路网上移动对象连续k近邻查询的一种方法 [J], 范平2.高度动态环境下移动对象连续K近邻查询算法 [J], 牛剑光;陈荦;赵亮;谭洁3.道路网中的移动对象连续K近邻查询 [J], 赵亮;陈荦;景宁;廖巍4.面向不确定移动对象的连续K近邻查询算法 [J], 于彦伟;齐建鹏;宋鹏;张永刚5.面向多核多线程的移动对象连续K近邻查询 [J], 赵亮;景宁;陈荦;廖巍;钟志农因版权原因，仅展示原文概要，查看原文内容请购买。

面向多核多线程的移动对象连续K近邻查询赵亮;景宁;陈荦;廖巍;钟志农【摘要】针对移动对象的多用户连续K近邻查询处理问题,结合多核多线程技术的发展,提出了一种基于多线程的两阶段多用户连续K近邻查询处理框架.将查询处理分为查询预处理阶段和查询执行阶段,分别执行数据更新任务和查询处理任务,每个阶段都设计了优化cache访问命中率,并利用多线程技术提高多用户连续查询处理并行性的方法及数据结构.提出了一种查询执行阶段的查询分组技术,利用查询之间的相关性提高了算法执行时内存访问的时间局部性.基于查询处理框架和移动对象内存格网索引结构提出了K近邻查询处理算法.充分的实验结果表明,采用了多线程和cache优化技术的连续查询处理框架与其他算法相比,在性能上具有较大优势,并且在不同核心数目的CPU平台下具有较好的性能扩展性.%To solve the problem of multiple continuous K nearest neighbor (KNN) queries over moving objects, considering the development of multi-core and multi-threading technologies, a two-stage framework is proposed for Multi-Threading Processing of Multiple Continuous KNN Queries (MPMCQ). This includes a preprocessing stage and a query execution stage to carry out the data updating task and the query execution task separately. In each of the stages, techniques are designed to optimize the cache access hit ratio and improve the parallelism through multi-threading. A query grouping technique in the query execution stage is proposed to improve the data temporal locality when accessing the memory. Thus, the cache hit ratio can be guaranteed. A KNN query algorithm is given based on the MPMCQ framework and the grid index for moving objects. Extensive experimentsare carried out to verify that by adopting the multi-threading and the cache optimization technologies, the proposed framework implements a much superior performance than other famous algorithms; moreover, it maintains excellent performance scalability when executed under different multi-core CPUs.【期刊名称】《软件学报》【年(卷),期】2011(022)008【总页数】11页(P1805-1815)【关键词】移动对象;连续K近邻查询;多核多线程;cache优化;查询分组【作者】赵亮;景宁;陈荦;廖巍;钟志农【作者单位】国防科学技术大学电子科学与工程学院,湖南长沙410073;空军装备研究院通信所,北京100085;国防科学技术大学电子科学与工程学院,湖南长沙410073;国防科学技术大学电子科学与工程学院,湖南长沙410073;海军工程大学电子工程学院,湖北武汉430033;国防科学技术大学电子科学与工程学院,湖南长沙410073【正文语种】中文【中图分类】TP311随着无线通信、计算技术、GPS空间定位等技术的快速发展以及众多具有定位功能的无线手持和车载设备的大量普及,在许多应用,如交通调度、救援服务及位置服务等领域,往往需要对大量的空间移动对象进行监控和管理.在移动对象管理技术研究领域,当前的研究热点逐步从最初的索引技术、单查询处理技术转移到多用户查询上,其中,对多用户连续K近邻(K nearest neighbor,简称KNN)查询技术的研究尤为突出[1-6].连续K近邻查询是指从提交查询时刻开始,不断地给出随着查询位置或者移动对象位置信息变化的K近邻查询结果.多用户连续 K近邻查询则具有以下特点[3]:需要处理多个长时间运行的查询;需要频繁计算并保持最新的查询结果;通常基于内存来处理大量的移动对象或查询的更新;目标是最小化CPU的执行时间或客户端服务器之间的通信代价,而不是单查询中通常的优化目标磁盘 I/O代价.根据算法优化目标的不同,可以将多用户连续K近邻查询的研究成果分为两类:(1)以优化算法的CPU 执行时间为目标:Xiong等人提出了SEA-CNN算法[1],通过引入查询搜索区域并利用共享查询执行思想进行多用户连续K近邻查询批更新处理;Yu等人提出的YPK-CNN算法[2]采用移动对象层次格网索引和查询索引以提高连续K近邻查询更新性能;Mouratidis等人提出的CPM算法[3]利用概念空间划分技术以支持多用户连续K近邻查询处理;(2)以优化客户端和服务器通信代价为目标:Hu等人[4]首次引入了通信代价这一优化目标,并详细讨论了计算移动对象安全区域的算法以减少位置信息的更新;Hseuh等人[5]进一步假设客户端具有一定的计算能力,通过维护位置信息表来减少更新.除了以上研究之外,文献[6]研究了道路网中的移动对象多用户K近邻查询问题,通过利用空间网络的相关属性和移动对象运动受限这一性质,减少连续查询的重复计算.总的来说,上述多用户连续K近邻查询处理技术多采用基于内存的查询处理框架,利用格网索引对移动对象进行存储和管理,通过研究不同的查询搜索策略减少对移动对象集的重复访问,并采用单线程的共享查询执行机制,提高多用户连续K近邻查询处理的整体性能.目前,随着内存与处理器中cache之间的速度差距越来越大,处理器等待cache从内存读取数据造成的延迟正成为数据库系统的主要瓶颈,尤其在多核处理器的多级存储体系结构下如何提高处理器中最下一级cache的数据缓存命中率,已经成为高性能数据库领域的研究热点[7].另外,传统单线程查询执行模式难以充分利用多核处理器的并行计算优势,因此,研究面向多核多线程的多用户连续 K近邻查询处理框架和算法已成为目前多核计算环境下的必然趋势.本文研究如何将多核多线程技术引入移动对象多用户连续 K近邻查询处理问题,希望从以下两个方面提高连续K近邻查询处理性能:(1)使用多线程并行处理技术;(2)设计相关方法提高cache访问命中率.为此,重点提出了一个基于多线程的多用户连续K近邻查询处理框架,设计了查询分组技术提高cache访问命中率,并提出了K近邻查询处理算法.本文第1节～第3节分别对应于上述关键技术.第4节为实验分析.第5节进行总结与展望.1 基于多线程的多用户连续K近邻查询的处理框架(multi-threading processing of multiple continuous queries,简称MPMCQ)已有的多用户连续 K近邻查询处理算法通常在内存中对移动对象进行格网索引,周期性地更新移动对象数据和查询的位置信息,并周期性地给出查询计算结果,通过维护每个查询的影响区域和重用中间结果来减少周期性计算中访问格网索引中单元格的次数,既没有考虑到在多核体系结构下如何使用多线程来提高算法的性能,也没有考虑如何通过提高内存中数据的空间局部性和时间局部性,进而改善cache访问命中率.基于上述认识,本文提出了一种基于多线程的多用户连续查询处理框架.与已有的移动对象连续查询处理技术相比,该框架采用多线程技术周期性地重复计算所有查询结果,力求利用多核处理器的并行处理能力提高连续查询处理的性能.如图1所示,MPMCQ框架将多用户连续查询处理分解为查询预处理(preprocessing)和查询执行(execution)两个阶段,在每一阶段中同时考虑如何提高 cache访问命中率和采用多线程提高多用户连续查询的并行性.只有当Preprocessing阶段处理完成后,才开始执行Execution阶段.Fig.1 Framework of MPMCQ图1 MPMCQ框架下面对各个阶段包含的子处理和数据结构进行详细说明.1.1 预处理阶段(preprocessing)在移动对象连续查询处理问题中,移动对象位置信息和查询的位置信息都是不断变化的.因此,需要对这些信息在查询处理之前进行更新,保证结果的即时性和正确性.即预处理阶段的目的是在周期性的查询计算时刻首先更新移动对象数据和查询信息,为查询执行阶段准备数据.图2为MPMCQ中预处理阶段的示意图,其中包含两个主要过程:更新查询表和更新移动对象格网索引.图2上半部分显示了更新查询表的过程,首先对两个查询计算时刻之间发生变化的查询信息进行排序,将排序结果放到查询缓存(query buffer)中;而后,线程调度器通过均匀划分所需处理的数据,调度多个更新线程,将查询更新到查询表中.移动对象更新的过程与之类似.Fig.2 Detailed explanations to the preprocessing stage图2 预处理阶段详细说明需要特殊说明的是:(1)根据查询的空间位置,利用空间填充曲线[8]对其进行排序,使得空间上位置相邻的查询在 buffer中存储时也保持相邻,目的是减少更新线程更新查询表和格网索引时的互斥访问,同时提高查询处理阶段多线程处理的cache访问命中率(第2节图4有详细解释);而对移动对象进行排序的目的是提高多线程索引更新时访问索引数据的时间局部性(即如果某一存储位置的数据被访问,则其可能被再次访问)和空间局部性(即如果某一存储位置的数据被访问,则其相邻位置的数据也可能被访问).(2)图 2中的查询缓存(query buffer)采用文献[9]提出的Parallel Buffer进行内存访问和管理,整块内存分成若干个Chunk,每个线程以Chunk为单位读/写内存,可以大大降低互斥访问代价.(3)预处理阶段包含的数据结构主要有: · 查询表(query table),基于内存的线性结构,用以存放用户提交的连续查询.记录形式为〈QID,Qloc,k,Range,InfReg〉.其中,QID为连续查询q的唯一标识;Qloc为当前更新时刻查询q的位置;k为查询q的近邻个数;Range为查询q的搜索半径;InfReg为查询q的影响区域(即上一周期的查询结果所在的单元格),形式为格网单元格标识的集合.· 格网索引(grid index),基于内存的格网结构.整个移动对象运动的空间划分为δ×δ个单元格,将移动对象根据其空间位置映射到单元格中.每一个单元格可表示为〈CellId,ObjectSet〉,其中,CellId为单元格的标识,ObjectSet为单元格中移动对象的集合;ObjectSet中每一个移动对象表示为〈OID,Oloc〉,OID为移动对象标识,Oloc为移动对象当前的二维空间位置信息.· 查询缓冲区(query buffer),基于内存的Parallel Buffer线性结构,用于缓存更新的连续查询.记录形式为〈OID,(xold,yold),(xnew,ynew)〉,其中,QID为连续查询q 标识,(xold,yold)和(xnew,ynew)分别表示查询q更新前和更新后的位置.· 移动对象缓冲区(object buffer),基于内存的Parallel Buffer线性结构,用于缓存更新的移动对象.记录形式为〈OID,(xold,yold),(xnew,ynew)〉,其中,OID 为移动对象标识,(xold,yold)和(xnew,ynew)分别表示移动对象更新前和更新后的位置.1.2 查询处理阶段(execution)查询处理阶段的目的是在获得前一个阶段准备的数据后,在已经更新了的查询数据和移动对象格网索引间进行连接扫描(即调用K近邻查询处理算法),获得多查询的结果.图3为MPMCQ中查询处理阶段的示意图,其中包含两个主要过程:对查询进行分组和调用查询处理算法.空间位置相邻的查询在调用查询处理算法时会扫描很多相同的移动对象格网索引中的单元格,将空间位置相邻的查询分组后,有利于提高查询算法调用时访问格网索引数据的时间局部性.分组后,线程调度器调用多个查询线程在格网索引和每个查询分组之间进行连接扫描,最终得出多用户查询的结果.查询处理阶段包含的数据结构主要有:查询工作集(query set),基于内存的Parallel Buffer 线性结构,用于存放查询分组集合;每一个查询分组用一块chunk存储,其记录形式为〈CID,(QID,Qloc,k,InfReg,Results,Range),…〉,其中,CID为该内存块chunk的标识;每个形为(QID,Qloc,k,InfReg,Results,Range)的元组存放了该工作集中的一个连续查询信息,Results用以存放查询q的结果集,其他属性含义与查询表中查询的对应属性一致.Fig.3 Detailed explanations to the query execution stage图3 查询执行阶段详细说明2 查询分组技术MPMCQ框架在预处理阶段对查询利用空间填充曲线(hilbert curve)[8]进行了空间重排序,并将其存入查询表中.Hilbert Curve能够很好地保持查询位置的空间临近性,使得空间位置相邻的查询在存储时也是相邻的.如图4所示,如果按照查询更新的顺序,应该是从q1到qn的存储顺序,经过Hilbert Curve排序后,则按照空间位置从q2,q1,…,qn,qk的顺序存储.这种处理使得在调用查询处理算法时,算法遍历格网索引中的移动对象时能够保持较好的时间局部性.即处理 qn时访问的单元格中的移动对象在处理 qk时能够继续被访问,因而提高了 cache访问命中率.Fig.4 Sorting the queries by Hilbert curve图4 Hilbert曲线对查询排序但是,这种简单的处理并不能很好地利用查询之间的相关性,从而进一步地提高格网中移动对象访问时的时间局部性.如图5所示,给定连续K近邻查询q和q′,图5(a)阴影区域所示为q在计算K近邻时所需要访问的7个格网单元;在同一时刻用户提交连续K近邻查询q′,如图5(b)所示,斜线阴影区域为q′的影响区域,即q′需要搜索访问5个格网单元.q和q′的影响区域是部分重叠的,意味着处理q和q′时很可能需要搜索同样的单元格.如果将具有重叠搜索区域较多的查询分为一组并以多线程处理时,重用数据非常多,cache访问冲突较少,进而能够提高cache访问命中率. Fig.5 Influence region of CKNN query图5 连续K近邻查询影响区域采用模式识别技术中经典的聚类算法——ISODATA算法[10]对查询进行分组.与大多数聚类方法以欧式距离为相似性测度不同,在本文的查询分组中,定义查询相似性函数 s(qm,qn)为查询 qm和 qn的影响区域重叠部分的格网单元格数.具体来说,s(qm,qn)可表示为接下来讨论算法中7个初始参数设置.表1列出了聚类算法中参数设置使用的符号及其含义.(1)预期的组个数NG、初始分组中心个数Nc、每组中允许的最少查询个数Nq 查询分组是为了提高访问移动对象索引时,对索引中移动对象数据的 cache访问命中率.由于多核处理器一般共享最下一级高速缓存,最多将C/To个移动对象装入cache中.每个K近邻查询至少需要访问K个移动对象数据才能获取正确的查询结果.因此,每组中最大的查询个数为C/(To×K).从而设置:Table 1 Symbols and their meanings used in the clustering algorithm表1 聚类算法中使用的符号及其含义Symbols Meanings C L2 cache size To Size of each moving object tuple δ×δ Total cell numbers Sumq Total query numbers(2)组内查询分布的标准差下限θs和两组中心间的相似性上限θD对于第j个查询分组来说,其组内查询分布的标准差用下式进行计算:其中,Nj表示第j个分组的查询个数,qj表示其组心.σj的值表示组的聚类程度.标准差下限θs表示如果σj＜θs,则该组需要分裂为两组.对第i和第j个分组来说,其组心间相似性用下式计算:其值表示两组的相似性程度.两组中心间的相似性上限θD表示,如果dij＞θD,则第i 和j组需要合并为一组.假设移动对象在运动空间中均匀分布,每个单元格平均包含No/δ2个移动对象,则对每个 K近邻查询来说,至少访问K×δ2/No个单元格才能获得正确结果.θs越小且θD越大,则分组速度越快,但分组效果较差.为此设置:(3)每次迭代中可以合并的组的最多对数L和允许的最多迭代次数I在聚类算法中,这两个参数主要用来控制聚类算法的运行时间.当然,迭代次数越多分组效果越好.由于ISODATA算法本身计算较多,希望能够快速完成聚类.为此,设置最多对数L为1;设置最大迭代次数I为3.通过实验发现,将迭代次数控制较低时,也即聚类算法耗时较少时,能够带来较好的框架执行性能.3 K近邻查询处理算法MPMCQ框架在查询处理阶段调用多个线程执行 K近邻查询处理算法得到每个查询的结果.其主要思想是:针对预处理阶段生成的查询分组(query group)任务队列,算法从队列中拾取查询分组分配给线程池中的空闲工作线程进行处理,查询分组中的多个查询在多线程之间均匀分配,即每个线程处理一个查询分组的子集QGsub. K近邻查询处理算法的基础是首先对移动对象进行格网索引.假设移动对象的运动空间为单位正方形区域,将该区域划分为δ×δ个单元格,则第 i行第 j列的单元格 cij 包含横坐标范围为[i⋅δ,(i+1)⋅δ]且纵坐标范围为[j⋅δ,(j+1)⋅δ]的移动对象.反之,坐标为(x,y)的移动对象存储在第行、第列的单元格中.表 2 对下面的描述中常用的符号和函数进行了说明.Table 2 K近邻查询算法中的符号和函数说明表2 Symbols and functions used in the KNN query algorithmSymbols Descriptions dist(p,q)The Euclidean distance between p and q Results q’s result list InfReg q’s influence region Range The distance between the kth nearest neighbor and q mindist(c,q)The minimal distance between cell c and q令Results为当前查询q的K近邻结果集,Range为当前第K个最近邻距q的距离.如果某一单元格c距q的距离mindist(c,q)≥Range,则该单元格c肯定不包含查询q的K近邻,从而不用遍历c中的移动对象.因此,一种自然的算法是根据单元格c 到查询q的最短距离,由小到大排序.对于序列中的单元格,遍历其中的移动对象,计算dist(p,q)并更新Results和Range,直到序列中某一单元格距q的距离大于Range为止.这种最直观的方法需要计算所有单元格与查询之间的最短距离并排序,效率很低.由于采用多线程来进行查询处理,因此没有像CPM算法那样考虑计算结果的重用减少查询的重复计算,而是对每个查询都周期性地重新计算查询结果.因此,设计了一种相对于CPM算法来说,具有简单数据结构的K近邻的算法.基于移动对象格网索引的K近邻查询处理算法可用图6进行阐释.以计算查询q的3近邻为例,说明算法的运算过程.在遍历格网索引时,首先搜索查询q所在单元格,如果当前单元格不足3个移动对象,则搜索以所在单元格为中心的周围的其他8个单元格,此时,算法找到了3个最近邻;然后,在与以当前结果集中的最大距离为半径圆相交的单元格中继续搜索找到正确的第3个近邻,即图中p1,p2,p4为实际的查询结果.Fig.6 Explanations of the KNN query algorithm图6 K近邻查询算法说明在查询执行阶段,将多个查询均匀划分给多个线程执行.对每个查询来说,具体的算法如下:算法分4个步骤,对每一个查询qi,算法第1步需要找到围绕qi的K个移动对象,并将这些对象所在单元格加入临时列表中(第2行、第3行);第2步计算临时列表中所有移动对象到查询qi的最远距离(第4行);第3步将与以 qi为圆心、最远距离为半径圆相交的格网加入临时列表(第 5行);最后,从临时列表中计算查询 qi的 K近邻并更新查询的影响区域(第6行).4 实验结果与分析利用大量并发的连续K近邻查询来评估MPMCQ框架的性能.首先介绍实验采用的硬件环境:采用了3种不同的CPU平台:单核CPU为Intel Celeron 3.2GHz、双核CPU为Intel Pentium Dual E2200 2.2GHz, 1MB L2高速缓存、四核CPU为Intel Core 2 Quad Q8200, 4MB L2高速缓存.内存均为1GB.操作系统均采用Windows XP SP2.使用Visual Studio 2005开发环境,采用C++语言实现了本文提出的算法.使用随机生成的数据来进行性能测试.移动对象在运动空间为1×1的单位正方形内均匀分布.移动对象和查询数据的更新周期为10s,两次查询执行的间隔为30s.具体的参数设置见表3.Table 3 Experimental parameters表3 实验参数Parameters Default value Optional values Numbers of moving objects (N)500K 250K, 500K, 750K, 1 000K Numbers of queries (Q)20K 10K, 15K, 20K, 25K Value of k 16 1, 4, 16, 64, 2564.1 MPMCQ框架与其他算法的比较实验在双核CPU平台上比较YPK-CNN,CPM,MPMCQ这3种计算框架的性能.由于3种机制都是基于内存的算法,因此比较的性能指标采用执行一个处理周期(包括数据更新和查询处理)的 CPU时间.其中,MPMCQ框架中的多线程操作设置为两个线程,采用运行10个周期求平均的方法得出性能指标;YPK-CNN和CPM算法均采用单线程处理方式.格网索引设置为1000×1000大小.如图7所示为各种算法的计算时间随着移动对象数目、查询数目、近邻个数的变化而变化的情况.从图中可以看出,MPMCQ框架和CPM[3]算法在3种情况下的性能指标均优于YPK-CNN[2]算法.这是由于YPK-CNN算法当移动对象更新后位于查询影响区域之内时立即对查询进行更新,极大地降低了查询更新性能.CPM 算法则优化了查询更新算法,在查询或移动对象更新时只需访问最少的格网.随着数据规模的增加,MPMCQ框架中多线程和cache优化的性能优势逐步体现得比较明显.能够看出,MPMCQ框架的性能明显优于CPM算法.这是因为相对于其执行代价来说,无论是排序优化还是查询分组优化都能带来更大的性能提升.事实上,CPM算法的共享查询特性使其具有非常好的查询性能,且其性能随着数据量的变化并不会明显地恶化.而 MPMCQ框架中的 cache访问优化技术和多线程技术的使用,一方面提高了内存数据访问时的数据空间局部性和时间局部性,保证了cache访问命中率;另一方面,多线程的使用切实利用了多核CPU的并行计算能力.在如图7所示的3种不同情况下采用最大数据量时,MPMCQ框架相对于CPM算法的性能提升分别为48%,21%,17%.Fig.7 Effects of data amount to the query performance of different algorithms图7 数据量的变化对各种算法性能的影响4.2 MPMCQ框架在不同处理器平台下的性能本节测试MPMCQ框架在不同处理器平台下的性能.在MPMCQ框架中的移动对象更新、查询更新和K近邻查询处理3个操作设置为多线程执行,以上3个操作是一种顺序执行的关系,在框架中依次执行.同样,采用运行10个周期求平均的方法得出性能指标.首先,使用默认参数测试不同处理器平台下,MPMCQ框架的性能随着算法中线程数设置的不同而变化的情况.如图 8所示,在单核平台上,多线程执行并没有带来性能的提升.相反,随着线程数目的增加,算法的执行时间略微有所增长.这主要是因为单核平台上的多线程执行并不是真正意义上的并行执行,线程之间的频繁交互导致性能降低;在双核平台上,多线程执行在性能上具有比单线程明显的优势,当线程数大于 2(核的数目)且为奇数时,由于处理器核心之间负载不均衡,导致性能下降.但随着线程数的增加,单个线程数据量变小,负载不均衡的程度也随之降低,性能有所回升.但总的来说,在线程数等于核心数时,多线程执行性能最高;在四核平台上,得到了与双核平台类似的结果.其次,使用默认的查询16近邻,测试在双核和四核平台下,分别设置MPMCQ框架中执行线程为2和4时,MPMCQ框架性能随数据量的变化而变化的情况.如图 9所示,在不同数据量的情况下,四核平台具有更好的查询性能,体现了MPMCQ框架较好的扩展性.Fig.8 Effects of thread numbers to the performance图8 线程数对性能的影响Fig.9 Effects of data amount to the performance under different platforms 图9 不同平台下数据量对性能的影响4.3 Cache访问性能优化本节在双核平台上测试采用cache优化前后MPMCQ框架的执行性能,以验证MPMCQ框架中提出的排序优化和查询分组优化对提高cache命中率的作用及对整个框架执行性能的影响.采用Intel VTune V8.0.014版本记录cache缺失次数. 图10和图11分别显示了随着移动对象数据量的变化,采用cache优化前后框架的执行性能和平均每个查询的cache缺失次数.在实验中仍使用多线程进行更新和查询处理操作.从结果来看,采用cache优化前后的性能平均提高了23.3%,且能够明显降低cache缺失次数.Fig.10 Performance before and after cache optimization图10 采用cache优。