面向计算密集型的海量数据查询处理关键技术研究

随着社会经济的迅速发展，面对海量数据的计算密集型查询处理需求日益增加，呈现出数据大规模、类型多样化、计算复杂化等特点。这些需求和特点都对传统的海量数据管理和查询处理方式提出了新的挑战。本项目以构建可靠、高效、低成本的大规模数据查询处理平台为目标，以大规模数据的存储、分布、索引、查询处理及用户接口等为研究重点，研究有利于在线数据高效查询和离线数据可靠备份的分布式存储体系结构、高效的大规模数据存取访问机制、大规模异构数据的索引管理机制、智能调度与任务管理机制以及面向用户的高效并行查询语言及新型编程模型等基本理论和关键技术，并为智能电网、电子商务等行业需要构建自适应性强、性能好的计算密集型应用平台提供基础。本课题的研究工作具有重要的理论价值和现实意义，将对大规模数据管理的基础理论与关键技术的研究起到重要推动作用，对其在航空航天、天文气象等国家重要领域的应用起到引导作用。

随着社会经济的迅速发展，面对海量数据的计算密集型查询处理需求日益增加，呈现出数据大规模、类型多样化、计算复杂化等特点。这些需求和特点都对传统的海量数据管理和查询处理方式提出了新的挑战。本项目以大规模数据的存储、分布、索引、查询处理等为研究重点，从海量数据的特点出发，提出了利用非结构化数据的子结构来设计面向计算密集型查询的索引结构和剪枝方法。具体的，在本课题的研究过程中，我们研究了三类典型的查询“字符串匹配查询”，“图匹配查询”和“多属性Skyline查询”。我们利用数据预处理、索引、过滤及提炼的框架进行字符串查询处理。在预处理过程中，引入了有效的数据结构——n-gram对字符串的特征进行提取，并设计出两层索引机制、剪枝算法TA和CA过滤不在查询结果之内的字符串，从而得到查询的候选结果集。基于该研究成果的论文已经被国际顶尖会议VLDB 2014录用并发表。同时为了解决图数据中的近似匹配问题，我们根据已有的框架结构，利用图的子结构特征创建了两层索引SEGOS，该方法可以增加剪枝的能力，但同时它也会增大查询过程中索引过滤的代价。在研究过程当中，我们动态的调整子结构的复杂度，以使得最终建立的索引达到最低的查询代价。基于该研究成果的论文已经被国际顶尖会议ICDE 2012以长文形式发表。大规模分布式系统中高效率数据访问与查询的关键因素是路由路径的选择, 而基本路由算法在实际应用中往往引起很大的通讯负担，特别是在大规模分布式系统中会产生网络堵塞。鉴于此，我们给出了一个分布式概率skyline 查询的处理框架，以及分布式概率 skyline 查询处理算法DSUD和e-DSUD，利用中央服务器提供的反馈信息，删除本地节点上不可能成为查询结果的数据，从而加速查询处理的时间并减少网络的通讯负担，基于该研究成果的论文已经被国际顶尖期刊IEEE TKDE发表。本课题研究过程中，我们已经在国内外期刊和会议上发表学术论文12篇，其中计算机学会推荐的顶级（A类）期刊/会议论文3篇，包括IEEE TKDE, VLDB, ICDE等。根据Google Scholar统计，本项目所发表的论文，目前已被国内外同行引用40余次。在人才培养方面，本项目总共培养研究生9名，其中包括博士3名和硕士6名。