{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T00:08:57Z","timestamp":1719274137033},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,6,14]],"date-time":"2017-06-14T00:00:00Z","timestamp":1497398400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s00453-017-0335-z","type":"journal-article","created":{"date-parts":[[2017,6,14]],"date-time":"2017-06-14T18:21:33Z","timestamp":1497464493000},"page":"1439-1458","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Sampling in Space Restricted Settings"],"prefix":"10.1007","volume":"80","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":[[2017,6,14]]},"reference":[{"key":"335_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 \u201902, pp. 633\u2013634, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics (2002)"},{"key":"335_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 \u201913, pp. 775\u2013782. NY, USA, ACM, New York (2013)","DOI":"10.1145\/2488608.2488707"},{"key":"335_CR3","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Panagiotou, K.: Efficient sampling methods for discrete distributions. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) Automata. Languages, and Programming, volume 7391 of Lecture Notes in Computer Science, pp. 133\u2013144. Springer, Berlin Heidelberg (2012)","DOI":"10.1007\/978-3-642-31594-7_12"},{"issue":"5","key":"335_CR4","doi-asserted-by":"crossref","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. Inf. Process. Lett. 97(5), 181\u2013185 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"335_CR5","doi-asserted-by":"crossref","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$$ D 2 -sampling based PTAS for $$k$$ k -means and other clustering problems. Algorithmica 70(1), 22\u201346 (2014)","journal-title":"Algorithmica"},{"key":"335_CR6","volume-title":"The Art of Computer Programming","author":"DE Knuth","year":"1981","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. 2. Addison-Wesley, Boston (1981)"},{"issue":"4","key":"335_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. Am. Stat. 33(4), 214\u2013218 (1979)","journal-title":"Am. Stat."},{"issue":"4","key":"335_CR8","doi-asserted-by":"crossref","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}))$$ o ( n ( 1 + log N \/ n ) ) . ACM Trans. Math. Softw. 20(4), 481\u2013493 (1994)","journal-title":"ACM Trans. Math. Softw."},{"issue":"2","key":"335_CR9","doi-asserted-by":"crossref","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. Comput. Stat. Data Anal. 52(2), 750\u2013762 (2007)","journal-title":"Comput. Stat. Data Anal."},{"issue":"7","key":"335_CR10","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1145\/358105.893","volume":"27","author":"JS Vitter","year":"1984","unstructured":"Vitter, J.S.: Faster methods for random sampling. Commun. ACM 27(7), 703\u2013718 (1984)","journal-title":"Commun. ACM"},{"issue":"1","key":"335_CR11","doi-asserted-by":"crossref","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. Softw. 11(1), 37\u201357 (1985)","journal-title":"ACM Trans. Math. Softw."},{"issue":"8","key":"335_CR12","doi-asserted-by":"crossref","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. Electron. Lett. 10(8), 127\u2013128 (1974)","journal-title":"Electron. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0335-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0335-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0335-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T19:42:16Z","timestamp":1719258136000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0335-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,14]]},"references-count":12,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["335"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0335-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,14]]}}}