Cell-probe lower bounds for the partial match problem. (English) Zbl 1192.68215
Proceedings of the thirty-fifth annual ACM symposium on theory of computing (STOC 2003), San Diego, CA, USA,. New York, NY: ACM Press (ISBN 1-58113-674-9). 667-672, electronic only (2003).
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\), is there a database point \(y\) such that for every \(i\) whenever \(x_i\neq *\), we have \(x_i=y_i\). In this paper we show randomized lower bounds in the cell-probe model for this well-studied problem.
Our lower bounds follow from a near-optimal asymmetric communication complexity lower bound for this problem. Specifically, we show that either Alice has to send \(\Omega (d/\log n)\) bits or Bob has to send \(\Omega(n^{1-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 \(\Omega(d/\log^2n)\) probes are needes. This is an exponential improvement over the previously known lower bounds for this problem obtained by P. B. Miltersen, N. Nisan, S. Safra and A. Wigderson [J. Comput. Syst. Sci. 57, 37–49 (1998; Zbl 0920.68042)] and A. Borodin, R. Ostrovsky and Y. Rabani [“Lower bounds for high dimensional nearest neighbor search and related problems”, in: Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, 1999, 312–321 (1999), cf. Zbl 1104.68442 ].
Our lower bound also leads to new and improved lower bounds for related problems including a lower bound for the \(\ell_\infty\) \(c\)-nearest neighbor problem for \(c<3\) and an improved communication complexity lower bound for the exact nearest neighbor problem.
For an extended version, see hte published article [J. Comput. Syst. Sci. 69, No. 3, 435–447 (2004; Zbl 1084.68037)].
For the entire collection see [Zbl 1074.68503].
Our lower bounds follow from a near-optimal asymmetric communication complexity lower bound for this problem. Specifically, we show that either Alice has to send \(\Omega (d/\log n)\) bits or Bob has to send \(\Omega(n^{1-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 \(\Omega(d/\log^2n)\) probes are needes. This is an exponential improvement over the previously known lower bounds for this problem obtained by P. B. Miltersen, N. Nisan, S. Safra and A. Wigderson [J. Comput. Syst. Sci. 57, 37–49 (1998; Zbl 0920.68042)] and A. Borodin, R. Ostrovsky and Y. Rabani [“Lower bounds for high dimensional nearest neighbor search and related problems”, in: Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, 1999, 312–321 (1999), cf. Zbl 1104.68442 ].
Our lower bound also leads to new and improved lower bounds for related problems including a lower bound for the \(\ell_\infty\) \(c\)-nearest neighbor problem for \(c<3\) and an improved communication complexity lower bound for the exact nearest neighbor problem.
For an extended version, see hte published article [J. Comput. Syst. Sci. 69, No. 3, 435–447 (2004; Zbl 1084.68037)].
For the entire collection see [Zbl 1074.68503].
MSC:
| 68P15 | Database theory |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | M. Ajtai. A lower bound for finding predecessors in Yao’s cell probe model. Combinatorica, 8:235-247, 1988. · Zbl 0659.68030 |
| [2] | O. Barkol and Y. Rabani. Tight bounds for nearest neighbor search and related problems in the cell probe model. In Proc. 32nd Annual ACM Symposium on the Theory of Computing, pages 388-396, 2000. 10.1145/335305.335350 · Zbl 1296.68174 |
| [3] | P. Beame and E. Vee. Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. In Proc. 34th Annual ACM Symposium on the Theory of Computing, pages 688-697, 2002. 10.1145/509907.510006 · Zbl 1192.68346 |
| [4] | A. Borodin, R. Ostrovsky, and Y. Rabani. Lower bounds for high dimensional nearest neighbor search and related problems. In Proc. 31st Annual ACM Symposium on the Theory of Computing, pages 312-321, 1999. 10.1145/301250.301330 · Zbl 1346.68077 |
| [5] | A. Chakrabarti, B. Chazelle, B. Gum, and A. Lvov. A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube. In Proc. 31st Annual ACM Symposium on the Theory of Computing, pages 305-311, 1999. 10.1145/301250.301325 · Zbl 1346.68078 |
| [6] | M. Charikar, P. Indyk, and R. Panigrahy. New algorithms for subset query, partial match, orthogonal range searching, and related problems. In Proc. 29th International Colloquium on Algorithms, Logic, and Programming, pages 451-462, 2002. · Zbl 1056.68512 |
| [7] | B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, 2000. · Zbl 0960.65149 |
| [8] | P. Indyk. On approximate nearest neighbors under l∞ norm. J. of Computer and System Sciences, 63(4):627-638, 2001. 10.1006/jcss.2001.1781 · Zbl 1006.68040 |
| [9] | P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proc. 30th Annual ACM Symposium on the Theory of Computing, pages 604-613, 1998. 10.1145/276698.276876 · Zbl 1029.68541 |
| [10] | J. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. In Proc. 29th Annual ACM Symposium on the Theory of Computing, pages 599-608, 1997. 10.1145/258533.258653 · Zbl 0963.68049 |
| [11] | D. Knuth. The Art of Computer Programming: Sorting and Searching. Addison-Wesley, 1973. · Zbl 0302.68010 |
| [12] | E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM J. on Computing, 30(2):451-474, 2000. 10.1137/S0097539798347177 · Zbl 0963.68078 |
| [13] | S. Meiser. Point location in arrangement of hyperplanes. Information and Computation, 106(2):286-303, 1993. 10.1006/inco.1993.1057 · Zbl 0781.68121 |
| [14] | P. B. Miltersen. Lower bounds for union-split-find related problems on random access machines. In Proc. 26th Annual ACM Symposium on the Theory of Computing, pages 625-634, 1994. 10.1145/195058.195415 · Zbl 1345.68118 |
| [15] | P. B. Miltersen. Cell probe complexity - a survey. In Pre-Conference Workshop on Advances in Data Structures at the 19th Conference on Foundations of Software Technology and Theoretical Computer Science, 1999. |
| [16] | P. B. Miltersen, N. Nisan, S. Safra, and A. Wigderson. On data structures and asymmetric communication complexity. J. of Computer and System Sciences, 57(1):37-49, 1998. 10.1006/jcss.1998.1577 · Zbl 0920.68042 |
| [17] | N. Nisan and A. Wigderson. Hardness vs. randomness. J. of Computer and System Sciences, 49(2):149-167, 1994. 10.1016/S0022-0000(05)80043-1 · Zbl 0821.68057 |
| [18] | R. Rivest. Analysis of Associative Retrieval Algorithms. PhD thesis, Stanford University, 1974. |
| [19] | R. Rivest. Partial match retrieval algorithms. SIAM J. on Computing, 5(1):19-50, 1976. · Zbl 0331.68064 |
| [20] | A. C. Yao. Should tables be sorted. J. of the ACM, 28(3):615-628, 1981. 10.1145/322261.322274 · Zbl 0462.68079 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
