DIMACS TR: 93-30

Lasy Structure Sharing for Query Optimization

Authors: Adam L. Buchsbaum, Rajamani Sundar, and Robert E. Tarjan


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