{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:06:03Z","timestamp":1742918763893,"version":"3.40.3"},"publisher-location":"Cham","reference-count":12,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_38","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"483-494","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sampling in Space Restricted Settings"],"prefix":"10.1007","author":[{"given":"Anup","family":"Bhattacharya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Davis","family":"Issac","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ragesh","family":"Jaiswal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"38_CR1","unstructured":"Babcock, B., Datar, M., Motwani, R.: Sampling from a moving window over streaming data. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp. 633\u2013634 (2002)"},{"key":"38_CR2","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Larsen, K.G.: Succinct sampling from discrete distributions. In: Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 775\u2013782. ACM, New York (2013)","DOI":"10.1145\/2488608.2488707"},{"key":"38_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-642-31594-7_12","volume-title":"Automata, Languages, and Programming","author":"K Bringmann","year":"2012","unstructured":"Bringmann, K., Panagiotou, K.: Efficient sampling methods for discrete distributions. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 133\u2013144. Springer, Heidelberg (2012)"},{"issue":"5","key":"38_CR4","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.ipl.2005.11.003","volume":"97","author":"PS Efraimidis","year":"2006","unstructured":"Efraimidis, P.S., Spirakis, P.G.: Weighted random sampling with a reservoir. Information Processing Letters 97(5), 181\u2013185 (2006)","journal-title":"Information Processing Letters"},{"issue":"1","key":"38_CR5","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s00453-013-9833-9","volume":"70","author":"R Jaiswal","year":"2014","unstructured":"Jaiswal, R., Kumar, A., Sen, S.: A simple $${D}^2$$ -sampling based PTAS for $$k$$ -means and other clustering problems. Algorithmica 70(1), 22\u201346 (2014)","journal-title":"Algorithmica"},{"key":"38_CR6","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. 2. Addison-Wesley (1981)"},{"issue":"4","key":"38_CR7","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1080\/00031305.1979.10482697","volume":"33","author":"RA Kronmal","year":"1979","unstructured":"Kronmal, R.A., Peterson Jr, A.V.: On the alias method for generating random variables from a discrete distribution. The American Statistician 33(4), 214\u2013218 (1979)","journal-title":"The American Statistician"},{"issue":"4","key":"38_CR8","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/198429.198435","volume":"20","author":"K-H Li","year":"1994","unstructured":"Li, K.-H.: Reservoir-sampling algorithms of time complexity $$o( n (1 + \\log {N \/ n}))$$ . ACM Trans. Math. Software 20(4), 481\u2013493 (1994)","journal-title":"ACM Trans. Math. Software"},{"issue":"2","key":"38_CR9","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1016\/j.csda.2007.03.010","volume":"52","author":"B-H Park","year":"2007","unstructured":"Park, B.-H., Ostrouchov, G., Samatova, N.F.: Sampling streaming data with replacement. Computational Statistics and Data Analysis 52(2), 750\u2013762 (2007)","journal-title":"Computational Statistics and Data Analysis"},{"issue":"7","key":"38_CR10","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1145\/358105.893","volume":"27","author":"JS Vitter","year":"1984","unstructured":"Vitter, J.S.: Faster methods for random sampling. Comm. ACM 27(7), 703\u2013718 (1984)","journal-title":"Comm. ACM"},{"issue":"1","key":"38_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/3147.3165","volume":"11","author":"JS Vitter","year":"1985","unstructured":"Vitter, J.S.: Random sampling with a reservoir. ACM Trans. Math. Software 11(1), 37\u201357 (1985)","journal-title":"ACM Trans. Math. Software"},{"issue":"8","key":"38_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1049\/el:19740097","volume":"10","author":"AJ Walker","year":"1974","unstructured":"Walker, A.J.: New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letters 10(8), 127\u2013128 (1974)","journal-title":"Electronics Letters"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,9]],"date-time":"2024-06-09T17:32:06Z","timestamp":1717954326000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}