空间连接(Spatial Join)操作是地理信息系统(Geographic Information System,GIS)空间数据库中最基本和最重要的操作之一。庞大的数据量导致空间数据读写和传输需要耗费较多的I/O资源；复杂的空间数据结构使得空间数据的连接操作大多基于计算几何的相关算法,算法复杂度较高,需要的计算资源也较多。鉴于以上原因,空间连接运算成为空间查询中最耗时、最复杂的操作,空间连接效率对于空间数据库的整体查询效率起决定作用。近些年,随着对地观测技术、传感器技术以及计算机技术的迅速发展,人们获取空间数据的手段不断丰富并日趋成熟,空间数据的数据量规模也突飞猛涨、与日俱增。如何对海量空间数据进行高效空间连接成为GIS的关键问题之一。云计算技术为解决这一问题提供了有效的支持：利用分布式存储技术可以缓解海量空间数据带来的存储压力；利用并行计算技术可以高效完成空间连接过程中复杂的计算几何算法。因此,将云计算技术应用于空间连接成为当前GIS领域的研究热点和未来的发展方向。空间数据划分是并行空间连接的前提和基础。在并行空间连接算法中,连接条件判定是耗时最长的步骤,这要求前期的数据划分结果具有尽量少的冗余数据,避免工作节点进行无效的空间连接操作。此外,在数据划分时需要对空间数据均衡划分,以使得不同的工作节点处理的任务量大体相当,提高系统的并行化性能。针对并行空间连接的数据划分需求,本文提出一种两轮映射的数据划分方法(Two Rounds Map Partitioning Method,TRM),能够有效地减少划分过程产生的冗余数据,同时使划分结果具备较好的数据量均衡性；然后,在此划分方法的基础上,基于MapReduce框架,提出一种基于两轮映射划分的多重筛选MapReduce并行空间连接算法(Parallelizing Spatial Join with Multiple Filter based TRM, TRMMFSJ),能够有效提高大数据量空间数据的空间连接效率；最后,将TRMMFSJ算法应用于Top-k空间连接查询中,并针对Top-k空间连接应用提出一种优化查询算法。具体研究内如下：(1)提出一种两轮映射的空间数据划分方法。分析现有空间数据划分方法的特点及其应用于并行空间连接时的适用性,针对现有并行空间连接中数据划分方法的不足——难以使划分结果保持低冗余、高均衡的特性,提出一种两轮映射数据划分算法TRM。该方法具有两点优势：1)在第一轮映射中通过充分利用划分对象的空间属性来减少冗余数据,通过合理设置阈值来均衡划分数据；2)在第二轮映射中通过动态映射机制,进一步提高划分结果的数据量均衡度。实验表明,TRM可以有效抑制冗余数据的产生,并大幅提高划分结果的数据量均衡度,同时具备较高的划分效率,具有很强的实用性。(2)提出一种基于两轮映射划分的多重筛选MapReduce并行空间连接算法。分析现有MapReduce框架下的空间连接算法原理,针对其数据划分和空间连接过程存在的问题,提出一种基于两轮映射划分的多重筛选MapReduce并行空间连接算法TRMMFSJ.该方法具有三点优势：1)两轮映射划分方法能够得到理想的数据划分结果,有利于后续并行空间连接算法的高效运行；2)并行空间连接过程中,采用多重筛选的空间连接策略,能够有效减少候选集中的对象数,从而降低精炼阶段的计算资源消耗;3)提出网格单元定位的冗余避免算法,能够在并行空间连接的过程中完全消除冗余任务,避免后续无效空间连接操作,提高算法运行效率。实验结果表明TRMMFSJ算法相比于MapReduce并行空间连接算法(Parallelizing Spatial Join with MapReduce,SJMR)具有更高的空间连接效率。(3)提出一种并行Top-k空间连接优化查询算法。Top-k空间连接是在空间连接基础上进行的一类特殊查询,返回前七个交叠/包含数最多的空间对象。利用Top-k空间连接可以从海量数据中迅速提取出重要信息,如交通高峰时段查询此时包含汽车数量最多的k个街区,即可得到交通拥堵区域。将TRMMFSJ算法应用于Top-k空间连接查询中,并针对Top-k空间连接的应用需求提出一种优化查询算法。该算法通过两步优化实现Top-k空间连接的高效操作：1)通过计数器完成对空间对象交叠／包含数的局部统计,并将局部统计结果替换空间对象作为输出数据,从而降低数据传输的资源消耗；2)将全局统计和Top-k结果获取整合到一个MapReduce作业中完成,避免了启动多个MapReduce任务对系统资源的消耗,提高了算法效率。实验结果表明应用TRMMFSJ进行Top-k空间连接能够显著降低查询耗时,同时优化查询算法具有更好的Top-k空间连接效率。