{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:06:44Z","timestamp":1768108004604,"version":"3.49.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>\n            Visualizations are frequently used as a means to understand trends and gather insights from datasets, but often take a long time to generate. In this paper, we focus on the problem of\n            <jats:italic>rapidly generating approximate visualizations while preserving crucial visual properties of interest to analysts.<\/jats:italic>\n            Our primary focus will be on sampling algorithms that preserve the visual property of\n            <jats:italic>ordering<\/jats:italic>\n            ; our techniques will also apply to some other visual properties. For instance, our algorithms can be used to generate an approximate visualization of a bar chart very rapidly, where the comparisons between any two bars are correct. We formally show that our sampling algorithms are generally applicable and provably optimal in theory, in that they do not take more samples than necessary to generate the visualizations with ordering guarantees. They also work well in practice, correctly ordering output groups while taking orders of magnitude fewer samples and much less time than conventional sampling schemes.\n          <\/jats:p>","DOI":"10.14778\/2735479.2735485","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"521-532","source":"Crossref","is-referenced-by-count":71,"title":["Rapid sampling for visualizations with ordering guarantees"],"prefix":"10.14778","volume":"8","author":[{"given":"Albert","family":"Kim","sequence":"first","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Blais","sequence":"additional","affiliation":[{"name":"MIT and University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aditya","family":"Parameswaran","sequence":"additional","affiliation":[{"name":"MIT and Illinois (UIUC)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Indyk","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sam","family":"Madden","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[{"name":"MIT and Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335450"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304581"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872822"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCECE.2013.6567840"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00171-T"},{"key":"e_1_2_1_8_1","volume-title":"Duxbury","author":"Casella G.","year":"2001","unstructured":"G. Casella and R. Berger . Statistical Inference . Duxbury , June 2001 . G. Casella and R. Berger. Statistical Inference. Duxbury, June 2001."},{"key":"e_1_2_1_9_1","first-page":"111","volume-title":"VLDB","author":"Chakrabarti K.","year":"2000","unstructured":"K. Chakrabarti , M. N. Garofalakis , R. Rastogi , and K. Shim . Approximate query processing using wavelets . In VLDB , pages 111 -- 122 , 2000 . K. Chakrabarti, M. N. Garofalakis, R. Rastogi, and K. Shim. Approximate query processing using wavelets. In VLDB, pages 111--122, 2000."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656545"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242526"},{"key":"e_1_2_1_12_1","volume-title":"Sampling techniques","author":"Cochran W. G.","year":"1977","unstructured":"W. G. Cochran . Sampling techniques . John Wiley & Sons , 1977 . W. G. Cochran. Sampling techniques. John Wiley & Sons, 1977."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/789081.789233"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2379776.2379788"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70561"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/LDAV.2011.6092320"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2207676.2208294"},{"key":"e_1_2_1_18_1","volume-title":"http:\/\/stat-computing.org\/dataexpo\/2009\/the-data.html","year":"2009","unstructured":"Flight Records. http:\/\/stat-computing.org\/dataexpo\/2009\/the-data.html . 2009 . Flight Records. http:\/\/stat-computing.org\/dataexpo\/2009\/the-data.html. 2009."},{"key":"e_1_2_1_19_1","first-page":"725","volume-title":"VLDB","author":"Garofalakis M. N.","unstructured":"M. N. Garofalakis and P. B. Gibbons . Approximate query processing: Taming the terabytes . VLDB , pages 725 --, 2001. M. N. Garofalakis and P. B. Gibbons. Approximate query processing: Taming the terabytes. VLDB, pages 725--, 2001."},{"key":"e_1_2_1_20_1","first-page":"541","volume-title":"VLDB","author":"Gibbons P. B.","year":"2001","unstructured":"P. B. Gibbons . Distinct sampling for highly-accurate answers to distinct values queries and event reports . In VLDB , pages 541 -- 550 , 2001 . P. B. Gibbons. Distinct sampling for highly-accurate answers to distinct values queries and event reports. In VLDB, pages 541--550, 2001."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807286"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.ivs.9500053"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0041"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213902"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_26_1","volume-title":"Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301): 13--30","author":"Hoeffding W.","year":"1963","unstructured":"W. Hoeffding . Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301): 13--30 , 1963 . W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301): 13--30, 1963."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/308386.308455"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66933"},{"key":"e_1_2_1_29_1","first-page":"174","volume-title":"VLDB '99","author":"Ioannidis Y. E.","year":"1999","unstructured":"Y. E. Ioannidis and V. Poosala . Histogram-based approximation of set-valued query-answers . VLDB '99 , pages 174 -- 185 , 1999 . Y. E. Ioannidis and V. Poosala. Histogram-based approximation of set-valued query-answers. VLDB '99, pages 174--185, 1999."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412335"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497428"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254556.2254659"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213931"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/354756.354819"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90224-H"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1561\/1500000016"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12129"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253335"},{"key":"e_1_2_1_41_1","first-page":"50","volume-title":"On a test of whether one of two random variables is stochastically larger than the other. The annals of mathematical statistics","author":"Mann H. B.","year":"1947","unstructured":"H. B. Mann and D. R. Whitney . On a test of whether one of two random variables is stochastically larger than the other. The annals of mathematical statistics , pages 50 -- 60 , 1947 . H. B. Mann and D. R. Whitney. On a test of whether one of two random variables is stochastically larger than the other. The annals of mathematical statistics, pages 50--60, 1947."},{"key":"e_1_2_1_42_1","volume-title":"VLDB","author":"Parameswaran A.","year":"2014","unstructured":"A. Parameswaran , N. Polyzotis , and H. Garcia-Molina . SeeDB: Visualizing Database Queries Efficiently . In VLDB , 2014 . A. Parameswaran, N. Polyzotis, and H. Garcia-Molina. SeeDB: Visualizing Database Queries Efficiently. In VLDB, 2014."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.ivs.9500091"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176342611"},{"key":"e_1_2_1_45_1","volume-title":"spotfire.com (retrieved","author":"Spotfire Inc.","year":"2014","unstructured":"Spotfire Inc. spotfire.com (retrieved March 24, 2014 ). Spotfire Inc. spotfire.com (retrieved March 24, 2014)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400214.1400234"},{"key":"e_1_2_1_47_1","volume-title":"The visual display of quantitative information","author":"Tufte E. R.","year":"1983","unstructured":"E. R. Tufte and P. Graves-Morris . The visual display of quantitative information , volume 2 . Graphics press Cheshire , CT , 1983 . E. R. Tufte and P. Graves-Morris. The visual display of quantitative information, volume 2. Graphics press Cheshire, CT, 1983."},{"key":"e_1_2_1_48_1","volume-title":"All of Statistics","author":"Wasserman L.","year":"2003","unstructured":"L. Wasserman . All of Statistics . Springer , 2003 . L. Wasserman. All of Statistics. Springer, 2003."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1670243.1670245"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132864"},{"key":"e_1_2_1_51_1","first-page":"19","volume-title":"VISSYM '03","author":"Yang J.","year":"2003","unstructured":"J. Yang Visual hierarchical dimension reduction for exploration of high dimensional datasets . VISSYM '03 , pages 19 -- 28 , 2003 . J. Yang et al. Visual hierarchical dimension reduction for exploration of high dimensional datasets. VISSYM '03, pages 19--28, 2003."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2735479.2735485","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:21:14Z","timestamp":1672226474000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2735479.2735485"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":49,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.14778\/2735479.2735485"],"URL":"https:\/\/doi.org\/10.14778\/2735479.2735485","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}