首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 156 毫秒
1.
提出了一种新的高维数据空间的索引结构XSA—tree.它扩展了现有索引结构SA—tree,提出了卫星数据域的思想,以增强索引的过滤能力.通过对根节点中数据点选取进行优化,以得到相对平衡的索引树.文中给出了该索引结构并详细介绍了相关索引算法.实验结果表明,该索引结构显著提高了高维数据空间中相似性检索性能.是一种有效的高维索引结构.  相似文献   

2.
本文给出一种称为HB~+结构的数据组织,用它建立的PROLOG外部数据库不但具有高效的检索性能,而且还具有与B~+树类似的顺序处理能力和平衡易变等优点。尤其,通过HB~+上的分蘖操作,人们还可以把检索效率控制在期望的时间范围内。  相似文献   

3.
基于CBR系统事例检索算法的研究   总被引:9,自引:0,他引:9  
事例检索是基于事例推理CBR系统的中心环节,检索速度和精度关系着整个系统的质量。根据应用的需要先后分析了基于数据库、ID3决策树和k—d树的事例检索算法,并在标准的k—d树算法的基础上引入聚类的概念,将原始的事例库组织成聚合中心库和类库二级结构,提出了改进的k—d树事例检索算法,理论分析和对比实验证实了改进的k—d树事例检索算法在事例检索速度上逼近ID3决策树检索算法,在检索精度上远远超过了ID3决策树检索算法和标准的k—d树检索算法,其性能开销比是四种算法中最为理想的。  相似文献   

4.
提出了一个基于聚类索引树的高维近似检索方法。详细描述了其建树算法和检索算法。由于传统索引对高维空间的k-近邻检索效率的提高非常有限,我们把近似检索和聚类索引树结合起来。从而用很小的精度损失换取很高的检索效率。实验表明,与精确检索相比,本方法的误差非常小,而检索速度大大优于其他方法,因此具有广泛的应用前景。  相似文献   

5.
传统的Hilbert Packed R-树是利用Hilbert值对空间实体依次进行压缩,算法简单快速,然而空间位置上邻近的空间实体的Hilbert值并不一定相邻,使得在数据分布不均匀时,查询效率开始下降;递归聚类的算法虽然解决了以上问题,但是它计算复杂,而且容易造成R-树的不平衡,以至降低了存储利用率和检索的效率。文中对两种方法加以综合,提出了一种新的批量加载R-树的算法—HilCluster。实验结果表明,新算法不仅继承了Hilbert Packed R-树构造过程时间消耗低、存储利用率高的优点,还使得查询效率进一步提高。  相似文献   

6.
传统的Hilbert Packed R-树是利用Hilbert值对空间实体依次进行压缩,算法简单快速,然而空间位置上邻近的空间实体的Hilbert值并不一定相邻,使得在数据分布不均匀时,查询效率开始下降;递归聚类的算法虽然解决了以上问题,但是它计算复杂,而且容易造成R-树的不平衡,以至降低了存储利用率和检索的效率。文中对两种方法加以综合,提出了一种新的批量加载R-树的算法—HilCluster。实验结果表明,新算法不仅继承了Hilbert Packed R-树构造过程时间消耗低、存储利用率高的优点,还使得查询效率进一步提高。  相似文献   

7.
一种基于聚类分析的R~*树结点重叠判定算法   总被引:1,自引:0,他引:1  
聚类分析可以对大量空间对象进行聚类划分,优化R*树的结点.根据R*树的强制重插原则,在聚类分析基础上提出一种扩展MBR的对角线段对相交算法以判定类结点的重叠.从根本上改变以往在解决R*树结点重叠时仅将MBR形状改变或单纯紧致正交MBR所存在的问题,以此为判定条件可以控制聚类算法迭代次数,减少噪声点对聚类的影响.其中判定算法时间复杂性为O(nlogn)级.实验结果表明在范围查询中引入基于聚类分析的对角线段对相交判定算法的查询效率优于基于R*树的Gain/Loss度量的贪婪算法和基于SR树的算法的查询效率.  相似文献   

