Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns
Proceedings of the VLDB Endowment · 01.01.2026 · 19 (5) · 987-1000
DOI: 10.14778/3796195.3796210 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 05.05.2026. Verfasst von Cong Yu und 3 weiteren Autor:innen. Die Arbeit nennt 83 Literaturangaben.
Abstract (Originalsprache)
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, the respective engines typically evaluate multiple shared patterns simultaneously, in order to improve the result quality for downstream applications. The evaluation of a large number of patterns under tight latency bounds is challenging, though, since matching needs to maintain state , i.e., intermediate results, that grow exponentially in the input size. Hence, systems turn to best-effort processing, striving for maximal recall under a latency bound. Existing techniques, however, consider patterns in isolation, neglecting the optimization potential induced by state sharing and corresponding interactions and interference across shared patterns. We describe Sharp, a state management library that employs state reduction for efficient best-effort pattern matching in shared patterns. To this end, Sharp incorporates state sharing between patterns through a new abstraction, coined pattern-sharing degree (PSD). At runtime, PSD facilitates the categorization and indexing of partial pattern matches. Once a latency bound is exceeded, Sharp realizes best-effort processing by using a cost model to select a subset of partial matches for further processing in constant time. In experiments with real-world data, Sharp achieves a recall of 95%, 93% and 72% for pattern matching in CEP, OLAP, and RAG applications, under a bound of 50% of the average processing latency.
Zitieren
APA
Yu, C., Shi, T., Weidlich, M., & Zhao, B. (2026). Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns. Proceedings of the VLDB Endowment, 19(5), 987-1000. https://doi.org/10.14778/3796195.3796210
Vancouver
Yu C, Shi T, Weidlich M, Zhao B. Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns. Proceedings of the VLDB Endowment. 2026;19(5):987-1000. doi:10.14778/3796195.3796210
BibTeX
@article{Yu2026,
author = {Yu, Cong and Shi, Tuo and Weidlich, Matthias and Zhao, Bo},
title = {Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {5},
pages = {987--1000},
doi = {10.14778/3796195.3796210}
}
EUVIMED