对等计算系统中的相似查询处理研究

论文题目: 对等计算系统中的相似查询处理研究

论文类型: 博士论文

论文专业: 计算机软件与理论

作者: 徐林昊

导师: 周傲英

关键词: 对等计算,相似查询,索引,缓存,概率

文献来源: 复旦大学

发表年度: 2005

论文摘要: 对等计算(peer-to-peer computing，简称P2P)已经成为了计算机科学领域的研究热点。在对等计算系统中，每个节点都是完全自治的，拥有相同的责任，扮演着双重角色—既可以是客户机(服务消费者)，也可以足服务器(服务提供者)，而且任意一个节点都可以随意地加入或退出系统。因此，对等计算系统是一个完全动态的、没有任何集中控制的分布式系统。对等计算模型具有许多潜在的优势，如扩展性强、鲁棒性好、资源可用性高等特点，特别适用于具有地理分布、资源异构、扩展性要求高、局部自治等特征的分布式系统。因而，对等计算模型推动了“以主机为中心(host-centric)”的传统互联网向“以数据为中心(data-centric)”的未来互联网的发展，被学术界和工业界公认为是重构基于互联网应用的关键技术之一。虽然，学术界已经取得了不少对等计算环境下的查询处理研究成果，但仍然存在着许多有待研究与解决问题。本文研究了对等计算环境下的相似查询问题，探索了对等计算环境下的基于路由索引、数据空间划分、协作缓存和概率模型的相似查询处理技术，旨在为现有的对等计算系统提供基于语义或者相似度的查询处理功能。本文的主要贡献有如下四个方面：1．将多维数据空间中的相似查询处理(similarity search)技术引入到无结构(unstructured)对等计算系统中，利用近似向量(vector approximation)技术和路由索引(routing index)技术，为系统中的每个节点建立基于近似向量的路由索引，使得用户查询能够准确地路由到并且有效地查询拥有相关数据资源的节点，实现无结构对等计算系统中的相似查询处理。另外，利用无结构对等计算系统中的网络自配置(self-reconfiguration)特性，通过动态调整节点在网络中的位置，使得与相似查询相关的节点保持位置邻近，进一步提高了系统的查询处理性能。仿真实验表明，该方法对无结构对等计算环境下的相似查询处理非常有效。2．将数据空间划分(space partitioning)技术引入到结构化(structured)对等计算系统中，通过选定的代表点(reference point)，将整个数据空间划分成没有任何重叠(overlap)的数据子空间。通过将代表点线性化，在节点、代表点和数据子空间三者之间建立起一一映射关系。利用传统的高维索引技术和基于分布式散列表(distributed hash table，或DHT)的资源查找和定位机制，使得高维数据空间中的相似查询处理在结构化对等计算系统上得以实现。此外，通过维护数据子空间之间的物理邻近(physical proximity)特征，降低了系统的查询路由代价；通过调整数据子空间的粒度，达到均衡系统负载(load balance)的目的。仿真实验表明，该方法能够有效地适应数据维度的增长和系统规模的扩展。3．针对关系查询处理，探索了基于协商(negotiation)的协作缓存技术(collaborative caching)，提出了一种基于网络传输代价的查询代价模型，用于评价不同查询计划的执行代价。在对等计算环境下，一个查询计划的执行代价可以被分解为子查询计划的执行代价。结合代价模型，利用协调重叠网络(collaborative overlap network)，通过查询请求节点(requester)和协调节点(coordinator)之间的协商，确定协作缓存的逻辑查询表达式和参与数据缓存的查询请求节点，实现了对等计算环境下的基于语义的查询处理。仿真和真实实验表明，该方法能够确定较优的数据缓存放置策略，降低系统的查询处理开销。尤其是在单个节点仅能贡献有限的存储资源的情况下，该方法的优势更为明显。4．针对基于主题(topic)的对等计算文件共享系统，研究了一种基于概率的相似查询处理技术。该技术的核心思想是利用概率模型(probabilistic model)描述共享主题之间的语义重叠度(overlap)以及节点对主题的信息覆盖度(coverage)，为节点建立起概率路由信息。相似查询处理算法以每个节点已有的概率信息为基础，依据推导出的邻居节点对查询主题的覆盖度，决定主题查询的搜索路径。此外，利用查询反馈的信息，通过更新路由查询的节点上的概率信息，使得这些节点能够为将来的主题查询选择更准确的查询搜索路径。模拟实验表明，该方法能够利用基于自反馈的概率更新算法，逐步改善查询处理的效果，提高查询处理的效率。总之，本文详细地介绍了四种相似查询处理方法的算法设计与实现，以及测试结果。这些方法是对现有对等计算环境下的查询处理技术的有益补充和改进。本文的研究工作建立在对当前已有技术的详尽分析与理论研究，以及大量的实验测试的基础上。实验和分析表明，与当前对等计算环境下的查询处理技术相比，上述方法在查询效率和资源利用率等方面具有优势。

论文目录:

中文摘要

英文摘要

图目录

第一章绪论

1.1 对等计算概述

1.1.1 对等计算发展历史简要回顾

1.1.2 对等计算发展现状简介

1.2 本文的研究目标、内容与面临的挑战

1.2.1 研究目标与内容

1.2.2 面临的挑战

1.3 本文的组织结构

第二章对等计算查询处理研究进展

2.1 对等计算研究简介

2.2 从查询处理角度研究对等计算

2.2.1 主题查询处理

2.2.2 关系或XML查询处理

2.2.3 范围或k-最近邻查询处理

2.2.4 连续查询处理

2.2.5 信息检索

2.3 本章小结

第三章基于路由索引的相似查询处理

3.1 引言

3.2 应用场景与问题描述

3.3 基于路由索引的相似查询处理

3.3.1 近似向量技术

3.3.2 扩展近似向量路由索引

3.3.3 相似查询处理

3.3.4 网络自配置

3.4 索引的建立与维护

3.4.1 索引的建立

3.4.2 索引的维护

3.4.3 关于路由索引的性能分析

3.5 性能评价

3.5.1 实验设置

3.5.2 实验结果与分析

3.6 本章小结

第四章基于空间划分的相似查询处理

4.1 引言

4.2 数据空间划分

4.2.1 如何选取代表点

4.2.2 生成代表点

4.2.3 划分数据空间

4.3 一个结构化P2P相似查询处理系统

4.3.1 概述

4.3.2 节点结构

4.3.3 查询路由

4.3.4 节点的加入与退出

4.4 相似查询处理

4.4.1 范围查询处理

4.4.2 k-最近邻查询处理

4.5 负载均衡

4.5.1 基于采样的负载均衡策略

4.5.2 主动的负载均衡策略

4.5.3 数据倾斜、单元格粒度和负载均衡三者之间的关系

4.6 性能评价

4.6.1 实验设置

4.6.2 实验结果与分析

4.7 本章小结

第五章基于协作缓存的相似查询处理

5.1 引言

5.2 基于协作缓存的P2P查询处理系统

5.2.1 协调重叠网络

5.2.2 节点的加入与退出

5.2.3 节点失效

5.3 基于协作缓存的查询处理

5.4 协作缓存的建立过程

5.4.1 缓存计划的初始化

5.4.2 查询者与协调者之间的协商

5.4.3 协作缓存的建立

5.4.4 查询处理的实现

5.5 性能评价

5.5.1 仿真实验设置

5.5.2 仿真实验结果与分析

5.5.3 真实实验环境设置

5.5.4 真实实验结果与分析

5.6 本章小结

第六章基于概率信息的相似查询处

6.1 引言

6.2 应用场景描述

6.2.1 主题查询与节点描述

6.3 两种概率信息

6.3.1 概述

6.3.2 主题之间的重叠度

6.3.3 节点对主题的覆盖度

6.4 相似查询处理算法

6.5 概率信息的建立与维护

6.5.1 概率信息的初始化

6.5.2 概率信息的更新

6.6 性能评价

6.6.1 实验设置

6.6.2 实验结果与分析

6.7 本章小结

第七章总结与展望

7.1 本文工作的总结

7.2 未来工作的展望

参考文献

攻读博士期间发表的论文

致谢

发布时间: 2007-06-28

参考文献

[1].对等计算中的分布式路由算法及其安全性研究[D]. 周世杰.电子科技大学2004
[2].基于对等计算的信息检索技术[D]. 凌波.复旦大学2004
[3].对等计算系统中的数据管理[D]. 钱卫宁.复旦大学2004
[4].对等计算中的若干问题研究[D]. 宋建涛.复旦大学2004
[5].基于复杂网络理论的对等计算系统关键技术研究[D]. 黄新力.上海交通大学2006
[6].基于对等计算的信息共享相关技术研究[D]. 唐九阳.国防科学技术大学2006
[7].移动对等计算资源定位与分发技术研究[D]. 左克.国防科学技术大学2010
[8].基于对等计算的无线射频识别网络若干问题研究[D]. 徐鹤.南京邮电大学2012
[9].大规模对等资源共享关键技术研究[D]. 刘勇.电子科技大学2010
[10].基于格雷码的结构化对等计算系统及其数据管理[D]. 周敏奇.复旦大学2008

对等计算系统中的相似查询处理研究

猜你喜欢