On the application of shared retrieval to orthogonal range queries
Dan E. Willard · 1986
We propose a new search technique, called the Shear-Based Format, which shows that Yao's lower bound on the time-space tradeoff for orthogonal range queries is either optimal or nearly optimal [Ya82, Ya85]. Shearing is also a very pragmatic technique.