基于kd树的多维索引在数据库中的运用

Kd- Tree-Based Multi-Dimensional Indexing in the Database Application

吴涵 杨克俭

该文突破在数据库查询中建立传统索引进行数据的查询，而是针对微型数据库引擎的设计中要实现的嵌套查询和多表连接查询引进了kd树，kd树在B＋树的基础上进行了改进，从而来加快查询速度。该文介绍了kd树的结构、kd树的操作以及其实现的查询。

基于形状特征k-d树的多维时间序列相似搜索

Similarity Search Based on Shape k-d Tree for Multidimensional Time Sequences

黄河 史忠植 郑征

多维时间序列是信息系统中一类重要的数据对象，相似搜索是其应用的一个核心,两个序列（子序列）相似度加以比较的常用方法是：将序列（子序列）转换成空间中的曲线，然后计算曲线间的欧几里德距离．这种方法的主要缺陷是它仅考虑了序列（子序列）间的整体距离关系，而不能体现它们自身的局部变化．针对此问题，提出了一种新的可应用于多维时间序列的快速相似搜索方法．该方法将序列（子序列）的局部变化特性与检索结构（k-d树）结合起来，使得在搜索k-d树的同时实现了序列（子序列）的局部变化匹配，从而极大地提高了查询效率和正确率．实验结果表明了算法的有效性。

例题49 利用Java Applet之问的通信实现KD树算法的演示

陈鹏

本文重点介绍了用Java applets通信编写KD树算法演示方法和并提供了具体实例。

一个适用于内存数据库系统的多维索引结构

马洪连 杨波 姚建伟

树形结构一直都是数据库系统中建立多维索引最有效的方法之一，其中比较流行的有k-d树，R树等。但是对于内存空间极为宝贵的内存数据库来说，它们都有浪费内存的缺点。而T树作为内存数据库最常使用的一维索引结构，具有存取速度快，节约空间的优点，但是对于多维索引的情况它的效率却不高。该文首先介绍了k-d树，R树的特点及缺点，然后介绍T树的特点，操作和在多维条件下的缺陷，并提出了一种网格+T树的结构对其进行改进，从而使它适用于多维索引的情况。

基于多维二进制搜索树的异常检测技术

Anomaly detection technology based on multidimensional binary search tree

仇明华 殷丽华 李斌

将多维二进制搜索树（kd树）应用于异常检测,用kd树对网络数据进行组织、建立用户轮廓并以此为基础实现了一个异常检测系统,通过实验给出了系统对不同种类攻击的检测效果。实验结果表明,kd树在异常检测中具有很高的适用性。

3D GIS空间索引技术研究

Study on Spatial Indexing Techniques for 3D GIS

郑坤 朱良峰 吴信才 刘修国 李菁

概括并分析3DGIS中使用的空间索引技术，介绍各类技术方法的基本思想；对典型的空间索引方法进行分类，综合比较其优缺点和适用对象；按照空间分割方式将三维空间索引分为规则分割和对象分割两大类，规则分割包括规则网格、BSP树、八叉树、KD树、KDB树和R树系列等，对象分割则通过层次包围体来实现。指出在3DGIS实际应用中，应根据实际情况和应用需要组合多种索引技术，进而生成灵活、高效的索引机制。

一种新的移动机器人全局定位算法

A Novel Algorithm for Mobile Robot Global Localization

厉茂海 洪炳熔 蔡则苏

粒子滤波器能够给出移动机器人全局定位非线性非高斯模型的近似解．然而，当新感知出现存先验概率的尾部或者与先验相比感知概率太尖时，传统的粒子滤波器会退化导致定位失败．本文提出了一种重要性采样跟中心差分滤波器（central difference filter，CDF）相结合的新算法，并对测量更新步的加权粒子集应用基于KD-树的加权期望最大（weighted expectation maximization．WEM）自适应聚类算法获得表示机器人位姿状态后验密度的高斯混合模型（Gaussian mixture model．GMM）．实验结果表明，新方法提高了定位准确率，降低了计算复杂度．

基于特征点的最近邻配准算法

Image Registration by NN Based on Features

戚世贵 戚素娟

利用尺度不变特征点的提取方法提取特征点，并对SIFT方法提取出的特征点用最近邻算法进行配准，在搜索最近邻特征点和次近邻特征点时使用了在K-D树搜索算法基础上进行改进的搜索算法BBF（Best Bin First）算法。实验证明该算法具有配准精度高，鲁棒性好的特点。

基于k-d树的k-means聚类方法

孙总参 陶兰 齐建东 王保迎

在直接k-means算法的基础上提出了一种新的基于k-d树的聚类方法。通过把所有的对象组织在一棵k-d树中，可以高效地发现给定原型的所有最近邻对象。利用的主要思想是：在根结点，所有的聚类中心(或称为候选原型)都是所有对象的最近邻候选集合，对于根结点的子结点，通过简单几何约束来剪枝该候选集，这种方法可以被递归使用。使用基于k-d树的方法可以使直接k-means算法的总体性能提高一到两个数量级。

基于相对距离的密度聚类算法

Density of clustering algorithm based on relative distance

何孝金 傅彦 陈安龙

首先介绍传统距离计算方法在聚类应用中的不足，并针对这点提出一种基于权重向量的相对距离计算方法。在应用DBSCAN算法的基础上，融入相对距离的计算及k-d树的范围查找的应用。该算法不仅能得到很好的聚类效果，而且消除了数据的度量单位对聚类结果的影响。