DIMACS TR: 93-30
Lasy Structure Sharing for Query Optimization
Authors: Adam L. Buchsbaum, Rajamani Sundar, and Robert E. Tarjan
ABSTRACT
We study {\em lazy structure sharing} as a tool for optimizing
equivalence testing on complex data types. We investigate a
number of strategies for a restricted case of the problem and
provide upper and lower bounds on their performance (how
quickly they effect ideal configurations of our data
structure). In most cases, the bounds provide nontrivial
improvements over the na\"{\i}ve linear-time
equivalence-testing strategy that employs no optimization.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-30.ps
DIMACS Home Page