ACM Transactions on Database Systems · 2015 · 33 citations · 22 references
ComputingComputer ScienceComputer SystemsData ManagementData StructuresDatabasesQuery ProcessingStream ProcessingStreaming AlgorithmsRuntime PerformanceSliding Window AlgorithmsSliding WindowsStream Query ProcessingStreaming Data ProcessingStreaming DatabasesTop-k Query ProcessingTop-k Searching
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.
22
Issues in data stream management
Lukasz Golab, M. TAMER ÖZSU · ACM SIGMOD Record · 2003 · 916 citations
Progressive skyline computation in database systems
Dimitris Papadias, Yufei Tao, Greg Fu et al. · ACM Transactions on Database Systems · 2005 · 886 citations
Sliding-window top-k queries on uncertain streams
Cheqing Jin, Ke Yi, Lei Chen et al. · Proceedings of the VLDB Endowment · 2008 · 150 citations
Panayiotis Tsaparas, Themis Palpanas, Yannis Kotidis et al. · 2004 · 97 citations · Full text