SigMatch: Fast and Scalable Multi-Pattern Matching

Summary: SigMatch scales multi-pattern signature matching via a cache-efficient q-gram sigTree that groups shared subpatterns for early elimination. Parallel Bloom filters and load balancing yield order-of-magnitude speedups across diverse workloads. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10243
Venue: VLDB
Year: 2010
Pagerank: 5.7958663e-05
Overall Rank: 6,716 | 53.93%
DOI: 10.14778/1920841.1920987

Incoming Non-self Citations Over Time

Authors

1. Ramakrishnan Kandhan (University of Wisconsin)
2. Nikhil Teletia (University of Wisconsin)
3. Jignesh M. Patel (University of Wisconsin)

BibTeX Citation

@article{kandhan_vldb10,
        title = {{SigMatch: Fast and Scalable Multi-Pattern Matching}},
        author = {Kandhan, Ramakrishnan and Teletia, Nikhil and Patel, Jignesh M.},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {1173--1184},
        doi = {10.14778/1920841.1920987},
        url = {https://doi.org/10.14778/1920841.1920987},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,549	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	5.8442558e-05
8,114	Approximate Substring Matching over Uncertain Strings	2011	VLDB	5.484341e-05
9,973	Exploiting Structure in Regular Expression Queries	2023	SIGMOD	5.1845938e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,040	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012466499
2,405	DBLife: A Community Information Management Platform for the Database Research Community	2007	CIDR	8.6217909e-05
3,442	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	7.4122197e-05
4,009	Flexible String Matching Against Large Databases in Practice	2004	VLDB	6.9612537e-05
4,391	Scalable Regular Expression Matching on Data Streams	2008	SIGMOD	6.7290402e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,872	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB
2	10,564	gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs	2026	VLDB
3	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
4	11,762	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD
5	3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD
6	10,204	Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching	2026	SIGMOD
7	9,400	PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads	2019	VLDB
8	5,426	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB
9	11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
10	7,476	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB