Subspace exploration: Bounds on Projected Frequency Estimation.

Given an × dimensional dataset , a projection query specifies a subset ⊆ [] of columns which yields a new × || array. We study the space complexity of computing data analysis functions over such subspaces, including heavy hitters and norms, when the subspaces are revealed only after observing the data. We show that this important class of problems is typically hard: for many problems, we show 2 lower bounds.

An evaluation of multi-probe locality sensitive hashing for computing similarities over web-scale query logs.

Many modern applications of AI such as web search, mobile browsing, image processing, and natural language processing rely on finding similar items from a large database of complex objects. Due to the very large scale of data involved (e.g.