Time- and Space-Efficient Sliding Window Top-k Query Processing
Time- and Space-Efficient Sliding Window Top-k Query Processing
复制标题
DOI：
10.1145/2736701
复制
发表时间：
2015-03
期刊：
影响因子：
--
通讯作者：
K. Pripužić;Ivana Podnar Žarko;K. Aberer
中科院分区：
文献类型：
--
作者：
K. Pripužić;Ivana Podnar Žarko;K. Aberer
滑动窗口top-k（top-k/w）查询监视大小为w的滑动窗口内的传入数据流对象，以识别随时间相对于给定评分函数的k个最高排名的对象。这种查询的处理是具有挑战性的，因为即使当对象在进入处理系统时不是前k/w对象时，它也可能在将来成为前k/w对象。因此，一组潜在的top-k/w对象必须存储在存储器中，同时其大小应被最小化以有效地科普高数据流速率。现有的方法通常存储top-k/w和候选滑动窗口对象中的k-skyband在一个二维的分数时间空间。然而，由于k-skyband的不断变化，其维护成本相当高。Probbbank-skyband是一种新的数据结构，存储来自滑动窗口的数据流对象，这些对象在未来有很大的概率成为top-k/w对象。连续概率k-天空波段维护提供了相当大的改进的运行时性能相比，k-天空波段维护，特别是对于大的k值，在一个小的和可控的错误率为代价。我们提出了两种可能的概率k-skyband用法：（i）当它被用来处理所有的滑动窗口对象，所得到的top-k/w算法是近似的，足以处理随机顺序的数据流。(ii)当概率k-skyband仅用于处理最近滑动窗口对象的一个子集时，它可以提高连续k-skyband维护的运行时性能，从而产生一种新的精确top-k/w算法。我们的实验评估系统地比较了不同的top-k/w处理算法，并表明，而竞争算法提供的时间效率在空间效率的膨胀，反之亦然，我们的算法的基础上的概率k-skyband的时间和空间效率。
A sliding window top-k (top-k/w) query monitors incoming data stream objects within a sliding window of size w to identify the k highest-ranked objects with respect to a given scoring function over time. Processing of such queries is challenging because, even when an object is not a top-k/w object at the time when it enters the processing system, it might become one in the future. Thus a set of potential top-k/w objects has to be stored in memory while its size should be minimized to efficiently cope with high data streaming rates. Existing approaches typically store top-k/w and candidate sliding window objects in a k-skyband over a two-dimensional score-time space. However, due to continuous changes of the k-skyband, its maintenance is quite costly. Probabilistic k-skyband is a novel data structure storing data stream objects from a sliding window with significant probability to become top-k/w objects in future. Continuous probabilistic k-skyband maintenance offers considerably improved runtime performance compared to k-skyband maintenance, especially for large values of k, at the expense of a small and controllable error rate. We propose two possible probabilistic k-skyband usages: (i) When it is used to process all sliding window objects, the resulting top-k/w algorithm is approximate and adequate for processing random-order data streams. (ii) When probabilistic k-skyband is used to process only a subset of most recent sliding window objects, it can improve the runtime performance of continuous k-skyband maintenance, resulting in a novel exact top-k/w algorithm. Our experimental evaluation systematically compares different top-k/w processing algorithms and shows that while competing algorithms offer either time efficiency at the expanse of space efficiency or vice-versa, our algorithms based on the probabilistic k-skyband are both time and space efficient.