License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.33
URN: urn:nbn:de:0030-drops-161931
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16193/
Go to the corresponding LIPIcs Volume Portal

Yanagita, Tatsuya ; Chakraborty, Sankardeep ; Sadakane, Kunihiko ; Satti, Srinivasa Rao

Space-Efficient Data Structure for Posets with Applications

pdf-format:
LIPIcs-SWAT-2022-33.pdf (0.8 MB)

Abstract

Space efficient data structures for partial ordered sets or posets are well-researched field. It is known that a poset with n elements can be represented in n²/4 + o(n²) bits [Munro and Nicholson, 2016] and can also be represented in (1 + ε)n log n + 2nk + o(nk) bits [Farzan and Fischer, 2011] where k is width of the poset. In this paper, we make the latter data structure occupy 2n(k-1) + o(nk) bits by considering topological labeling on the elements of posets. Also considering the topological labeling, we propose a new data structure that calculates queries on transitive reduction graphs of posets faster though queries on transitive closure graphs are computed slower. Moreover, we propose an alternative data structure for topological labeled posets that calculates both of the queries faster though it uses 3nk - 2n + o(nk) bits of space. Additionally, we discuss the advantage of these data structures from the perspective of an application for BlockDAG, which is a more scalable version of Blockchain.

BibTeX - Entry

@InProceedings{yanagita_et_al:LIPIcs.SWAT.2022.33,
  author =	{Yanagita, Tatsuya and Chakraborty, Sankardeep and Sadakane, Kunihiko and Satti, Srinivasa Rao},
  title =	{{Space-Efficient Data Structure for Posets with Applications}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16193},
  URN =		{urn:nbn:de:0030-drops-161931},
  doi =		{10.4230/LIPIcs.SWAT.2022.33},
  annote =	{Keywords: Succinct Data Structures, Posets, Blockchain}
}

Keywords: Succinct Data Structures, Posets, Blockchain
Collection: 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Issue Date: 2022
Date of publication: 22.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI