随着移动互联网与智能手机的高速发展,基于位置的服务(Location Based Service,简称LBS)逐渐成为一种基础服务。在基于位置的服务中,用户往往需要考虑实体在空间上的密集程度(密度)。如何在组织空间数据时标记实体的密度,以提高查询的有效性和服务的质量,是非常有价值的应用研究课题。另一方面,LBS业务高度依赖于迅猛增长的空间数据,同时用户在使用位置服务过程中又不断产生新的带有位置信息的空间数据,随着时间积累数据量将会越来越大。海量空间数据对高效组织方法和高效查询算法提出了极高的要求。本文的主要工作是面对海量空间数据,设计合理的算法同时满足空间查询的有效性和实时性两个要求。k最近邻(k-Nearest Neighbor,简称kNN)查询是LBS中的重要操作。已有空间数据管理kNN查询研究中,很少关心查询结果之间的位置关系,没有考虑实体密度因素,从而造成查询结果正确但是并不一定合理的情况。本文首先从空间数据的密度属性入手,通过R树建立过程中的节点分裂操作,加入密度属性值,基于R树和R*树的分裂方法提出了 DR树(Density R-tree)及其分裂方法,并设计了基于DR树的范围查询算法。利用DR树的密度属性值,减少了k N查询中的遍历次数和最后一次查询包含的实体数量,进一步优化了k N查询算法,提升了kNN查询的有效性和效率,达到海量空间数据查询的有效性要求。对于海量空间数据,传统集中式处理方法很难达到实时性的要求,于是要求对大数据集分块为小数据集,然后将每一个分块数据送入到分布式系统进行处理。其中,分块技术是分布式kNN连接查询中的第一步且重要的环节。已有分块方法存在分块之间地理位置不相关、分块大小不均匀、分块的额外开销太大、与现有系统不兼容等缺点。本文结合R树最小外接矩形特性和四叉树可固定树高,分块地理位置相关特性,提出一种新的分块方法——QR树分块算法,在一次扫描数据集的基础上达到了地理位置相关和均匀分块两个要求。在QR树分块算法基础之上提出了 QR树分块过滤算法,可以大幅度过滤掉不相关分块。在分布式kNN连接的第一次MapReduce阶段,通过合理的分块技术和过滤技术大幅度降低任务启动数量,最佳情况下降低到原来任务数量的约1/20。将海量数据进行分块处理,并且通过过滤技术将并行任务最大程度降低,最终达到了海量空间数据查询的实时性要求。最后基于Java EE平台实现了一个可演示空间查询系统,系统支持DR树范围查询、DR树kNN查询和QR树kNN连接操作。在南京市饭店和北京出租车两个真实数据集上通过实验验证了 DR树范围查询、DR树kNN查询和QR树分块过滤算法在有效性和效率方面的明显优势。