中文摘要：

轮廓查询（Skyline）是一种典型的多目标优化问题.动态轮廓查询（Dynamic Skyline）是轮廓查询的一个重要变种,其目标是对于一个给定的查询点q,返回在各维度上最接近q的所有点.对比轮廓查询,动态轮廓查询根据查询点q的位置变动,可以更加灵活地返回查询结果.文中关注数据流上动态轮廓查询处理,此问题在多目标决策方面具有非常重要的应用.为有效地解决该问题,首先提出了一种组合式索引结构来管理数据流上的点,该索引结构包括两个部分：对整体数据使用分层次划分结构进行维护;对子划分内部数据采用倒排索引结构进行维护.该组合式索引结构具有更新快、过滤性能高、适合任意数据分布等优点,可以提高动态轮廓的查询处理效率.然后,基于该组合式索引结构,提出了基础的数据流上动态轮廓查询算法（Basic Dynamic Skyline Query over Data Stream,BDS2）.通过维护少量的数据,BDS2可以快速地计算出数据流上的动态轮廓集合.然而BDS2在处理个别更新时,会有较大的时间延迟,为了更稳定地计算数据流上的动态轮廓,避免更新某些点时计算量急剧增加,进一步提出了改进的数据流上动态轮廓查询算法（Improved Dynamic Skyline Query over Data Stream,IDS2）.最后,通过一系列的实验验证了文中所提出算法的有效性.

英文摘要：

Skyline query is a typical mulit-objective optimization problem. Dynamic Skyline is an important variant of skyline operator. Given a query point q, dynamic skyline query can return the tuples which are close to q in all the dimensions. Comparing with the skyline query, dynamic skyline can return the result flexibly by changing locations of the query point q. In this paper, we focus on the dynamic skyline query problem over the data stream, which plays a very important role in the multi-criteria decision making. To solve this problem efficiently, firstly, we propose a combined index structure to manage the data in the data stream. The combined index structure contains two parts, the whole data are managed by a hierarchical division structure; the data in the leaf division are managed by an inverted index structure. This combined index structure has some advantages, such as be updated fast, have high filtering capacity and be suitable for arbitrary data distributions. It can accelerate the speed of update operation over the data stream and improve the performance of dynamic skyline calculation. Secondly, based on this combined index, we propose the basic dynamic skyline query algorithm over data streams （BDS^2 for short）, which can quickly compute the dynamic skyline by maintaining a small amount of data. However, BDS^2 has a long delay when dealing with some updates. In order to calculate the dynamic skyline stably over the data stream and avoid a sharp increase in calculation when updating some points, we propose the improved dynamic skyline query algorithm over data stream （IDS2 for short）. Finally, we verify the effectiveness of our proposed algorithms through a series of experiments.