.png){kind=icon}
.png){kind=icon}
Return
Optimizing Multi-Top-k Queries over Uncertain Data Streams
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2012.126.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Query processing over uncertain data streams, in particular top-k query processing, has become increasingly important due to its wide application in many fields such as sensor network monitoring and internet traffic control. In many real applications, multiple top-k queries are registered in the system. Sharing the results of these queries is a key factor in saving the computation cost and providing real-time response. However, due to the complex semantics of uncertain top-k query processing, it is nontrivial to implement sharing among different top-k queries and few works have addressed the sharing issue. In this paper, we formulate various types of sharing among multiple top-k queries over uncertain data streams based on the frequency upper bound of each top-k query. We present an optimal dynamic programming solution as well as a more efficient (in terms of time and space complexity) greedy algorithm to compute the execution plan of executing queries for saving the computation cost between them. Experiments have demonstrated that the greedy algorithm can find the optimal solution in most cases, and it can almost achieve the same performance (in terms of latency and throughput) as the dynamic programming approach.
Keywords:
Data streams
uncertain data streams
top-k query
multiquery optimization
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.4
Papers:
6.7K
Citations:
3.2W