Categorical Range Reporting with Frequencies
Categorical Range Reporting with Frequencies
复制标题
带频率的分类范围报告
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Sharma V. Thankachan
中科院分区：
文献类型：
--
作者：
Arnab Ganguly;J. Munro;Yakov Nekrich;Rahul Shah;Sharma V. Thankachan
在本文中，我们考虑颜色范围报告问题的一种变体，称为频率颜色报告。我们的目标是将一组彩色点预处理为数据结构，以便给定查询范围 Q，我们可以报告 Q 中出现的所有颜色以及它们各自的频率。换句话说，对于每个报告的颜色，我们还输出它在 Q 中出现的次数。我们描述了一个外部存储器数据结构，该结构使用 O(N(1 + log2 D/ logN)) 个单词并在 O(1 +K/B) I/O 中回答一维查询，其中 N 是数据结构中的总点数，D 是数据结构中的颜色总数，K 是报告的颜色数量，B 是块大小。接下来我们转向这个问题的近似版本：报告查询范围内出现的所有颜色 σ；对于每种报告的颜色，我们提供其频率的常数因子近似值。我们考虑二维近似频率的颜色报告。我们的数据结构使用 O(N) 空间，并在查询范围在两侧有界的特殊情况下以 O(logB N + log*B +K/B) I/O 响应二维查询。作为推论，我们还可以在相同的时间和空间范围内回答一维近似查询。 2012 ACM 学科分类 计算理论 → 数据结构设计与分析
In this paper, we consider a variant of the color range reporting problem called color reporting with frequencies. Our goal is to pre-process a set of colored points into a data structure, so that given a query range Q, we can report all colors that appear in Q, along with their respective frequencies. In other words, for each reported color, we also output the number of times it occurs in Q. We describe an external-memory data structure that uses O(N(1 + log2 D/ logN)) words and answers one-dimensional queries in O(1 +K/B) I/Os, where N is the total number of points in the data structure, D is the total number of colors in the data structure, K is the number of reported colors, and B is the block size. Next we turn to an approximate version of this problem: report all colors σ that appear in the query range; for every reported color, we provide a constant-factor approximation on its frequency. We consider color reporting with approximate frequencies in two dimensions. Our data structure uses O(N) space and answers two-dimensional queries in O(logB N + log∗B +K/B) I/Os in the special case when the query range is bounded on two sides. As a corollary, we can also answer one-dimensional approximate queries within the same time and space bounds. 2012 ACM Subject Classification Theory of computation → Data structures design and analysis