Lazy Structure Sharing for Query Optimization

Abstract:

We study 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.