基于数据空间网格划分的PK-树索引结构

在大规模高维数据挖掘研究中,数据存储与索引方法的有效性是决定算法时空效率的重要因素。将数据空间网格划分策略与高效率的树型索引结构结合起来,可以充分发挥两者在数据组织上的综合优势,将复杂问题转换为结构化的简单重复问题：在统一的框架下给出了各种数据空间网格划分的定义,讨论了两种适用于实现网格化数据索引的R-树和PK-树索引结构：试验结果表明,PK-树在数据存储和索引上具有更高的效率,与网格化数据组织方法结合起来,对于降低大规模高维数据分析问题的时空复杂度具有重要意义。     

HBase中基于时空特征的监测视频大数据关联查询研究

针对传统的时空索引构建、维护困难且实时查询效率低等问题,首先提出基于HBase的时空索引构造方法。该方法采用HBase作为监测视频大数据时空特征索引结构,通过Z填充曲线对空间特征进行降维存储,并利用时间、空间和属性特征之间的关联及依赖规则来安排rowkey索引键,可有效解决传统的时空索引构建、维护困难的缺陷。此外,针对传统的时空索引实时查询效率低的问题,进一步提出了基于Z曲线的时空关联查询算法,该算法对查询空间计算Z值范围和建立空间划分子集,利用划分后的时空特征进行列索引查询得到候选数据集并反查HBase索引表完成关联查询。实验结果表明,与传统的R树索引算法相比,提出的基于HBase的时空索引构造方法索引插入效率更高,提出的基于Z曲线的时空关联查询算法能够快速高效地处理时空关联查询。     

时空相点移动对象数据索引PM-Tree

随着移动定位技术和无线通讯技术发展,移动对象的应用领域越来越广阔.位置随时间而变化的移动对象产生的时空数据具有规模大、多维性、结构复杂和关系复杂等特点.由于移动对象的运动轨迹大多被限定在特定的交通网络中,因此基于路网的移动对象索引成为时空数据索引研究的一个重要应用分支.目前,针对移动对象历史数据的区域查询优化的研究重点是如何提高窗口查询的效率.这类索引通常以同一线路为单位来组织轨迹数据的存储.索引通常采用两层的R-tree索引结构,上层的2D R-tree用于索引在某个区域内的线路,下层的2D R-tree用于索引某个时间段内在这些区域的移动对象.这类索引在处理轨迹信息的时间维度的时候,仅仅是把时间维度等同于空间的维度来进行R树维度的扩展.由于R树算法不能有效地降低最小限定矩形的空间堆叠问题,尤其是在数据量较大、数据维数增加时表现得更为明显.所以,为了提高路网中移动对象时空信息的存储以及查询的效率,本文则将轨迹信息中的时间数据和空间数据整合起来,提出了一种移动对象数据索引PM-tree(Phase-point Moving Object Tree).首先运用映射函数把路网中移动对象运动轨迹的二维时空矩形投影成带参数的一维"时空相点",并讨论了时空相点之间的偏序关系,建立了基于相点偏序划分的相点序分枝结构,为索引的建立提供了理论支撑.接着论文以MON-tree索引为基础,以相点序分枝结构来改进其下层索引结构,提出了时空相点移动对象数据索引,该索引能完成运动轨迹时空的一体化查询,能避免类R-tree索引中最小限定矩形堆叠导致的效率低下的问题,有效地缩小搜索空间.最后论文实现了索引的增量式动态更新管理.通过实验的对比分析,表明PM-tree索引不但能有效提高储存空间的利用率,"一次一集合"的查询模式还提高了查询性能.     

基于实时数据和历史查询分布的时空索引新方法

在大数据时代,数据具有体量大、时空复杂性明显、对实时性要求较高等特点,而传统基于树形结构对大规模时空数据进行索引的方法存在存储空间浪费和查询效率较低的问题。为了解决该问题,提出了一种基于数据和历史查询记录分布建立时空索引的新方法HDL-index。该算法一方面根据数据在空间上的分布,通过空间划分的思想建立索引网格;另一方面考虑到查询在时间上的延续性,对查询记录对象进行密度聚类后抽象出查询代表模型,然后根据模型的坐标位置和其查询粒度对整体查询区域进行分割。两部分所得到的索引网格都采用Geohash编码,最终合并得到最优的索引编码。HDL-index在考虑数据分布的同时充分考虑用户查询行为,使得频繁查询区域上的索引更加细化。在真实航空数据集上与同类方法进行比较测试的结果表明,其创建索引的效率提高了50%;同时在数据均匀分布的情况下对热点区域的查询效率可提高75%以上。     

基于KDG-tree的数据库多维索引技术

