论文部分内容阅读
时空数据管理是时态数据管理和空间数据管理的统一体,包括时间与空间两个要素,主要用于管理和储存位置或形状随时间变化的空间对象。时空数据管理可以应用于环境变迁研究、行政区域管理、地籍管理等诸多领域中。与此同时,基于Map-Reduce的云计算以其廉价、容错等优良特性,成为商业中逐渐普及的计算模式。在进行时空数据管理时,经常用到Top-k、k最近邻和skyline查询问题。这些问题都是具有可分解性的。但在应用这些算法到Map-Reduce框架时,中间结果不能被很好的过滤掉,影响了这些算法在云计算领域的应用范围。针对这一问题,本文基于Map-Reduce框架提出了Map-Filter-Reduce计算框架。首先,通过分析在Map-Reduce框架上处理Top-k、k最近邻和skyline查询等可分解时空查询问题的特殊性,提出了Map-Filter-Reduce计算框架及其编程接口,并对其可扩展性和容错性进行了分析。其次,本文在Map-Filter-Reduce框架的基础上,提出了Lazy、Eager、Hybrid和Prepositive的调度策略,并对这些调度策略进行了比较与分析。再次,本文详细介绍了如何利用Map-Reduce-Filter计算框架,选择合适的过滤器来处理Top-k, k最近邻和skyline时空数据查询问题,并对算法的正确性进行了分析。最后,本文以丰富的合成数据集评估了Map-Filter-Reduce框架,实验结果显示本文提出的Map-Filter-Reduce框架在查询时间和中间结果数量等方面都优于原有的Map-Reduce框架,具有良好的可扩展性。