RE-Tree: An Efficient Index Structure for Regular Expressions

Summary: RE-tree is a novel index for large databases of regular expressions that speeds up input-string matching by pruning to a small subset of candidate REs. It uses new size measures for infinite languages, node splitting, tight bounding REs, and sampling-based approximations to outperform naive sequential search. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8849
Venue: VLDB
Year: 2002
Pagerank: 7.0078308e-05
Overall Rank: 3,526 | 75.48%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,949	Indexing Boolean Expressions	2009	VLDB	7.8340452e-05
4,589	Scalable Regular Expression Matching on Data Streams	2008	SIGMOD	6.06476e-05
5,582	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	5.4241353e-05
6,788	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	4.9252064e-05
6,992	An Efficient Publish/Subscribe Index for E-Commerce Databases	2014	VLDB	4.8701339e-05
9,826	Exploiting Structure in Regular Expression Queries	2023	SIGMOD	4.2751057e-05
10,857	An Evaluation of N-Gram Selection Strategies for Regular Expression Indexing in Contemporary Text Analysis Tasks	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
207	Storing Semistructured Data with STORED	1999	SIGMOD	0.00034611968
226	Efficient Filtering of XML Documents for Selective Dissemination of Information	2000	VLDB	0.00032431532
992	XTRACT: A System for Extracting Document Type Descriptors from XML Documents	2000	SIGMOD	0.00014799689
3,016	Evaluation of Signature Files as Set Access Facilities in OODBs	1993	SIGMOD	7.7052964e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,376	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	8.9424361e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
10,857	An Evaluation of N-Gram Selection Strategies for Regular Expression Indexing in Contemporary Text Analysis Tasks	2025	VLDB	4.1945683e-05
5,615	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4101086e-05
4,333	An Efficient Index Structure for String Databases	2001	VLDB	6.2805237e-05
8,587	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	4.4902253e-05
6,919	Efficient Indexing and Querying over Syntactically Annotated Trees	2012	VLDB	4.8925595e-05
391	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024564567
1,184	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	0.00013455208
10,106	Regular Expression Indexing for Log Analysis	2026	SIGMOD	4.1945683e-05