首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 171 毫秒
1.
空间数据库中反向最近邻查询在低维查询时一般利用基于R-Tree的改进树作为索引结构,由于树型索引结构本身的限制,R-Tree等索引结构的查询在高维中都会出现维数灾难。针对这个问题,提出了一种基于VARdnn-Tree的索引结构,采用量化压缩的方法存储数据,能够有效地支持高维查询。  相似文献   

2.
VA-Trie:一种用于近似k近邻查询的高维索引结构   总被引:1,自引:1,他引:1  
近年来,随着多媒体信息检索技术的不断发展,如何实现高维特征矢量的快速相似性查询成为一个重要的研究课题.为此,人们提出了许多索引结构,包括:R—Tree及其变种、对矢量进行量化近似的VA—File、引入量化思想的A—Tree等等.从公开发表的成果看,这些索引结构在较低维数时,都能够表现出较好的查询性能;而当维数增加时,性能则急剧恶化.为了在更高维数下实现快速相似查询,可采用VA—File和A—Tree中的近似思想,并借助Trie结构来组织和管理压缩后的近似矢量,即所谓的VA—Trie.实验结果表明,在高达128维时VA—Trie仍有查询加速,其性能远好于A—Tree.  相似文献   

3.
逐维聚类的相似度索引算法   总被引:5,自引:0,他引:5  
随着多媒体信息技术的迅速发展,多维度索引技术在图像、视频等可视信息的存储、检索方面成为一个重要的研究领域,针对“维数危机”难题,提出逐维聚类相似度索引算法,该算法根据数据集的分布特性,对特征矢量的每一维进行聚类,算法在实现检索时可以逐步滤除与查询矢量不相似的数据集,缩小检索范围,进而提高了检索速度,实验结果表明,逐维聚类算法适用于基于相似度的高维数据矢量检索和查询,是一种简单、灵活的索引结构。  相似文献   

4.
基于矢量量化的快速图像检索   总被引:7,自引:0,他引:7  
叶航军  徐光祐 《软件学报》2004,15(5):712-719
传统索引方法对高维数据存在"维数灾难"的困难.而对数据分布的精确描述及对数据空间的有效划分是高维索引机制中的关键问题.提出一种基于矢量量化的索引方法.该方法使用高斯混合模型描述数据的整体分布,并训练优化的矢量量化器划分数据空间.高斯混合模型能更好地描述真实图像库的数据分布;而矢量量化的划分方法可以充分利用维之间的统计相关性,能够对数据向量构造出更加精确的近似表示,从而提高索引结构的过滤效率并减少需要访问的数据向量.在大容量真实图像库上的实验表明,该方法显著减少了支配检索时间的I/O开销,提高了索引性能.  相似文献   

5.
数字图像数据量的急剧增张使传统的基于文本的图像检索技术越来越无法适用,本文结合数字图像数据的高维空间属性,探讨了R-Tree动态索引结构在基于内容的图像检索中的应用,并结合R-Tree的搜索算法,综合分析了各种扩展R-Tree结构的优缺点。  相似文献   

6.
BC-iDistance:基于位码的优化高维索引   总被引:1,自引:0,他引:1  
在高维空间KNN查询算法中,近似向量和一维转换表示法能有效克服维数灾难,本文结合这两种思想,提出一种基于位码的优化高维索引结构(BC-iDistance).针对iDistance缺点,高维向一维转换引起的大量数据信息丢失,BC-iDistance不仅利用一维距离表示点对象和参考点间的远近关系,而且引入位码近似表示它们之间的位置关系,将高维向量压缩为二维向量表示.利用特殊的B+树组织,KNN检索时实现两层剪枝处理,降低I/O和距离计算代价.采用模拟数据和真实数据,实验验证了优化后的索引具有更高的检索效率.  相似文献   

7.
在高维空间KNN查询算法中,近似向量和一维转换表示法能有效克服维数灾难,结合这两种思想,提出一种基于区位码和距离的索引结构(BD)以实现快速KNN查询.根据高维空间向量分布特点,合理分区使得大量分布在空间表面的点尽可能地划分到不同的分区中,提高检索剪枝效率.引入区位码概念和转换函数,将高维向量近似表示并转换为一维数值形式,组织成B 树索引.利用快速KNN查询算法,实现两层过滤,缩小搜索范围,降低树搜索代价.采用模拟数据和真实数据,大量实验验证了BD比其他同类索引具有更高的检索效率.  相似文献   

8.
几乎所有的多维空间索引都没有考虑空间对象之间的顺序关系,只支持单个空间对象的索引和查询,无法直接支持空间对象序列查询.本文在R-Tree的基础上,提出一种可直接用于空间对象序列查询的动态索引--OR-Tree,保存了空间对象序列中对象之间的序关系.时间序列的相似性查询实验表明:与R-Tree相比,基于OR-Tree的方法在磁盘I/O次数和查询结果的候选集大小上显著降低,并且查询序列越长,性能提高就越明显.  相似文献   

9.
针对数据流上近似查询中的梗概计算,提出了一种新的基于最小误差的维压缩小波变换算法(MEDC).MEDC算法通过映射流数据时间戳,快速无冗余地维护流数据的有序性;基于最小误差,高效压缩小波变换阵列,最大化MEDC算法时间效率及近似查询实时处理能力;引入小波系数与查询准确度之间的数值性关联规则,支持小波系数梗概上的查询多级共享,整体查询执行性能最佳.实验表明,与传统小波变换、直方图和采样等算法相比,MEDC算法在数据流近似查询处理的响应速度、查询结果质量等方面具有更为优越的性能.  相似文献   

