{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:42:49Z","timestamp":1783035769100,"version":"3.54.6"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,11]]},"abstract":"<jats:p>Visual exploration of spatial data relies heavily on spatial aggregation queries that slice and summarize the data over different regions. These queries comprise computationally-intensive point-in-polygon tests that associate data points to polygonal regions, challenging the responsiveness of visualization tools. This challenge is compounded by the sheer amounts of data, requiring a large number of such tests to be performed. Traditional pre-aggregation approaches are unsuitable in this setting since they fix the query constraints and support only rectangular regions. On the other hand, query constraints are defined interactively in visual analytics systems, and polygons can be of arbitrary shapes. In this paper, we convert a spatial aggregation query into a set of drawing operations on a canvas and leverage the rendering pipeline of the graphics hardware (GPU) to enable interactive response times. Our technique trades-off accuracy for response time by adjusting the canvas resolution, and can even provide accurate results when combined with a polygon index. We evaluate our technique on two large real-world data sets, exhibiting superior performance compared to index-based approaches.<\/jats:p>","DOI":"10.14778\/3157794.3157803","type":"journal-article","created":{"date-parts":[[2017,12,12]],"date-time":"2017-12-12T18:33:38Z","timestamp":1513103618000},"page":"352-365","source":"Crossref","is-referenced-by-count":44,"title":["GPU rasterization for real-time spatial aggregation over arbitrary polygons"],"prefix":"10.14778","volume":"11","author":[{"given":"Eleni Tzirita","family":"Zacharatou","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Harish","family":"Doraiswamy","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anastasia","family":"Ailamaki","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cl\u00e1udio T.","family":"Silva","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juliana","family":"Freire","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2996982"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536227"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.311"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002974.2002975"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2013.6691708"},{"key":"e_1_2_1_7_1","volume-title":"O. Cheong, M. v. Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications","author":"M.","year":"2008","unstructured":"M. d. Berg , O. Cheong, M. v. Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications . Springer-Verlag TELOS , Santa Clara, CA, USA , 3 rd edition, 2008 . M. d. Berg, O. Cheong, M. v. Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, Santa Clara, CA, USA, 3rd edition, 2008.","edition":"3"},{"key":"e_1_2_1_8_1","first-page":"1","volume-title":"Transactions on Large-Scale Data- and Knowledge-Centered Systems XV","author":"Bre\u00df S.","year":"2014","unstructured":"S. Bre\u00df , M. Heimel , N. Siegmund , L. Bellatreche , and G. Saake . Gpu-accelerated database systems: Survey and open challenges . In Transactions on Large-Scale Data- and Knowledge-Centered Systems XV , pages 1 -- 35 . Springer , 2014 . S. Bre\u00df, M. Heimel, N. Siegmund, L. Bellatreche, and G. Saake. Gpu-accelerated database systems: Survey and open challenges. In Transactions on Large-Scale Data- and Knowledge-Centered Systems XV, pages 1--35. Springer, 2014."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170075"},{"key":"e_1_2_1_10_1","unstructured":"Chicago Open Data. https:\/\/data.cityofchicago.org\/.  Chicago Open Data. https:\/\/data.cityofchicago.org\/."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915245"},{"key":"e_1_2_1_12_1","volume-title":"https:\/\/github.com\/raptor\/clip2tri","author":"Using","year":"2015","unstructured":"Using clipper and poly2tri together for robust triangulation. https:\/\/github.com\/raptor\/clip2tri , 2015 . Using clipper and poly2tri together for robust triangulation. https:\/\/github.com\/raptor\/clip2tri, 2015."},{"key":"e_1_2_1_13_1","volume-title":"Sensation and Perception","author":"Coren S.","year":"2003","unstructured":"S. Coren , L. M. Ward , and J. T. Enns . Sensation and Perception . Wiley , 2003 . S. Coren, L. M. Ward, and J. T. Enns. Sensation and Perception. Wiley, 2003."},{"key":"e_1_2_1_14_1","volume-title":"Oracle","author":"O. Corporation","year":"2014","unstructured":"O. Corporation . Oracle spatial and graph: Advanced data management. Technical report , Oracle , 2014 . O. Corporation. Oracle spatial and graph: Advanced data management. Technical report, Oracle, 2014."},{"key":"e_1_2_1_15_1","volume-title":"IBM White Paper","author":"Davis J.","year":"1998","unstructured":"J. Davis . Ibms db2 spatial extender : Managing geo-spatial information with the dbms . IBM White Paper , 1998 . J. Davis. Ibms db2 spatial extender: Managing geo-spatial information with the dbms. IBM White Paper, 1998."},{"issue":"12","key":"e_1_2_1_16_1","first-page":"2634","article-title":"Using topological analysis to support event-guided exploration in urban data","volume":"20","author":"Doraiswamy H.","year":"2014","unstructured":"H. Doraiswamy , N. Ferreira , T. Damoulas , J. Freire , and C. Silva . Using topological analysis to support event-guided exploration in urban data . IEEE TVCG , 20 ( 12 ): 2634 -- 2643 , 2014 . H. Doraiswamy, N. Ferreira, T. Damoulas, J. Freire, and C. Silva. Using topological analysis to support event-guided exploration in urban data. IEEE TVCG, 20(12):2634--2643, 2014.","journal-title":"IEEE TVCG"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498315"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920927"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376737"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/VAST.2015.7347636"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/83821"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007594"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1179\/000870403235002042"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376670"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2013.6691710"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-5883-1_9"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206049.1206056"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732953"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816674"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.179"},{"issue":"12","key":"e_1_2_1_34_1","first-page":"2122","article-title":"The effects of interactive latency on exploratory visual analysis","volume":"20","author":"Liu Z.","year":"2014","unstructured":"Z. Liu and J. Heer . The effects of interactive latency on exploratory visual analysis . IEEE TVCG , 20 ( 12 ): 2122 -- 2131 , 2014 . Z. Liu and J. Heer. The effects of interactive latency on exploratory visual analysis. IEEE TVCG, 20(12):2122--2131, 2014.","journal-title":"IEEE TVCG"},{"key":"e_1_2_1_35_1","first-page":"32","article-title":"immens: Real-time visual querying of big data","author":"Liu Z.","year":"2013","unstructured":"Z. Liu , B. Jiang , and J. Heer . immens: Real-time visual querying of big data . CGF , 32 , 2013 . Z. Liu, B. Jiang, and J. Heer. immens: Real-time visual querying of big data. CGF, 32, 2013.","journal-title":"CGF"},{"key":"e_1_2_1_36_1","unstructured":"Mapd technology. https:\/\/www.mapd.com\/.  Mapd technology. https:\/\/www.mapd.com\/."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2016.2598585"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.291528"},{"key":"e_1_2_1_39_1","unstructured":"MySQL 5.0 Reference Manual (11.5 Extensions for Spatial Data) 2015. MySQL 5.0 Reference Manual (11.5 Extensions for Spatial Data) 2015."},{"key":"e_1_2_1_40_1","volume-title":"NVIDIA CUDA Compute Unified Device Architecture - Programming Guide","year":"2007","unstructured":"Nvidia. NVIDIA CUDA Compute Unified Device Architecture - Programming Guide , 2007 . Nvidia. NVIDIA CUDA Compute Unified Device Architecture - Programming Guide, 2007."},{"key":"e_1_2_1_41_1","unstructured":"NYC Open Data. http:\/\/data.ny.gov.  NYC Open Data. http:\/\/data.ny.gov."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/258694.258723"},{"key":"e_1_2_1_43_1","unstructured":"Yahoo labs. https:\/\/webscope.sandbox.yahoo.com\/.  Yahoo labs. https:\/\/webscope.sandbox.yahoo.com\/."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2016.2520920"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2016.2598624"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/647227.719095"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233338"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498280"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/378456.378457"},{"key":"e_1_2_1_50_1","unstructured":"PostGIS: Spatial and geographic objects for PostgreSQL. http:\/\/postgis.net\/.  PostGIS: Spatial and geographic objects for PostgreSQL. http:\/\/postgis.net\/."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.181"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00047-5"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/832277.834354"},{"key":"e_1_2_1_54_1","volume-title":"Version 4.3","author":"Shreiner D.","year":"2013","unstructured":"D. Shreiner , G. Sellers , J. M. Kessenich , and B. M. Licea-Kane . OpenGL Programming Guide: The Official Guide to Learning OpenGL , Version 4.3 . Addison-Wesley Professional , 8 th edition, 2013 . D. Shreiner, G. Sellers, J. M. Kessenich, and B. M. Licea-Kane. OpenGL Programming Guide: The Official Guide to Learning OpenGL, Version 4.3. Addison-Wesley Professional, 8th edition, 2013.","edition":"8"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534921.2534923"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.981851"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872813"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-013-1383-8"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/645340.650234"},{"key":"e_1_2_1_60_1","volume-title":"http:\/\/www.nyc.gov\/html\/tlc\/html\/about\/trip_record_data.shtml","author":"Trip Record Data TLC","year":"2015","unstructured":"TLC Trip Record Data . http:\/\/www.nyc.gov\/html\/tlc\/html\/about\/trip_record_data.shtml , 2015 . TLC Trip Record Data. http:\/\/www.nyc.gov\/html\/tlc\/html\/about\/trip_record_data.shtml, 2015."},{"key":"e_1_2_1_61_1","volume-title":"Pearson","author":"Tukey J. W.","year":"1977","unstructured":"J. W. Tukey . Exploratory Data Analysis . Pearson , 1977 . J. W. Tukey. Exploratory Data Analysis. Pearson, 1977."},{"key":"e_1_2_1_62_1","unstructured":"Twitter API. https:\/\/dev.twitter.com\/.  Twitter API. https:\/\/dev.twitter.com\/."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.34"},{"key":"e_1_2_1_64_1","volume-title":"FOSS4G","author":"Vermeij M.","year":"2008","unstructured":"M. Vermeij , W. Quak , M. Kersten , and N. Nes . Monetdb, a novel spatial columnstore dbms . In FOSS4G , 2008 . M. Vermeij, W. Quak, M. Kersten, and N. Nes. Monetdb, a novel spatial columnstore dbms. In FOSS4G, 2008."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850584"},{"key":"e_1_2_1_66_1","volume-title":"Bin-summarise-smooth: a framework for visualising large data. Technical report, had.co.nz","author":"Wickham H.","year":"2013","unstructured":"H. Wickham . Bin-summarise-smooth: a framework for visualising large data. Technical report, had.co.nz , 2013 . H. Wickham. Bin-summarise-smooth: a framework for visualising large data. Technical report, had.co.nz, 2013."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01440.x"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915237"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2447481.2447485"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390045.2390060"},{"key":"e_1_2_1_71_1","volume-title":"High-performance spatial join processing on gpgpus with applications to large-scale taxi trip data. Technical report","author":"Zhang J.","year":"2012","unstructured":"J. Zhang , S. You , and L. Gruenwald . High-performance spatial join processing on gpgpus with applications to large-scale taxi trip data. Technical report , The City College of New York , 2012 . J. Zhang, S. You, and L. Gruenwald. High-performance spatial join processing on gpgpus with applications to large-scale taxi trip data. Technical report, The City College of New York, 2012."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835185.2835187"},{"key":"e_1_2_1_73_1","first-page":"558","volume-title":"Proc. VLDB","author":"Zimbrao G.","year":"1998","unstructured":"G. Zimbrao and J. M. d. Souza . A raster approximation for processing of spatial joins . In Proc. VLDB , pages 558 -- 569 , 1998 . G. Zimbrao and J. M. d. Souza. A raster approximation for processing of spatial joins. In Proc. VLDB, pages 558--569, 1998."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3157794.3157803","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:38:12Z","timestamp":1672220292000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3157794.3157803"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11]]},"references-count":73,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["10.14778\/3157794.3157803"],"URL":"https:\/\/doi.org\/10.14778\/3157794.3157803","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,11]]}}}