About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 2003
Conference paper
Cell-probe lower bounds for the partial match problem
Abstract
Given a database of n points in {0, 1}d, the partial match problem is: In response to a query x in {0, 1, *}d, find a database point y such that for every i whenever xi ≠ *, we have xi = yi. In this paper we show randomized lower bounds in the cell-probe model for this well-studied problem. Our lower bounds follow from a two-party asymmetric randomized communication complexity near-optimal lower bound for this problem, where we show that either Alice has to send Ω(d/log n) bits or Bob has to send Ω(n1-0(1)) bits. When applied to the cell-probe model, it means that if the number of cells is restricted to be poly(n, d) where each cell is of size poly (log n,d), then Ω(d/log2n) probes are needed. This is an exponential improvement over the previously known lower bounds for this problem. Our lower bound also leads to new and improved lower bounds for related problems including a lower bound for the l∞ c-nearest neighbor problem for c < 3 and an improved communication complexity lower bound for the exact nearest neighbor problem.