空间相似查询中MBR边界区域关系研究

相似查询是基于向量空间的一种重要查询方法。点、线段、区域是向量空间对空间对象的三种基本表达。本文在不改变结点MBR区域前提下,通过区域扫描对MBR区域重叠面积进行计算。利用R*树结点MBR允许重叠的特性,在不能消除区域重叠产生的死空间情况下,研究了更为精确的MBR边界的线段关系,并给出线段的最近邻查询算法和相似线段选取算法。实验结果表明该方法的CPU计算代价较低且显著提高了相似查询与更新的效率。     

R*-树结点多目标遗传分裂算法

R*-树可有效地提高散乱点云、网格曲面等数据的处理效率.为提高R*-树结点空间利用率,将结点分裂过程视为多目标优化问题,采用遗传多目标优化求解结点分裂的近似全局最优解集;以结点最小外接矩形的重叠度和体积作为评价标准选取最佳分裂方案,实现R*-树的结点最优分裂.实例结果证明,该算法可实现各类复杂几何对象的R*-树结点分裂问题,并有效地降低R*-树结点分裂的参数依赖性,提高R*-树空间数据的查询效率.     

基于QCR-树的空间索引方法

QR-树处理海量空间数据时,其深度和R-树内目录矩形的重叠面积会变大,导致查询效率降低。针对该问题采用K-means算法对索引对象进行聚类分析,构造新的聚类中心使其能处理具有多种形体的索引对象,并在QR-树中引入超结点存储聚类结果。提出一种QCR-树空间索引结构来提高查询效率,给出QCR-树的插入、删除和查询算法。实验结果表明QCR-树的查询性能优于QR-树,适用于海量数据。     

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

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

基于空间填充曲线网格划分的最近邻查询算法

在建树过程中,R树存在最小边界矩形之间重叠的现象。当数据量较大时,重叠现象尤为严重,基于R树最近邻查询算法的性能急剧恶化。针对该问题,利用空间填充曲线的降低维度特性和数据聚类特性,提出一种基于网格划分最近邻查询算法。该算法将整个数据空间划分成大小相等、互不重叠的网格,对网格中的点进行线性排序之后,只需要访问查询点所在网格中的点及其周边邻近网格中的点,就能够获得最近邻。在Hilbert曲线、Z曲线和Gray曲线上实现3种最近邻查询算法,在映射算法和数据聚类特性上实验比较3种曲线之间的性能差异。实验结果表明,算法的查询性能明显优于顺序扫描算法和基于R树的最近邻查询算法。     

基于聚类的Hilbert R-树空间索引算法

R-树适合于动态索引,但空间重叠大,而Hilbert R-树也不能有效降低节点覆盖和交叠,直接影响R-树的查询效率。为适应大量的GIS查询应用需要,提出对Hilbert R-树节点进行聚类的索引算法,较好地解决相邻数据的聚类存放,使叶节点MBR面积减小,内部节点交叠降低,并对该算法进行实验测试和性能分析,结果表明该算法具有较高的查询效率。     

一种基于参考点和密度的快速聚类算法

数据的规模越来越大,要求数据挖掘算法有很高的执行效率.基于密度的聚类是聚类分析中的一种,其主要优点是发现任意形状的聚类和对噪音数据不敏感.提出了一种新的基于参考点和密度的CURD(clustering using references and density)聚类算法,其创新点在于,通过参考点来准确地反映数据的空间几何特征,然后基于参考点对数据进行分析处理.CURD算法保持了基于密度的聚类算法的上述优点,而且CURD算法具有近似线性的时间复杂性,因此CURD算法适合对大规模数据的挖掘.理论分析和实验结果也证明了CURD算法具有处理任意形状的聚类、对噪音数据不敏感的特点,并且其执行效率明显高于传统的基于R*-树的DBSCAN算法.     

基于直角多边形的R树结点的分裂算法

对于空间查询来说,目标近似是一个非常重要的问题.在R树中常用的是最小包围矩形(MBR),但是它的近似精度不是很高,因此用直角多边形来近似空间对象可以提高近似的精度.文中主要探讨了结点是直角多边形近似的R树的结点分裂算法.     

