结构化对等网络上的多维数据查询研究

摘要

近年来，对等网络上的多维数据查询在数据库研究领域逐渐引起关注，在处理精确匹配查询和区间查询方面已经提出不少解决算法和相应的查询系统。然而，这些系统却不能扩展支持其他复杂的多维数据查询，比如多个属性之间有约束关系的Skyline查询。针对Skyline查询，现今大多数研究专注在传统的集中式系统领域，在对等网络这样的分布式环境中处理Skyline查询还需要探索合理高效的解决方案。所谓高效的查询处理方案，在对等网络上应该满足以下几点要求：(1)查询结果非单个值时，在查询过程中渐进地返回结果；(2)降低查询处理的网络开销，包括减少不必要的节点访问，以及避免冗余消息在网络上传播；(3)在各节点之间平衡查询负载。遗憾的是，现有的研究工作没有对分布查询性能做足够的优化，尚不能完全满足这些要求。针对上述问题，本文在结构化对等网络上提出包含精确匹配查询、区间查询、Skyline查询以及扩展的决策支持查询等的多维数据查询整体化解决方案，并满足上述要求。 本文的解决方案基于一个现有的一维平衡树结构的对等网络，在这个基础网络层上建立了适合多维数据查询的分布式索引结构。在查询过程中，根据数据存取模式动态地切分搜索空间，缓解了区间查询和Skyline查询处理中潜在的查询传播热点问题。通过估算、定位查询子区间里的目标节点，有效地控制了查询转发数量，减少重复的节点访问，同时避免冗余消息在网络中传播。除此之外，在节点加入、退出时通过平均分割查询负载的方法来划分数据空间，并在系统平稳运行态时定期进行动态负载调整，达到了查询负载均衡。最后，在真实数据和合成数据集上进行了充分实验，结果验证了本文算法在结构化对等网络上的有效性和可扩展性。

目录

文摘

英文文摘

声明

第一章 引言

1.1研究背景及动机

1.2研究内容

第二章 相关研究工作

2.1对等网络

2.2 Skyline查询

第三章 结构化对等网络上的多维数据查询系统

3.1研究问题定义

3.2 BATON简介

3.3多维数据的分布式索引结构

3.4多维数据空间划分

第四章 精确匹配查询

第五章 区间查询

第六章Skyline查询

6.1 Skyline搜索空间

6.2搜索空间动态切分及优化

6.3 SSP查询算法

第七章扩展的Skyline查询

7.1 Top K Skyline查询

7.2约束区间Skyline查询优化

第八章 查询负载均衡

第九章 实验结果及分析

9.1实验度量

9.2网络规模影响

9.3数据维数影响

9.4数据集规模影响

9.5真实数据实验结果

9.6查询负载平衡效果

9.7查询响应时间

第十章 结论及展望

致谢

参考文献