8 Search Results for "Sandlund, Bryce"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.87
Lazy B-Trees

Authors: Casper Moldrup Rysgaard and Sebastian Wild

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Lazy search trees (Sandlund & Wild FOCS 2020, Sandlund & Zhang SODA 2022) are sorted dictionaries whose update and query performance smoothly interpolates between that of efficient priority queues and binary search trees - automatically, depending on actual use; no adjustments are necessary to the data structure to realize the cost savings. In this paper, we design lazy B-trees, a variant of lazy search trees suitable for external memory that generalizes the speedup of B-trees over binary search trees wrt. input/output operations to the same smooth interpolation regime. A key technical difficulty to overcome is the lack of a (fully satisfactory) external variant of biased search trees, on which lazy search trees crucially rely. We give a construction for a subset of performance guarantees sufficient to realize external-memory lazy search trees, which we deem of independent interest. As one special case, lazy B-trees can be used as an external-memory priority queue, in which case they are competitive with some tailor-made heaps; indeed, they offer faster decrease-key and insert operations than known data structures.
Cite as

Casper Moldrup Rysgaard and Sebastian Wild. Lazy B-Trees. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 87:1-87:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rysgaard_et_al:LIPIcs.MFCS.2025.87,
  author =	{Rysgaard, Casper Moldrup and Wild, Sebastian},
  title =	{{Lazy B-Trees}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{87:1--87:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.87},
  URN =		{urn:nbn:de:0030-drops-241949},
  doi =		{10.4230/LIPIcs.MFCS.2025.87},
  annote =	{Keywords: B-tree, lazy search trees, lazy updates, external memory, deferred data structures, database cracking}
}
Document
Research
DOI: 10.4230/OASIcs.Grossi.12
Encoding Data Structures for Range Queries on Arrays

Authors: Seungbum Jo and Srinivasa Rao Satti

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract
Efficiently processing range queries on arrays is a fundamental problem in computer science, with applications spanning diverse domains such as database management, computational biology, and geographic information systems. A range query retrieves information about a specific segment of an array, such as the sum, minimum, maximum, or median of elements within a given range. The challenge lies in designing data structures that allow such queries to be answered quickly, often in constant or logarithmic time, while keeping space overhead (and preprocessing time) small. Encoding data structures for range queries has emerged as a pivotal area of research due to the increasing demand for high-performance systems handling massive datasets. These structures consider the data together with the queries and aim to store only as much information about the data as is needed to answer the queries. The data structure does not need to access the original data to answer the queries. Encoding-based solutions often leverage techniques from succinct data structures, bit manipulation, and combinatorial optimization to achieve both space and time efficiency. By encoding the array in a manner that preserves critical information, these methods strike a balance between query time and space usage. In this survey article, we explore the landscape of encoding data structures for range queries on arrays, providing a comprehensive overview of some important results on space-efficient encodings for various types of range query.
Cite as

