13 Search Results for "Jo, Seungbum"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.29
Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings

Authors: Michael Elberfeld, Frank Kammer, and Johannes Meintrup

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We call a graph G separable if a balanced separator can be computed for G of size O(n^ε) with ε < 1. Many real-world graphs are separable such as graphs of bounded genus, graphs of constant treewidth, and graphs excluding a fixed minor. In particular, the well-known planar graphs are separable. We present a succinct encoding of separable graphs G such that, after the encoding is computed, any number of depth-first searches (DFS) can be performed from any given start vertex, each in o(n) time and o(n) bits in the word RAM model. After the execution of a DFS, the succinct encoding of G is augmented such that the DFS tree is encoded inside the encoding while maintaining succinctness. Afterward, the encoding provides common DFS-related queries in constant time. These queries include queries such as lowest-common ancestor of two given vertices in the DFS tree or queries that output the lowpoint of a given vertex in the DFS tree. Furthermore, for planar graphs, we show that the succinct encoding can be computed in O(n) bits and expected linear time, and a compact variant can be constructed in O(n) time and bits. For other separable graph classes 𝒢 the runtime and space usage depends on the specific algorithms used to find balanced separators in graphs of 𝒢.
Cite as

Michael Elberfeld, Frank Kammer, and Johannes Meintrup. Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{elberfeld_et_al:LIPIcs.ISAAC.2025.29,
  author =	{Elberfeld, Michael and Kammer, Frank and Meintrup, Johannes},
  title =	{{Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.29},
  URN =		{urn:nbn:de:0030-drops-249379},
  doi =		{10.4230/LIPIcs.ISAAC.2025.29},
  annote =	{Keywords: Depth-First Search, Succinct, Space Efficient, Separable Graphs, Planar Graphs, Table Lookup, r-Division}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.10
The Bend Number of Cocomparability Graphs

Authors: Todor Antić, Vit Jelínek, Martin Pergel, Felix Schröder, Peter Stumpf, and Pavel Valtr

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We introduce a new complexity measure for cocomparability graphs of posets or in other words, intersection graphs of piecewise linear functions, the bend number. We prove that cocomparability graphs of bounded bend number are not too plentiful and give two hierarchies of classes of cocomparability graphs, depending on whether the piecewise linear functions are restricted to slopes of ±1 (diagonal case) or not (general case). These hierarchies give a gradation between permutation graphs and cocomparability graphs.
Cite as

Todor Antić, Vit Jelínek, Martin Pergel, Felix Schröder, Peter Stumpf, and Pavel Valtr. The Bend Number of Cocomparability Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{antic_et_al:LIPIcs.GD.2025.10,
  author =	{Anti\'{c}, Todor and Jel{\'\i}nek, Vit and Pergel, Martin and Schr\"{o}der, Felix and Stumpf, Peter and Valtr, Pavel},
  title =	{{The Bend Number of Cocomparability Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.10},
  URN =		{urn:nbn:de:0030-drops-249963},
  doi =		{10.4230/LIPIcs.GD.2025.10},
  annote =	{Keywords: Intersection Graphs, Bend Number, Piecewise Linear Functions, Graph Class Hierarchy, Cocomparability Graphs, Permutation Graphs, Poset Dimension}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.35
Succinct Data Structures for Chordal Graph with Bounded Leafage or Vertex Leafage

Authors: Meng He and Kaiyu Wu

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We improve the recent succinct data structure result of Balakrishnan et al. for chordal graphs with bounded vertex leafage (SWAT 2024). A chordal graph is a widely studied graph class which can be characterized as the intersection graph of subtrees of a host tree, denoted as a tree representation of the chordal graph. The vertex leafage and leafage parameters of a chordal graph deal with the existence of a tree representation with a bounded number of leaves in either the subtrees representing the vertices or the host tree itself. We simplify the lower bound proof of Balakrishnan et al. which applied to only chordal graphs with bounded vertex leafage, and extend it to a lower bound proof for chordal graphs with bounded leafage as well. For both classes of graphs, the information-theoretic lower bound we (re-)obtain for k = o(n) is (k-1)nlog n - knlog k - o(knlog n) bits, where the leafage or vertex leafage of the graph is at most k = o(n). We further extend the range of the parameter k to Θ(n) as well. Then we give a succinct data structure using (k-1)nlog (n/k) + o(knlog n) bits to answer adjacent queries, which test the adjacency between pairs of vertices, in O((log k)/(log log n) + 1) time compared to the O(klog n) time of the data structure of Balakrishnan et al. For the neighborhood query which lists the neighbours of a given vertex, our query time is O((log n)/(log log n)) per neighbour compared to O(k²log n) per neighbour. We also extend the data structure ideas to obtain a succinct data structure for chordal graphs with bounded leafage k, answering an open question of Balakrishnan et al. Our succinct data structure, which uses (k-1)nlog (n/k) + o(knlog n) bits, has query time O(1) for the adjacent query and O(1) per neighbour for the neighborhood query. Using slightly more space (an additional (1+ε)nlog n bits for any ε > 0) allows distance queries, which compute the number of edges in the shortest path between two given vertices, to be answered in O(1) time as well.
Cite as

Meng He and Kaiyu Wu. Succinct Data Structures for Chordal Graph with Bounded Leafage or Vertex Leafage. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 35:1-35:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.WADS.2025.35,
  author =	{He, Meng and Wu, Kaiyu},
  title =	{{Succinct Data Structures for Chordal Graph with Bounded Leafage or Vertex Leafage}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{35:1--35:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.35},
  URN =		{urn:nbn:de:0030-drops-242660},
  doi =		{10.4230/LIPIcs.WADS.2025.35},
  annote =	{Keywords: Chordal Graph, Leafage, Vertex Leafage, Succinct Data Structure}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.86
Optimal Distance Labeling for Permutation Graphs

Authors: Paweł Gawrychowski and Wojciech Janczewski

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
A permutation graph is the intersection graph of a set of segments between two parallel lines. In other words, they are defined by a permutation π on n elements, such that u and v are adjacent if an only if u < v but π(u) > π(v). We consider the problem of computing the distances in such a graph in the setting of informative labeling schemes. The goal of such a scheme is to assign a short bitstring 𝓁(u) to every vertex u, such that the distance between u and v can be computed using only 𝓁(u) and 𝓁(v), and no further knowledge about the whole graph (other than that it is a permutation graph). This elegantly captures the intuition that we would like our data structure to be distributed, and often leads to interesting combinatorial challenges while trying to obtain lower and upper bounds that match up to the lower-order terms. For distance labeling of permutation graphs on n vertices, Katz, Katz, and Peleg [STACS 2000] showed how to construct labels consisting of 𝒪(log² n) bits. Later, Bazzaro and Gavoille [Discret. Math. 309(11)] obtained an asymptotically optimal bound by showing how to construct labels consisting of 9log{n}+𝒪(1) bits, and proving that 3log{n}-𝒪(log{log{n}}) bits are necessary. This however leaves a quite large gap between the known lower and upper bounds. We close this gap by showing how to construct labels consisting of 3log{n}+𝒪(1) bits.
Cite as

Paweł Gawrychowski and Wojciech Janczewski. Optimal Distance Labeling for Permutation Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 86:1-86:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.ICALP.2025.86,
  author =	{Gawrychowski, Pawe{\l} and Janczewski, Wojciech},
  title =	{{Optimal Distance Labeling for Permutation Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{86:1--86:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.86},
  URN =		{urn:nbn:de:0030-drops-234632},
  doi =		{10.4230/LIPIcs.ICALP.2025.86},
  annote =	{Keywords: informative labeling, permutation graph, distance labeling}
}
Document
DOI: 10.4230/LIPIcs.CPM.2025.7
FL-RMQ: A Learned Approach to Range Minimum Queries

Authors: Paolo Ferragina and Filippo Lari

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract
We address the problem of designing and implementing a data structure for the Range Minimum Query problem. We show a surprising connection between this classical problem and the geometry of a properly defined set of points in the Cartesian plane. Building on this insight, we hinge upon a well-known result in Computational Geometry to introduce the first RMQ solution that exploits (i.e., learns) the distribution of such 2D-points via proper error-bounded linear approximations. Because of these features, we name the resulting data structure: Fully-Learned RMQ, shortly FL-RMQ. We prove theoretical bounds for its space usage and query time, covering both worst-case scenarios and average-case performance for uniformly distributed inputs. These bounds compare favorably with the ones achievable by the best-known indexing solutions (i.e., the ones that allow access to the indexed array), especially when the input data follow some geometric regularities that we characterize in the paper, thus providing principled evidence of FL-RMQ being a novel data-aware solution to the RMQ problem. We corroborate our theoretical findings with a wide set of experiments showing that FL-RMQ offers more robust space-time trade-offs than the other known practical indexing solutions on both artificial and real-world datasets. We believe that our novel approach to the RMQ problem is noteworthy not only for its interesting space-time trade-offs, but also because it is flexible enough to be applied easily to the encoding variant of RMQ (i.e., the one that does not allow access to the indexed array), and moreover, because it paves the way to research opportunities on possibly other problems.
Cite as

Paolo Ferragina and Filippo Lari. FL-RMQ: A Learned Approach to Range Minimum Queries. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ferragina_et_al:LIPIcs.CPM.2025.7,
  author =	{Ferragina, Paolo and Lari, Filippo},
  title =	{{FL-RMQ: A Learned Approach to Range Minimum Queries}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.7},
  URN =		{urn:nbn:de:0030-drops-231014},
  doi =		{10.4230/LIPIcs.CPM.2025.7},
  annote =	{Keywords: Range-Minimum query, Learned data structures, Compact data structures, Experimental results}
}
Document
DOI: 10.4230/LIPIcs.CPM.2025.25
Encodings for Range Minimum Queries over Bounded Alphabets

Authors: Seungbum Jo and Srinivasa Rao Satti

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract
Range minimum queries (RMQs) are fundamental operations with widespread applications in database management, text indexing and computational biology. While many space-efficient data structures have been designed for RMQs on arrays with arbitrary elements, there has not been any results developed for the case when the alphabet size is small, which is the case in many practical scenarios where RMQ structures are used. In this paper, we investigate the encoding complexity of RMQs on arrays over bounded alphabet. We consider both one-dimensional (1D) and two-dimensional (2D) arrays. For the 1D case, we present a near-optimal space encoding. For constant-sized alphabets, this also supports the queries in constant time. For the 2D case, we systematically analyze the 1-sided, 2-sided, 3-sided and 4-sided queries and derive lower bounds for encoding space, and also matching upper bounds that support efficient queries in most cases. Our results demonstrate that, even with the bounded alphabet restriction, the space requirements remain close to those for the general alphabet case.
Cite as

Seungbum Jo and Srinivasa Rao Satti. Encodings for Range Minimum Queries over Bounded Alphabets. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jo_et_al:LIPIcs.CPM.2025.25,
  author =	{Jo, Seungbum and Satti, Srinivasa Rao},
  title =	{{Encodings for Range Minimum Queries over Bounded Alphabets}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.25},
  URN =		{urn:nbn:de:0030-drops-231198},
  doi =		{10.4230/LIPIcs.CPM.2025.25},
  annote =	{Keywords: Range minimum queries, Encoding data structures, Cartesian trees}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.17
Succinct Data Structures for Baxter Permutation and Related Families

Authors: Sankardeep Chakraborty, Seungbum Jo, Geunho Kim, and Kunihiko Sadakane

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
A permutation π: [n] → [n] is a Baxter permutation if and only if it does not contain either of the patterns 2-41-3 and 3-14-2. Baxter permutations are one of the most widely studied subclasses of general permutation due to their connections with various combinatorial objects such as plane bipolar orientations and mosaic floorplans, etc. In this paper, we introduce a novel succinct representation (i.e., using o(n) additional bits from their information-theoretical lower bounds) for Baxter permutations of size n that supports π(i) and π^{-1}(j) queries for any i ∈ [n] in O(f₁(n)) and O(f₂(n)) time, respectively. Here, f₁(n) and f₂(n) are arbitrary increasing functions that satisfy the conditions ω(log n) and ω(log² n), respectively. This stands out as the first succinct representation with sub-linear worst-case query times for Baxter permutations. The main idea is to traverse the Cartesian tree on the permutation using a simple yet elegant two-stack algorithm which traverses the nodes in ascending order of their corresponding labels and stores the necessary information throughout the algorithm. Additionally, we consider a subclass of Baxter permutations called separable permutations, which do not contain either of the patterns 2-4-1-3 and 3-1-4-2. In this paper, we provide the first succinct representation of the separable permutation ρ: [n] → [n] of size n that supports both ρ(i) and ρ^{-1}(j) queries in O(1) time. In particular, this result circumvents Golynski’s [SODA 2009] lower bound result for trade-offs between redundancy and ρ(i) and ρ^{-1}(j) queries. Moreover, as applications of these permutations with the queries, we also introduce the first succinct representations for mosaic/slicing floorplans, and plane bipolar orientations, which can further support specific navigational queries on them efficiently.
Cite as

Sankardeep Chakraborty, Seungbum Jo, Geunho Kim, and Kunihiko Sadakane. Succinct Data Structures for Baxter Permutation and Related Families. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2024.17,
  author =	{Chakraborty, Sankardeep and Jo, Seungbum and Kim, Geunho and Sadakane, Kunihiko},
  title =	{{Succinct Data Structures for Baxter Permutation and Related Families}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.17},
  URN =		{urn:nbn:de:0030-drops-221441},
  doi =		{10.4230/LIPIcs.ISAAC.2024.17},
  annote =	{Keywords: Succinct data structure, Baxter permutation, Mosaic floorplan, Plane bipolar orientation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.64
A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs

Authors: Kou Hamada, Sankardeep Chakraborty, Seungbum Jo, Takuto Koriyama, Kunihiko Sadakane, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Tree covering is a technique for decomposing a tree into smaller sized trees with desirable properties, and has been employed in various succinct data structures. However, significant hurdles stand in the way of a practical implementation of tree covering: a lot of pointers are used to maintain the tree-covering hierarchy and many indices for tree navigational queries consume theoretically negligible yet practically vast space. To tackle these problems, we propose a simple representation of tree covering using a balanced-parenthesis representation. The key to the proposal is the observation that every micro tree splits into at most two intervals on the BP representation. Utilizing the representation, we propose several data structures that represent a tree and its tree cover, which consequently allow micro tree compression with arbitrary coding and efficient tree navigational queries. We also applied our data structure to average-case optimal RMQ by Munro et al. [ESA 2021] and implemented the RMQ data structure. Our RMQ data structures spend less than 2n bits and process queries in a practical time on several settings of the performance evaluation, reducing the gap between theoretical space complexity and actual space consumption. For example, our implementation consumes 1.822n bits and processes queries in 5µs on average for random queries and in 13µs on average for the worst query widths. We also implement tree navigational operations while using the same amount of space as the RMQ data structures. We believe the representation can be widely utilized for designing practically memory-efficient data structures based on tree covering.
Cite as

Kou Hamada, Sankardeep Chakraborty, Seungbum Jo, Takuto Koriyama, Kunihiko Sadakane, and Srinivasa Rao Satti. A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hamada_et_al:LIPIcs.ESA.2024.64,
  author =	{Hamada, Kou and Chakraborty, Sankardeep and Jo, Seungbum and Koriyama, Takuto and Sadakane, Kunihiko and Satti, Srinivasa Rao},
  title =	{{A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{64:1--64:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.64},
  URN =		{urn:nbn:de:0030-drops-211359},
  doi =		{10.4230/LIPIcs.ESA.2024.64},
  annote =	{Keywords: Hypersuccinct trees, Succinct data structures, Range minimum queries, Binary trees}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.10
Practical Implementation of Encoding Range Top-2 Queries

Authors: Seungbum Jo, Wooyoung Park, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
We design a practical variant of an encoding for range Top-2 queries (RT2Q), and evaluate its performance. Given an array A[1,n] of n elements from a total order, the range Top-2 encoding problem is to construct a data structure that can answer RT2Q queries, which return the positions of the first and the second largest elements within a given query range of A, without accessing the array A at query time. Davoodi et al. [Phil. Trans. Royal Soc. A, 2016] proposed a (3.272n + o(n))-bit encoding, which answers RT2Q queries in O(1) time, while Gawrychowski and Nicholson [ICALP, 2015] gave an optimal (2.755n + (n))-bit encoding which doesn't support efficient queries. In this paper, we propose the first practical implementation of the encoding data structure for answering RT2Q. Our implementation is based on an alternative representation of Davoodi et al.’s data structure. The experimental results show that our implementation is efficient in practice, and gives improved time-space trade-offs compared to the indexing data structures (which keep the original array A as part of the data structure) for range maximum queries.
Cite as

Seungbum Jo, Wooyoung Park, and Srinivasa Rao Satti. Practical Implementation of Encoding Range Top-2 Queries. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jo_et_al:LIPIcs.SEA.2021.10,
  author =	{Jo, Seungbum and Park, Wooyoung and Satti, Srinivasa Rao},
  title =	{{Practical Implementation of Encoding Range Top-2 Queries}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.10},
  URN =		{urn:nbn:de:0030-drops-137827},
  doi =		{10.4230/LIPIcs.SEA.2021.10},
  annote =	{Keywords: Range top-2 query, Range minimum query, Cartesian tree, Succinct encoding}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.54
Approximate Query Processing over Static Sets and Sliding Windows

Authors: Ran Ben Basat, Seungbum Jo, Srinivasa Rao Satti, and Shubham Ugare

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Indexing of static and dynamic sets is fundamental to a large set of applications such as information retrieval and caching. Denoting the characteristic vector of the set by B, we consider the problem of encoding sets and multisets to support approximate versions of the operations rank(i) (i.e., computing sum_{j <= i} B[j]) and select(i) (i.e., finding min{p|rank(p) >= i}) queries. We study multiple types of approximations (allowing an error in the query or the result) and present lower bounds and succinct data structures for several variants of the problem. We also extend our model to sliding windows, in which we process a stream of elements and compute suffix sums. This is a generalization of the window summation problem that allows the user to specify the window size at query time. Here, we provide an algorithm that supports updates and queries in constant time while requiring just (1+o(1)) factor more space than the fixed-window summation algorithms.
Cite as

Ran Ben Basat, Seungbum Jo, Srinivasa Rao Satti, and Shubham Ugare. Approximate Query Processing over Static Sets and Sliding Windows. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 54:1-54:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.ISAAC.2018.54,
  author =	{Ben Basat, Ran and Jo, Seungbum and Satti, Srinivasa Rao and Ugare, Shubham},
  title =	{{Approximate Query Processing over Static Sets and Sliding Windows}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{54:1--54:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.54},
  URN =		{urn:nbn:de:0030-drops-100027},
  doi =		{10.4230/LIPIcs.ISAAC.2018.54},
  annote =	{Keywords: Streaming, Algorithms, Sliding window, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.69
Encoding Two-Dimensional Range Top-k Queries Revisited

Authors: Seungbum Jo and Srinivasa Rao Satti

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We consider the problem of encoding two-dimensional arrays, whose elements come from a total order, for answering Top-k queries. The aim is to obtain encodings that use space close to the information-theoretic lower bound, which can be constructed efficiently. For 2 x n arrays, we first give upper and lower bounds on space for answering sorted and unsorted 3-sided Top-k queries. For m x n arrays, with m <=n and k <=mn, we obtain (m lg{(k+1)n choose n}+4nm(m-1)+o(n))-bit encoding for answering sorted 4-sided Top-k queries. This improves the min{(O(mn lg{n}),m^2 lg{(k+1)n choose n} + m lg{m}+o(n))}-bit encoding of Jo et al. [CPM, 2016] when m = o(lg{n}). This is a consequence of a new encoding that encodes a 2 x n array to support sorted 4-sided Top-k queries on it using an additional 4n bits, in addition to the encodings to support the Top-k queries on individual rows. This new encoding is a non-trivial generalization of the encoding of Jo et al. [CPM, 2016] that supports sorted 4-sided Top-2 queries on it using an additional 3n bits. We also give almost optimal space encodings for 3-sided Top-k queries, and show lower bounds on encodings for 3-sided and 4-sided Top-k queries.
Cite as

Seungbum Jo and Srinivasa Rao Satti. Encoding Two-Dimensional Range Top-k Queries Revisited. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 69:1-69:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jo_et_al:LIPIcs.ISAAC.2018.69,
  author =	{Jo, Seungbum and Satti, Srinivasa Rao},
  title =	{{Encoding Two-Dimensional Range Top-k Queries Revisited}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{69:1--69:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.69},
  URN =		{urn:nbn:de:0030-drops-100179},
  doi =		{10.4230/LIPIcs.ISAAC.2018.69},
  annote =	{Keywords: Encoding model, top-k query, range minimum query}
}
Document
DOI: 10.4230/LIPIcs.CPM.2016.3
Encoding Two-Dimensional Range Top-k Queries

Authors: Seungbum Jo, Rahul Lingala, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

Abstract
We consider various encodings that support range top-k queries on a two-dimensional array containing elements from a total order. For an m x n array, we first propose an almost optimal encoding for answering one-sided top-k queries, whose query range is restricted to [1 ... m][1 .. a], for 1 <= a <= n. Next, we propose an encoding for the general top-k queries that takes m^2 * lg(binom((k+1)n)(n)) + m * lg(m) + o(n) bits. This generalizes the one-dimensional top-k encoding of Gawrychowski and Nicholson [ICALP, 2015]. Finally, for a 2 x n array, we obtain a 2 lg(binom(3n)(n)) + 3n + o(n)-bit encoding for answering top-2 queries.
Cite as

Seungbum Jo, Rahul Lingala, and Srinivasa Rao Satti. Encoding Two-Dimensional Range Top-k Queries. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jo_et_al:LIPIcs.CPM.2016.3,
  author =	{Jo, Seungbum and Lingala, Rahul and Satti, Srinivasa Rao},
  title =	{{Encoding Two-Dimensional Range Top-k Queries}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{3:1--3:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Grossi, Roberto and Lewenstein, Moshe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.3},
  URN =		{urn:nbn:de:0030-drops-60704},
  doi =		{10.4230/LIPIcs.CPM.2016.3},
  annote =	{Keywords: Encoding model, top-k query, range minimum query}
}
  • Refine by Type
  • 13 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 7 2025
  • 2 2024
  • 1 2021
  • 2 2018
  • 1 2016

  • Refine by Author
  • 8 Jo, Seungbum
  • 7 Satti, Srinivasa Rao
  • 2 Chakraborty, Sankardeep
  • 2 Sadakane, Kunihiko
  • 1 Antić, Todor
  • Show More...

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

  • Refine by Classification
  • 6 Theory of computation → Data structures design and analysis
  • 5 Theory of computation → Data compression
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Information systems → Information retrieval
  • 1 Mathematics of computing → Graphs and surfaces
  • Show More...

  • Refine by Keyword
  • 2 Cartesian tree
  • 2 Encoding model
  • 2 Range minimum queries
  • 2 range minimum query
  • 2 top-k query
  • 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