Before revision:  In particular,  we design combinatorial algorithms that provide instance-specific delay guarantees in nearly linear preprocessing time.
After revision:  In particular, for star queries, we design combinatorial algorithms that provide instance-specific delay guarantees in nearly linear preprocessing time.