Lower bounds for predecessor searching in the cell probe model
type: Item
instance of: scholarly article
title: Lower bounds for predecessor searching in the cell probe model
zbMATH Open document ID: 1133.68017
author: Yanyan Li
published in: Journal of Computer and System Sciences
publication date: 2008-03-11T00:00:00Z
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5246770
zbMATH Keywords: predecessor searching problem
zbMATH Keywords: cell probe model
zbMATH Keywords: data structures
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
full work available at URL: j.jcss.2007.06.016
OpenAlex ID: W2038255135
cites work: Q4542516
cites work: A lower bound for finding predecessors in Yao's cell probe model
cites work: Optimal bounds for the predecessor problem and related problems
cites work: Are Bitvectors Optimal?
cites work: Q4939137
cites work: Q4023085
cites work: Ecole d'ete de probabilités de Saint-Flour VII-1977
cites work: Storing a Sparse Table with 0 (1) Worst Case Access Time
cites work: Surpassing the information theoretic bound with fusion trees
cites work: Mathematical techniques for quantum communication theory
cites work: Q4228473
cites work: Quantum complexities of ordered searching, sorting, and element distinctness
cites work: Q4542583
cites work: Q4449184
cites work: Fidelity for Mixed Quantum States
cites work: Exponential lower bound for 2-query locally decodable codes via a quantum argument
cites work: Interaction in quantum communication and the complexity of set disjointness
cites work: Communication Complexity
cites work: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
cites work: A strong lower bound for approximate nearest neighbor searching
cites work: Lower bounds for union-split-find related problems on random access machines
cites work: On data structures and asymmetric communication complexity
cites work: Private vs. common random bits in communication complexity
cites work: Q2706552
cites work: Q4284623
cites work: Time-space trade-offs for predecessor search
cites work: Q4535029
cites work: Preserving order in a forest in less than logarithmic time and linear space
cites work: Design and implementation of an efficient priority queue
cites work: Log-logarithmic worst-case range queries are possible in space theta(N)
cites work: Q4864428
cites work: Should Tables Be Sorted?
DOI: 10.1016/J.JCSS.2007.06.016
description: scientific article