Accelerating Rule-matching Systems with Learned Rankers

Authors: 

Zhao Lucis Li, University of Science and Technology China; Chieh-Jan Mike Liang and Wei Bai, Microsoft Research; Qiming Zheng, Shanghai Jiao Tong University; Yongqiang Xiong, Microsoft Research; Guangzhong Sun, University of Science and Technology China

Abstract: 

Infusing machine learning (ML) and deep learning (DL) into modern systems has driven a paradigm shift towards learning-augmented system design. This paper proposes the learned ranker as a system building block, and demonstrates its potential by using rule-matching systems as a concrete scenario. Specifically, checking rules can be time-consuming, especially complex regular expression (regex) conditions. The learned ranker prioritizes rules based on their likelihood of matching a given input. If the matching rule is successfully prioritized as a top candidate, the system effectively achieves early termination. We integrated the learned rule ranker as a component of popular regex matching engines: PCRE, PCRE-JIT, and RE2. Empirical results show that the rule ranker achieves a top-5 classification accuracy at least 96.16%, and reduces the rule-matching system latency by up to 78.81% on a 8-core CPU.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {234938,
author = {Zhao Lucis Li and Chieh-Jan Mike Liang and Wei Bai and Qiming Zheng and Yongqiang Xiong and Guangzhong Sun},
title = {Accelerating Rule-matching Systems with Learned Rankers},
booktitle = {2019 {USENIX} Annual Technical Conference ({USENIX} {ATC} 19)},
year = {2019},
isbn = {978-1-939133-03-8},
address = {Renton, WA},
pages = {1041--1048},
url = {https://www.usenix.org/conference/atc19/presentation/li-zhao},
publisher = {{USENIX} Association},
}