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.

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.

We study the efficient regular expression (regex) matching problem. Existing algorithms are scanning-based algorithms that typically use an equivalent automaton compiled from the regex query to verify a document. Although some works propose various strategies to quickly jump to candidate locations in a document where a query result may appear, they still need to utilize the scanning-based method to verify these candidate locations. These methods become inefficient when there are still many candidate locations needed to be verified. In this paper, we propose a novel approach to efficiently compute all matching positions for a regex query purely based on a positional q-gram inverted index. We propose a gram-driven NFA to represent the language of a regex and show all regex matching locations can be obtained by finding positions on q-grams of GNFA that satisfy certain positional constraints. Then we propose several GNFA-based query plans to answer the query using the positional inverted index. In order to improve the query efficiency, we design the algorithm to build a tree-based query plan by carefully choosing a checking order for positional constraints. Experimental results on real-world datasets show that our method outperforms state-of-the-art methods by up to an order of magnitude in query efficiency.

We study the efficient regular expression (regex) matching problem. Existing algorithms are the scanning-based algorithms which typically use an equivalent automaton compiled from the regex query to verify a document. Although some works propose various strategies to quickly jump tocandidate locationsin a document where a query result may appear, they still need to utilize the scanning-based method to verify these candidate locations. These methods become inefficient when there are still many candidate locations needed to be verified. In this article, we propose a novel approach to efficiently compute all matching positions for a regex query purely based on a positional$q$-gram inverted index. We propose a gram-driven NFA to represent the language of a regex and show all regex matching locations can be obtained by finding positions on$q$-grams of GNFA that satisfy certain positional constraints. Then we propose several GNFA-based query plans to answer the query using the positional inverted index. In order to improve the query efficiency, we design the algorithm to build a tree-based query plan by carefully choosing a checking order for positional constraints. Experimental results on real-world datasets show that our method outperforms state-of-the-art methods by up to an order of magnitude in query efficiency.

The problem of finding matches of a regular expression (RE) on a string exists in many applications, such as text editing, biosequence search, and shell commands. Existing techniques first identify candidates using substrings in the RE, then verify each of them using an automaton. These techniques become inefficient when there are many candidate occurrences that need to be verified. In this article, we propose a novel technique that prunes false negatives by utilizing negative factors , which are substrings that cannot appear in an answer. A main advantage of the technique is that it can be integrated with many existing algorithms to improve their efficiency significantly. We present a detailed description of this technique. We develop an efficient algorithm that utilizes negative factors to prune candidates, then improve it by using bit operations to process negative factors in parallel. We show that negative factors, when used with necessary factors (substrings that must appear in each answer), can achieve much better pruning power. We analyze the large number of negative factors, and develop an algorithm for finding a small number of high-quality negative factors. We conducted a thorough experimental study of this technique on real datasets, including DNA sequences, proteins, and text documents, and show significant performance improvement of the state-of-the-art tools by an order of magnitude.

The problem of finding matches of a regular expression (RE) on a string exists in many applications such as text editing, biosequence search, and shell commands. Existing techniques first identify candidates using substrings in the RE, then verify each of them using an automaton. These techniques become inefficient when there are many candidate occurrences that need to be verified. In this paper we propose a novel technique that prunes false negatives by utilizing negative factors, which are substrings that cannot appear in an answer. A main advantage of the technique is that it can be integrated with many existing algorithms to improve their efficiency significantly. We give a full specification of this technique. We develop an efficient algorithm that utilizes negative factors to prune candidates, then improve it by using bit operations to process negative factors in parallel. We show that negative factors, when used together with necessary factors (substrings that must appear in each answer), can achieve much better pruning power. We analyze the large number of negative factors, and develop an algorithm for finding a small number of high-quality negative factors. We conducted a thorough experimental study of this technique on real data sets, including DNA sequences, proteins, and text documents, and show the significant performance improvement when applying the technique in existing algorithms. For instance, it improved the search speed of the popular Gnu Grep tool by 11 to 74 times for text documents.