论文部分内容阅读
随着互联网技术的快速发展以及各种网络通讯设备的迅速普及,Web数据的规模呈指数级增长,Web服务已渗入人们的日常生活。与此同时,Web用户数量也在与日俱增,这些用户使用Web服务来便捷日常生活已成常态。Web数据和Web用户的快速增长,迫切需要我们设计高效的Web数据管理系统来满足用户日益增长的个性化需求。Web数据管理系统,通过获取Web数据源上的数据,来为用户提供高质量、带有附加值的数据服务。其中Web用户查询的高效调度和Web数据的高效获取,是用户满意和Web数据管理系统成功的关键。Web用户查询的高效调度是指对用户查询的执行设计排序策略,有效地提升系统的性能。高效的查询调度使得Web数据管理系统提供用户更好的服务体验,潜在增加系统管理者的经济收入。与此同时,用户查询的目标是为了获取高质量的数据进行决策支持,因此我们还需要从众多的Web数据源上获取数据。然而Web数据源的自治性、动态性、重叠性和海量性给我们快速获取时新、完整的Web数据带来重大挑战。因此为了能够提供Web用户高质量的数据服务,开展面向Web数据的高效查询调度和数据获取方法的研究具有重要的社会意义和经济价值。本研究以Web数据为对象,研究如何提高基于公共子表达式结果共享的查询调度的性能,如何提高在动态Web环境下基于top-k查询约束的深网增量爬取效率,以及如何提高从海量Web数据源中选择高相关、低重叠数据源集合的效率。具体而言,本文主要包括以下四个研究工作:(1)基于公共子表达式结果共享的查询调度用户在数据空间中注册个性化查询,进而在数据管理系统中找到满足需求的数据。然而Web数据的动态变化,需要系统有效调度查询,更快更多地“按需获取”Web数据源上的新数据。针对现有查询调度工作中未考虑查询相关性,导致冗余工作重复执行降低查询效率的问题,本文提出一种基于公共子表达式结果共享的查询调度方法,高效地调度用户查询,提高用户满意度。为了综合衡量调度的效率和效果,本文首先定义用户满意度为查询的收益率QHR(Query Harvest Rate),即查询结果中新元组数量和查询处理时间的比率。然后提出了基于查询表达式的查询划分策略,提取查询之间的公共子表达式,去除冗余的查询部分。最后,本文针对查询收益率设计了查询优先级,有效地共享公共子表达式结果,最大化总体QHR。基于TPC-H数据集上的实验结果表明,本文方法能够有效地优化QHR。(2)基于top-k查询约束的深网增量爬取在仅允许top-k查询的动态Web数据源中,爬虫获取变化元组时也会得到不变的元组,导致爬取效率低下。本文提出一种基于查询树自底向上的增量爬取方法,在查询类型约束(top-k查询)和查询资源约束下高效爬取已变化的元组。首先,本文基于top-k查询生成查询树,基于查询树获取有效的叶子查询集合,利用历史数据和领域知识估计这些叶子查询的变化规律和变化所需的查询代价;其次,基于估计的查询数据质量增益和查询代价,在深网数据源查询次数约束下,建模爬取问题为背包问题,并近似地选择最优的查询子集,获取时新的查询结果,最大化本地数据质量。基于Microsoft Academic Graph数据集上的实验结果表明,本文方法较好地提高动态深网数据源爬取的效率和本地数据质量。(3)基于分层抽样的重叠深网数据源选择针对海量深网数据源中查询在多个数据源上的结果重叠导致查询效率低下的问题,本文提出一种元组水平分层抽样的数据源选择方法,高效地选择高相关、低重叠的数据源集合。首先,本文设计了一种基于误差约束的分层抽样方法,利用样本精确估计查询在各数据源上的覆盖率;其次,本文提出一种基于部分样本数据的数据源重叠率精确估计方法,利用给定的样本和已查询数据源的结果来估计查询在数据源上的重叠;最后,本文基于估计的统计数据提出一种启发式的高效重叠数据源选择方法(类似KNN方法),选择高相关、低重叠的数据源集合。基于TPC-W合成数据集和Abebooks真实数据集上的实验结果表明,本文方法不仅能保证用户查询结果的精度,同时相比传统的方法能够显著提高效率。(4)T-Music:个性化Web音乐系统基于上述Web数据管理及其关键技术的研究成果,本文研发了 T-Music,一个以多媒体音乐数据服务和数据管理为核心的个性化Web音乐系统。T-Music以数据服务层、数据管理层以及数据获取层为基本的三层架构。为了提高系统的性能,T-Music在数据服务层通过查询调度来提高数据空间中用户的满意度,在数据管理层通过增量爬取提高top-k查询约束时获取时新数据的效率,在数据获取层通过数据源选择来提高多数据源选择的性能。开发完成的原型系统在实际中得到了应用,本文在Sogou音乐网上爬取到的音乐数据集上1进行了测试,实验结果证明了本文方法在Web数据管理方面的优越性。