8.
光谱图相似性匹配是推测化合物结构的重要研究方法之一,而如何在标准谱图数据库中进行相似性查找是关键步骤。传统的谱图匹配方法在数据量较大时,检索效率较低。本文首次将互关联后继树(TRST)算法思想应用于光谱图数据领域,从光谱图特征数据点出发,通过对算法的改进,提出了1种基于斜率序列的互关联后继树算法(SSIRST)实现光谱图相似性匹配查找,旨在通过减少匹配过程中的数据量缩短查找时间。实验结果表明,算法可以有效提高光谱图相似性匹配查找效率1倍以上。  相似文献   

9.
利用高维数据空间合理划分,提出一种简单有效的KNN检索算法-LBD。通过聚类将数据划分成多个子集空间,对每个聚类子集内的高维向量,利用距离和位码定义简化表示形式。KNN搜索时,首先利用距离信息确定候选范围,然后利用某些维上的位码不相同信息进一步缩小搜索范围,提高剪枝效率。位码字符串比较时,按照维度贡献优先顺序,大大加快非候选点过滤。LBD利用特殊的B+树组织,降低I/O和距离计算代价。采用模拟数据和真实数据,实验验证了LBD具有更高的检索效率。  相似文献   

10.
在研究进行图像拷贝检测检索技术时,传统的图像拷贝检测检索使用的是顺序检索.针对目前大容量、高维度的图像数据集,传统检索方法效率低,无法有效发现非法拷贝,阻止盗版行为.为提高检索效率,对图像数据库进行必要的预处理并建立高效索引,首先利用k-d树构建图像多维特征的索引结构,对其进行改进,使之适应于维度较高的情况,再结合聚类处理思想,对k-means聚类方法进行改进,实现对高维特征向量做聚类预处理,最后再基于聚类中心做k-d树的索引结构.实验结果表明,上述方法在满足大规模图像拷贝检测的效率的同时,其查全率和查准率都有较大提升,为打击盗版提供技术支持.  相似文献   

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

12.
人们设计了许多索引以有效地处理高维空间中的近邻查询和区域查询。已经证明,维数较高时利用高维索引处理这两类查询几乎不可能比线性扫描快。提出了一种两层索引以自适应地识别数据集中的聚簇;数据集具有聚簇特性时,用该索引处理邻近查询和区域查询比现有的索引结构快;对其他数据集,利用该索引处理邻近查询和区域查询与线性扫描大致相当。该索引的上层结构将一些参考点组织成一棵二叉树,下层结构是一系列动态哈希表。数据集中的数据点根据它们到参考点的相对距离被哈希到相应的哈希桶中。查询处理时用查询点到参考点的距离进行剪除搜索。实验表明,提出的索引结构具有良好的性能。  相似文献   

13.
Multidimensional Index Structures in Relational Databases   总被引:2,自引:0,他引:2  
Efficient query processing is one of the basic needs for data mining algorithms. Clustering algorithms, association rule mining algorithms and OLAP tools all rely on efficient query processors being able to deal with high-dimensional data. Inside such a query processor, multidimensional index structures are used as a basic technique. As the implementation of such an index structure is a difficult and time-consuming task, we propose a new approach to implement an index structure on top of a commercial relational database system. In particular, we map the index structure to a relational database design and simulate the behavior of the index structure using triggers and stored procedures. This can be easily done for a very large class of multidimensional index structures. To demonstrate the feasibility and efficiency, we implemented an X-tree on top of Oracle8. We ran several experiments on large databases and recorded a performance improvement up to a factor of 11.5 compared to a sequential scan of the database.  相似文献   

