Name
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[18, 11, 19, 16, 4, 6 ].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 - o(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/log2 n) probes are needed. This is an exponential improvement over the previously known lower bounds for this problem[16, 4]. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/j.jcss.2004.04.006 | Journal of Computer and System Sciences - Special issue: STOC 2003 |
Keywords | DocType | Volume |
partial match problem,log2 n,c-nearest neighbor problem,lower bound,cell-probe lower bound,log n,two-party asymmetric randomized communication,well-studied problem,database point y,computer programming,n point,size poly,related problem,cell-probe model,communication complexity,randomness | Conference | 69 |
Issue | ISSN | Citations |
3 | 0022-0000 | 19 |
PageRank | References | Authors |
1.13 | 14 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| T. S. Jayram | 1 | 1373 | 75.87 |
| Subhash Khot | 2 | 2064 | 112.51 |
| Ravi Kumar | 3 | 13932 | 1642.48 |
| Yuval Rabani | 4 | 2265 | 274.98 |