Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
type: Item
instance of: scholarly article
title: Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
zbMATH Open document ID: 1015.68057
author: Omer Barkol
author: Yuval Rabani
published in: Journal of Computer and System Sciences
publication date: 2002-09-12T00:00:00Z
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 1800319
zbMATH Keywords: nearest neighbor search
zbMATH Keywords: Hamming cube
MaRDI profile type: Publication
full work available at URL: jcss.2002.1831
OpenAlex ID: W3023640601
cites work: Determinism versus non-determinism for linear time RAMs (extended abstract)
cites work: Q4004078
cites work: Q3140429
cites work: Q3128920
cites work: Q4344150
cites work: Lower bounds for high dimensional nearest neighbor search and related problems
cites work: A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
cites work: A Randomized Algorithm for Closest-Point Queries
cites work: Nearest neighbor pattern classification
cites work: Q4749022
cites work: Multidimensional Searching Problems
cites work: Q4403756
cites work: Q4952640
cites work: Q4542583
cites work: Q4527027
cites work: Q4542584
cites work: Point location in arrangements of hyperplanes
cites work: Lower bounds for union-split-find related problems on random access machines
cites work: Q4234056
cites work: Recent Studies in Automatic Text Analysis and Document Retrieval
cites work: Should Tables Be Sorted?
DOI: 10.1006/JCSS.2002.1831
Recommended article: Tighter bounds for nearest neighbor search and related problems in the cell probe model
Recommended article: An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching
Recommended article: A cell probe lower bound for dynamic nearest-neighbour searching
Recommended article: Lower bounds for predecessor searching in the cell probe model
Recommended article: Cell-probe lower bounds for the partial match problem
Recommended article: A strong lower bound for approximate nearest neighbor searching
Recommended article: Lower bounds for high dimensional nearest neighbor search and related problems
Recommended article: Q5692700
Recommended article: Q4633874
description: scientific article; zbMATH DE number 1800319