10.
随着XML逐渐成为Internet数据表示与交换的标准,如何快速准确地访问XML文档中的数据已成为亟待解决的关键问题,建立路径索引是提高查询效率的一种重要手段.本文设计了一种基于PATRICIA-TRIES的路径索引,简称PT索引.该索引有如下特点:一、基于PATRICIA-TRIES结构,实现快速检索.二、采用压缩编码能够将路径索引放入内存,三、索引含有结构和文本信息,通过查询索引就能提供结果,无需打开原文档.其后,分析了PT索引的时间和空间复杂性,并与三种的典型的索引结构进行了对比实验,结果证明了其在路径查询方面具有更高的效率.  相似文献   

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

12.
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.  相似文献   

13.
基于本体的案例检索系统中,由于数据库中的案例数量随着时间的推移而成倍增加,案例检索的效率不断降低。提出了一种多维案例检索算法—DRR,该算法通过将多维空间案例点降维成二维空间点,利用一个二维空间点来代表类案例点组成的集合,并对此二维空间点建立R树空间索引,通过两级检索的方法,加速了检索效率和准确率。实验证明,该方法不仅提高了案例检索的准确率,还极大地提高了案例检索的效率。  相似文献   

14.
历史查询是移动对象数据库管理的一个重要方面.为提高历史查询效率,在3D R-Tree基础上实现了优化的索引结构E3D R-Tree.在E3D R-Tree中,结合移动对象数据特征引入空白区域作为新的插入代价参数,同时,在插入算法中利用最小代价优先搜索算法确定全局最优插入路径,并给出算法正确性证明.实验结果表明,E3D R-Tree查询效率高于3D R-Tree.  相似文献   

15.
Similarity-based search has been a key factor for many applications such as multimedia retrieval, data mining, Web search and retrieval, and so on. There are two important issues related to the similarity search, namely, the design of a distance function to measure the similarity and improving the search efficiency. Many distance functions have been proposed, which attempt to closely mimic human recognition. Unfortunately, some of these well-designed distance functions do not follow the triangle inequality and are therefore nonmetric. As a consequence, efficient retrieval by using these nonmetric distance functions becomes more challenging, since most existing index structures assume that the indexed distance functions are metric. In this paper, we address this challenging problem by proposing an efficient method, that is, local constant embedding (LCE), which divides the data set into disjoint groups so that the triangle inequality holds within each group by constant shifting. Furthermore, we design a pivot selection approach for the converted metric distance and create an index structure to speed up the retrieval efficiency. Moreover, we also propose a novel method to answer approximate similarity search in the nonmetric space with a guaranteed query accuracy. Extensive experiments show that our method works well on various nonmetric distance functions and improves the retrieval efficiency by an order of magnitude compared to the linear scan and existing retrieval approaches with no false dismissals.  相似文献   

16.
Dominant features for the content-based image retrieval usually have high-dimensionality. So far, many researches have been done to index such values to support fast retrieval. Still, many existing indexing schemes are suffering from performance degradation due to the curse of dimensionality problem. As an alternative, heuristic algorithms have been proposed to calculate the answer with ??high probability?? at the cost of accuracy. In this paper, we propose a new hash tree-based indexing structure called tertiary hash tree for indexing high-dimensional feature data. Tertiary hash tree provides several advantages compared to the traditional extendible hash structure in terms of resource usage and search performance. Through extensive experiments, we show that our proposed index structure achieves outstanding performance.  相似文献   

17.
网络受限移动对象过去、现在及将来位置的索引   总被引:1,自引:0,他引:1       下载免费PDF全文
丁治明  李肖南  余波 《软件学报》2009,20(12):3193-3204
提出了一种适合于网络受限移动对象数据库的动态轨迹R树索引结构(network-constrained moving objects dynamic trajectory R-Tree,简称NDTR-Tree).NDTR-Tree不仅能够索引移动对象的整个历史轨迹,而且能够动态地索引和维护移动对象的当前及将来位置.为了比较相关索引结构及算法的性能,进行了详细的实验.实验结果表明,与现有的基于道路网络的移动对象索引方法如MON-Tree和FNR-Tree等相比,NDTR-Tree有效地提高了对网络受限移动对象动态全轨迹的查询处理性能.  相似文献   

18.
In many advanced applications, data are described by multiple high-dimensional features. Moreover, different queries may weight these features differently; some may not even specify all the features. In this paper, we propose our solution to support efficient query processing in these applications. We devise a novel representation that compactly captures f features into two components. The first component is a 2D vector that reflects a distance range (minimum and maximum values) of the f features with respect to a reference point (the center of the space) in a metric space and the second component is a bit signature, with two bits per dimension, obtained by analyzing each feature's descending energy histogram. This representation enables two levels of filtering: the first component prunes away points that do not share similar distance ranges, while the bit signature filters away points based on the dimensions of the relevant features. Moreover, the representation facilitates the use of a single index structure to further speed up processing. We employ the classical B/sup +/-tree for this purpose. We also propose a KNN search algorithm that exploits the access orders of critical dimensions of highly selective features and partial distances to prune the search space more effectively. Our extensive experiments on both real-life and synthetic data sets show that the proposed solution offers significant performance advantages over sequential scan and retrieval methods using single and multiple VA-files.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号