{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T04:21:00Z","timestamp":1754194860987,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,9,24]],"date-time":"2018-09-24T00:00:00Z","timestamp":1537747200000},"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. Algorithms"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>\n            Unaggregated data, in a streamed or distributed form, are prevalent and come from diverse sources such as interactions of users with web services and IP traffic. Data elements have\n            <jats:italic>keys<\/jats:italic>\n            (cookies, users, queries), and elements with different keys interleave. Analytics on such data typically utilizes statistics expressed as a sum over keys in a specified segment of a function\n            <jats:italic>f<\/jats:italic>\n            applied to the frequency (the total number of occurrences) of the key. In particular,\n            <jats:italic>Distinct<\/jats:italic>\n            is the number of active keys in the segment,\n            <jats:italic>Sum<\/jats:italic>\n            is the sum of their frequencies, and both are special cases of\n            <jats:italic>frequency cap<\/jats:italic>\n            statistics, which cap the frequency by a parameter\n            <jats:italic>T<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Random samples can be very effective for quick and efficient estimation of statistics at query time. Ideally, to estimate statistics for a given function\n            <jats:italic>f<\/jats:italic>\n            , our sample would include a key with frequency\n            <jats:italic>w<\/jats:italic>\n            with probability roughly proportional to\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>w<\/jats:italic>\n            ). The challenge is that while such \u201cgold-standard\u201d samples can be easily computed after aggregating the data (computing the set of key-frequency pairs), this aggregation is costly: It requires structure of size that is proportional to the number of active keys, which can be very large.\n          <\/jats:p>\n          <jats:p>\n            We present a sampling framework for unaggregated data that uses a single pass (for streams) or two passes (for distributed data) and structure size proportional to the desired sample size. Our design unifies classic solutions for Distinct and Sum. Specifically, our \u2113-capped samples provide nonnegative unbiased estimates of any monotone non-decreasing frequency statistics and statistical guarantees on quality that are close to gold standard for cap statistics with\n            <jats:italic>T<\/jats:italic>\n            =\u0398 (\u2113). Furthermore, our\n            <jats:italic>multi-objective<\/jats:italic>\n            samples provide these statistical guarantees on quality for all\n            <jats:italic>concave sub-linear<\/jats:italic>\n            statistics (the nonnegative span of cap functions) while incurring only a logarithmic overhead on sample size.\n          <\/jats:p>","DOI":"10.1145\/3234338","type":"journal-article","created":{"date-parts":[[2018,9,24]],"date-time":"2018-09-24T12:05:57Z","timestamp":1537790757000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Stream Sampling Framework and Application for Frequency Cap Statistics"],"prefix":"10.1145","volume":"14","author":[{"given":"Edith","family":"Cohen","sequence":"first","affiliation":[{"name":"Google AI, CA, USA and Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,9,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806729"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-842X.1972.tb00899.x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/69.3.653"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594546"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/HotWeb.2015.8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783279"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098020"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254798"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687677"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.04.009"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/10079817X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453884"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687701"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314696"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/505202.505212"},{"volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","key":"e_1_2_1_19_1","unstructured":"W. Feller. 1971. An Introduction to Probability Theory and Its Applications, Vol. 2. John Wiley 8 Sons, New York, NY."},{"key":"e_1_2_1_20_1","volume-title":"Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In Analysis of Algorithms. DMTCS.","author":"Flajolet P.","year":"2007","unstructured":"P. Flajolet, E. Fusy, O. Gandouet, and F. Meunier. 2007. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In Analysis of Algorithms. DMTCS."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164179"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276334"},{"volume-title":"Frequency capping: AdWords help. Retrieved","year":"2014","key":"e_1_2_1_24_1","unstructured":"Google. Frequency capping: AdWords help. Retrieved December 2014 from https:\/\/support.google.com\/adwords\/answer\/117579."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452456"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948235"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1952.10483446"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796606"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"W. Johnson and J. Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Math. 26.","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/270146"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"J. Misra and D. Gries. 1982. Finding repeated elements. Technical Report Cornell University.","DOI":"10.5555\/867576"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873693"},{"key":"e_1_2_1_34_1","first-page":"149","article-title":"Sequential poisson sampling","volume":"14","author":"Ohlsson E.","year":"1998","unstructured":"E. Ohlsson. 1998. Sequential poisson sampling. J. Off. Stat. 14, 2 (1998), 149--162.","journal-title":"J. Off. Stat."},{"key":"e_1_2_1_35_1","volume-title":"Retrieved","author":"Osborne M.","year":"2014","unstructured":"M. Osborne. Facebook Reach and Frequency Buying. Retrieved October 2014 from http:\/\/citizennet.com\/blog\/2014\/10\/01\/facebook-reach-and-frequency-buying\/."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177692620"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-3758(96)00185-1"},{"volume-title":"Sampling Algorithms","author":"Till\u00e9 Y.","key":"e_1_2_1_39_1","unstructured":"Y. Till\u00e9. 2006. Sampling Algorithms. Springer-Verlag, New York."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3234338","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3234338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:06Z","timestamp":1750268946000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3234338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,24]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3234338"],"URL":"https:\/\/doi.org\/10.1145\/3234338","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,9,24]]},"assertion":[{"value":"2017-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}