大规模分布式内容检索技术

《大规模分布式内容检索技术》围绕大规模分布式内容检索技术展开，通过结合对等网络的概念、结构、资源描述和组织、资源定位和路由选择、结果融合及排序方法等，从结构化对等网络、无结构对等网络、和混合式对等网络各自的特点出发，全面系统的阐述了各种环境下进行分布式大规模内容检索的策略。包括：基于结构化DHT的分布式全局倒排索引和文本检索策略；联邦式对等搜索策略；混合对等搜索策略。在每一类方法的讨论中作者结合自己的研究实践对已有工作的来龙去脉进行了详细深入地分析。

大规模分布式内容检索是近年来分布式系统方向的一个热点研究领域。陈汉华，金海的这本《大规模分布式内容检索技术》全面地阐述了各种体系结构的分布式大规模内容检索系统的关键技术和核心理论，并对各项技术和理论的来龙去脉进行了详细深入的分析。
《大规模分布式内容检索技术》通过丰富的文献资料和研究成果，从研究者的视角对大规模分布式内容检索技术进行了深入剖析，是分布式处理系统领域的学术专著。
《大规模分布式内容检索技术》可供高等院校计算机科学与技术相关专业的高年级本科生、研究生、教师、研究人员及工程技术人员阅读参考，也可作为相关专业的研究生教材。

序
前言
第1章 绪论
1.1 对等网络概述
1.2 基于对等模式的大规模分布式文本内容检索
1.3 大规模分布式文本内容检索研究面临的挑战
1.4 大规模分布式文本内容检索技术分类
1.4.1 基于结构化分布式哈希表的分布式全局倒排索引
1.4.2 基于非结构化对等网络的联邦式搜索网络
1.4.3 混合对等网络搜索引擎
1.5 本书内容
参考文献

第2章 分布式哈希表及单关键字全局索引
2.1 分布式哈希表
2.1.1 Chord：基于二分查找的环状对等结构
2.1.2 CAN：基于多维空间划分的对等结构
2.1.3 Pastry：基于多分查找的前缀匹配对等结构
2.1.4 Tapestry：基于多分查找的对等结构
2.2 现有分布式哈希表算法的比较
2.3 利用分布式哈希表构建单关键字全局索引
2.3.1 eSearch：基于分布式哈希表的水平索引
2.3.2 Minerva：在查询中挖掘关联关键字
2.3.3 局限性
参考文献

第3章 布隆滤波
3.1 哈希编码的时间/空间权衡
3.1.1 一种经典的哈希编码方法
3.1.2 两种存在误判率的哈希编码方法
3.1.3 计算因子
3.1.4 三种哈希编码方法的数学分析
3.1.5 时空性能比较
3.2 布隆滤波的基本理论
3.2.1 布隆滤波概念
3.2.2 位向量长度的下界
3.2.3 布隆滤波与集合运算
3.3 布隆滤波的扩展形式
3.3.1 计数布隆滤波
3.3.2 压缩布隆滤波
3.3.3 动态布隆滤波
3.4 布隆滤波的应用
3.4.1 早期应用
3.4.2 分布式缓存
3.4.3 P2P网络
3.4.4 资源路由
3.4.5 数据包路由
3.4.6 基础设施测量
参考文献

第4章 基于分布式哈希表单关键字索引的搜索
4.1 结构化对等网多关键字检索面临的挑战
4.2 Top-k查询策略
4.2.1 倒排索引
4.2.2 Top-k裁剪算法
4.2.3 性能评估
4.3 PWEB系统
4.3.1 PWEB网络结构
4.3.2 多关键字搜索通信开销优化策略
4.3.3 扩展性算法
4.3.4 分布式交集运算执行顺序优化策略
4.3.5 搜集关键字全局统计信息
4.3.6 模拟仿真方法
4.3.7 性能评估
4.4 小结
参考文献

第5章 多关键字全局索引及搜索
5.1 分布式关键字集索引面临的挑战
5.2 文本检索中的关键字权重方法
5.2.1 关键字权重模型TF×IDF
5.2.2 理解逆文档频率
5.2.3 用逆向总关键字频率替换逆文档频率的尝试
5.2.4 词频在相关权重模型中的探索
5.3 HDK：基于高区分关键字集的索引技术
5.3.1 关键字集倒排索引
5.3.2 高区分关键字集索引
5.3.3 基于高区分关键字集索引的搜索
5.3.4 扩展性分析
5.3.5 性能评估
5.4 TSS：基于关键字集索引的P2P搜索系统
5.4.1 TSS系统结构
5.4.2 分布式关键字集索引
5.4.3 模拟测试方法
5.4.4 性能评估
参考文献

