Radius-bounded$k$-core queries (RB-$k$-core queries) in geo-social networks aim to identify all$k$-cores containing a given query vertex$q$, where all vertices in each$k$-core fall within a circle defined by a specified query radius$r$. These queries are widely used in applications such as team formation and event organization. However, specifying query parameters$k$and$r$can be challenging for users without domain expertise, often resulting in misaligned query results. Specifically, some expected vertices may be missing, while unexpected vertices may appear in the results. To address this issue, we investigate the problem ofexploringoptimalrefinedparametersforexpected(EOPE) andunexpected(EOPU) results in RB-$k$-core queries. The goal is to explore optimal parameters that ensure the expected vertex$\omega$(or unexpected vertex$\psi$) and query vertex$q$appear (or do not appear) in the same RB-$k$-core. For the EOPE problem, we first propose two baseline algorithms:PriorityRandHybridR. To improve efficiency, we develop two more advanced algorithms:PriorityKandHybridK. Additionally, we introduce a novel index calledHCR-Tree, based on hierarchical coreness of vertices and R-Tree, to enhance exploration efficiency. For the EOPU problem, we begin with a basic solution (BS) and then design the segmentation algorithmSA, which incorporates effective pruning and termination strategies. We conduct extensive experiments on five real-world geo-social network datasets. The results demonstrate that our proposed algorithms effectively explore optimal parameters. Among them,HybridKproves most effective for EOPE, whileSAperforms best for EOPU. Furthermore,HCR-Treeoutperforms R-Tree for both EOPE and EOPU problems.

The advent of Single Instruction Multiple Data (SIMD) instructions in modern processors has revolutionized data processing by enabling simultaneous computation across multiple data elements. While database systems have extensively adopted SIMD for traditional operations, its potential for complex event pattern matching remains largely unexplored. This paper presents a novel approach that bridges this gap through bit-parallel processing enhanced with AVX-512 vectorization. Our approach encodes event streams into compact bit sequences, where each bit corresponds to a time slice, and an event's presence is marked by a 1-bit when its timestamp falls within the respective slice. This representation enables the formulation of bit-parallel operations that natively enforce complex event constraints, including temporal window requirements and event ordering relationships. We develop a family of bit-parallel algorithms that leverage this representation for continuous event matching, and further optimize their performance through SIMD vectorization (AVX-512 instructions) to exploit modern hardware parallelism. Experimental evaluations on both real-world and synthetic datasets demonstrate the superiority of our method, achieving at least 35.7x improvement in query efficiency compared to state-of-the-art alternatives.

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.

Graph clustering plays a crucial role in analyzing graph data. Among various clustering techniques, Structural Graph Clustering (SCAN) stands out for its ability to not only identify clusters but also recognize hubs and outliers. Evaluating the robustness of graph clustering methods is essential, and manipulating SCAN is an effective approach for this purpose. However, the scarcity of efficient manipulation techniques for SCAN poses a significant challenge, hindering the development of robust structural graph clustering algorithms. To address this issue, we investigate the problem of efficiently manipulating SCAN by strategically inserting a maximum number of$\tau$edges to maximize the increment of the$\epsilon$-neighborhood$(\Delta N_{\epsilon}[t])$under Jaccard similarity around a given target vertex$t$. This problem termed Maximum$\epsilon$. Neighborhood (MaxN), is NP-hard and non-monotonic. To tackle this, we first develop efficient edge insertion strategies and present a basic algorithm MaxNS. Then, we propose an effective algorithm, IncreMaxNS, that incrementally calculates the vertex costs in each round. Furthermore, we explore a pruning and optimization algorithm, called pMaxNS, which uses a novel strategy to select a valid candidate vertex set based on the budget$\tau$, eliminating the need to evaluate all vertices in the graph. Finally, we conduct extensive experiments on seven real-world datasets, which demonstrate that our algorithm pMaxNS significantly improves manipulation efficiency, achieving 1-1.5 orders of magnitude speedup compared to the state-of-the-art approach, while consistently delivering high-quality results.

As more detailed POI (Point of Interest) information has been incorporated into road network, routing has evolved from finding paths from one place to another, to satisfying users’ needs (keywords) along the trip. However, the existing solutions either only support one keyword per POI, or require a fixed visiting order, or only provide one option to choose from. Therefore, we study the top-k Optimal Routes with Collective Spatial Keywords (k-ORCSK) problem, which is the most general keyword-aware routing problem that supports multiple keywords, arbitrary orders, and top-k results. To solve this problem, we apply an enumeration framework and reduce the complexity by contracting non POI-related vertices and taking the keywords into account. After that, we propose a best-first path expansion method DA-CSK based on deviation to convert the enumeration paradigm from the distance-oriented to the keyword-oriented. Finally, several optimization techniques are provided to further improve the query efficiency. Extensive experiments conducted on multiple real-life road networks show that our method can provide higher quality results more efficiently.

Existing electronic map apps, such as Baidu map, AutoNavi map, Google map, only provide the services “find k nearest POIs around me” and “give me the bus plan from s to d”. But they cannot answer “give me k POIs that I can reach earliest within one transfer by bus”. Such type of query is to find k nearest neighbors (kNN) on public transportation network (PTN), that is, returns k POIs whose arrival time are earliest starting from query location at some time and the number of required transfers is less than the user-specified constrain. Existing kNN algorithm on road network cannot be directly applied on PTN due to the more complex line combinations. Two algorithms TT-INE and TT-IER are proposed based on Incremental Network Expansion and Incremental Euclidean Restriction respectively. To address the loss of efficiency caused by the proliferation of alternative routes, a pruning strategy based on the route dominance relationship is designed. Moreover, to filter those stations who are not associated with POIs, a node compression method is also proposed, And a grid index is utilized to prune the POIs far away from the query based on the upper bound of arrival time. Extensive experiments have been conducted based on the real data of Beijing's PTN. Experimental results show that the TT-INE algorithm with pruning strategy is two orders of magnitude faster than the traditional incremental expansion method. When POIs are sparse, i.e. the percentage of POIs is 1 %, TT-IER is an order of magnitude faster than TT-INE.

Outsourcing data services to the public cloud will help data owners save administrative costs, while it may bring privacy concerns. To guarantee the confidentiality of sensitive data against the untrusted cloud and unauthorized users, one way is to have the cloud perform the query processing with encrypted query requests over outsourced encrypted data. However, it is of great challenge to support various types of query processing, especially those of answering why-not questions, under data encryption settings without sensitive information leakage. In this paper, we define and solve the problem of answering why-not questions on top-$k$queries with privacy protection. To address the problem, we propose two Secure Why-Not top$k$Query (SWN$k$Q) processing approaches. In the basic approach, we adopt the Paillier cryptosystem to guarantee the semantic security of data and queries and propose two new secure protocols to support computations on ciphertext in SWN$k$Q processing. Then, we propose a secure weighing space generation method for obtaining the best approximate refined query. To solve the efficiency problem of the basic approach, we further propose an optimized approach, in which dominance-based secure data pruning and early stopping conditions are presented to improve the query efficiency by pruning searching space in the retrieval of refined queries. Thorough analysis shows the security and computational complexity of our approaches, and extensive experimental results on real datasets further demonstrate the query performance of our approaches.