李 松，李 爽，张丽平，郝晓红

哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080

障碍空间中基于R+树的空间Skyline查询方法*

李 松+，李 爽，张丽平，郝晓红

哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080

为了解决已有研究成果无法有效解决障碍空间中的空间Skyline查询问题，提出了障碍物环境下基于R+树的空间Skyline查询方法——SOS算法。该算法采用了两个过程：过滤过程和精炼过程。过滤过程主要是利用R+树的快速定位特性有效地剪枝掉大量被支配的数据点，缩小查询范围，提高算法效率。精炼过程主要根据障碍距离以及数据点与查询点间的拓扑关系对候选集中数据点进行二次筛选，最终得到Skyline集合。进一步给出新增点的ADD_SOS算法和删除点的DEN_SOS算法。理论研究和实验结果表明，该算法在处理障碍空间中的空间Skyline查询问题时具有优势。

R+树；空间Skyline查询；障碍空间；障碍距离

1 引言

由于“空间数据爆炸但知识贫乏”的现象，利用空间数据挖掘和知识发现（spatial data mining and knowledge discovery，SDMKD）从空间数据库中挖掘事先未知却潜在有用的空间模式变得十分重要[1]。其中空间数据库中的各种查询方法为空间数据分析和空间知识发现等提供了有力支持。空间数据库查询包括点查询、窗口查询[2]、区域查询[3]、最近邻查询[4-5]、聚类查询和空间Skyline查询[6]等。而在这些查询中，空间Skyline查询作为一种用户偏好查询，应用极其广泛。

Skyline查询在市场分析、决策制定、数据挖掘、知识发现、数据检索和计量经济学等方面有着广泛的应用。例如，金融商务需要搜集大量数据，并分析这些数据，发现其模式和特征，同时可能发现个体、消费群体或组织的金融和商业兴趣，并可推测整个市场的变化走势。……