Data structures for range-aggregate extent queries

Computational Geometry - Tập 47 - Trang 329-347 - 2014
Prosenjit Gupta1,2, Ravi Janardan3, Yokesh Kumar3, Michiel Smid4
1Mentor Graphics, Hyderabad 5000082, India
2International Institute of Information Technology, Gachibowli, Hyderabad 500032, India
3Department of Computer Science & Engineering, University of Minnesota, Minneapolis, MN 55455, USA
4School of Computer Science, Carleton University, Ottawa, Ontario K1S 5B6, Canada

Tài liệu tham khảo

Abam, 2013, On the power of the semi-separated pair decomposition, Computational Geometry: Theory and Applications, 46, 631, 10.1016/j.comgeo.2013.02.003 Agarwal, 1999, Geometric range searching and its relatives, vol. 223, 1 Agarwal, 2004, Approximating extent measures of points, Journal of the ACM, 51, 606, 10.1145/1008731.1008736 Bose, 2005, Approximate range mode and range median queries, vol. 3404, 377 Datta, 2000, An efficient algorithm for computing the maximum empty rectangle in three dimensions, Information Sciences, 128, 43, 10.1016/S0020-0255(00)00047-5 de Berg, 2000 Felsner H. Gabow, J. Bentley, R. Tarjan, Scaling and related techniques for geometry problems, in: Proceedings of the 16th ACM Symposium on Theory of Computing, 1984, pp. 135–142. S. Govindarajan, P.K. Agarwal, L. Arge, CRB-tree: An efficient indexing scheme for range aggregate queries, in: Proceedings of the 9th International Conference on Database Theory, 2003, pp. 143–157. Gupta, 2005, Algorithms for range-aggregate query problems involving geometric aggregation operations, vol. 3827, 892 R.H. Güting, O. Nurmi, T. Ottmann, The direct dominance problem, in: Proc. 1st Annu. ACM Sympos. Comput. Geom., 1985, pp. 81–88. Hong, 2001, Efficient execution of range-aggregate queries in data warehouse environments, vol. 2224, 299 Janardan, 1993, On maintaining the width and diameter of a planar point-set online, International Journal of Computational Geometry & Applications, 3, 331, 10.1142/S021819599300021X Kirkpatrick, 1983, Optimal search in planar subdivisions, SIAM Journal on Computing, 12, 28, 10.1137/0212002 Klein, 1987, Direct dominance of points, International Journal of Computer Mathematics, 19, 225, 10.1080/00207168608803518 Krizanc, 2005, Range mode and range median queries on lists and trees, Nordic Journal of Computing, 12, 1 Mitzenmacher, 2005 Preparata, 1988 Shan, 2003, On spatial-range closest-pair query, vol. 2750, 252 R. Sharathkumar, P. Gupta, Range-aggregate proximity detection for design rule checking in VLSI layouts, in: Proceedings of the 18th Canadian Conference on Computational Geometry, 2006, pp. 151–154. Sharathkumar, 2007 Shekhar, 2002 Szymanski, 1988, Layout analysis and verification, 347 Tao, 2004, Range aggregate processing in spatial databases, IEEE Transactions on Knowledge and Data Engineering, 16, 1555, 10.1109/TKDE.2004.93 D. Zhang, A. Markowetz, V. Tsotras, D. Gunopulos, B. Seeger, Efficient computation of temporal aggregates with range predicates, in: Proceedings of the 20th Symposium on Principles of Database Systems, 2001, pp. 237–245. Zhang, 2005, Improving min/max aggregation over spatial objects, VLDB Journal, 14, 170, 10.1007/s00778-004-0142-4 D. Zhang, V.J. Tsotras, D. Gunopulos, Efficient aggregation over objects with extent, in: Proceedings of the 21st Symposium on Principles of Database Systems, 2002, pp. 121–132.