{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:53:44Z","timestamp":1756000424311,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384331","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1251-1264","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Non-adaptive adaptive sampling on turnstile streams"],"prefix":"10.1145","author":[{"given":"Sepideh","family":"Mahabadi","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilya","family":"Razenshteyn","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samson","family":"Zhou","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Geometric approximation via coresets. Combinatorial and computational geometry, 52","author":"Agarwal Pankaj K","year":"2005","unstructured":"Pankaj K Agarwal , Sariel Har-Peled , and Kasturi R Varadarajan . 2005. Geometric approximation via coresets. Combinatorial and computational geometry, 52 ( 2005 ), 1\u201330. Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan. 2005. Geometric approximation via coresets. Combinatorial and computational geometry, 52 (2005), 1\u201330."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9846-4"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"volume-title":"50th Annual IEEE Symposium on Foundations of Computer Science, FOCS. 324\u2013330","author":"Andoni Alexandr","key":"e_1_3_2_1_4_1","unstructured":"Alexandr Andoni , Khanh Do Ba , Piotr Indyk , and David P. Woodruff . 2009. Efficient Sketches for Earth-Mover Distance, with Applications . In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS. 324\u2013330 . Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P. Woodruff. 2009. Efficient Sketches for Earth-Mover Distance, with Applications. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS. 324\u2013330."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.82"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509947"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.105"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.10.002"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699007"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.018"},{"volume-title":"Input Sparsity and Hardness for Robust Subspace Approximation. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS. 310\u2013329","author":"Kenneth","key":"e_1_3_2_1_13_1","unstructured":"Kenneth L. Clarkson and David P. Woodruff. 2015 . Input Sparsity and Hardness for Robust Subspace Approximation. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS. 310\u2013329 . Kenneth L. Clarkson and David P. Woodruff. 2015. Input Sparsity and Hardness for Robust Subspace Approximation. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS. 310\u2013329."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039801"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a012"},{"volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 641\u2013650","author":"Deshpande Amit","key":"e_1_3_2_1_16_1","unstructured":"Amit Deshpande and Kasturi R. Varadarajan . 2007. Sampling-based dimension reduction for subspace approximation . In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 641\u2013650 . Amit Deshpande and Kasturi R. Varadarajan. 2007. Sampling-based dimension reduction for subspace approximation. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 641\u2013650."},{"key":"e_1_3_2_1_17_1","volume-title":"9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX and 10th International Workshop on Randomization and Computation, RANDOM, Proceedings. 292\u2013303","author":"Deshpande Amit","year":"2006","unstructured":"Amit Deshpande and Santosh Vempala . 2006 . Adaptive Sampling and Fast Low-Rank Matrix Approximation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX and 10th International Workshop on Randomization and Computation, RANDOM, Proceedings. 292\u2013303 . Amit Deshpande and Santosh Vempala. 2006. Adaptive Sampling and Fast Low-Rank Matrix Approximation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX and 10th International Workshop on Randomization and Computation, RANDOM, Proceedings. 292\u2013303."},{"key":"e_1_3_2_1_18_1","volume-title":"Woodruff","author":"Feldman Dan","year":"2010","unstructured":"Dan Feldman , Morteza Monemizadeh , Christian Sohler , and David P . Woodruff . 2010 . Coresets and Sketches for High Dimensional Subspace Approximation Problems. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 630\u2013649. Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P. Woodruff. 2010. Coresets and Sketches for High Dimensional Subspace Approximation Problems. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 630\u2013649."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.95"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007400"},{"key":"e_1_3_2_1_21_1","volume-title":"Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. In International Conference on Machine Learning. 4254\u20134263","author":"Indyk Piotr","year":"2019","unstructured":"Piotr Indyk , Sepideh Mahabadi , Shayan Oveis Gharan , and Alireza Rezaei . 2019 . Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. In International Conference on Machine Learning. 4254\u20134263 . Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, and Alireza Rezaei. 2019. Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. In International Conference on Machine Learning. 4254\u20134263."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381192"},{"volume-title":"Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS. 100\u2013108","author":"Indyk Piotr","key":"e_1_3_2_1_23_1","unstructured":"Piotr Indyk , Sepideh Mahabadi , Mohammad Mahdian , and Vahab S. Mirrokni . 2014. Composable core-sets for diversity and coverage maximization . In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS. 100\u2013108 . Piotr Indyk, Sepideh Mahabadi, Mohammad Mahdian, and Vahab S. Mirrokni. 2014. Composable core-sets for diversity and coverage maximization. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS. 100\u2013108."},{"volume-title":"59th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 544\u2013555","author":"Jayaram Rajesh","key":"e_1_3_2_1_24_1","unstructured":"Rajesh Jayaram and David P. Woodruff . 2018. Perfect Lp Sampling in a Data Stream . In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 544\u2013555 . Rajesh Jayaram and David P. Woodruff. 2018. Perfect Lp Sampling in a Data Stream. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 544\u2013555."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG.","author":"Kerber Michael","year":"2015","unstructured":"Michael Kerber and Sharath Raghvendra . 2015 . Approximation and Streaming Algorithms for Projective Clustering via Random Projections . In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG. Michael Kerber and Sharath Raghvendra. 2015. Approximation and Streaming Algorithms for Projective Clustering via Random Projections. In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG."},{"volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS. 10706\u201310716","author":"Levin Roie","key":"e_1_3_2_1_28_1","unstructured":"Roie Levin , Anish Prasad Sevekari , and David P. Woodruff . 2018. Robust Subspace Approximation in a Stream . In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS. 10706\u201310716 . Roie Levin, Anish Prasad Sevekari, and David P. Woodruff. 2018. Robust Subspace Approximation in a Stream. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS. 10706\u201310716."},{"key":"e_1_3_2_1_29_1","volume-title":"Non-Adaptive Adaptive Sampling on Turnstile Streams. CoRR, abs\/2004.10969","author":"Mahabadi Sepideh","year":"2020","unstructured":"Sepideh Mahabadi , Ilya Razenshteyn , David P. Woodruff , and Samson Zhou . 2020. Non-Adaptive Adaptive Sampling on Turnstile Streams. CoRR, abs\/2004.10969 ( 2020 ). Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, and Samson Zhou. 2020. Non-Adaptive Adaptive Sampling on Turnstile Streams. CoRR, abs\/2004.10969 (2020)."},{"key":"e_1_3_2_1_30_1","volume-title":"Woodruff","author":"Monemizadeh Morteza","year":"2010","unstructured":"Morteza Monemizadeh and David P . Woodruff . 2010 . 1-Pass Relative-Error L_ p-Sampling with Applications. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 1143\u20131160. Morteza Monemizadeh and David P. Woodruff. 2010. 1-Pass Relative-Error L_ p-Sampling with Applications. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 1143\u20131160."},{"volume-title":"Encyclopedia of Machine Learning and Data Mining. 1018\u20131025.","author":"Procopiuc Cecilia M.","key":"e_1_3_2_1_31_1","unstructured":"Cecilia M. Procopiuc . 2017. Projective Clustering . In Encyclopedia of Machine Learning and Data Mining. 1018\u20131025. Cecilia M. Procopiuc. 2017. Projective Clustering. In Encyclopedia of Machine Learning and Data Mining. 1018\u20131025."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116263.3116427"},{"volume-title":"Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC. 755\u2013764","author":"Sohler Christian","key":"e_1_3_2_1_34_1","unstructured":"Christian Sohler and David P. Woodruff . 2011. Subspace embeddings for the L_ 1-norm with applications . In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC. 755\u2013764 . Christian Sohler and David P. Woodruff. 2011. Subspace embeddings for the L_ 1-norm with applications. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC. 755\u2013764."},{"volume-title":"59th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 802\u2013813","author":"Sohler Christian","key":"e_1_3_2_1_35_1","unstructured":"Christian Sohler and David P. Woodruff . 2018. Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension . In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 802\u2013813 . Christian Sohler and David P. Woodruff. 2018. Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 802\u2013813."},{"volume-title":"Proceedings of the 44th Symposium on Theory of Computing Conference, STOC. 941\u2013960","author":"David","key":"e_1_3_2_1_36_1","unstructured":"David P. Woodruff and Qin Zhang. 2012. Tight bounds for distributed functional monitoring . In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC. 941\u2013960 . David P. Woodruff and Qin Zhang. 2012. Tight bounds for distributed functional monitoring. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC. 941\u2013960."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chicago IL USA","acronym":"STOC '20"},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384331","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:57Z","timestamp":1750199577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":36,"alternative-id":["10.1145\/3357713.3384331","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384331","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}