Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
复制标题
用于多维优势报告和计数的空间高效且快速的算法
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Qingmin Shi
中科院分区：
文献类型：
--
作者：
J. JáJá;C. Mortensen;Qingmin Shi
我们提出了用于处理 3 维优势报告和 2 维优势计数问题的线性空间亚对数算法。在 [M L Fredman 和 D E Willard “Surpassing the information theoretic limit with fusion trees”, Journal of Computer and System Sciences, 47:424–436, 1993]中描述的 RAM 模型下，我们的算法实现了 O(log n/loglog n+f) 3 维查询时间优势报告问题，其中 f 是输出大小，二维优势计数问题的查询时间为 O(log n/loglog n) 我们将这些结果扩展到任何常量维度 d ≥ 3，实现报告案例的 O(n(log n/loglog n)d−3) 空间和 O((log n/loglog n)d−2+ f) 查询时间以及 O(n(log n/loglog n)d−2) 空间和 O((log n/loglog n)d−1) 计数案例的查询时间。
We present linear-space sub-logarithmic algorithms for handling the 3-dimensional dominance reporting and the 2-dimensional dominance counting problems Under the RAM model as described in [M L Fredman and D E Willard “Surpassing the information theoretic bound with fusion trees”, Journal of Computer and System Sciences, 47:424–436, 1993], our algorithms achieve O(log n/loglog n+f) query time for the 3-dimensional dominance reporting problem, where f is the output size, and O(log n/loglog n) query time for the 2-dimensional dominance counting problem We extend these results to any constant dimension d ≥ 3, achieving O(n(log n/loglog n)d−3) space and O((log n/loglog n)d−2+ f) query time for the reporting case and O(n(log n/loglog n)d−2) space and O((log n/loglog n)d−1) query time for the counting case.