{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:44Z","timestamp":1775638484122,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p>\n            Tracking and approximating data matrices in streaming fashion is a fundamental challenge. The problem requires more care and attention when data comes from multiple distributed sites, each receiving a stream of data. This paper considers the problem of \"tracking approximations to a matrix\" in the distributed streaming model. In this model, there are\n            <jats:italic>m<\/jats:italic>\n            distributed sites each observing a distinct stream of data (where each element is a row of a distributed matrix) and has a communication channel with a coordinator, and the goal is to track an \u03b5-approximation to the norm of the matrix along any direction. To that end, we present novel algorithms to address the matrix approximation problem. Our algorithms maintain a smaller matrix\n            <jats:italic>B<\/jats:italic>\n            , as an approximation to a distributed streaming matrix\n            <jats:italic>A<\/jats:italic>\n            , such that for any unit vector\n            <jats:italic>x<\/jats:italic>\n            : |||\n            <jats:italic>Ax<\/jats:italic>\n            ||\n            <jats:sup>2<\/jats:sup>\n            \u2212 ||\n            <jats:italic>Bx<\/jats:italic>\n            ||\n            <jats:sup>2<\/jats:sup>\n            | \u2264 \u03b5||\n            <jats:italic>A<\/jats:italic>\n            ||\n            <jats:sup>2<\/jats:sup>\n            <jats:sub>\n              <jats:italic>F<\/jats:italic>\n            <\/jats:sub>\n            . Our algorithms work in streaming fashion and incur small communication, which is critical for distributed computation. Our best method is deterministic and uses only\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>m<\/jats:italic>\n            \/\u03b5) log(\u03b2\n            <jats:italic>N<\/jats:italic>\n            )) communication, where\n            <jats:italic>N<\/jats:italic>\n            is the size of stream (at the time of the query) and \u03b2 is an upperbound on the squared norm of any row of the matrix. In addition to proving all algorithmic properties theoretically, extensive experiments with real large datasets demonstrate the efficiency of these protocols.\n          <\/jats:p>","DOI":"10.14778\/2732951.2732954","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"809-820","source":"Crossref","is-referenced-by-count":6,"title":["Continuous matrix approximation on distributed data"],"prefix":"10.14778","volume":"7","author":[{"given":"Mina","family":"Ghashami","sequence":"first","affiliation":[{"name":"University of Utah"}]},{"given":"Jeff M.","family":"Phillips","sequence":"additional","affiliation":[{"name":"University of Utah"}]},{"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"University of Utah"}]}],"member":"320","published-online":{"date-parts":[[2014,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380858"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213562"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872764"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862923"},{"key":"e_1_2_1_6_1","volume-title":"ISMIR","author":"Bertin-Mahieux T.","year":"2011","unstructured":"T. Bertin-Mahieux , D. P. Ellis , B. Whitman , and P. Lamere . The million song dataset . In ISMIR , 2011 . T. Bertin-Mahieux, D. P. Ellis, B. Whitman, and P. Lamere. The million song dataset. In ISMIR, 2011."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2005.07.021"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536445"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2481528.2481530"},{"key":"e_1_2_1_11_1","volume-title":"VLDB","author":"Cormode G.","year":"2005","unstructured":"G. Cormode and M. Garofalakis . Sketching streams through the net: Distributed approximate query tracking . In VLDB , 2005 . G. Cormode and M. Garofalakis. Sketching streams through the net: Distributed approximate query tracking. In VLDB, 2005."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066161"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921667"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160163"},{"key":"e_1_2_1_16_1","volume-title":"SODA","author":"Drineas P.","year":"2003","unstructured":"P. Drineas and R. Kannan . Pass efficient algorithms for approximating large matrices . In SODA , 2003 . P. Drineas and R. Kannan. Pass efficient algorithms for approximating large matrices. In SODA, 2003."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314696"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73499-4_35"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634127"},{"key":"e_1_2_1_22_1","volume-title":"Continuous matrix approximation on distributed data. ArXiv:1404.7571","author":"Ghashami M.","year":"2014","unstructured":"M. Ghashami , J. M. Phillips , and F. Li . Continuous matrix approximation on distributed data. ArXiv:1404.7571 , 2014 . http:\/\/arxiv.org\/abs\/1404.7571. M. Ghashami, J. M. Phillips, and F. Li. Continuous matrix approximation on distributed data. ArXiv:1404.7571, 2014. http:\/\/arxiv.org\/abs\/1404.7571."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213596"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502529"},{"key":"e_1_2_1_25_1","volume-title":"LATIN.","author":"Hung R. Y.","year":"2008","unstructured":"R. Y. Hung and H.-F. Ting . Finding heavy hitters over the sliding window of a weighted data stream . In LATIN. 2008 . R. Y. Hung and H.-F. Ting. Finding heavy hitters over the sliding window of a weighted data stream. In LATIN. 2008."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142507"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015492"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005686.1005697"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487623"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0709640104"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.68"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_34_1","volume-title":"NIPS","author":"Mitliagkas I.","year":"2013","unstructured":"I. Mitliagkas , C. Caramanis , and P. Jain . Memory limited, streaming pca . In NIPS , 2013 . I. Mitliagkas, C. Caramanis, and P. Jain. Memory limited, streaming pca. In NIPS, 2013."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019604"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_2_1_37_1","volume-title":"VLDB","author":"Papadimitriou S.","year":"2005","unstructured":"S. Papadimitriou , J. Sun , and C. Faloutsos . Streaming pattern discovery in multiple time-series . In VLDB , 2005 . S. Papadimitriou, J. Sun, and C. Faloutsos. Streaming pattern discovery in multiple time-series. In VLDB, 2005."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028788.1028808"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168857"},{"key":"e_1_2_1_40_1","volume-title":"MIT","author":"Strumpen V.","year":"2003","unstructured":"V. Strumpen , H. Hoffmann , and A. Agarwal . A stream algorithm for the svd. Technical report , MIT , 2003 . V. Strumpen, H. Hoffmann, and A. Agarwal. A stream algorithm for the svd. Technical report, MIT, 2003."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132539"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2075029.2075065"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9584-4"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732951.2732954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:57:35Z","timestamp":1672225055000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732951.2732954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6]]},"references-count":44,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.14778\/2732951.2732954"],"URL":"https:\/\/doi.org\/10.14778\/2732951.2732954","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,6]]}}}