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

DOI10.1006/JCSS.2002.1831MaRDI QIDQ696979zbMATHOpenAlexFDO

Authors 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

nearest neighbor searchHamming cube

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Tighter bounds for nearest neighbor search and related problems in the cell probe model
• An optimal randomized cell probe lower bound for approximate nearest neighbor searching
• A cell probe lower bound for dynamic nearest-neighbour searching
• Lower bounds for predecessor searching in the cell probe model
• Cell-probe lower bounds for the partial match problem
• Cell-probe lower bounds for the partial match problem
• A strong lower bound for approximate nearest neighbor searching
• Lower bounds for high dimensional nearest neighbor search and related problems
• scientific article; zbMATH DE number 2209718
• Cell probe lower bounds for succinct data structures

Cites work

• scientific article; zbMATH DE number 1003290 (Why is no real title available?)
• scientific article; zbMATH DE number 437552 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1263186 (Why is no real title available?)
• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• scientific article; zbMATH DE number 3436645 (Why is no real title available?)
• scientific article; zbMATH DE number 1559575 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 1775451 (Why is no real title available?)
• scientific article; zbMATH DE number 3806754 (Why is no real title available?)
• scientific article; zbMATH DE number 1445325 (Why is no real title available?)
• A Randomized Algorithm for Closest-Point Queries
• A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
• Determinism versus non-determinism for linear time RAMs (extended abstract)
• Lower bounds for high dimensional nearest neighbor search and related problems
• Lower bounds for union-split-find related problems on random access machines
• Multidimensional Searching Problems
• Nearest neighbor pattern classification
• Point location in arrangements of hyperplanes
• Recent Studies in Automatic Text Analysis and Document Retrieval
• Should Tables Be Sorted?

Cited in

(15)

• Cell-probe lower bounds for the partial match problem
• Cell-probe lower bounds for the partial match problem
• The cell probe complexity of succinct data structures
• Higher lower bounds for near-neighbor and further rich problems
• Tight Cell-Probe Bounds for Online Hamming Distance Computation
• scientific article; zbMATH DE number 2209718 (Why is no real title available?)
• A cell probe lower bound for dynamic nearest-neighbour searching
• Lower bounds for high dimensional nearest neighbor search and related problems
• Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities
• Tighter bounds for nearest neighbor search and related problems in the cell probe model
• A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
• An optimal randomized cell probe lower bound for approximate nearest neighbor searching
• A strong lower bound for approximate nearest neighbor searching
• Computing (and Life) Is All about Tradeoffs
• scientific article; zbMATH DE number 2209721 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q696979)