{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:03Z","timestamp":1750306803282,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>\n            Large-scale map visualization systems play an increasingly important role in presenting geographic datasets to end-users. Since these datasets can be extremely large, a map rendering system often needs to select a small fraction of the data to visualize them in a limited space. This article addresses the fundamental challenge of\n            <jats:italic>thinning<\/jats:italic>\n            : determining appropriate samples of data to be shown on specific geographical regions and zoom levels. Other than the sheer scale of the data, the thinning problem is challenging because of a number of other reasons: (1) data can consist of complex geographical shapes, (2) rendering of data needs to satisfy certain constraints, such as data being preserved across zoom levels and adjacent regions, and (3) after satisfying the constraints, an\n            <jats:italic>optimal<\/jats:italic>\n            solution needs to be chosen based on\n            <jats:italic>objectives<\/jats:italic>\n            such as\n            <jats:italic>maximality<\/jats:italic>\n            ,\n            <jats:italic>fairness<\/jats:italic>\n            , and\n            <jats:italic>importance<\/jats:italic>\n            of data.\n          <\/jats:p>\n          <jats:p>\n            This article formally defines and presents a complete solution to the thinning problem. First, we express the problem as an integer programming formulation that efficiently solves thinning for desired objectives. Second, we present more efficient solutions for maximality, based on DFS traversal of a spatial tree. Third, we consider the common special case of point datasets, and present an even more efficient randomized algorithm. Fourth, we show that\n            <jats:italic>contiguous<\/jats:italic>\n            regions are tractable for a general version of maximality for which arbitrary regions are intractable. Fifth, we examine the structure of our integer programming formulation and show that for point datasets, our program is integral. Finally, we have implemented all techniques from this article in Google Maps [Google 2005] visualizations of fusion tables [Gonzalez et al. 2010], and we describe a set of experiments that demonstrate the trade-offs among the algorithms.\n          <\/jats:p>","DOI":"10.1145\/2539032.2539034","type":"journal-article","created":{"date-parts":[[2013,12,10]],"date-time":"2013-12-10T13:28:12Z","timestamp":1386682092000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Consistent thinning of large geographical data for map visualization"],"prefix":"10.1145","volume":"38","author":[{"given":"Anish Das","family":"Sarma","sequence":"first","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongrae","family":"Lee","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hector","family":"Gonzalez","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayant","family":"Madhavan","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alon","family":"Halevy","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,12,4]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"388","article-title":"The relaxation method for linear inequalities","volume":"5","author":"Agmon S.","year":"1954","journal-title":"Canadian J. Math."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.136"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.03.006"},{"volume-title":"Proceedings of the IEEE Symposium on Visual Analytics Science and Technology (VAST'08)","author":"Chan S.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","unstructured":"Cochran W. G. 1977. Sampling Techniques 3rd Ed. John Wiley.  Cochran W. G. 1977. Sampling Techniques 3 rd Ed. John Wiley."},{"volume-title":"Proceedings of the Conference on Innovative Data Systems Research. 148--151","author":"Cohen S.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213859"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1556262.1556289"},{"key":"e_1_2_1_9_1","unstructured":"Esri. 2012. Arcgis. http:\/\/www.esri.com\/software\/arcgis\/index.html.  Esri. 2012. Arcgis. http:\/\/www.esri.com\/software\/arcgis\/index.html."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2207676.2208294"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-8493(94)90008-6"},{"key":"e_1_2_1_12_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman and Co.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman and Co."},{"key":"e_1_2_1_13_1","unstructured":"Geoiq. 2012. Geocommons. http:\/\/geocommons.com\/.  Geoiq. 2012. Geocommons. http:\/\/geocommons.com\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807286"},{"key":"e_1_2_1_15_1","unstructured":"GOOGLE. 2005. Google maps. http:\/\/maps.google.com.  GOOGLE. 2005. Google maps. http:\/\/maps.google.com."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276324"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"volume-title":"Data Mining: Concepts and Techniques. Morgan Kaufmann.","year":"2000","author":"Han J.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","unstructured":"Han J. Kamber M. and Tung A. K. H. 2001. Spatial clustering methods in data mining: A survey. In Geographic Data Mining and Knowledge Discovery Taylor and Francis 1--29.  Han J. Kamber M. and Tung A. K. H. 2001. Spatial clustering methods in data mining: A survey. In Geographic Data Mining and Knowledge Discovery Taylor and Francis 1--29."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01199431"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276326"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1641\/0006-3568(2001)051[0933:TEOTWA]2.0.CO;2"},{"key":"e_1_2_1_24_1","unstructured":"Oracle. 2007. Oracle spatial. http:\/\/www.oracle.com\/us\/products\/database\/options\/spatial\/index.html.  Oracle. 2007. Oracle spatial. http:\/\/www.oracle.com\/us\/products\/database\/options\/spatial\/index.html."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253342"},{"volume-title":"Proceedings of the International Cartographic Conference. 288--298","author":"Petzold I.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1179\/caj.1982.19.2.122"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2009.110"},{"volume-title":"Proceedings of the International Symposium on Large Spatial Database. 152--169","author":"Puppo E.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Sagan H. 1994. Space-Filling Curves. Springer.  Sagan H. 1994. Space-Filling Curves. Springer.","DOI":"10.1007\/978-1-4612-0871-6"},{"key":"e_1_2_1_31_1","unstructured":"Samet H. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley Longman Publishing Co.   Samet H. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley Longman Publishing Co."},{"key":"e_1_2_1_32_1","unstructured":"Schrijver A. 1986. Theory of Linear and Integer Programming. John Wiley.   Schrijver A. 1986. Theory of Linear and Integer Programming. John Wiley."},{"key":"e_1_2_1_33_1","first-page":"56","article-title":"Cartographic generalization in a digital environment: When and how to generalize","volume":"9","author":"Shea K.","year":"1989","journal-title":"AutoCarto"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2003.1196005"},{"key":"e_1_2_1_35_1","unstructured":"Thomas J. and Cook K. A. Eds. 2005. Illuminating the Path: The Research and Development Agenda for Visual Analytics. IEEE Computer Society Press Los Alamitos CA.  Thomas J. and Cook K. A. Eds. 2005. Illuminating the Path: The Research and Development Agenda for Visual Analytics. IEEE Computer Society Press Los Alamitos CA."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9671.1996.tb00044.x"},{"key":"e_1_2_1_37_1","unstructured":"Vizzuality. 2012. Cartodb. http:\/\/cartodb.com.  Vizzuality. 2012. Cartodb. http:\/\/cartodb.com."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810310001596085"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/948496.948505"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2539032.2539034","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2539032.2539034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:50Z","timestamp":1750232090000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2539032.2539034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2539032.2539034"],"URL":"https:\/\/doi.org\/10.1145\/2539032.2539034","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2012-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}