EUVIMEDEUVIMED entdecken
Crossref

Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns

Cong Yu, Tuo Shi, Matthias Weidlich, Bo Zhao

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →