×

Cell-probe lower bounds for the partial match problem. (English) Zbl 1084.68037

Summary: 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)].
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.

MSC:

68P15 Database theory
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 0920.68042
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai, M., A lower bound for finding predecessors in Yao’s cell probe model, Combinatorica, 8, 235-247 (1988) · Zbl 0659.68030
[2] O. Barkol, Y. Rabani, Tight bounds for nearest neighbor search and related problems in the cell probe model, in: Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 2000, pp. 388-396.; O. Barkol, Y. Rabani, Tight bounds for nearest neighbor search and related problems in the cell probe model, in: Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 2000, pp. 388-396. · Zbl 1296.68174
[3] P. Beame, E. Vee, Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems, in: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, 2002, pp. 688-697.; P. Beame, E. Vee, Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems, in: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, 2002, pp. 688-697. · Zbl 1192.68346
[4] A. Borodin, R. Ostrovsky, 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, pp. 312-321.; A. Borodin, R. Ostrovsky, 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, pp. 312-321. · Zbl 1346.68077
[5] A. Chakrabarti, B. Chazelle, B. Gum, A. Lvov, A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, in: Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, 1999, pp. 305-311.; A. Chakrabarti, B. Chazelle, B. Gum, A. Lvov, A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, in: Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, 1999, pp. 305-311. · Zbl 1346.68078
[6] A. Chakrabarti, O. Regev, An optimal randomised cell probe lower bound for approximate nearest neighbor searching, Electronic Colloquium on Computational Complexity, 2003.; A. Chakrabarti, O. Regev, An optimal randomised cell probe lower bound for approximate nearest neighbor searching, Electronic Colloquium on Computational Complexity, 2003. · Zbl 1207.68156
[7] M. Charikar, P. Indyk, R. Panigrahy, New algorithms for subset query, partial match, orthogonal range searching, and related problems, in: Proceedings of the 29th International Colloquium on Algorithms, Logic, and Programming, 2002, pp. 451-462.; M. Charikar, P. Indyk, R. Panigrahy, New algorithms for subset query, partial match, orthogonal range searching, and related problems, in: Proceedings of the 29th International Colloquium on Algorithms, Logic, and Programming, 2002, pp. 451-462. · Zbl 1056.68512
[8] Chazelle, B., The Discrepancy Method: Randomness and Complexity (2000), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0960.65149
[9] Indyk, P., On approximate nearest neighbors under \(ℓ_∞\) norm, J. Comput. System Sci, 63, 4, 627-638 (2001) · Zbl 1006.68040
[10] P. Indyk, R. Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, in: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, 1998, pp. 604-613.; P. Indyk, R. Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, in: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, 1998, pp. 604-613. · Zbl 1029.68541
[11] J. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, in: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, 1997, pp. 599-608.; J. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, in: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, 1997, pp. 599-608. · Zbl 0963.68049
[12] Knuth, D., The Art of Computer Programming: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010
[13] Kushilevitz, E.; Ostrovsky, R.; Rabani, Y., Efficient search for approximate nearest neighbor in high dimensional spaces, SIAM J. Comput, 30, 2, 451-474 (2000) · Zbl 0963.68078
[14] D. Liu, A strong lower bound for approximate nearest neighbor searching in the cell probe model, 2003, Submitted for publication.; D. Liu, A strong lower bound for approximate nearest neighbor searching in the cell probe model, 2003, Submitted for publication.
[15] Meiser, S., Point location in arrangement of hyperplanes, Inform. and Comput, 106, 2, 286-303 (1993) · Zbl 0781.68121
[16] P.B. Miltersen, Lower bounds for union-split-find related problems on random access machines, in: Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 625-634.; P.B. Miltersen, Lower bounds for union-split-find related problems on random access machines, in: Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 625-634. · Zbl 1345.68118
[17] 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.; 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.
[18] Miltersen, P. B.; Nisan, N.; Safra, S.; Wigderson, A., On data structures and asymmetric communication complexity, J. Comput. System Sci, 57, 1, 37-49 (1998) · Zbl 0920.68042
[19] Nisan, N.; Wigderson, A., Hardness vs. randomness, J. Comput. System Sci, 49, 2, 149-167 (1994) · Zbl 0821.68057
[20] R. Rivest, Analysis of associative retrieval algorithms, Ph.D. Thesis, Stanford University, 1974.; R. Rivest, Analysis of associative retrieval algorithms, Ph.D. Thesis, Stanford University, 1974.
[21] Rivest, R., Partial match retrieval algorithms, SIAM J. Comput, 5, 1, 19-50 (1976) · Zbl 0331.68064
[22] Yao, A. C., Should tables be sorted, J. Assoc. Comput. Mach, 28, 3, 615-628 (1981) · 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.