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: 9040
Venue: VLDB
Year: 2002
Pagerank: 7.1577657e-05
Overall Rank: 3,742 | 74.33%
DOI: 10.1016/B978-155860869-6/50030-5

Incoming Non-self Citations Over Time

Authors

1. Chee-Yong Chan (Bell Labs, Lucent Technologies)
2. Minos Garofalakis (Bell Labs, Lucent Technologies)
3. Rajeev Rastogi (Bell Labs, Lucent Technologies)

BibTeX Citation

@article{chan_vldb02,
        title = {{RE-Tree: An Efficient Index Structure for Regular Expressions}},
        author = {Chan, Chee-Yong and Garofalakis, Minos and Rastogi, Rajeev},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50030-5},
        url = {https://doi.org/10.1016/B978-155860869-6/50030-5},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,739	Indexing Boolean Expressions	2009	VLDB	8.1872509e-05
4,391	Scalable Regular Expression Matching on Data Streams	2008	SIGMOD	6.7290402e-05
5,199	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	6.3216824e-05
6,549	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	5.8442558e-05
6,861	An Efficient Publish/Subscribe Index for E-Commerce Databases	2014	VLDB	5.7517379e-05
9,973	Exploiting Structure in Regular Expression Queries	2023	SIGMOD	5.1845938e-05
11,081	An Evaluation of N-Gram Selection Strategies for Regular Expression Indexing in Contemporary Text Analysis Tasks	2025	VLDB	5.093636e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
236	Efficient Filtering of XML Documents for Selective Dissemination of Information	2000	VLDB	0.00023721569
318	Storing Semistructured Data with STORED	1999	SIGMOD	0.00021380325
1,142	XTRACT: A System for Extracting Document Type Descriptors from XML Documents	2000	SIGMOD	0.00012002609
3,098	Evaluation of Signature Files as Set Access Facilities in OODBs	1993	SIGMOD	7.7612856e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,036	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD
2	2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD
3	11,081	An Evaluation of N-Gram Selection Strategies for Regular Expression Indexing in Contemporary Text Analysis Tasks	2025	VLDB
4	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
5	4,776	An Efficient Index Structure for String Databases	2001	VLDB
6	8,577	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD
7	7,524	Efficient Indexing and Querying over Syntactically Annotated Trees	2012	VLDB
8	341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB
9	2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD
10	10,396	Regular Expression Indexing for Log Analysis	2026	SIGMOD