Hierarchical Categories in Colored Searching

TY - GEN

T1 - Hierarchical Categories in Colored Searching

AU - Afshani, Peyman

AU - Killmann, Rasmus

AU - Larsen, Kasper Green

N1 - Publisher Copyright: © Peyman Afshani, Rasmus Killmann, and Kasper Green Larsen.

PY - 2022/12

Y1 - 2022/12

N2 - In colored range counting (CRC), the input is a set of points where each point is assigned a “color” (or a “category”) and the goal is to store them in a data structure such that the number of distinct categories inside a given query range can be counted efficiently. CRC has strong motivations as it allows data structure to deal with categorical data. However, colors (i.e., the categories) in the CRC problem do not have any internal structure, whereas this is not the case for many datasets in practice where hierarchical categories exists or where a single input belongs to multiple categories. Motivated by these, we consider variants of the problem where such structures can be represented. We define two variants of the problem called hierarchical range counting (HCC) and sub-category colored range counting (SCRC) and consider hierarchical structures that can either be a DAG or a tree. We show that the two problems on some special trees are in fact equivalent to other well-known problems in the literature. Based on these, we also give efficient data structures when the underlying hierarchy can be represented as a tree. We show a conditional lower bound for the general case when the existing hierarchy can be any DAG, through reductions from the orthogonal vectors problem.

AB - In colored range counting (CRC), the input is a set of points where each point is assigned a “color” (or a “category”) and the goal is to store them in a data structure such that the number of distinct categories inside a given query range can be counted efficiently. CRC has strong motivations as it allows data structure to deal with categorical data. However, colors (i.e., the categories) in the CRC problem do not have any internal structure, whereas this is not the case for many datasets in practice where hierarchical categories exists or where a single input belongs to multiple categories. Motivated by these, we consider variants of the problem where such structures can be represented. We define two variants of the problem called hierarchical range counting (HCC) and sub-category colored range counting (SCRC) and consider hierarchical structures that can either be a DAG or a tree. We show that the two problems on some special trees are in fact equivalent to other well-known problems in the literature. Based on these, we also give efficient data structures when the underlying hierarchy can be represented as a tree. We show a conditional lower bound for the general case when the existing hierarchy can be any DAG, through reductions from the orthogonal vectors problem.

KW - Categorical Data

KW - Computational Geometry

UR - http://www.scopus.com/inward/record.url?scp=85144230597&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2022.25

DO - 10.4230/LIPIcs.ISAAC.2022.25

M3 - Article in proceedings

AN - SCOPUS:85144230597

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 33rd International Symposium on Algorithms and Computation, ISAAC 2022

A2 - Bae, Sang Won

A2 - Park, Heejin

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 33rd International Symposium on Algorithms and Computation, ISAAC 2022

Y2 - 19 December 2022 through 21 December 2022

ER -