Cell-probe lower bounds for the partial match problem

DOI10.1016/j.jcss.2004.04.006zbMath1084.68037OpenAlexW4212978476MaRDI QIDQ5917577

Yuval Rabani, T. S. Jayram, Subhash A. Khot, Ravi Kumar

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.04.006

zbMATH Keywords

Asymmetric communication complexityCell-probe modelNearest neighbor problemPartial match problem

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Point location in arrangements of hyperplanes
• A lower bound for finding predecessors in Yao's cell probe model
• On data structures and asymmetric communication complexity
• Hardness vs randomness
• On approximate nearest neighbors under \(l_\infty\) norm
• Lower bounds for union-split-find related problems on random access machines
• A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
• Lower bounds for high dimensional nearest neighbor search and related problems
• An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching
• Tighter bounds for nearest neighbor search and related problems in the cell probe model
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
• Should Tables Be Sorted?
• Partial-Match Retrieval Algorithms
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces

This page was built for publication: Cell-probe lower bounds for the partial match problem