论文标题
进一步的彩色范围搜索结果
Further Results on Colored Range Searching
论文作者
论文摘要
我们提供了许多有关搜索彩色（或“分类”）数据的新结果： 1。对于三个维度的一组$ n $彩色点，我们描述了$ o（n \ mathop {\ rm polylog} n）$ space的随机数据结构，可以在任何查询正交范围（axis arigned box）中报告$ o（k \ ntrions phution the $ rm polyloglog} $ k.该坐标位于$ \ {1，\ ldots，n \} $中。先前的数据结构要求$ o（\ frac {\ log n} {\ log \ log n} + k）$查询时间。我们的结果也意味着改善较高的恒定维度。 2。我们的数据结构可以在三个维度（或二维中的圆形范围）中适应半空间范围，从而实现$ O（k \ log n）$预期查询时间。先前的数据结构需要$ O（k \ log^2n）$查询时间。 3。对于二维$ n $彩色点的集合，我们描述了一个具有$ o（n \ mathop {\ rm polylog} n）$ space的数据结构，该空间可以回答彩色的“类型-2”范围计数查询：报告查询正性范围中每个独特颜色的出现数量。查询时间为$ o（\ frac {\ log n} {\ log \ log n} + k \ log \ log \ log n）$，其中$ k $是该范围内不同颜色的数量。天真执行$ k $未颜色的范围计数查询将需要$ o（k \ frac {\ log n} {\ log \ log \ log n}）$ time。 我们的数据结构是使用各种技术设计的，包括随机增量结构的彩色变体（可能是独立感兴趣的），浅插曲的彩色变体以及填充位的技巧。
We present a number of new results about range searching for colored (or "categorical") data: 1. For a set of $n$ colored points in three dimensions, we describe randomized data structures with $O(n\mathop{\rm polylog}n)$ space that can report the distinct colors in any query orthogonal range (axis-aligned box) in $O(k\mathop{\rm polyloglog} n)$ expected time, where $k$ is the number of distinct colors in the range, assuming that coordinates are in $\{1,\ldots,n\}$. Previous data structures require $O(\frac{\log n}{\log\log n} + k)$ query time. Our result also implies improvements in higher constant dimensions. 2. Our data structures can be adapted to halfspace ranges in three dimensions (or circular ranges in two dimensions), achieving $O(k\log n)$ expected query time. Previous data structures require $O(k\log^2n)$ query time. 3. For a set of $n$ colored points in two dimensions, we describe a data structure with $O(n\mathop{\rm polylog}n)$ space that can answer colored "type-2" range counting queries: report the number of occurrences of every distinct color in a query orthogonal range. The query time is $O(\frac{\log n}{\log\log n} + k\log\log n)$, where $k$ is the number of distinct colors in the range. Naively performing $k$ uncolored range counting queries would require $O(k\frac{\log n}{\log\log n})$ time. Our data structures are designed using a variety of techniques, including colored variants of randomized incremental construction (which may be of independent interest), colored variants of shallow cuttings, and bit-packing tricks.
