摘要: In the colored (or categorical) range reporting problem set of input points is partitioned into categories and stored in a data structure; query asks for that belong to range. this paper we study two-dimensional external memory model present I/O-efficient structures problem.In particular, describe answer three-sided queries O(K/B) I/Os in(log2logB N + K/B) when lie on an x grid, K number reported colors, B block size. The space usage both close optimal.
acm.org
sci-hub.se 参考文章(27)
Yakov Nekrich, Gonzalo Navarro, Top-k document retrieval in optimal time and linear space symposium on discrete algorithms. pp. 1066- 1077 ,(2012) , 10.5555/2095116.2095200
Alexandros Nanopoulos, Panayiotis Bozanis, Categorical range queries in large databases symposium on large spatial databases. pp. 122- 139 ,(2003) , 10.1007/978-3-540-45072-6_8
Panayiotis Bozanis, Nectarios Kitsios, Christos Makris, Athanasios Tsakalidis, New Upper Bounds for Generalized Intersection Searching Problems international colloquium on automata languages and programming. pp. 464- 474 ,(1995) , 10.1007/3-540-60084-1_97
Yakov Nekrich, External memory range reporting on a grid international symposium on algorithms and computation. pp. 525- 535 ,(2007) , 10.1007/978-3-540-77120-3_46
Marek Karpinski, Yakov Nekrich, Top-K color queries for document retrieval symposium on discrete algorithms. pp. 401- 411 ,(2011) , 10.5555/2133036.2133068
Travis Gagie, Gonzalo Navarro, Simon J. Puglisi, Colored range queries and document retrieval string processing and information retrieval. pp. 67- 81 ,(2010) , 10.1007/978-3-642-16321-0_7
Rasmus Pagh, Kasper Green Larsen, I/O-efficient data structures for colored range and prefix reporting symposium on discrete algorithms. pp. 583- 592 ,(2012) , 10.5555/2095116.2095165
Harold N. Gabow, Jon Louis Bentley, Robert E. Tarjan, Scaling and related techniques for geometry problems symposium on the theory of computing. pp. 135- 143 ,(1984) , 10.1145/800057.808675
Prosenjit Gupta, Ravi Janardan, Michiel Smid, Algorithms for generalized halfspace range searching and other intersection searching problems Computational Geometry: Theory and Applications. ,vol. 6, pp. 1- 19 ,(1996) , 10.1016/0925-7721(95)00012-7
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