R*-Tree强制重插算法的改进

为了提高检索速度,在分析R-Tree及R*-Tree的基础上,提出一种强制重插算法,通过改进R*-Tree多维空间索引结构加速搜索过程。实验结果表明,相比传统算法,该算法在索引空间利用率、动态创建索引、索引检索方面具有更高性能。     

空间索引技术研究

空间索引可以提高空间数据库的操作效率,目前人们的研究工作更多地集中在空间数据的多维索引的研究上.文中全面地总结了当前空间数据库领域中空间索引以及时空索引的研究进展,描述了R树系列索引的构建思想,节点插入与分裂操作的不同.通过实验深入分析了R树以及R树变体的磁盘访问率,插入,删除,更新的CPU时间,验证了在数据激增的情况下,R树系列索引的复杂性带来的重叠问题会指数递增.由于R树当前应用的深度和广度,研究基于 R树的高效时空高维索引技术是解决索引应用问题一个有效方法.提出了索引性能改进的方向在于多种索引技术的结合,尤其是树形结构索引和网状结构索引的结合.     

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

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

一种基于R树的图像检索方法

把图像的七个不变矩组合成一个七维向量,在R-树索引结构的基础上设计和实现了此向量的多维索引结构及相关操作。试验结果显示使用该索引方法大大提高了图像检索的效率。     

R*-树空间索引的改进

R*-树基于局部调整的思想对节点进行管理,存在时间与效率上的不足。为克服R*-树的不足,给出了一种新型的存储结构,并给出新型存储结构的插入、溢出、分裂等空间索引常用操作的算法。分析新的存储结构的优点,并通过实验结果说明该方案比R*-树具有更高的效率。     

基于DPR树的分布式并行空间索引机制的研究

针对分布式并行环境下海量空间数据管理与并行化处理的效率问题,以提高分布式并行空间数据的查询效率为目的,根据现有的空间索引结构与并行化技术,提出一种新的分布式并行空间索引结构--DPR树.DPR树是空间索引技术与并行化技术优化结合的成果.DPR树在数据的总体划分与部分查询中所采用的均是基于高效处理技术.它在原有的并行Master-client R树的基础上进行改进,采用了HCSDP数据划分技术,并将其应用到分布式环境下,且每个节点机中各子树采用了改进的R树--R*Q树.通过性能分析表明,该索引结构具有高效的查询性能.     

一种支持快速相似检索的多维索引结构