针对目前网格索引(Grid index)的冗余数据及KD-tree等多维索引的维度灾难等问题,提出一种将网格索引与二叉搜索树结合起来的高效索引结构KDG-tree。KDG-tree通过纵横向指针将结点链接起来构成二叉索引树,树中的结点分为中间索引结点和叶子结点,所有数据对象只存于叶子结点。创建索引时分别从高维到低维按结点索引值顺序插入,查找对象时逐维搜索。实验分析表明,KDG-tree避免了Grid index的数据冗余,又改进了KD-tree与KDB-tree的性能,是一种适合高维海量数据的多维索引。     

一种采用Z曲线高维空间范围查询算法

低维空间中线性扫描算法及基于R树、VA文件和NB树的空间范围查询算法的效率较高,高维空间中它们的效率出现恶化现象.Z曲线将空间分割成大小相等网格并依次穿过它们,将网格中的点映射到线性空间中,从而能够使用B+树作为点集的索引结构.利用Z曲线聚类和降维特性,本文给出网格划分方法、搜索区域分解过程,提出一种高维空间范围查询算法.实验结果表明在高维空间中算法的效率优于上述算法.     

一种有效的混合空间索引机制

论文结合网格索引和R树索引的特点,提出了一种基于粗分网格和聚类R树的混合索引方案(HSIBGR)。该方案首先将矩形地理空间进行粗网格划分建立一级索引,然后针对每个小网格建立基于R树的二级索引,采用聚类技术处理溢出R树结点的分裂。论文还对HSIBGR索引机制进行了理论分析和实验验证,结果表明HSIBGR索引机制能有效地减少存储开销,提高检索效率,具有良好的性能。     

一种用于时空体元编解码存储的低计算量优化方法

针对时空网格体对象的编解码占用存储空间大的问题,提出了一种用于时空体元编解码存储的低计算量优化方法。首先以十六叉树索引结构为基础,构建了时空网格体元编解码的数学模型,实现体元对象标识和时空位置索引,并借助3DGIS的自动编解码方法,实现了时空网格体元对象编解码存储表示的换算;其次,采用伽罗华有限域理论,构建了网格体元的二进制编码矩阵和存储的低计算量优化算法,实现了体元对象编解码存储过程中的优化计算;最后,以某矿山的矿床空间块体数据为例,对网格体元编解码模型、存储表示换算以及低计算量优化算法进了实际应用,并与八叉树索引结构的Morton码进行比较和分析,结果表明：该方法可有效降低30%的编解码存储计算量,提高了存储网格体元对象的时空效率。     

一种多对象时间序列数据存储设计

本文讨论了在现有的数据存储和索引技术的基础上,结合固定周期产生状态数据设备的检测特点定义了一种存储结构和索引结构,以获得更高的空间利用率和查询效率。首先深入分析状态数据所具有的时间和设备二维性并定义了相应的二维存储结构,分别针对每一维建立了索引,然后分析了基于此结构的存储和查询方法。     

一种基于网格与R树的多级混合索引

结合网格索引和R树索引的特点,提出了一种基于网格与R树的多级混合索引.该方案首先将矩形地理空间进行粗网格划分建立多级网格索引.然后针对每个小网格建立基于R树的空间索引.详细讨论了该索引的结构、建立算法、删除算法以及应用该索引的检索算法,并进行了算法分析.与网格索引和R树索引相比,该索引以略大的空间开销换取了更高的查找性能.     

一种基于Hilbert排列码的GIS空间索引方法

分析了基于栅格格网的索引数据结构在空间查询中的重要地位,讨论了基于多维数据一维映射的空间排列的优点,对Morton码、Gray码、Hibert码和Sierpinsky码的空间聚类特征进行了分析和比较,得出了Hilbert码在空间查询中效率最高的结论,考虑到基于特征的GIS数据模型的特点,兼顾内存索引与磁盘索引,提出了基于Hilbert空间排列的点特征二叉平衡排序树动态索引结构和基于角点回溯的线特征索引结构,并对其在GIS空间查询中的应用方法进行了论述。     

空间数据索引技术

多维数据库的应用日益广泛，如何有效地存储组织多维的数据，提高多维数据处理的效率已成为一个核心问题，对空间数据索引技术的研究情况作了分析，介绍了各类技术的基本思想，最后着重介绍一种用于高维持特征向量检索的新的、通用的空间数据索引技术，将只能在空间坐标数据类型之上建立索的传统的R树扩充为任意在数据类型上建立索引的类属的R树。     

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

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

一种基于网格的增量聚类算法*