近似查询中重叠区域的扫描计算

根据R*树节点硬盘主引导记录(MBR)特征,在不改变最小外包矩形特征的前提下,通过区域扫描对正交MBR重叠区域边界建立二叉线段树,以此为基础分别计算面积和周长,有效改善了R*树节点结构。理论分析和实验均表明,与未经过重叠区域计算的R*树相比,经计算的R*树节点比较次数平均下降了近60%,准确率提高了约60%。     

TPR-树性能优化研究

为了降低TPR-树的时间复杂度、提高查询效率,提出结点分裂的改进算法及基于距离的结构调整策略.改进算法把TPBR(time-parametedzed bounding rectangle)在某时阃段内的周长定积分作为代价函数,并在投影定积分值最大的轴上进行结点分裂,做到了同时兼顾移动对象的空间属性与速度属性.在结构调整策略中通过删除结点中移动距离超过阈值的记录,从而使TPBRs的扩张速度变慢,在一定程度上抑制了TPBRs之间的重叠.实验结果表明,与原TPR-树结点分裂算法相比,改进后的结点分裂算法的运行时间降低了5～8倍,查询性能至少提高了50%,而且,在此基础上应用基于距离的结构调整策略使查询性能进一步提高约10%.     

基于路网的LBSN用户移动轨迹聚类挖掘方法

基于LBSN（基于位置的社交网络）中数据的地理和社交属性, 结合用户轨迹和好友关系, 有助于提高不确定轨迹聚类挖掘的效率。根据LBSN用户的好友关系特征, 引入评分函数, 对用户影响力进行排序, 找出其中的活跃用户; 在传统路网子轨迹匹配和对签到数据清理的基础上, 加入子轨迹匹配准确性监测, 并存储活跃用户匹配成功的路段, 进而减少路网匹配时间。最后综合R*树的空间索引机制和DBSCAN聚类算法对城市内的热点路径进行挖掘。理论分析和实验表明, 相比于已有方法, 改进的的聚类挖掘方法在LBSN环境中的时间效率和准确性都有较大的提高, 且有较好的可伸缩性。     

基于Voronoi图的障碍不确定数据的聚类算法

数据采集过程中普遍存在不确定性,并且在现实地理空间中,不确定数据之间可能存在障碍物间隔。为解决障碍空间中不确定数据的聚类问题,提出APPGCUO算法,该算法包括三个过程:在障碍物约束下采用R树节点最小最大值方法提出的RPT-OUCure算法,用以生成局部最优解,提高生成局部最优解的效率;继而利用近似骨架的理论提出GIABO算法,以局部最优解生成有效初始解,避免划分聚类算法中任意初始解的不足;最后结合Voronoi图的特性提出VPT-KMediods算法,减少不确定数据的积分运算量。实验结果表明,APPGCUO算法具有较高的聚类效率和质量。     

基于惰性聚类分裂的动态R树实现方法

R^＊树是目前公认查询效果很好的R树变体，但是其构造代价较原始R树增加数倍，对于插入删除和更新频繁的空间数据效果不好。为此，本文提出一种基于惰性聚类分裂技术的R树动态实现方法（LR树）。惰性聚类分裂技术是在对象插入节点导致溢出时不立即进行分裂，而是尝试将其插入到邻近的未满节点中，直到邻近节点均已满时，再利用聚类技术进行节点分裂，在邻近节点和分裂节点之间重组入口项。LR树在确保查询性能的前提下，大大降低了构造代价，并且大幅提高了索引结构的空间利用率。最后的分析和实验证明了LR树的高效性。     

多维向量动态索引结构研究

