中文摘要：

无线数据广播环境下位置相关Skyline查询综合了Skyline计算、位置相关查询与数据广播三方面的特性，能很好地满足数量众多、资源受限且运动模式多变的移动客户端对广播数据的复杂查询需求，因而可广泛地应用于智能交通、物流管理、数字战场等涉及到位置相关服务的移动计算领域。与传统的Skyline查询相比，由于受应用环境(无线数据广播)和应用特征(位置相关、移动查询点)的影响，无线数据广播环境下位置相关Skyline查询面临诸多新的问题。本项目在深入分析无线数据广播环境下位置相关Skyline查询问题的特征、约束、需求与性能评价标准的基础上，以低能耗为优化目标，研究支持动态偏好、增量计算、网络距离度量的有效的广播数据组织模式、索引结构与高效的位置相关Skyline查询处理算法。本项目的研究有助于丰富和完善Skyline查询理论成果，拓广其应用范围，从而为相关产业的发展提供理论与技术支持。

结论摘要：

Skyline查询是一个典型的多目标优化问题，在多目标决策、数据挖掘等领域有着重要的应用。考虑到现实生活中许多信息都与地理位置紧密相关，位置相关Skyline查询作为Skyline查询的一种新的类型被提出，并广泛地应用在交通导航、物流配送、紧急救援等众多移动应用领域。现有的位置相关Skyline查询算法常假定基于传统的Client/Server计算模式，即Client向Server发送查询请求，Server接收请求后执行查询并将结果返回Client。在这样一种计算模式中，所有的计算任务都落在Server上，随着Client数目的增长，Server将遭遇性能瓶颈。数据广播的“一次传送，无限共享”的特点则能很好地满足数量众多移动客户端对热点数据的访问需求。将数据广播技术与位置相关Skyline查询相结合，在现有的数据广播平台上提供支持多目标决策的位置相关Skyline查询功能，是一项有着广泛应用前景的研究项目。本项目在深入分析数据广播环境下位置相关Skyline查询问题的特征、约束、需求与性能评价标准的基础上，以低能耗为优化目标，研究广播数据组织模式、索引结构与位置相关Skyline查询处理算法。主要研究成果包括1）在广播数据组织模式方面，提出了一种新的基于分类和排序的(k, m)交错广播数据组织模式；2）在节能且高效的位置相关Skyline查询处理算法方面，采用巧妙的过滤和提纯策略，设计出节能且高效的位置相关skyline查询算法；3）在连续查询中增量计算方面，提出了基于Peer-to-Peer共享的连续位置相关Skyline查询的方法；4）在查询结果的有效性验证与增量维护方面，提出了采用有效区域、通过共享临近Peer的查询结果来计算位置相关Skyline查询的新方法；5）在不同距离度量问题上，除了常规的欧式距离，针对网络距离，提出了一种新的基于路径的受限最近邻查询，从理论上证明了该类查询可转化为离散交叉节点上静态最近邻查询；6）在并行Skyline查询方面，分别提出基于衰减式网格划分和基于角度划分的并行Skyline查询算法；7）设计原型系统，通过广泛实验证明了上述方法的优越性。上述成果分别发表在IEEE Transactions等期刊和DEXA、DASFAA、ApWeb等国际会议上，对丰富与完善Skyline查询理论成果，拓广其应用范围有着大的促进作用。