动态确定K值聚类算法的R-树空间索引构建

目前采用的R-树空间聚类技术使用指定k值的聚类算法,初始聚类中心随机或指定选取。这样聚类的结果受初始k值影响,且易受离群空间数据的干扰。为解决上述问题,根据空间数据分布的特点,提出了动态确定k值的空间聚类算法(dynamical k-value spatial clustering algorithm,DKSC)。该算法通过聚类划分空间数据,把同一子空间的数据组织在同一个子树下,从根节点到叶子节点逐层构建R-树,形成高效的R-树空间索引。分别用真实和模拟的空间数据集进行了实验,结果表明该算法优化了构建的R-树空间索引,且具有更高效的查找效率。     

一种基于R-树的空间索引结构

为了有效构建R-树,通过分析数据矩形的性质,结合改进的K-均值算法,提出一种用于构建R-树的数据矩形聚类新方法,给出基于R-树和四叉树的空间索引结构以及该空间索引结构的构造算法和节点插入算法。研究结果表明,该索引结构具有更紧凑的结构和更高的空间查询效率。     

带聚类的Hilbert R-树建树算法

本文提出了一种新的建立在一维聚类上的建树方法.该算法改变了原来Hillbert R-树建树方法中的机械填充方式,通过在数据的Hilbert值集合中进行的聚类而对叶子节点中的数据进行优化组合从而得到了更小的叶子节点,提高了检索的效率.实验表明,特别对于分布不均匀的数据,该算法在有限增加计算复杂度的前提下可以大大提高检索效率.     

QR-树:一种基于R-树与四叉树的空间索引结构

提出了一种基于R-树与“四叉树”空间层次划分的空间索引结构QR-树,给出了其数据结构和算法描述。实验证明:与R-树相比,QR-树以略大(有时甚至略小)的空间开销代价,换取了更高的性能,且索引目标数越多,QR-树的整体性能越好。     

一种基于混合聚类的空间索引算法

R-Tree允许兄弟节点之间的相互重叠,具有多路查找的特点,而Hilbert R-Tree也不能有效降低子空间的相互重叠,直接影响查询效率。提出了一种基于混合聚类的空间索引算法,将K-means和K中心点引入索引结构,改变了经典K-means算法对初始聚类中心的随机选取,减少了叶节点的MBR面积和各个子空间的重叠。通过实验表明,该算法具有更快的响应速度和查询效率。     

一种新的通用聚类索引树及其相似检索算法

1.引言数据库的查询操作一般依赖于物理层的特殊算法的支持,尤其在许多面向对象和空间数据库的应用领域,如在文献数据库、多媒体数据库、金融数据库、CAD数据库等的检索操作中,都需要特殊检索算法支持对象的相似检索。数据库中的对象常常用高维特征矢量表示,因此对象的相似检索问题实际上归结为高维特征矢量的相似检索问题。由于用于表示对象的多维特征矢量的维数一般都很高(从几十到几百都是可     

基于聚类的空间数据多比例尺索引树

针对现有空间对象多尺度索引结构聚簇性不高的问题,在R树索引的基础上提出一种基于聚类的空间数据多比例尺索引结构。利用树的层次结构反映空间数据的多比例尺特性,用k-means算法对相同等级的空间对象进行聚类分组,减少空间区域覆盖和重叠。实验结果表明,该方法与基于四叉树的多比例尺索引相比,能有效提高空间数据多比例尺显示的性能。     

树型空间索引及其在聚类中的应用研究

对大型高维数据集进行高效的聚类分析已成为许多领域的迫切需要,但是一般的聚类技术在处理高维数据时性能低下。树型空间索引可以高效地组织并检索高维数据,因此使用树型空间索引是改善聚类性能的有力途径。该文介绍各种树型空间索引的结构,并对它们的性能加以分析,接着讨论树型空间索引在聚类分析中的应用,并提出将树型空间索引与聚类技术相融合的思想。     

一种基于子空间聚类的图像分层索引方法

随着多媒体技术的发展,许多领域产生大量的高维数据集。为了有效地检索这些高维数据,高维索引成为人们研究的热点。聚类树是一种有效地支持高维数据检索的索引结构。提出了一种基于子空间聚类的聚类树结构,该索引结构基于一种改进的CLIQUE聚类算法,利用小波变换的多尺度特性对图像特征分布曲线进行不同尺度的小波变换,去除一些小的分类和可能的噪声干扰,从而得到不同粒度下的层次聚类。在层次聚类的基础上,建立起分层索引结构。由于改进的聚类算法使用爬山法确定子空间聚类,因而有效地避免了用户参数的定义。实验结果证明,该方法在不需要用户设定聚类参数下能够进行有效聚类,在不同尺度下构建的聚类结构能够有效地组织图像关系,大大提高图像的检索效率。     

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n~(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。     

一种基于R-tree的空间索引方法

为进一步提高R-tree的空间索引数据检索性能,提出一种基于R-tree的MRD-tree索引,它的结构中包含空间对象的外部近似图形和内部近似图形,同时允许数据入口存放在中间结点。在检索时既能减少I/O次数,也能相对减少一定的CPU时间。通过实验分析,该索引能提高空间数据的检索效率。     

基于CURE聚类算法的静态R树构建方法

R树索引结构在空间对象查询和复杂空间关系查询方面具有重要作用。传统空间索引结构R树是动态生成的,树的结构是根据连续插入算法实现的,通过分裂子节点直至生成R树的根节点。动态生成算法会导致R树节点最小外包矩形之间的大量重叠,影响空间查询效率,且空间利用率不高。为了弥补动态生成R树的不足,提出了基于CURE算法的静态R树生成方法,给出CU_RHbuilt建树算法,该算法不仅能有效地处理海量数据,识别任何形状的簇,减少矩形重叠度,而且采用划分技术可较大程度地减小计算代价,空间利用率较高。进一步提出了基于CURE算法的R树节点分裂方法。理论研究与实验表明,所提方法具有较高的查询效率。     

基于主存R树的空间连接的实现

空间查询效率是衡量数据库性能的关键，而空间连接查询是最耗时、最重要的空间查询。对几种典型的空间连接方法作了简单回顾，并具体给出了基于R树的空间连接算法(RJ)在空间数据库管理系统SADBS中的实现。     

基于分区技术的静态R树索引并行计算技术

海量空间数据静态R树索引的加载时耗很大。该文利用关系数据库的优势,以空间数据分区存储技术为基础,提出针对自上而下的贪婪分裂算法的静态R树并行加载方法。该方法提高了海量数据批量加载效率,支持分区粒度的索引重建。论证与实验结果表明,并行构建的R树在合理空间数据分区下可以获得更高查询效率。     

基于空间和属性数据的联合索引技术

传统联合查询通常需要空间数据库对2个索引进行检索,通过集合运算得到最终结果,运算效率较低。针对该缺陷,提出基于空间和属性数据的联合索引技术,在索引目录项中加入属性数据提高联合检索速度。实验结果表明,该技术对于属性与空间位置有较高相关度的数据,具有较高查询效率。     

基于动态R-树结构的DDM区域匹配算法

分析了传统数据分发管理(DDM)匹配方法,结合空间索引技术的特点,提出了一种动态R-树区域匹配方法,通过建立R-树对公布和订购区域进行组织管理,并在R-树上实现订购区域与公布区域的匹配搜索。仿真实验结果表明,选取适当参数M,可减少动态R-树DDM匹配算法的时间开销,达到较优性能。