P2P网络中高维数据对象相似性检索方法研究

摘要

为了在P2P网络上实现对海量多媒体信息的高效访问，多媒体信息处理和检索工具的研制成为了当前研究的一个热点。传统的关系数据库和建立在其上的精确数据查询已经无法满足应用的要求，基于内容的多媒体信息检索技术不断取得研究进展。基于内容的信息检索需要为多媒体数据如文本、图像、音频、视频等数据建立索引来有效支持越来越复杂多样的查询请求，如此引出一个非常具有挑战性的研究课题：如何在P2P上实现海量、高维的特征矢量数据(从多媒体对象中提取，用来表征多媒体对象的内容)的相似性检索。 本文以在P2P网络下实现对海量、高维数据的高效相似性检索为目标，进行了如下的工作： (1)提出了PLCID索引方法(modified iDistance based on Proximity Location Code)，该方法利用近似向量表示法和一维向量转换法的优点，在检索时，采用两层过滤处理：首先通过距离映射，进行一维数值的检索；其次，比较近似位置编码。该方法有效地缩小了需要搜索的范围，减少了数据对象间的距离计算次数，从而提高了检索性能。 (2)基于PLCID索引方法，在结构化P2P网络上实现高维数据检索。通过实验表明，相比原来的iDistance索引方法，在时间性能上提高了30％左右，系统开销缩小了20％左右。 (3)对网络中存在的负载均衡问题，提出一种基于采样的均衡方案；并利用基于负载变化和分发代价的方法，对网络中节点的负载进行度量。实验表明，该方法具有良好的负载均衡效果。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景及意义

1.1.1高维数据检索

1.1.2 P2P系统

1.1.3 P2P中的高维数据对象检索

1.2本文主要工作

1.3本文组织结构

第二章高维数据索引研究

2.1高维数据查询方式

2.2向量空间和度量空间

2.3 向量空间与度量空间索引方法及其异同点

2.4向量空间高维数据索引

2.4.1 R-树

2.4.2 R+-树

2.4.3其他几种索引

2.5度量空间高维数据索引

2.5.1 BK-树

2.5.2 FQ-树相关

2.5.3 BS-树相关

2.5.4 VP-树相关

2.5.5 M-树相关

2.5.6 Pyramid技术

2.5.7 iDistance方法

2.6本章总结

第三章P2P网络下的高维数据检索研究

3.1 P2P技术

3.1.1 P2P系统的分类

3.1.2结构化P2P网络

3.2 P2P网络中多维数据对象的相似性检索

3.2.1基于空间填充曲线的范围划分

3.2.2基于kd-树的多维超立方体

3.2.3 SkipIndex

3.2.4 pSearch

3.3本章总结

第四章P2P网络下的高维数据相似性检索方法

4.1 引言

4.2 PLCID：基于近似位置信息的iDistance索引方法

4.2.1高维数据压缩

4.2.2检索方法

4.2.3对性能的分析

4.3数据空间划分及参考点的选择

4.3.1基于空间的划分策略

4.3.2基于数据的划分策略

4.3.3参考点评价及数据空间划分方法

4.4基于PLCID的结构化P2P相似性检索系统

4.4.1基本思想

4.4.2节点结构

4.4.3节点的加入与退出

4.4.4相似查询的处理过程

4.5实验结果与分析

4.5.1实验设计

4.5.2数据及分析

4.6本章总结

第五章基于负载变化和分发代价的负载均衡方法

5.1基于采样的负载均衡方案

5.2存在的问题

5.2 LVDCB：基于负载变化和分发代价的负载均衡方法

5.3实验与分析

5.4本章总结

第六章总结与展望

6.1 本文工作的总结

6.2未来工作的展望

参考文献

致谢

硕士期间发表的学术论文与参与的研究项目