# SHARP: Shared State Reduction for Efficient Matching of Sequential Patterns

arXiv: https://arxiv.org/abs/2507.04872 · HTML: https://mlsanity.com/paper/2507.04872/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Generation and context integration, one of 15 directions in Retrieval-augmented generation.
- Builds on 18 of its 84 references that are in the map.
- First posted on arXiv 7 Jul 2025.

## Placed in

- Retrieval-augmented generation / [Generation and context integration](https://mlsanity.com/rag/generation-and-context-integration/)

## Builds on (most cited first, 18 of 18)

- [Graph Retrieval-Augmented Generation: A Survey](https://mlsanity.com/paper/2408.08921/) (2024)
- [Variational Reasoning for Question Answering with Knowledge Graph](https://mlsanity.com/paper/1709.04071/) (2017)
- [HybridRAG: Integrating Knowledge Graphs and Vector Retrieval Augmented Generation for Efficient Information Extraction](https://mlsanity.com/paper/2408.04948/) (2024)
- [Paths-over-Graph: Knowledge Graph Empowered Large Language Model Reasoning](https://mlsanity.com/paper/2410.14211/) (2024)
- [KG-GPT: A General Framework for Reasoning on Knowledge Graphs Using Large Language Models](https://mlsanity.com/paper/2310.11220/) (2023)
- [Direct Evaluation of Chain-of-Thought in Multi-hop Reasoning with Knowledge Graphs](https://mlsanity.com/paper/2402.11199/) (2024)
- [Foundations of Modern Query Languages for Graph Databases](https://mlsanity.com/paper/1610.06264/) (2016)
- [VerdictDB: Universalizing Approximate Query Processing](https://mlsanity.com/paper/1804.00770/) (2018)
- [eSPICE: Probabilistic Load Shedding from Input Event Streams in Complex Event Processing](https://mlsanity.com/paper/2002.05896/) (2020)
- [On Load Shedding in Complex Event Processing](https://mlsanity.com/paper/1312.4283/) (2013)
- [pSPICE: Partial Match Shedding for Complex Event Processing](https://mlsanity.com/paper/2002.04436/) (2020)
- [Regular Path Query Evaluation on Streaming Graphs](https://mlsanity.com/paper/2004.02012/) (2020)
- [hSPICE: State-Aware Event Shedding in Complex Event Processing](https://mlsanity.com/paper/2006.08211/) (2020)
- [GRETA: Graph-based Real-time Event Trend Aggregation](https://mlsanity.com/paper/2010.02988/) (2020)
- [Sharon: Shared Online Event Sequence Aggregation](https://mlsanity.com/paper/2010.02989/) (2020)
- [To Share, or not to Share Online Event Trend Aggregation Over Bursty Event Streams](https://mlsanity.com/paper/2101.00361/) (2021)
- [Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing](https://mlsanity.com/paper/2103.15994/) (2021)
- [Real-Time, Low-Latency Surveillance Using Entropy-Based Adaptive Buffering and MobileNetV2 on Edge Devices](https://mlsanity.com/paper/2506.14833/) (2025)

## Abstract (arXiv)

The detection of sequential patterns in data is a basic functionality of modern data processing systems for complex event processing (CEP), OLAP, and retrieval-augmented generation (RAG). In practice, pattern matching is challenging, since common applications rely on a large set of patterns that shall be evaluated with tight latency bounds. At the same time, matching needs to maintain state, i.e., intermediate results, that grows exponentially in the input size. Hence, systems turn to best-effort processing, striving for maximal recall under a latency bound. Existing techniques, however, consider each pattern in isolation, neglecting the optimization potential induced by state sharing in pattern matching. In this paper, we present SHARP, a library that employs state reduction to achieve efficient best-effort pattern matching. To this end, SHARP incorporates state sharing between patterns through a new abstraction, coined pattern-sharing degree (PSD). At runtime, this abstraction facilitates the categorization and indexing of partial pattern matches. Based thereon, once a latency bound is exceeded, SHARP realizes best-effort processing by selecting a subset of partial matches for further processing in constant time. In experiments with real-world data, SHARP achieves a recall of 97%, 96% and 73% for pattern matching in CEP, OLAP, and RAG applications, under a bound of 50% of the average processing latency.