MapReduce框架下基于B 树的高维索引

针对MapReduce数据块处理机制、高维数据分布特征和KNN查询需求,本文设计一种基于B 树的高维索引结构（iPartition）,创新性提出基于主成分区分度的优化数据划分策略和邻接数据域分散存储等原则,将数据均匀划分到不同的Slave节点,使尽可能多的数据域对计算共同贡献,提升MapReduce任务处理并行性;利用B 树构造分布式的双层索引实现查询时数据范围快速过滤,降低高维计算代价。实验表明,iPartition在高维数据近似查询环境下,具有良好的性能和扩展性。     

An encoding-based dual distance tree high-dimensional index

The paper proposes a novel symmetrical encoding-based index structure, which is called EDD-tree （for encoding-based dual distance tree）, to support fast k-nearest neighbor （k-NN） search in high-dimensional spaces. In the EDD-tree, all data points are first grouped into clusters by a k-means clustering algorithm. Then the uniform ID number of each data point is obtained by a dual-distance-driven encoding scheme, in which each cluster sphere is partitioned twice according to the dual distances of start- and centroid-distance. Finally, the uniform ID number and the centroid-distance of each data point are combined to get a uniform index key, the latter is then indexed through a partition-based B^＋-tree. Thus, given a query point, its k-NN search in high-dimensional spaces can be transformed into search in a single dimensional space with the aid of the EDD-tree index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of our proposed scheme, and the results demonstrate that this method outperforms the state-of-the-art high-dimensional search techniques such as the X-tree, VA-file, iDistance and NB-tree, especially when the query radius is not very large.     

采用动态主分量距离测度的视频索引技术

针对有界坐标技术(BCS)技术中静态计算主分量距离的固有缺陷,指出在高维空间中正轴顶点之间的距离不一定是主分量之间的最小距离,提出了一种基于动态主分量测度的视频索引方法,用于视频特征的相似性度量．该方法充分考虑了高维空间中主分量的方向特性,能够精确计算出主分量之间的最小距离,从而提高了视频特征相似性度量的准确性．在 30000个视频片段数据库上的实验表明,新方法能够显著提高BCS技术的查询准确率．     

深度优先遍历△-tree的非递归KNN查询

kNN查询是高维数据库中最重要的操作之一,尽管它在数据库研究中得到了极大的关注,但很少有关于主存数据库kNN查询的工作.充分利用kNN查询自身的特点,基于高效的主存索引△-tree设计了一种新的kNN查询算法NR-DF-knn-Search,该算法采用非递归方式深度优先搜索△-tree中距离查询点较近的叶子节点,能够快速找到较优的kNN候选,更新修剪距离,加大剪枝力度,缩小搜索空间,从而提高kNN查询效率.通过实验对该算法进行了估价,结果证明该算法是有效的.     

高维索引机制中的降维方法综述

全面总结了现有的高维数据降维方法,深入分析比较了它们各自的优缺点,并从应用的角度指出其今后发展的趋势在于多种降维技术的合理组合,尤其是线性降维与非线性降维思想的有机结合。     

图像检索中的相似性判别及索引方法综述

基于内容的图像检索(CBIR)是对传统信息检索领域的扩展.它采用图像视觉内容的相似性判别进行查询.CBIR涉及到很多科学领域的课题.本文则仅主要综述CBIR技术中的相似性度量方法,索引方式,以及检索性能的评价.最后,分析了该领域现存的问题、最新研究动态及发展方向.     

基于DHT的高维数据相似性检索方法研究

以在P2P网络下实现对海量、高维数据的高效相似性检索为目标,提出PLCID索引方法(modified iDistance based on Proximity Location Code),该方法有效地缩小了需要搜索的范围,减少了数据对象间的距离计算次数,提高了检索性能;根据PLCID索引方法,在结构化P2P网络上实现高维数据检索.通过实验表明,相比原来的iDistance索引方法,在时间性能和系统开销上都有了明显提高.     

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

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

基于混合距离树的海量书法字索引

提出一种基于混合距离树的高维书法字索引方法以加速检索.首先将n个书法字通过层次聚类聚成若干类,然后分别计算每个字对应的统一化始点距离和质心距离,最后将两者结合生成索引键值.给定一个查询字,借助混合距离树索引完成高维书法字的查询.实验证明,该方法能够取得较高的查询效率,特别适合海量书法字检索.     

基于相关反馈的高维图像检索方法

传统索引方法在高维情况下会面临维数灾难问题，基于向量近似的索引方法是有效的高维检索方法．对向量近似方法中k近邻搜索算法加以改进，应用到基于相关反馈的交互式图像检索系统中．根据反馈过程前后的距离变化特性，在进行k近邻搜索过程中，将上轮次的查询结果和用户反馈信息用作过滤信息，可减少特征向量的访问数量．在大容量真实图像数据库上的实验表明，将新算法应用干相关反馈过程的图像检索中，可提高k近邻搜索速度．