Tighter lower bounds for nearest neighbor search and related problems in the cell probe model

DOI10.1006/jcss.2002.1831zbMath1015.68057OpenAlexW3023640601MaRDI QIDQ696979

Omer Barkol, Yuval Rabani

Publication date: 12 September 2002

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

Full work available at URL: https://doi.org/10.1006/jcss.2002.1831

zbMATH Keywords

Hamming cubenearest neighbor search

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (2)

The cell probe complexity of succinct data structures ⋮ Computing (and Life) Is All about Tradeoffs

Cites Work

• Point location in arrangements of hyperplanes
• 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
• Determinism versus non-determinism for linear time RAMs (extended abstract)
• A Randomized Algorithm for Closest-Point Queries
• Should Tables Be Sorted?
• Multidimensional Searching Problems
• Nearest neighbor pattern classification
• Recent Studies in Automatic Text Analysis and Document Retrieval
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Tighter lower bounds for nearest neighbor search and related problems in the cell probe model