基于内容的图像检索是一种典型的相似检索问题,对于尺度空间上的图像相似匹配问题,一般认为距离计算费用很高.因此,需要建立有效的索引结构,以减少每个查询中的距离计算次数.为此,基于数据空间的"优化划分",并且使用"代表点",以层次结构方式划分数据,提出了一种新的基于距离的相似索引结构opt-树及其变种(-树.为了更有效地支持基于内容的图像检索,在(-树索引结构中采用了"(-最优化划分"和"(-对称冗余存储"策略,以提高相似检索的效率.详细讨论了这种索引结构的建立与检索等问题,并给出了相应的算法.实验结果显示了这种索引技术的有效性.     

基于混合相似度的高效图像检索方案

融合文本和视觉信息进行图像检索可避免图像低层视觉特征与高层语义之间的语义鸿沟,但在提高检索质量的同时难以保证检索效率。为此,针对基于文本和内容的混合图像检索,通过结合曼哈顿哈希、倒排索引和R树等技术,设计一个新型的索引结构CAT树和相应的top-k检索算法,并由此提出三段式图像检索方案。在基准图像数据集上的实验结果表明,该方案可以在保持准确率的前提下,显著提升图像检索的效率。     

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

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

一种用于空间数据多尺度表达的R树索引结构

针对现有R树无法支持空间数据多尺度表达的问题,提出了一种用于空间数据多尺度表达的R树变形索引结构:(1)允许空间对象出现在非叶结点上;(2)利用树的深度反映空间分辨率的变化,提供分辨率维的支持;(3)树的分支结构考虑对自动制图综合算法的支持.分析了该变形R树索引结构的空间数据多尺度查询过程,并着重对该索引结构生成算法中的约束条件、插入算法和分裂算法进行了讨论.针对相同数据源,使用该方法与基于四叉树的空间数据多尺度索引方法进行了对比实验,结果表明,该索引方法能有效检索多分辨率形式组织的空间数据,具有综合结果记忆功能,效率明显.     

一种基于固定网络的移动对象运动轨迹索引模型

实际应用中移动对象通常运动在城市固定道路上,针对此特征研究人员已提出一些相关索引模型,但都存在一定的局限性,表现为索引模型只管理对象的历史位置信息或实时位置信息以及只对窗口查询或轨迹查询进行优化.IMTFN是一种基于固定网络的移动对象运动轨迹索引模型,管理移动对象的实时位置信息和历史轨迹信息,并且有效优化窗口查询及轨迹查询操作.IMTFN由一个管理固定网络的2D R^＊-Tree、一组管理移动对象运动轨迹的1D R^＊-Tree以及记录移动对象实时位置信息的Hash结构组成.最后通过实验IMTFN分别与STR-Tree与FNR-Tree进行性能比较,证明IMTFN模型提供速度更快的查询操作.     

多核处理器中支持频繁访问的B+-Tree

针对传统B+-Tree自顶向下访问模式的缺点,提出了支持频繁访问的FAB+-Tree（Frequent Access B+-Tree）。在B+-Tree的基础上增加了Hash辅助索引,使得访问B+-Tree时直接定位到叶结点,并利用基于内存的直接访问表及位矢量列表提高更新性能。同时基于共享Cache多核处理器,提出了基于流水线的FAB+-Tree多线程访问模块,并优化了该模块的共享Cache访问性能。在实验中,基于开源数据库INGRES实现了FAB+-Tree和多线程访问模块,实验结果表明B+-Tree的访问性能得到显著提高。     

基于新的空间关系特征的图像检索方法

图像与图像之间没有清晰的空间结构,这样就不能有效利用图像间空间结构上的相关性信息,针对此问题提出一种基于新的空间关系特征的图像检索方法。首先,提取待查询图像在内的全部图像的特征向量。然后,计算特征向量每两个之间的相似性,形成相似性矩阵。将相似性矩阵的列集合作为新特征向量,命名为新的空间关系特征向量,从而将原来的特征向量映射到一个欧氏空间上。最后,在新特征空间上计算相似性,特征向量之间的相似性问题就转化为新的空间关系特征向量之间的相似性问题。在新特征空间上,图像与图像之间的空间结构变得清晰了,有利于图像检索准确度的提高。在Corel数据库上进行实验,所提方法在平均检索查准率、查全率-查准率和可视化评价指标上都优于基于颜色直方图的图像检索方法。结果表明,基于新的空间关系特征的图像检索方法有效利用了图像间空间结构上的相关性信息,具有更好的检索效果。     

道路网络中的移动对象索引方法研究

基于MON-Tree的思想提出了一种新的索引结构MON⁺-Tree。给出了MON⁺-Tree的数据结构、插入算法和查询算法。最后通过实验MON⁺-Tree、MON-Tree和MONC-Tree进行性能比较,证明MON⁺-Tree为效率更高的查询算法。     

An efficient compressed domain video indexing method

Video indexing is employed to represent the features of video sequences. Motion vectors derived from compressed video are preferred for video indexing because they can be accessed by partial decoding; thus, they are used extensively in various video analysis and indexing applications. In this study, we introduce an efficient compressed domain video indexing method and implement it on the H.264/AVC coded videos. The video retrieval experimental evaluations indicate that the video retrieval based on the proposed indexing method outperforms motion vector based video retrieval in 74 % of queries with little increase in computation time. Furthermore, we compared our method with a pixel level video indexing method which employs both temporal and spatial features. Experimental evaluation results indicate that our method outperforms the pixel level method both in performance and speed. Hence considering the speed and precision characteristics of indexing methods, the proposed method is an efficient indexing method which can be used in various video indexing and retrieval applications.     

Kernel Vector Approximation Files for Relevance Feedback Retrieval in Large Image Databases

Many data partitioning index methods perform poorly in high dimensional space and do not support relevance feedback retrieval. The vector approximation file (VA-File) approach overcomes some of the difficulties of high dimensional vector spaces, but cannot be applied to relevance feedback retrieval using kernel distances in the data measurement space. This paper introduces a novel KVA-File (kernel VA-File) that extends VA-File to kernel-based retrieval methods. An efficient approach to approximating vectors in an induced feature space is presented with the corresponding upper and lower distance bounds. Thus an effective indexing method is provided for kernel-based relevance feedback image retrieval methods. Experimental results using large image data sets (approximately 100,000 images with 463 dimensions of measurement) validate the efficacy of our method.     

Pattern classification models for classifying and indexing audio signals

In the age of digital information, audio data has become an important part in many modern computer applications. Audio classification and indexing has been becoming a focus in the research of audio processing and pattern recognition. In this paper, we propose effective algorithms to automatically classify audio clips into one of six classes: music, news, sports, advertisement, cartoon and movie. For these categories a number of acoustic features that include linear predictive coefficients, linear predictive cepstral coefficients and mel-frequency cepstral coefficients are extracted to characterize the audio content. The autoassociative neural network model (AANN) is used to capture the distribution of the acoustic feature vectors. Then the proposed method uses a Gaussian mixture model (GMM)-based classifier where the feature vectors from each class were used to train the GMM models for those classes. During testing, the likelihood of a test sample belonging to each model is computed and the sample is assigned to the class whose model produces the highest likelihood. Audio clip extraction, feature extraction, creation of index, and retrieval of the query clip are the major issues in automatic audio indexing and retrieval. A method for indexing the classified audio using LPCC features and k-means clustering algorithm is proposed.     

一种基于B+树的混合索引结构

针对文件中存在字符属性和数值属性特点的数据,提出一种基于B+树的2层混合索引结构。在索引创建过程中,将文件中的数据根据其类型进行分类,第1层是为数据属性建立B+树索引结构,第2层是根据不同的数据类型建立不同的索引结构。实验结果表明,该索引结构能实现跨数据范围的检索,提高索引的创建速度和空间利用率。     

Dimensionality reduction for similarity search with the Euclidean distance in high-dimensional applications

In multimedia information retrieval, multimedia data are represented as vectors in high-dimensional space. To search these vectors efficiently, a variety of indexing methods have been proposed. However, the performance of these indexing methods degrades dramatically with increasing dimensionality, which is known as the dimensionality curse. To resolve the dimensionality curse, dimensionality reduction methods have been proposed. They map feature vectors in high-dimensional space into vectors in low-dimensional space before the data are indexed. This paper proposes a novel method for dimensionality reduction based on a function that approximates the Euclidean distance based on the norm and angle components of a vector. First, we identify the causes of, and discuss basic solutions to, errors in angle approximation during the approximation of the Euclidean distance. Then, this paper propose a new method for dimensionality reduction that extracts a set of subvectors from a feature vector and maintains only the norm and the approximated angle for every subvector. The selection of a good reference vector is crucial for accurate approximation of the angle component. We present criteria for being a good reference vector, and propose a method that chooses a good reference vector. Also, we define a novel distance function using the norm and angle components, and formally prove that the distance function consistently lower-bounds the Euclidean distance. This implies information retrieval with this function does not incur any false dismissals. Finally, the superiority of the proposed approach is verified via extensive experiments with synthetic and real-life data sets.