REVIEW 2 cited by
Relational E-Matching
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
We present a new approach to e-matching based on relational join; in particular, we apply recent database query execution techniques to guarantee worst-case optimal run time. Compared to the conventional backtracking approach that always searches the e-graph "top down", our new relational e-matching approach can better exploit pattern structure by searching the e-graph according to an optimized query plan. We also establish the first data complexity result for e-matching, bounding run time as a function of the e-graph size and output size. We prototyped and evaluated our technique in the state-of-the-art egg e-graph framework. Compared to a conventional baseline, relational e-matching is simpler to implement and orders of magnitude faster in practice.
Forward citations
Cited by 2 Pith papers
-
rEGGression: an Interactive and Agnostic Tool for the Exploration of Symbolic Regression Models
rEGGression uses e-graphs to store and interactively explore large sets of symbolic regression expressions, with pattern matching and building-block distribution queries.
-
Omelets Need Onions: E-graphs Modulo Theories via Bottom-up E-matching
The paper proposes bottom-up e-matching plus semantic e-ids as a pragmatic way to make e-graphs work modulo mathematical theories.
Discussion (0). Continue with ORCID to comment.