Optimal static range reporting in one dimension

No abstract is available for this paper.

• Publication year

  2001

• Venue

  Symposium on the Theory of Computing

• Publication date

  2001-07-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/380752.380842
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Spatial Complexity of Oblivious k-Probe Hash Functions

  2018cited by this paper
• Computational Geometry

  2018cited by this paper
• Data Structures and Algorithms 3

  2012cited by this paper
• Tight(er) worst-case bounds on dynamic searching and priority queues

  2000influential reference
• Efficient regular data structures and algorithms for location and proximity problems

  1999cited by this paper
• Optimal bounds for the predecessor problem

  1999influential reference
• Approximate Indexed Lists

  1998cited by this paper
• Faster deterministic sorting and priority queues in linear space

  1998influential reference
• Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes

  1996cited by this paper
• Sorting in linear time?

  1995cited by this paper
• Approximate data structures with applications

  1994cited by this paper
• On data structures and asymmetric communication complexity

  1994cited by this paper
• An algorithm for approximate closest-point queries

  1994cited by this paper
• Surpassing the Information Theoretic Bound with Fusion Trees

  1993influential reference
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths

  1990influential reference
• Randomized search trees

  1989influential reference
• A lower bound for finding predecessors in Yao's cell probe model

  1988cited by this paper
• The input/output complexity of sorting and related problems

  1988cited by this paper
• Two Results on Tables

  1986cited by this paper
• Computational Geometry

  1985cited by this paper
• Multi-dimensional searching and computational geometry

  1984cited by this paper
• Fast Algorithms for Finding Nearest Common Ancestors

  1984cited by this paper
• Log-logarithmic worst-case range queries are possible in space ⊕(N)

  1983influential reference
• Storing a sparse table with O(1) worst case access time

  1982cited by this paper
• Algorithm 245: Treesort

  1964cited by this paper
• Algorithm 232: Heapsort

  1964cited by this paper

• Learned Static Function Data Structures

  2025cites this paper
• Non-overlapping indexing in BWT-runs bounded space

  2025cites this paper
• Call Me By My Name: Simple, Practical Private Information Retrieval for Keyword Queries

  2024cites this paper
• Grafite: Taming Adversarial Queries with Optimal Range Filters

  2023cites this paper
• Tiny Pointers

  2021influential citation
• New Data Structures for Orthogonal Range Reporting and Range Minima Queries

  2020cites this paper
• Predecessor Search

  2020cites this paper
• Four-Dimensional Dominance Range Reporting in Linear Space

  2020cites this paper
• Ranked document retrieval for multiple patterns

  2018cites this paper
• Space Efficient Data Structures and Algorithms in the Word-RAM Model

  2018influential citation
• Succinct Dynamic One-Dimensional Point Reporting

  2018cites this paper
• In-Memory Storage for Labeled Tree-Structured Data

  2017cites this paper
• Stabbing Colors in One Dimension

  2017cites this paper
• Predecessor Search, String Algorithms and Data Structures

  2016cites this paper
• Succinct Indices for Path Minimum, with Applications

  2016cites this paper
• 41 RANGE SEARCHING

  2016cites this paper
• String Searching with Ranking Constraints and Uncertainty

  2015influential citation
• Succinct Non-overlapping Indexing

  2015cites this paper
• Exploring the Problem Space of Orthogonal Range Searching

  2015cites this paper
• Reporting consecutive substring occurrences under bounded gap constraints

  2015cites this paper
• On Top-k Range Reporting in 2D Space

  2015cites this paper
• Compressed Indexes for String Searching in Labeled Graphs

  2015cites this paper
• Ranked Document Retrieval with Forbidden Pattern

  2015cites this paper
• Improved Explicit Data Structures in the Bitprobe Model

  2014cites this paper
• LZ77-Based Self-indexing with Faster Pattern Matching

  2014cites this paper
• Document retrieval with one wildcard

  2014cites this paper
• On hardness of several string indexing problems

  2014cites this paper
• Concurrent Range Reporting in Two-Dimensional Space

  2014cites this paper
• Approximate Range Emptiness in Constant Time and Optimal Space

  2014cites this paper
• Space-Efficient Data Structures in the Word-RAM and Bitprobe Models

  2013cites this paper
• Optimal Color Range Reporting in One Dimension

  2013influential citation
• Minimal Discriminating Words Problem Revisited

  2013cites this paper
• String Processing and Information Retrieval

  2013influential citation
• Better Space Bounds for Parameterized Range Majority and Minority

  2012cites this paper
• Better Space Bounds for Parameterized Range Majority and Minority

  2012cites this paper
• Dynamic Indexability and the Optimality of B-Trees

  2012cites this paper
• Substring Range Reporting

  2011cites this paper
• Persistent predecessor search and orthogonal point location on the word RAM

  2011cites this paper
• I/O-efficient data structures for colored range and prefix reporting

  2011cites this paper
• Hashing, randomness and dictionaries

  2010cites this paper
• Fast Prefix Search in Little Space, with Applications

  2010influential citation
• Counting inversions, offline orthogonal range counting, and related problems

  2010cites this paper
• Data Structures for Approximate Range Counting

  2009cites this paper
• Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes

  2009cites this paper
• Data Structures for Approximate Orthogonal Range Counting

  2009cites this paper
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time

  2009cites this paper
• Dynamic Indexability: The Query-Update Tradeoff for One-Dimensional Range Queries

  2008cites this paper
• Succinct Data Structures for Retrieval and Approximate Membership

  2008cites this paper
• Computational Geometry through the Information Lens by Mihai Pǎtraşcu

  2007cites this paper
• Data Structuring Problems in the Bit Probe Model

  2007cites this paper
• Computational geometry through the information lens

  2007cites this paper
• Orthogonal Range Searching in Linear and Almost-Linear Space

  2007cites this paper
• Point Location in Time, Voronoi Diagrams in Time, and Other Transdichotomous Results in Computational Geometry

  2006cites this paper
• In the last lecture we used round elimination to prove lower bounds for the static predecessor problem in the cell probe model. We showed a lower bound of

  2005cites this paper
• Predecessor Queries in Constant Time?

  2005cites this paper
• On dynamic range reporting in one dimension

  2005influential citation
• On Dynamic Dictionaries Using Little Space )

  2005cites this paper
• De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space)

  2005cites this paper
• De Dictionariis Dynamicis Pauco Spatio Utentibus

  2005cites this paper
• Algorithms for Memory Hierarchies

  2003cites this paper
• Optimal Bounds for the Predecessor Problem and Related Problems

  2002cites this paper
• A provably efficient computational model for approximate spatiotemporal retrieval

  1999cites this paper
• On Dynamic Dictionaries Using Little Space )

  year unknowncites this paper
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time (cid:3)

  year unknowncites this paper
• Counting Inversions, Offline Orthogonal Range Counting, and Related Problems

  year unknowncites this paper