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.