分析了现有基于网格的聚类算法,该算法具有高效且可以处理高维数据的特点,但传统网格聚类算法的聚类质量受网格划分的粒度影响较大。为此,提出了一种基于网格的增量聚类算法IGrid。IGrid算法具有传统网格聚类算法的高效性,且通过维度半径对网格空间进行了动态增量划分以提高聚类的质量。在真实数据集与仿真数据集上的实验结果表明,IGrid算法在聚类准确度以及效率上要高于传统的网格聚类算法。     

自适应近似树

在大规模多媒体数据库中进行基于内容的检索，高维数据牵引结构的研究是重要问题，提出了一种有效的高维索引结构－自适应近似树，阐述了它的结构，给出了构建和检索算法，它结合了树结构和顺序检索的共同优点，针对不同的数据分布情况可以自适应地调整结构，维数较低或数据分布偏斜较大时它呈现树的结构，高维或数据分布密集时呈现顺序扫描的结构，以达到更优的检索效率，在结构上，对MBR使用了压缩存储的方法以节省存储空间，在算法中充分利用了空间划分是MBS和MBR共存的特点，减少了大量复杂的计算，从而大大提高检索效率。     

Isosurface extraction and spatial filtering using Persistent OcTree (POT)

We propose a novel Persistent OcTree (POT) indexing structure for accelerating isosurface extraction and spatial filtering from volumetric data. This data structure efficiently handles a wide range of visualization problems such as the generation of view-dependent isosurfaces, ray tracing, and isocontour slicing for high dimensional data. POT can be viewed as a hybrid data structure between the interval tree and the Branch-On-Need Octree (BONO) in the sense that it achieves the asymptotic bound of the interval tree for identifying the active cells corresponding to an isosurface and is more efficient than BONO for handling spatial queries. We encode a compact octree for each isovalue. Each such octree contains only the corresponding active cells, in such a way that the combined structure has linear space. The inherent hierarchical structure associated with the active cells enables very fast filtering of the active cells based on spatial constraints. We demonstrate the effectiveness of our approach by performing view-dependent isosurfacing on a wide variety of volumetric data sets and 4D isocontour slicing on the time-varying Richtmyer-Meshkov instability dataset.     

基于BD结构的历史数据流存储与查询

实际应用中,人们往往不仅需要近期数据流,还需要结合大量历史数据流来共同解决问题。研究表明,处理大量历史数据流时,传统数据库索引技术(如B+树)不能提供高的存储利用率和查询效率。针对任意时间段历史数据流的存储查询问题,提出一种基于BD结构的存储与查询方法。该方法将BDTree和BDHash相结合,能有效降低BDTree的高度,减小索引项的规模,同时可以避免数据结点规模过大。在此基础上,研究了部分扩充策略以解决数据插入失败问题。理论分析和实验结果表明,该方法能提高存储空间利用率和查询效率,可以有效应用于历史数据流的存储和查询。     

基于矢量量化的快速图像检索

传统索引方法对高维数据存在"维数灾难"的困难.而对数据分布的精确描述及对数据空间的有效划分是高维索引机制中的关键问题.提出一种基于矢量量化的索引方法.该方法使用高斯混合模型描述数据的整体分布,并训练优化的矢量量化器划分数据空间.高斯混合模型能更好地描述真实图像库的数据分布;而矢量量化的划分方法可以充分利用维之间的统计相关性,能够对数据向量构造出更加精确的近似表示,从而提高索引结构的过滤效率并减少需要访问的数据向量.在大容量真实图像库上的实验表明,该方法显著减少了支配检索时间的I/O开销,提高了索引性能.     

Indexing and Integrating Multiple Features for WWW Images

In this paper, we present a novel indexing technique called Multi-scale Similarity Indexing (MSI) to index image's multi-features into a single one-dimensional structure. Both for text and visual feature spaces, the similarity between a point and a local partition's center in individual space is used as the indexing key, where similarity values in different features are distinguished by different scale. Then a single indexing tree can be built on these keys. Based on the property that relevant images have similar similarity values from the center of the same local partition in any feature space, certain number of irrelevant images can be fast pruned based on the triangle inequity on indexing keys. To remove the “dimensionality curse” existing in high dimensional structure, we propose a new technique called Local Bit Stream (LBS). LBS transforms image's text and visual feature representations into simple, uniform and effective bit stream (BS) representations based on local partition's center. Such BS representations are small in size and fast for comparison since only bit operation are involved. By comparing common bits existing in two BSs, most of irrelevant images can be immediately filtered. To effectively integrate multi-features, we also investigated the following evidence combination techniques—Certainty Factor, Dempster Shafer Theory, Compound Probability, and Linear Combination. Our extensive experiment showed that single one-dimensional index on multi-features improves multi-indices on multi-features greatly. Our LBS method outperforms sequential scan on high dimensional space by an order of magnitude. And Certainty Factor and Dempster Shafer Theory perform best in combining multiple similarities from corresponding multiple features.