Discovering the k Representative Skyline Over a Sliding Window
Discovering the k Representative Skyline Over a Sliding Window
复制标题
DOI：
10.1109/tkde.2016.2546242
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
Mei Bai;Junchang Xin;Guoren Wang;Luming Zhang;Roger Zimmermann;Ye Yuan;Xindong Wu
中科院分区：
文献类型：
--
作者：
Mei Bai;Junchang Xin;Guoren Wang;Luming Zhang;Roger Zimmermann;Ye Yuan;Xindong Wu
一个代表性的天际线包含$k$个天际线点，可以代表其相应的完整天际线。现有的$k$代表性天际线的测量标准是专门针对静态数据设计的，它们不能有效地处理流数据。在本文中，我们专注于问题的计算$k$代表天际线的数据流。首先，我们提出了一个新的标准来选择$k$天际线点作为$k$代表天际线的数据流环境，称为$k$最大优势天际线（$k$ -LDS），这是代表整个数据集，是高度稳定的流数据。其次，我们提出了一个有效的精确算法，称为基于前缀的算法（PBA），解决了$k$ -LDS问题在一个二维空间。PBA的时间复杂度仅为$\mathcal {O}（（M-k）\times k）$，其中$M$是完整天际线集的大小。第三，$d $维（$d\ge 3$）空间的$k$ -LDS问题变得非常复杂。因此，设计了一个贪婪算法来回答$k$ -LDS查询。为了进一步加速计算，我们提出了$\epsilon$ -greedy算法，可以实现$\frac{1}{（1+\epsilon）}（1-\frac{1}{\sqrt{e}}）$的近似因子。合成和真实世界的数据上的实验结果表明，我们的$k$ -LDS显着优于其竞争对手在数据流环境中。此外，我们证明了所提出的$\n $ -贪婪算法可以有效地解决$k$ -LDS，并具有竞争力的精度。
A representative skyline contains $k$ skyline points that can represent its corresponding full skyline. The existing measuring criteria of $k$ representative skylines are specifically designed for static data, and they cannot effectively handle streaming data. In this paper, we focus on the problem of calculating the $k$ representative skyline over data streams. First, we propose a new criterion to choose $k$ skyline points as the $k$ representative skyline for data stream environments, termed the $k$ largest dominance skyline ( $k$ -LDS), which is representative to the entire data set and is highly stable over the streaming data. Second, we propose an efficient exact algorithm, called Prefix-based Algorithm (PBA), to solve the $k$ -LDS problem in a 2-dimensional space. The time complexity of PBA is only $\mathcal {O}((M-k)\times k)$ where $M$ is the size of the full skyline set. Third, the $k$ -LDS problem for a $d$ -dimensional ( $d\ge 3$ ) space turns out to be very complex. Therefore, a greedy algorithm is designed to answer $k$ -LDS queries. To further accelerate the calculation, we propose a $\epsilon$ -greedy algorithm which can achieve an approximate factor of $\frac{1}{(1+\epsilon)}(1-\frac{1}{\sqrt{e}})$ . Experimental results on both synthetic and real-world data show that our $k$ -LDS significantly outperforms its competitors in data stream environments. Furthermore, we demonstrate that the proposed $\epsilon$ -greedy algorithm can solve $k$ -LDS efficiently and with a competitive accuracy.