Continuous top-$k$query over sliding window is a fundamental challenge in the domain of streaming data management. Specifically, a continuous top-k query$q$monitors the window$W$, returning the$k$objects with the highest scores to the system with each slide of the window. This paper delves into one of its important variants, referred to as multiple continuous top.$k$queries over data stream, which holds significant applications. While various efforts have been made to support continuous top-k query, few have addressed the complexities of multiple continuous top-k queries. The prevailing approach involves selecting a minimal number of objects in the window as candidates, incrementally maintaining them, and using them to support query processing as efficiently as possible. However, these endeavors exhibit sensitivity to the query workload scale or query parameters such as$k$, the window length$n$, and others. Consequently, they incur high running/space cost in updating the candidate set. In this paper, we propose a novel index PH-Tree (Partition and Heap-based Binary Tree), designed to facilitate multiple continuous top-k queries. We partition the query window into a group of disjoint partitions and use PH-Tree to organize these partitions. Additionally, the PH-Tree allows for flexible candidate selection based on the size of each partition, parameter distribution of queries and score distribution of objects. We further develop a group of efficient algorithms to support candidate set incremental maintenance and query processing. The effectiveness and efficiency of the proposed algorithms are validated through extensive theoretical analysis and exneriments detailed in this paper.

Complex event matching has gained a lot of at-tention for evaluating complex queries over event streams. The events composing a complex event occur within a user-specified time window and can be nonconsecutive on the stream. Existing methods widely utilize the state automaton to match complex events. However, the state automaton is typically used for matching consecutive items satisfying a pattern, e.g., the regular expression. To support nonconsecutive event matching, it has to maintain a large number of partial matches and skip irrelevant events, which results in a huge overhead. To avoid this problem, we employ the bit parallelism technique to match complex events continuously in this paper. We utilize a set of bit sequences to represent the events, where each bit is associated with a time slice, and an event is mapped to a 1-bit of the sequence if its timestamp belongs to the time slice. Then, bit-parallel operations are designed to process the constraints defined on the complex event, e.g., the time window limitation, and sequential order of the events, etc. We further propose the bit-parallel algorithms to support continuous complex event matching using these bit operations. Our experiments on real and synthetic datasets demonstrate that our method outperforms the existing methods by up to an order of magnitude in Query efficiency.

Radius-bounded$k$-core queries (RB-$k$-core queries) in geo-social networks aim to find all$k$-cores containing a given query vertex$q$while all vertices in each$k$-core fall into a circle under a given query radius$r$, which is widely used in many applications, such as team formulation and event organization. However, the query parameters$k$and$r$are hard to specify by the users without any background knowledge, which means the query results often do not meet the users' requirements, i.e., some expected vertices are missed in the query results. To tackle this issue, we investigate the problem of exploring optimal refined parameters (EOP) for expected results on RB­$k$-core queries, which aims to explore the optimal parameters that make the expected vertex$\omega$and query vertex$q$appear in the same RB-$k$-core. To address the EOP problem, we first propose two baseline algorithms, namely PriorityR and HybridR, which refine the parameters$k$and$r$simultaneously based on the effective bounds of the refined$r^{\prime}$• To enhance the efficiency of exploring optimal parameters, we develop two efficient al-gorithms. The first algorithm, Priority K, simultaneously refines both parameters based on the effective bound of the refined$k$• The second algorithm, HybridK, explores the optimal parameters using the continuous convergence bounds of the refined$k^{\prime}$and$r$• Furthermore, to enhance exploration efficiency, we develop a novel index, called HCR-Tree, based on the hierarchical coreness of vertices and R- Tree. This index accelerates the verification of whether the coreness of a vertex in any sub graph exceeds$k$in the above algorithms. Finally, we conduct extensive experiments using five real geo-social network datasets, which show that the optimal parameters can be explored effectively by the algorithms, and HybridK is the most effective. Meanwhile, the HCR- Tree performs better than the R- Tree for the EOP problem.

k-closest pair (KCP for short) search is a fundamental problem in database research. Given a set of d-dimensional streaming data S, KCP search aims to retrieve k pairs with the shortest distances between them. While existing works have studied continuous 1-closest pair query (i.e., k=1) over dynamic data environments, which allow for object insertions/deletions, they require high computational costs and cannot easily support KCP search with k>1. This paper investigates the problem of KCP search over data stream, aiming to incrementally maintain as few pairs as possible to support KCP search with arbitrarily k. To achieve this, we introduce the concept of NNS (short for N earest N eighbour pair- S et), which consists of all the nearest neighbour pairs and allows us to support KCP search via only accessing O(k) objects. We further observe that in most cases, we only need to use a small portion of NNS to answer KCP search as typically kłl n. Based on this observation, we propose TNNS (short for T hreshold-based NN pair S et), which contains a small number of high-quality NN pairs, and a partition named τ-DLBP (short for τ- D istance L ower- B ound based P artition) to organize objects, with τ being an integer significantly smaller than n. τ-DLBP organizes objects using up to O(łog n / τ) partitions and is able to support the construction and update of TNNS efficiently.

Continuous top-k query over streaming data is a fundamental problem in database. In this paper, we focus on sliding window scenario, where a continuous top-k query returns the top-k objects within each query window on the data stream. Existing algorithms support this type of queries via incrementally maintaining a subset of objects in the window and try to retrieve the answer from this subset as much as possible whenever the window slides. However, since all the existing algorithms are sensitive to query parameters and data distribution, they all suffer from expensive incremental maintenance cost. In this paper, we propose a self-adaptive partition framework to support continuous top-k query. It partitions the window into subwindows and only maintains a small number of candidates with highest scores in each sub-window. Based on this framework, we have developed several partition algorithms to cater for different object distributions and query parameters. It is the first algorithm that achieves logarithmic complexity w.r.t. k for incremental maintaining the candidate set even in the worst case.

Continuous top-k query over streaming data is a fundamental problem in database. In this paper, we focus on the sliding window scenario, where a continuous top-k query returns the top-k objects within each query window on the data stream. Existing algorithms support this type of queries via incrementally maintaining a subset of objects in the window and try to retrieve the answer from this subset as much as possible whenever the window slides. However, since all the existing algorithms are sensitive to query parameters and data distribution, they all suffer from expensive incremental maintenance cost. In this paper, we propose a self-adaptive partition framework to support continuous top-k query. It partitions the window into sub-windows and only maintains a small number of candidates with highest scores in each sub-window. Based on this framework, we have developed several partition algorithms to cater for different object distributions and query parameters. To our best knowledge, it is the first algorithm that achieves logarithmic complexity w.r.t. k for incrementally maintaining the candidate set even in the worstcase scenarios.