Seungbum Jo and Srinivasa Rao Satti. Encoding Data Structures for Range Queries on Arrays. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jo_et_al:OASIcs.Grossi.12,
  author =	{Jo, Seungbum and Satti, Srinivasa Rao},
  title =	{{Encoding Data Structures for Range Queries on Arrays}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{12:1--12:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.12},
  URN =		{urn:nbn:de:0030-drops-238116},
  doi =		{10.4230/OASIcs.Grossi.12},
  annote =	{Keywords: range queries, RMQ, Cartesian tree, top-k queries, range median, range mode}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.10
Maximizing the Optimality Streak of Deferred Data Structuring (a.k.a. Database Cracking)

Authors: Yufei Tao

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
This paper studies how to minimize the total cost of answering r queries over n elements in an online manner (i.e., the next query is given only after the previous query’s result is ready) when the value r ≤ n is unknown in advance. Traditional indexing, which first builds a complete index on the n elements before answering queries, may be unsuitable because the index’s construction time - usually Ω(n log n) - can become the performance bottleneck. In contrast, for many problems, a lower bound of Ω(n log (1+r)) holds on the total cost of r queries for every r ∈ [1, n]. Matching this lower bound is a primary objective of deferred data structuring (DDS), also known as database cracking in the system community. For a wide class of problems, we present generic reductions to convert traditional indexes into DDS algorithms that match the lower bound for a long range of r. For a decomposable problem, if a data structure can be built in O(n log n) time and has Q(n) query search time, our reduction yields an algorithm that runs in O(n log (1+r)) time for all r ≤ (n log n)/(Q(n)), where the upper bound (n log n)/(Q(n)) is asymptotically the best possible under mild constraints. In particular, if Q(n) = O(log n), then the O(n log (1+r))-time guarantee extends to all r ≤ n, with which we optimally settle a large variety of DDS problems. Our results can be generalized to a class of "spectrum indexable problems", which subsumes the class of decomposable problems.
Cite as

Yufei Tao. Maximizing the Optimality Streak of Deferred Data Structuring (a.k.a. Database Cracking). In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{tao:LIPIcs.ICDT.2025.10,
  author =	{Tao, Yufei},
  title =	{{Maximizing the Optimality Streak of Deferred Data Structuring (a.k.a. Database Cracking)}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.10},
  URN =		{urn:nbn:de:0030-drops-229512},
  doi =		{10.4230/LIPIcs.ICDT.2025.10},
  annote =	{Keywords: Deferred Data Structuring, Database Cracking, Data Structures}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.94
Faster Dynamic Range Mode

Authors: Bryce Sandlund and Yinzhan Xu

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In the dynamic range mode problem, we are given a sequence a of length bounded by N and asked to support element insertion, deletion, and queries for the most frequent element of a contiguous subsequence of a. In this work, we devise a deterministic data structure that handles each operation in worst-case Õ(N^0.655994) time, thus breaking the O(N^{2/3}) per-operation time barrier for this problem. The data structure is achieved by combining the ideas in Williams and Xu (SODA 2020) for batch range mode with a novel data structure variant of the Min-Plus product.
Cite as

Bryce Sandlund and Yinzhan Xu. Faster Dynamic Range Mode. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 94:1-94:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sandlund_et_al:LIPIcs.ICALP.2020.94,
  author =	{Sandlund, Bryce and Xu, Yinzhan},
  title =	{{Faster Dynamic Range Mode}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{94:1--94:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.94},
  URN =		{urn:nbn:de:0030-drops-125018},
  doi =		{10.4230/LIPIcs.ICALP.2020.94},
  annote =	{Keywords: Range Mode, Min-Plus Product}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.12
A Simple Algorithm for Minimum Cuts in Near-Linear Time

Authors: Nalin Bhardwaj, Antonio J. Molina Lovett, and Bryce Sandlund

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We consider the minimum cut problem in undirected, weighted graphs. We give a simple algorithm to find a minimum cut that 2-respects (cuts two edges of) a spanning tree T of a graph G. This procedure can be used in place of the complicated subroutine given in Karger’s near-linear time minimum cut algorithm [Karger, 2000]. We give a self-contained version of Karger’s algorithm with the new procedure, which is easy to state and relatively simple to implement. It produces a minimum cut on an m-edge, n-vertex graph in O(m log³ n) time with high probability, matching the complexity of Karger’s approach.
Cite as

Nalin Bhardwaj, Antonio J. Molina Lovett, and Bryce Sandlund. A Simple Algorithm for Minimum Cuts in Near-Linear Time. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhardwaj_et_al:LIPIcs.SWAT.2020.12,
  author =	{Bhardwaj, Nalin and Molina Lovett, Antonio J. and Sandlund, Bryce},
  title =	{{A Simple Algorithm for Minimum Cuts in Near-Linear Time}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.12},
  URN =		{urn:nbn:de:0030-drops-122594},
  doi =		{10.4230/LIPIcs.SWAT.2020.12},
  annote =	{Keywords: minimum cut, sparsification, near-linear time, packing}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.31
Space-Efficient Data Structures for Lattices

Authors: J. Ian Munro, Bryce Sandlund, and Corwin Sinnamon

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
A lattice is a partially-ordered set in which every pair of elements has a unique meet (greatest lower bound) and join (least upper bound). We present new data structures for lattices that are simple, efficient, and nearly optimal in terms of space complexity. Our first data structure can answer partial order queries in constant time and find the meet or join of two elements in O(n^{3/4}) time, where n is the number of elements in the lattice. It occupies O(n^{3/2}log n) bits of space, which is only a Θ(log n) factor from the Θ(n^{3/2})-bit lower bound for storing lattices. The preprocessing time is O(n²). This structure admits a simple space-time tradeoff so that, for any c ∈ [1/2, 1], the data structure supports meet and join queries in O(n^{1-c/2}) time, occupies O(n^{1+c}log n) bits of space, and can be constructed in O(n² + n^{1+3c/2}) time. Our second data structure uses O(n^{3/2}log n) bits of space and supports meet and join in O(d (log n)/(log d)) time, where d is the maximum degree of any element in the transitive reduction graph of the lattice. This structure is much faster for lattices with low-degree elements. This paper also identifies an error in a long-standing solution to the problem of representing lattices. We discuss the issue with this previous work.
Cite as

J. Ian Munro, Bryce Sandlund, and Corwin Sinnamon. Space-Efficient Data Structures for Lattices. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{munro_et_al:LIPIcs.SWAT.2020.31,
  author =	{Munro, J. Ian and Sandlund, Bryce and Sinnamon, Corwin},
  title =	{{Space-Efficient Data Structures for Lattices}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{31:1--31:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.31},
  URN =		{urn:nbn:de:0030-drops-122782},
  doi =		{10.4230/LIPIcs.SWAT.2020.31},
  annote =	{Keywords: Lattice, Partially-ordered set, Space-efficient data structure, Succinct data structure}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.57
On Approximate Range Mode and Range Selection

Authors: Hicham El-Zein, Meng He, J. Ian Munro, Yakov Nekrich, and Bryce Sandlund

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
For any epsilon in (0,1), a (1+epsilon)-approximate range mode query asks for the position of an element whose frequency in the query range is at most a factor (1+epsilon) smaller than the true mode. For this problem, we design a data structure occupying O(n/epsilon) bits of space to answer queries in O(lg(1/epsilon)) time. This is an encoding data structure which does not require access to the input sequence; the space cost of this structure is asymptotically optimal for constant epsilon as we also prove a matching lower bound. Furthermore, our solution improves the previous best result of Greve et al. (Cell Probe Lower Bounds and Approximations for Range Mode, ICALP'10) by saving the space cost by a factor of lg n while achieving the same query time. In dynamic settings, we design an O(n)-word data structure that answers queries in O(lg n /lg lg n) time and supports insertions and deletions in O(lg n) time, for any constant epsilon in (0,1); the bounds for non-constant epsilon = o(1) are also given in the paper. This is the first result on dynamic approximate range mode; it can also be used to obtain the first static data structure for approximate 3-sided range mode queries in two dimensions. Another problem we consider is approximate range selection. For any alpha in (0,1/2), an alpha-approximate range selection query asks for the position of an element whose rank in the query range is in [k - alpha s, k + alpha s], where k is a rank given by the query and s is the size of the query range. When alpha is a constant, we design an O(n)-bit encoding data structure that can answer queries in constant time and prove this space cost is asymptotically optimal. The previous best result by Krizanc et al. (Range Mode and Range Median Queries on Lists and Trees, Nordic Journal of Computing, 2005) uses O(n lg n) bits, or O(n) words, to achieve constant approximation for range median only. Thus we not only improve the space cost, but also provide support for any arbitrary k given at query time. We also analyse our solutions for non-constant alpha.
Cite as

Hicham El-Zein, Meng He, J. Ian Munro, Yakov Nekrich, and Bryce Sandlund. On Approximate Range Mode and Range Selection. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{elzein_et_al:LIPIcs.ISAAC.2019.57,
  author =	{El-Zein, Hicham and He, Meng and Munro, J. Ian and Nekrich, Yakov and Sandlund, Bryce},
  title =	{{On Approximate Range Mode and Range Selection}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{57:1--57:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.57},
  URN =		{urn:nbn:de:0030-drops-115531},
  doi =		{10.4230/LIPIcs.ISAAC.2019.57},
  annote =	{Keywords: data structures, approximate range query, range mode, range median}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.25
Improved Time and Space Bounds for Dynamic Range Mode

Authors: Hicham El-Zein, Meng He, J. Ian Munro, and Bryce Sandlund

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Given an array A of n elements, we wish to support queries for the most frequent and least frequent element in a subrange [l, r] of A. We also wish to support updates that change a particular element at index i or insert/ delete an element at index i. For the range mode problem, our data structure supports all operations in O(n^{2/3}) deterministic time using only O(n) space. This improves two results by Chan et al. [Timothy M. Chan et al., 2014]: a linear space data structure supporting update and query operations in O~(n^{3/4}) time and an O(n^{4/3}) space data structure supporting update and query operations in O~(n^{2/3}) time. For the range least frequent problem, we address two variations. In the first, we are allowed to answer with an element of A that may not appear in the query range, and in the second, the returned element must be present in the query range. For the first variation, we develop a data structure that supports queries in O~(n^{2/3}) time, updates in O(n^{2/3}) time, and occupies O(n) space. For the second variation, we develop a Monte Carlo data structure that supports queries in O(n^{2/3}) time, updates in O~(n^{2/3}) time, and occupies O~(n) space, but requires that updates are made independently of the results of previous queries. The Monte Carlo data structure is also capable of answering k-frequency queries; that is, the problem of finding an element of given frequency in the specified query range. Previously, no dynamic data structures were known for least frequent element or k-frequency queries.
Cite as

Hicham El-Zein, Meng He, J. Ian Munro, and Bryce Sandlund. Improved Time and Space Bounds for Dynamic Range Mode. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{elzein_et_al:LIPIcs.ESA.2018.25,
  author =	{El-Zein, Hicham and He, Meng and Munro, J. Ian and Sandlund, Bryce},
  title =	{{Improved Time and Space Bounds for Dynamic Range Mode}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.25},
  URN =		{urn:nbn:de:0030-drops-94886},
  doi =		{10.4230/LIPIcs.ESA.2018.25},
  annote =	{Keywords: dynamic data structures, range query, range mode, range least frequent, range k-frequency}
}
  • Refine by Type
  • 8 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 3 2020
  • 1 2019
  • 1 2018

  • Refine by Author
  • 5 Sandlund, Bryce
  • 3 Munro, J. Ian
  • 2 El-Zein, Hicham
  • 2 He, Meng
  • 1 Bhardwaj, Nalin
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 5 Theory of computation → Data structures design and analysis
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation
  • 1 Theory of computation → Data structures and algorithms for data management
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 3 range mode
  • 2 range median
  • 1 B-tree
  • 1 Cartesian tree
  • 1 Data Structures
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact