The landscape of compressibility measures for two-dimensional data Article Swipe

MAKE IMPACT

L. Carfagna , Giovanni Manzini · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2307.02629

In this paper we extend to two-dimensional data two recently introduced one-dimensional compressibility measures: the $γ$ measure defined in terms of the smallest string attractor, and the $δ$ measure defined in terms of the number of distinct substrings of the input string. Concretely, we introduce the two-dimensional measures $γ_{2D}$ and $δ_{2D}$, as natural generalizations of $γ$ and $δ$, and we initiate the study of their properties. Among other things, we prove that $δ_{2D}$ is monotone and can be computed in linear time, and we show that, although it is still true that $δ_{2D} \leq γ_{2D}$, the gap between the two measures can be $Ω(\sqrt{n})$ and therefore asymptotically larger than the gap between $γ$ and $δ$. To complete the scenario of two-dimensional compressibility measures, we introduce the measure $b_{2D}$ which generalizes to two dimensions the notion of optimal parsing. We prove that, somewhat surprisingly, the relationship between $b_{2D}$ and $γ_{2D}$ is significantly different than in the one-dimensional case. As an application of our results we provide the first analysis of the space usage of the two-dimensional block tree introduced in [Brisaboa et al., Two-dimensional block trees, The computer Journal, 2024]. Our analysis shows that the space usage can be bounded in terms of both $γ_{2D}$ and $δ_{2D}$. Finally, using insights from our analysis, we design the first linear time and space algorithm for constructing the two-dimensional block tree for arbitrary matrices.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2307.02629

PDF

https://arxiv.org/pdf/2307.02629

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4383604499

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4383604499

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2307.02629

Digital Object Identifier

Title

The landscape of compressibility measures for two-dimensional data

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-07-05

Full publication date if available

Authors

L. Carfagna, Giovanni Manzini

List of authors in order

Landing page

https://arxiv.org/abs/2307.02629

Publisher landing page

PDF URL

https://arxiv.org/pdf/2307.02629

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2307.02629

Direct OA link when available

Concepts

Measure (data warehouse), Dimension (graph theory), Substring, String (physics), Attractor, Monotone polygon, Mathematics, Space (punctuation), Block (permutation group theory), Compressibility, Tree (set theory), Combinatorics, Discrete mathematics, Pure mathematics, Computer science, Mathematical analysis, Physics, Data structure, Mathematical physics, Geometry, Data mining, Operating system, Thermodynamics, Programming language

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload