学位论文 > 优秀研究生学位论文题录展示

基于DHT的索引结构研究

作　者: 汤宇哲
导　师: 周水庚
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 分布式哈希表查询处理数据索引负载平衡分布式算法
分类号: TP311.13
类　型: 硕士论文
年　份: 2009年
下　载: 72次
引　用: 0次
阅　读: 论文下载

内容摘要

近年来,随着DHT(分布式哈希表)的发明,各种大规模高容错的分布式系统在实际应用中变得十分普遍。基于DHT的各种应用需求也随之应运而生,例如一些基于DHT的数据库系统就具有复杂查询的需求。但是,由于DHT中的哈希方程破坏了数据放置的邻近性,在DHT系统中支持复杂查询变成一件十分困难的事情。在现有的方法中,一部分方法通过修改DHT内部结构来重新设计系统,而另外一部分则通过在DHT上层建立索引来支持复杂查询。后一种方法由于基于模块化思想而更具有实用性,因此我们采用这种方法。在本文中,我们研究了如下问题:如何利用DHT对外的通用接口来构建高效的分布式查询系统。我们提出了一套完整的方法(m)-LIGHT来进行DHT上的索引和查询处理。(m)-LIGHT包括一维索引LIGHT和多维索引m-LIGHT。首先,我们考察了一维的情况,并提出了索引方法LIGHT。LIGHT通过一种全新的命名机制将索引结构分布地放置到DHT上,由此提高了查询性能并降低了索引维护开销。就查询处理而言,LIGHT能实现性能的最优化,具体的包括范围查询,k-NN查询和Min/Max查询。同时LIGHT也减少了维护索引的带宽需求。我们进一步研究了多维数据的情况,并提出了m-LIGHT。相似的,m-LIGHT能实现查询处理和索引维护上的高效性,并且极大的减轻了在多维数据下常见的负载不均衡的情况。具体而言,我们扩展了原有一维的命名方程,将多维索引结构合理的分布到底层DHT系统中。同时,m-LIGHT采用一种数据分布相关的分裂方法来对索引进行分布式维护,并由此实现负载平衡的最优化。我们进行了广泛的真实实验来测量和评定(m)-LIGHT的性能。与当前其他基于DHT的索引方法相比,(m)-LIGHT节省了相当多的索引维护开销,实现了更加平衡的负载分布,并且在带宽消耗和查询延迟上都提高了查询处理的性能。

全文目录

摘要  5-6
Abstract  6-7
第一章引言  7-10
  1.1 研究背景与意义  7-8
  1.2 研究内容与取得的成果  8-9
  1.3 本文结构  9-10
第二章相关工作  10-14
  2.1 DHT覆盖网络  10
  2.2 P2P索引系统  10-13
    2.2.1 基于DHT的索引  10-12
    2.2.2 依赖覆盖网的索引  12-13
  2.3 P2P多维索引方法  13
  2.4 小结  13-14
第三章一维P2P索引方法  14-37
  3.1 LIGHT的索引结构  14-18
    3.1.1 系统总览  14
    3.1.2 空间划分树  14-16
    3.1.3 本地树的存储  16-17
    3.1.4 命名方程  17-18
  3.2 LIGHT查找  18-20
  3.3 增量式索引维护  20-24
    3.3.1 数据插入和叶节点分裂  20-21
    3.3.2 数据删除与叶节点合并  21-23
    3.3.3 索引维护开销的分析  23-24
  3.4 复杂查询处理  24-28
    3.4.1 范围查询  24-27
    3.4.2 并行化的范围查询处理  27
    3.4.3 Min/Max查询  27-28
    3.4.4 k-NN查询  28
  3.5 实验评定  28-37
    3.5.1 实验设置  28-30
    3.5.2 索引的结构特征  30
    3.5.3 查找性能  30-31
    3.5.4 索引维护开销  31-34
    3.5.5 范围查询性能  34-36
    3.5.6 实验小结  36-37
第四章多维P2P索引方法  37-51
  4.1 m-LIGHT索引结构  37-40
    4.1.1 空间划分kd树  37
    4.1.2 m维命名方程  37-40
  4.2 索引结构的维护  40-44
    4.2.1 增量式索引维护  40-41
    4.2.2 数据敏感的分裂策略  41-42
    4.2.3 存储负载的平衡最优性  42-43
    4.2.4 数据删除  43-44
  4.3 范围查询处理  44-46
    4.3.1 基本范围查询算法  44-45
    4.3.2 并行范围查询算法  45-46
  4.4 实验评定  46-51
    4.4.1 实验设置  46-47
    4.4.2 索引维护开销  47
    4.4.3 数据敏感分裂下的负载平衡  47-48
    4.4.4 多维范围查询性能  48-50
    4.4.5 实验小结  50-51
第五章结束语  51-52
  5.1 未来工作  51
    5.1.1 查询负载平衡和数据副本  51
    5.1.2 数据缓存  51
  5.2 全文小结  51-52
参考文献  52-56
发表文章目录  56-57
致谢  57-58

相似论文

支持XML数据查询的F&B索引结构的研究,TP311.13
海量多数据库集成系统的查询处理研究,TP311.13
频繁图结构并行挖掘算法的研究与实现,TP311.13
遥感数据处理网格平台的设计与初步实现,TP79
概率XML文档中Holistic Twig查询处理算法的研究与实现,TP311.13
Linux集群环境下作业调度算法的研究与实现,TP301.6
不确定数据及相关性表示性实时概率查询处理,TP311.13
无线传感器网络节点三维定位算法研究,TN929.5
基于网络存储的流媒体服务器系统,TN919.8
无线传感器网络路由算法研究,TP212.9
网络环境下的分布式存储系统的设计与实现,TP333
配电网单相接地故障隔离方法的研究,TM862
在线备份系统中存储服务器的研究与实现,TP333
网络实体及其关系信息的组织和搜索,TP391.3
基于数据挖掘的社区网站用户行为分析系统,TP393.092
基于Agent实时监控系统的研究与实践,TP277
基于JAVA的多数据库中间件的设计与实现,TP311.10
基于分布式的频繁闭合模式挖掘算法研究,TP311.13
一种适用于井下超声波通信的FSK调制解调技术研究,TN914
分布式声源定位与跟踪算法研究,TN912.3
面向位置服务的轨迹数据时空索引技术研究,P208