Query processing over uncertain data streams, in particular top-kquery processing, has become increasingly importantdue to its wide application in many fields such as sensor network monitoring and internet traffic control. In many real applications,multiple top-kqueries are registered in the system. Sharing the results of these queries is a key factor in saving the computation costand providing real-time response. However, due to the complex semantics of uncertain top-kquery processing, it is nontrivial toimplement sharing among different top-kqueries and few works have addressed the sharing issue. In this paper, we formulate varioustypes of sharing among multiple top-kqueries over uncertain data streams based on the frequency upper bound of each top-kquery.We present an optimal dynamic programming solution as well as a more efficient (in terms of time and space complexity) greedyalgorithm to compute the execution plan of executing queries for saving the computation cost between them. Experiments havedemonstrated 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. Optimizing Multi-Top-k Queries over Uncertain Data Streams