1 Search Results for "Park, Wooyoung"

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-dev.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}
}
  • Refine by Author
  • 1 Jo, Seungbum
  • 1 Park, Wooyoung
  • 1 Satti, Srinivasa Rao

  • Refine by Classification
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 Cartesian tree
  • 1 Range minimum query
  • 1 Range top-2 query
  • 1 Succinct encoding

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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