14.
An efficient peer-to-peer indexing tree structure for multidimensional data   总被引:4,自引:1,他引:3  
As one of the most important technologies for implementing large-scale distributed systems, peer-to-peer (P2P) computing has attracted much attention in both research and industrial communities, for its advantages such as high availability, high performance, and high flexibility to the dynamics of networks. However, multidimensional data indexing remains as a big challenge to P2P computing, because of the inefficiency in search and network maintenance caused by the complicated existing index structures, which greatly limits the scalability of applications and dimensionality of the data to be indexed.We propose SDI (Swift tree structure for multidimensional Data Indexing), a swift index scheme with a simple tree structure for multidimensional data indexing in large-scale distributed systems. While keeping the query efficiency in O(logN) in terms of routing hops, SDI has extremely low maintenance costs which is proved through theoretical analysis. Furthermore, SDI overcomes the root-bottleneck problem existing in most other tree-based distributed indexing systems. Extensive empirical study verifies the superiority of SDI in both query and maintenance performance.  相似文献   

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

16.
为了实现基于语义的密文检索,提高密文检索的准确率和效率,本文提出了一种基于biterm主题模型(biterm topic model,BTM)的多关键词可排序对称可搜索加密方案(BTM-MRSE).通过主题模型对关键词和文档之间的潜在语义进行建模,用户利用查询关键词的概率分布作为检索陷门,根据查询关键词与文档之间的语义相关性得分来获得最相关的文档.本方案将密文检索中的特定关键词替换为基于语义的主题,实现了关键词和文档标识符的分离,从而增强了文档关键词与查询关键词的隐私保护.为了减小索引规模,我们提出两层索引结构,利用平衡二叉树构造关键词-主题安全索引,结合倒排索引构造主题-文档安全索引.一方面,主题模型减小了索引节点中向量的维数,从而提高了检索效率,同时基于平衡二叉树的二级索引机制也进一步改善了密文检索效率.安全性分析证明了所提方案是安全有效的,同时利用真实数据集进行实验对比,表明本方案的密文检索准确率和效率都有极大提升.  相似文献   

17.
讨论了高维数据空间索引的基本结构、建树算法,重,最对几种有代表性的索引方法,如R—Tree,X-Tree,M—tree,VP-tree在重叠、插入原则、分裂原则、再插入等方面进行了比较研究。该文中主要介绍了一些索引结构的特点和一些具有代表性的索引结构。  相似文献   

18.
讨论了高维数据空间索引的基本结构、建树算法,重点对几种有代表性的索引方法,如R-Tree,X-Tree,M-tree,VP-tree在重叠、插入原则、分裂原则、再插入等方面进行了比较研究。该文中主要介绍了一些索引结构的特点和一些具有代表性的索引结构。  相似文献   

19.
随着基因测序技术和人类基因组计划的发展,从大量的生物数据中寻找相似的序列就越来越成为当前研究的热点问题.本文提出了一种聚类的多解析度字符串索引结构,用于解决生物序列的相似性查询问题.首先,以较小容量的MBR(最小绑定矩形)构造基因序列的多解析度字符串索引结构,然后通过对MBR的聚类以夏保序技术的应用,减小索引中MBR的平均体积,从而增加了查询向量到索引的空间距离,提高了索引的过滤能力.还给出了一种新的后处理方法,通过大量的减少编辑距离的计算,提高索引的性能.文中给出了该索引结构并详细介绍了索引的相关算法.实验表明,该索引结构是一种有效的处理生物数据的相似性查询的索引结构.  相似文献   

20.
Similarity search (e.g., k-nearest neighbor search) in high-dimensional metric space is the key operation in many applications, such as multimedia databases, image retrieval and object recognition, among others. The high dimensionality and the huge size of the data set require an index structure to facilitate the search. State-of-the-art index structures are built by partitioning the data set based on distances to certain reference point(s). Using the index, search is confined to a small number of partitions. However, these methods either ignore the property of the data distribution (e.g., VP-tree and its variants) or produce non-disjoint partitions (e.g., M-tree and its variants, DBM-tree); these greatly affect the search efficiency. In this paper, we study the effectiveness of a new index structure, called Nested-Approximate-eQuivalence-class tree (NAQ-tree), which overcomes the above disadvantages. NAQ-tree is constructed by recursively dividing the data set into nested approximate equivalence classes. The conducted analysis and the reported comparative test results demonstrate the effectiveness of NAQ-tree in significantly improving the search efficiency.  相似文献   

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

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