Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
From MaRDI portal
Publication:696979
DOI10.1006/JCSS.2002.1831zbMATH Open1015.68057OpenAlexW3023640601MaRDI QIDQ696979FDOQ696979
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
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
- Nearest neighbor pattern classification
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Should Tables Be Sorted?
- Multidimensional Searching Problems
- Title not available (Why is that?)
- Point location in arrangements of hyperplanes
- Title not available (Why is that?)
- A Randomized Algorithm for Closest-Point Queries
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bounds for high dimensional nearest neighbor search and related problems
- Title not available (Why is that?)
- Lower bounds for union-split-find related problems on random access machines
- Recent Studies in Automatic Text Analysis and Document Retrieval
- 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)
Cited In (7)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Cell-probe lower bounds for the partial match problem
- Tight Cell-Probe Bounds for Online Hamming Distance Computation
- A cell probe lower bound for dynamic nearest-neighbour searching
- Computing (and Life) Is All about Tradeoffs
- The cell probe complexity of succinct data structures
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)
