{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T18:16:23Z","timestamp":1790878583530,"version":"4.1.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"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":[[2006,3]]},"abstract":"<jats:p>Histograms and related synopsis structures are popular techniques for approximating data distributions. These have been successful in query optimization and a variety of applications, including approximate querying, similarity searching, and data mining, to name a few. Histograms were a few of the earliest synopsis structures proposed and continue to be used widely. The histogram construction problem is to construct the best histogram restricted to a space bound that reflects the data distribution most accurately under a given error measure.The histograms are used as quick and easy estimates. Thus, a slight loss of accuracy, compared to the optimal histogram under the given error measure, can be offset by fast histogram construction algorithms. A natural question arises in this context: Can we find a fast near optimal approximation algorithm for the histogram construction problem? In this article, we give the first linear time (1+\u03f5)-factor approximation algorithms (for any \u03f5 &gt; 0) for a large number of histogram construction problems including the use of piecewise small degree polynomials to approximate data, workloads, etc. Several of our algorithms extend to data streams.Using synthetic and real-life data sets, we demonstrate that in many scenarios the approximate histograms are almost identical to optimal histograms in quality and are significantly faster to construct.<\/jats:p>","DOI":"10.1145\/1132863.1132873","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"396-438","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":89,"title":["Approximation and streaming algorithms for histogram construction problems"],"prefix":"10.1145","volume":"31","author":[{"given":"Sudipto","family":"Guha","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nick","family":"Koudas","sequence":"additional","affiliation":[{"name":"University of Toronto, Ont, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kyuseok","family":"Shim","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304581"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/320134.320172"},{"key":"e_1_2_1_4_1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","unstructured":"Borodin , A. and El-Yaniv , R. 1998. Online Computation and Competitive Analysis . Cambridge University Press , Cambridge, MA . Borodin, A. and El-Yaniv, R. 1998. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, MA."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Datar M.","year":"2002","unstructured":"Datar , M. , Gionis , A. , Indyk , P. , and Motwani , R . 2002. Maintaining stream statistics over sliding windows . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2002 ). ACM, New York, 635--644. Datar, M., Gionis, A., Indyk, P., and Motwani, R. 2002. Maintaining stream statistics over sliding windows. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2002). ACM, New York, 635--644."},{"key":"e_1_2_1_6_1","unstructured":"Donjerkovic D. Ioannidis Y. E. and Ramakrishnan R. 1999. Dynamic histograms: Capturing evolving data sets. CS-TR 99-1396 University of Wisconsin Madison WI. Mar.  Donjerkovic D. Ioannidis Y. E. and Ramakrishnan R. 1999. Dynamic histograms: Capturing evolving data sets. CS-TR 99-1396 University of Wisconsin Madison WI. Mar."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361701"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564746"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/974750.974753"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Gibbons P.","year":"1999","unstructured":"Gibbons , P. and Matias , Y . 1999. Synopsis data structures for massive data sets . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 1999 ). ACM, New York, 909--910. Gibbons, P. and Matias, Y. 1999. Synopsis data structures for massive data sets. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 1999). ACM, New York, 909--910."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509966"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375598"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the VLDB Conference. 409--420","author":"Guha S.","year":"2005","unstructured":"Guha , S. 2005 . Space efficiency in synopsis construction problems . In Proceedings of the VLDB Conference. 409--420 . Guha, S. 2005. Space efficiency in synopsis construction problems. In Proceedings of the VLDB Conference. 409--420."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109633"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the ICALP. 681--692","author":"Guha S.","unstructured":"Guha , S. , Indyk , P. , Muthukrishnan , S. , and Strauss , M . 2002a. Histogramming data streams with fast per-item processing . In Proceedings of the ICALP. 681--692 . Guha, S., Indyk, P., Muthukrishnan, S., and Strauss, M. 2002a. Histogramming data streams with fast per-item processing. In Proceedings of the ICALP. 681--692."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543637"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the IEEE 18th International Conference on Data Engineering (ICDE'02)","author":"Guha S.","unstructured":"Guha , S. and Koudas , N . 2002. Approximating a data stream for querying and estimation: Algorithms and performance evaluation . In Proceedings of the IEEE 18th International Conference on Data Engineering (ICDE'02) . IEEE Computer. Society Press, Los Alamitos, CA, 567--576. Guha, S. and Koudas, N. 2002. Approximating a data stream for querying and estimation: Algorithms and performance evaluation. In Proceedings of the IEEE 18th International Conference on Data Engineering (ICDE'02). IEEE Computer. Society Press, Los Alamitos, CA, 567--576."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380841"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the VLDB Conference, 300--311","author":"Guha S.","unstructured":"Guha , S. , Shim , K. , and Woo , J . 2004. REHIST: Relative error histogram construction algorithms . In Proceedings of the VLDB Conference, 300--311 . Guha, S., Shim, K., and Woo, J. 2004. REHIST: Relative error histogram construction algorithms. In Proceedings of the VLDB Conference, 300--311."},{"key":"e_1_2_1_21_1","unstructured":"Hochbaum D. 1996. Approximation Algorithms for NP Hard Problems. Brooks\/Cole Pubishing Company.   Hochbaum D. 1996. Approximation Algorithms for NP Hard Problems. Brooks\/Cole Pubishing Company."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796606"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223841"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the VLDB Conference, 256--267","author":"Ioannidis Y. E.","year":"1993","unstructured":"Ioannidis , Y. E. 1993 . Universality of serial histograms . In Proceedings of the VLDB Conference, 256--267 . Ioannidis, Y. E. 1993. Universality of serial histograms. In Proceedings of the VLDB Conference, 256--267."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315455"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the VLDB Conference, 275--286","author":"Jagadish H. V.","unstructured":"Jagadish , H. V. , Koudas , N. , Muthukrishnan , S. , Poosala , V. , Sevcik , K. C. , and Suel , T . 1998. Optimal histograms with quality guarantees . In Proceedings of the VLDB Conference, 275--286 . Jagadish, H. V., Koudas, N., Muthukrishnan, S., Poosala, V., Sevcik, K. C., and Suel, T. 1998. Optimal histograms with quality guarantees. In Proceedings of the VLDB Conference, 275--286."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/568518.568520"},{"key":"e_1_2_1_28_1","volume-title":"The optimization of queries in relational databases","author":"Kooi R.","unstructured":"Kooi , R. 1980. The optimization of queries in relational databases . Case Western Reserve University . Kooi, R. 1980. The optimization of queries in relational databases. Case Western Reserve University."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335223"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276342"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276344"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50205"},{"key":"e_1_2_1_33_1","unstructured":"Muthukrishnan S. and Strauss M. 2004. Approximate histogram and wavelet summaries of streaming data. DIMACS TR 52.  Muthukrishnan S. and Strauss M. 2004. Approximate histogram and wavelet summaries of streaming data. DIMACS TR 52."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233342"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564741"},{"key":"e_1_2_1_37_1","volume-title":"Approximation Algorithms","author":"Vazirani V.","unstructured":"Vazirani , V. 2001. Approximation Algorithms . Springer-Verlag , New York . Vazirani, V. 2001. Approximation Algorithms. Springer-Verlag, New York."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132873","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132863.1132873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:13Z","timestamp":1750259173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132873"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1132863.1132873"],"URL":"https:\/\/doi.org\/10.1145\/1132863.1132873","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}