第6章 基于复制的联邦式对等搜索策略
6.1 理论分析
6.1.1 模型建立
6.1.2 均匀复制策略和比例复制策略
6.1.3 平方根复制策略
6.1.4 混合复制策略
6.1.5 分布式复制算法的实现
6.2 基于随机游走的随机复制策略
6.2.1 生日悖论和理论下界
6.2.2 随机游走复制策略和搜索协议
6.2.3 性能评估
6.3 BubbleStorm：基于随机多图的概率穷尽搜索策略
6.3.1 副本数量的确定
6.3.2 网络大小的测量
6.3.3 随机多图与随机采样
6.3.4 洪泛和随机游走的完美结合
6.3.5 系统分析
6.3.6 性能评估
6.4 BloomCast：基于轻量级分布式哈希表的随机采样
6.4.1 BloomCast网络结构
6.4.2 网络结点数量估计
6.4.3 随机结点采样
6.4.4 基于布隆滤波的复制算法
6.4.5 多关键字搜索
6.4.6 性能评估
6.5 PlanetP：基于全局摘要索引的复制策略
6.5.1 全局目录索引复制
6.5.2 结点排序模型
6.5.3 查询处理算法
6.5.4 性能评估
参考文献

第7章 基于内容路由的联邦式搜索策略
7.1 基于语言模型的路由选择
7.1.1 联邦式搜索引擎的两层结构
7.1.2 语言模型
7.1.3 相对熵
7.1.4 搜索算法
7.1.5 性能评估
7.2 基于语义小世界模型的联邦式对等搜索
7.2.1 语义空间和向量
7.2.2 构造语义小世界
7.2.3 降低语义小世界的维度
7.2.4 基于语义小世界的搜索
7.2.5 性能评估
7.3 基于兴趣局部性的路由
7.3.1 兴趣局部性
7.3.2 基于兴趣局部性的拓扑和路由
7.3.3 性能评估
7.4 SemreX系统
7.4.1 SemreX系统模型
7.4.2 语义覆盖网
7.4.3 基于语义覆盖网的查询搜索算法
7.4.4 性能评估
参考文献

第8章 混合式对等搜索策略
8.1 混合对等搜索面临的挑战
8.2 基于预先探测的混合策略
8.2.1 Boon Thau Loo的Gnutella实验
8.2.2 SimplelHbrid混合P2P搜索策略
8.2.3 性能评估
8.3 基于Gossip的混合搜索选择
8.3.1 收集全局统计信息
8.3.2 使用全局信息进行搜索选择
8.3.3 洪泛阈值的调节
8.3.4 性能评估
8.4 难度感知的混合式搜索策略
8.4.1 很多复本≠很多结点
8.4.2 QRank设计
8.4.3 用QRank进行混合查询
8.4.4 自适应混合查询
8.4.5 QRank仿真器设计
8.4.6 性能评估
参考文献

第9章 大规模在线社会网络搜索
9.1 大规模在线社会网络搜索面临的挑战
9.2 在线社会网络系统研究现状
9.3 流行在线社会网络的数据划分与定位
9.4 大规模在线社会网络内容搜索关键技术
9.4.1 流式文本摘要技术
9.4.2 基于摘要索引的排序算法
9.4.3 多跳邻居摘要聚合技术
9.4.4 基于社区局部性降低摘要索引开销
参考文献

SBF在如下三种情况将出现问题。
①对于单机应用且集合为KUB时，SBF需要分配很大的空间来保证元素个数达到上限时依然有效，即假阳率不超过上限。由于需要预先分配较大空间，这种方法降低了SBF的空间效率，尤其是当这个动态集合在大部分时间元素个数都保持在一个较低的层次时，SBF空间利用率极低。因此，考虑设计一种随着集合规模改变而改变自身大小的布隆滤波，对于提高布隆滤波的空间利用率非常有意义。
②对于单机应用且集合为NKUB时，一般很难估计集合大小的上限，因此无法确定SBF的相关参数。当元素个数超过估计值时，SBT将会因为误判率超过阈值而变得不可用。
③对于分布式应用来说，所有的结点需要对SBF采用相同的配置来保证互操作性。在这种情况下，当某一个结点的SBF、误判率达到上限需要修改配置重新构建布隆滤波时，其他所有结点也需要修改成相同的配置并重新构建布隆滤波，这将不可避免地产生大量的开销。此外，一些结点上集合个数很小，但是为了保证相同的配置，其SBF占用的空间需要和其他结点上集合个数很大的SBF、的空间保持一致，这也降低了空间效率。
为了解决以上SBF的三个问题，Guo等［10］提出了动态布隆滤波的思想，在动态集合元素个数改变时可以动态地调整DBF的长度而不用像SBF需要重新构建。DBF的主要优势在于如下三个方面。
①在单机应用中，DBF可以扩充其容量，并且在元素个数增长时将其假阳率控制在某个指定范围内。此外，DBF可以支持数据删除与合并。
②在分布式应用中，DBF总能够满足结点问配置的一致性，同时避免SBF产生的空间浪费和通信开销。
③无论在单机应用还是分布式应用中，对于KUB的集合，DBF相对于SBF总能使用较少的存储空间；对于NKUB的集合，DBF、相对于SBF、表现得更加稳定即布隆滤波重构的次数更少。
下面对动态布隆滤波进行详细的理论分析。
（1）动态布隆滤波的定义DBF是由s个同构的SBF组成的。所谓同构是指这些SBF使用相同的哈希空间大小m和和k个哈希函数。由于DBF要支持元素的删除操作，因此这里每一个SBF都是计数布隆滤波。