{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T03:41:06Z","timestamp":1768448466249,"version":"3.49.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,1,25]],"date-time":"2021-01-25T00:00:00Z","timestamp":1611532800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100004347","name":"AT and T","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1343976, 1443858, 1624074, 1760059"],"award-info":[{"award-number":["1343976, 1443858, 1624074, 1760059"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-15-1-0020"],"award-info":[{"award-number":["W911NF-15-1-0020"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2021,1,25]]},"abstract":"<jats:p>Signal reconstruction problem (SRP) is an important optimization problem where the objective is to identify a solution to an underdetermined system of linear equations that is closest to a given prior. It has a substantial number of applications in diverse areas, such as network traffic engineering, medical image reconstruction, acoustics, astronomy, and many more. Unfortunately, most of the common approaches for solving SRP do not scale to large problem sizes. We propose a novel and scalable algorithm for solving this critical problem. Specifically, we make four major contributions. First, we propose a dual formulation of the problem and develop the DIRECT algorithm that is significantly more efficient than the state of the art. Second, we show how adapting database techniques developed for scalable similarity joins provides a substantial speedup over DIRECT. Third, we describe several practical techniques that allow our algorithm to scale---on a single machine---to settings that are orders of magnitude larger than previously studied. Finally, we use the database techniques of materialization and reuse to extend our result to dynamic settings where the input to the SRP changes. Extensive experiments on real-world and synthetic data confirm the efficiency, effectiveness, and scalability of our proposal.<\/jats:p>","DOI":"10.1145\/3441689","type":"journal-article","created":{"date-parts":[[2021,1,25]],"date-time":"2021-01-25T09:54:12Z","timestamp":1611568452000},"page":"106-115","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Scalable signal reconstruction for a broad range of applications"],"prefix":"10.1145","volume":"64","author":[{"given":"Abolfazl","family":"Asudeh","sequence":"first","affiliation":[{"name":"University of Illinois at Chicago"}]},{"given":"Jees","family":"Augustine","sequence":"additional","affiliation":[{"name":"University of Texas at Arlington"}]},{"given":"Saravanan","family":"Thirumuruganathan","sequence":"additional","affiliation":[{"name":"QCRI, HBKU"}]},{"given":"Azade","family":"Nazi","sequence":"additional","affiliation":[{"name":"Google Brain"}]},{"given":"Nan","family":"Zhang","sequence":"additional","affiliation":[{"name":"American University"}]},{"given":"Gautam","family":"Das","sequence":"additional","affiliation":[{"name":"University of Texas at Arlington"}]},{"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs-Research"}]}],"member":"320","published-online":{"date-parts":[[2021,1,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00562-z"},{"key":"e_1_2_1_2_1","first-page":"11","article-title":"Leveraging similarity joins for signal reconstruction","volume":"10","author":"Asudeh A.","year":"2018","unstructured":"Asudeh, A., Nazi, A., Augustine, J., Thirumuruganathan, S., Zhang, N., Das, G., Srivastava, D. Leveraging similarity joins for signal reconstruction. PVLDB 10, 11 (2018), 1276--1288.","journal-title":"PVLDB"},{"key":"e_1_2_1_3_1","first-page":"52","article-title":"Distinct-value synopses for multiset operations","volume":"10","author":"Beyer K.","year":"2009","unstructured":"Beyer, K., Gemulla, R., Haas, P.J., Reinwald, B., Sismanis, Y. Distinct-value synopses for multiset operations. Commun. ACM 10, 52 (2009), 87--95.","journal-title":"Commun. ACM"},{"key":"e_1_2_1_4_1","volume-title":"SEQUENCES","author":"Broder A.Z.","year":"1997","unstructured":"Broder, A.Z. On the resemblance and containment of documents. In SEQUENCES (1997), IEEE, 21--29."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_6_1","first-page":"1","article-title":"Tighter estimation using bottom k sketches","volume":"1","author":"Cohen E.","year":"2008","unstructured":"Cohen, E., Kaplan, H. Tighter estimation using bottom k sketches. PVLDB 1, 1 (2008), 213--224.","journal-title":"PVLDB"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-8749-5"},{"issue":"10","key":"e_1_2_1_8_1","first-page":"10","article-title":"Big, deep, and smart data in scanning probe microscopy","author":"Kalinin S.V.","year":"2016","unstructured":"Kalinin, S.V., Strelcov, E., Belianinov, A., Somnath, S., Vasudevan, R.K., Lingerfelt, E.J., Archibald, R.K., Chen, C., Proksch, R., Laanait, N., et al. Big, deep, and smart data in scanning probe microscopy. ACS Nano 10, 10 (2016), 9068--9086.","journal-title":"ACS Na"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4236\/jcc.2017.55005"},{"key":"e_1_2_1_10_1","volume-title":"Dark matter maps reveal cosmic scaffolding. arXiv preprint astro-ph\/0701594","author":"Massey R.","year":"2007","unstructured":"Massey, R., Rhodes, J., Ellis, R., Scoville, N., Leauthaud, A., Finoguenov, A., Capak, P., Bacon, D., Aussel, H., Kneib, J.-P., et al. Dark matter maps reveal cosmic scaffolding. arXiv preprint astro-ph\/0701594 (2007)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100030401"},{"key":"e_1_2_1_12_1","first-page":"89871","article-title":"Technical report","volume":"978","author":"Trefethen L.N.","year":"1997","unstructured":"Trefethen, L.N., Bau III, , D. Technical report. Numerical Linear Algebra. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-361-9, 1997.","journal-title":"Numerical Linear Algebra. Philadelphia: Society for Industrial and Applied Mathematics. ISBN"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717570"},{"key":"e_1_2_1_14_1","first-page":"395","article-title":"Compressed sensing imaging techniques for radio interferometry","volume":"3","author":"Wiaux Y.","year":"2009","unstructured":"Wiaux, Y., Jacques, L., Puy, G., Scaife, A.M., Vandergheynst, P. Compressed sensing imaging techniques for radio interferometry. Monthly Notices of the Royal Astronomical Society 3, 395 (2009), 1733--1742.","journal-title":"Monthly Notices of the Royal Astronomical Society"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/781027.781053"},{"key":"e_1_2_1_16_1","first-page":"12","article-title":"A compressive sensing approach to urban traffic estimation with prob vehicles","volume":"11","author":"Zhu Y.","year":"2012","unstructured":"Zhu, Y., Li, Z., Zhu, H., Li, M., Zhang, Q. A compressive sensing approach to urban traffic estimation with prob vehicles. IEEE Trans. Mobile Comput. 11, 12 (2012), 2289--2302.","journal-title":"IEEE Trans. Mobile Comput."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441689","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3441689","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3441689","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T16:55:57Z","timestamp":1768409757000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441689"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,25]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1,25]]}},"alternative-id":["10.1145\/3441689"],"URL":"https:\/\/doi.org\/10.1145\/3441689","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,25]]},"assertion":[{"value":"2021-01-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}