Space-Efficient and fast algorithms for multidimensional dominance reporting and counting
作者： Joseph JaJa , Christian W. Mortensen , Qingmin Shi
DOI: 10.1007/978-3-540-30551-4_49
关键词: Logarithm 、 Vector space 、 Fusion tree 、 Mathematics 、 Dimension (graph theory) 、 Counting problem 、 Binary logarithm 、 Linear space 、 Algorithm 、 Algorithmics
摘要: We present linear-space sub-logarithmic algorithms for handling the 3-dimensional dominance reporting and 2-dimensional counting problems Under RAM model as described in [M L Fredman D E Willard “Surpassing information theoretic bound with fusion trees”, Journal of Computer System Sciences, 47:424–436, 1993], our achieve O(log n/loglog n+f) query time problem, where f is output size, n) problem extend these results to any constant dimension d ≥ 3, achieving O(n(log n)d−3) space O((log n)d−2+ f) case n)d−2) n)d−1) case.
springer.com
core.ac.uk
sci-hub.st 参考文章(13)
Sathish Govindarajan, Pankaj K. Agarwal, Lars Arge, CRB-Tree: An Efficient Indexing Scheme for Range-Aggregate Queries international conference on database theory. pp. 143- 157 ,(2003) , 10.1007/3-540-36285-1_10
QINGMIN SHI, JOSEPH JAJA, Fast Algorithms for 3-D Dominance Reporting and Counting International Journal of Foundations of Computer Science. ,vol. 15, pp. 673- 684 ,(2004) , 10.1142/S0129054104002686
Bernard Chazelle, Leonidas J. Guibas, Fractional cascading: I. A data structuring technique Algorithmica. ,vol. 1, pp. 133- 162 ,(1986) , 10.1007/BF01840440
Bernard Chazelle, Herbert Edelsbrunner, Linear space data structures for two types of range search Discrete & Computational Geometry. ,vol. 2, pp. 113- 126 ,(1987) , 10.1007/BF02187875
Herbert Edelsbrunner, Mark H. Overmars, On the equivalence of some rectangle problems Information Processing Letters. ,vol. 14, pp. 124- 127 ,(1982) , 10.1016/0020-0190(82)90068-0
Christos Makris, Athanasios Tsakalidis, Algorithms for three-dimensional dominance searching in linear space Information Processing Letters. ,vol. 66, pp. 277- 283 ,(1998) , 10.1016/S0020-0190(98)00075-1
Michael L. Fredman, Dan E. Willard, Surpassing the information theoretic bound with fusion trees symposium on the theory of computing. ,vol. 47, pp. 424- 436 ,(1993) , 10.1016/0022-0000(93)90040-4
Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching SIAM Journal on Computing. ,vol. 17, pp. 427- 462 ,(1988) , 10.1137/0217026
Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe, Nearest common ancestors Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '02. pp. 258- 264 ,(2002) , 10.1145/564870.564914
Jon Louis Bentley, Multidimensional divide-and-conquer Communications of The ACM. ,vol. 23, pp. 214- 229 ,(1980) , 10.1145/358841.358850