多维向量的索引技术是多媒体数据库系统中的关键技术之一.集中研究基于向量空间模型的动态索引结构,以解决在图像数据库系统中按内容快速检索图像的对象问题.在分析研究R-Tree和R*-Tree的基础上,提出了ER-Tree动态索引结构.该索引树用超球体划分多维向量空间,以有利于计算最近邻;吸取R*-Tree树的重插技术,以增强索引树对数据集整体特征的表达能力,从而提高检索效率;通过引入插入安全点和删除安全点概念,有效地提高建树的效率.同时,给出了基于该结构的特征向量插入算法.实验结果表明,所提出的索引结构建树的     

基于频繁模式树的AOI聚类算法

为了克服KM-AOI算法聚类效率较低的缺点,提出了基于频繁模式树的AOI聚类算法,即在聚类过程中借助频繁模式树,采取分而治之的策略处理警报集以得到规则。然后举例说明了利用该算法进行聚类的过程。实例表明,该算法能够明显提高聚类的效率。     

一种基于Tabu搜索的模糊聚类方法

首先,对模糊C 均值聚类算法做了简要分析和评论,在此基础上,将Tabu搜索引入模糊聚类,以克服模糊C 均值聚类的局部性和对初始聚类中心的敏感性,采用了适合于模糊聚类的树型编码方案。然后,给出了新算法的实现方法及步骤。仿真实验表明,新方法在速度和解的质量方面都达到了令人满意的效果。     

Clustering in very large databases based on distance and density

Clustering in vergy large databases or data warehouses,with many applications in areas such as spatial computation,web information coollection,pattern recognition and econmic analysis,is a huge task that challenges data mining researches.Current clustering methods always have the problems:1)scanning the whole databased leads to high I/O cost and expensive maintenance(e.g.,R^*-tree);2)pre-specifying the uncertain parameter k,with which clustering can only be refined by trial and test many times;3) lacking high efficiency in treating arbitrary shape under very large data set environment.In this paper,we first present a new hybrid-clustering algorithm to solve these problesm,This new algorithm,which combines both distance and density strategies,can handle any arbitrary shape clusters effectively.It makes full use of statistics information in mining to reduce the time complexity greatly while keeping good clustering quality.Furthermore,this algorithm can easily eliminate noises and inentify outliers.An experimental evaluation is performed on a spatial database with this method and other popular clustering algorithms(CURE and DBSCAN).The results show that our algorithm outperforms them in terms of efficiency and cost,and even gets much more speedup as the data size scales up much larger.     

基于R树的空间数据索引技术的探索

目前,基于空间数据库管理系统的空间数据索引技术的研究与应用正不断地兴起,且日趋成熟。分析经典的空间数据索引技术R-树和R^＊-树的优势与特点,在R^＊-树索引结构的基础上融合了传统的四叉树索引方法的精髓,提出了一种改进的R^＊-树索引技术一即R^＊Q-树索引方法。设计并实现了R^＊Q-树索引方法中索引构造算法的主要改进部分,并采用大量的随机实验数据验证了改进算法对提高空间数据索引效率的有效贡献。     

宽度优先反复加宽及其启发式搜索算法研究

首先针对搜索树中深度固定且目标唯一的寻优问题，指出宽度优先反复加宽的搜索效率要比深度优先反复加深的搜索效率高，基于此，提出了基于宽度优先反复加宽的启发式搜索算法ＩＷＡ＊，算法ＩＷＡ＊是可采纳的。为了保持算法ＩＷＡ＊的搜索效率高于算法ＩＤＡ＊的搜索效率，同时又使算法ＩＷＡ＊的存贮空间复杂度减低，文中基于分层技术，提出了基于深度优先的ＩＷＡ＊算法──ＩＤＷＡ＊。算法ＩＤＷＡ＊也是一个可采纳的启发式搜索算法。     

一种基于网格和最小生成树的数据流聚类算法

针对CluStream算法对非球状簇聚类的不足,同时基于均匀网格划分的聚类算法多数是以降低聚类精度为代价来提高聚类效率,给出了一种新的数据流聚类算法一GTSClu算法,该算法是基于网格的最小生成树(MST)数据流聚类算法.算法分为在线处理与离线聚类两部分,并运用了网格拆分与最小生成树技术,可以有效排除噪声数据,发现任意...