External memory range reporting on a grid
作者： Yakov Nekrich
DOI: 10.1007/978-3-540-77120-3_46
关键词: Auxiliary memory 、 Range (computer programming) 、 Combinatorics 、 Computer science 、 Data structure 、 Theoretical computer science 、 Grid
摘要: In this paper we present external memory data structures for orthogonal range reporting queries on a grid. Our structure twodimensional uses O((N/B) log2 N) blocks of space size B and supports in optimal O(log2 logB U+ T/B) time, where U is the universe, N number elements structure, T answer. three-sided that O(N/B) +T/B) time. case threesided × grid, describe logB2 with O(T/B) query logB* O(logB* + O(logB(k) time any constant k.
springer.com
sci-hub.st 参考文章(28)
Sridhar Ramaswamy, Sairam Subramanian, Path Caching: A Technique for Optimal External Searching symposium on principles of database systems. pp. 25- 35 ,(1994)
Ch. Icking, R. Klein, Th. Ottmann, Priority search trees in secondary memory (extended abstract) workshop on graph-theoretic concepts in computer science. pp. 84- 93 ,(1987) , 10.1007/3-540-19422-3_7
Timothy Chan, Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry foundations of computer science. pp. 333- 344 ,(2006) , 10.1109/FOCS.2006.62
Mark H Overmars, Efficient data structures for range searching on a grid Journal of Algorithms. ,vol. 9, pp. 254- 275 ,(1988) , 10.1016/0196-6774(88)90041-7
Paul Beame, Faith E. Fich, Optimal bounds for the predecessor problem and related problems symposium on the theory of computing. ,vol. 65, pp. 38- 72 ,(2002) , 10.1006/JCSS.2002.1822
Sridhar Ramaswamy, Sairam Subramanian, Path caching (extended abstract): a technique for optimal external searching symposium on principles of database systems. pp. 25- 35 ,(1994) , 10.1145/182591.182595
Roberto Grossi, Giuseppe F. Italiano, Efficient Splitting and Merging Algorithms for Order Decomposable Problems Information & Computation. ,vol. 154, pp. 1- 33 ,(1999) , 10.1006/INCO.1999.2811
Yakov Nekrich, A data structure for multi-dimensional range reporting Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07. pp. 344- 353 ,(2007) , 10.1145/1247069.1247130
Alok Aggarwal, Jeffrey,S. Vitter, The input/output complexity of sorting and related problems Communications of The ACM. ,vol. 31, pp. 1116- 1127 ,(1988) , 10.1145/48529.48535
Lars Arge, Vasilis Samoladas, Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing symposium on principles of database systems. pp. 346- 357 ,(1999) , 10.1145/303976.304010