{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:36:40Z","timestamp":1758274600323,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T00:00:00Z","timestamp":1572912000000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2019,11,5]]},"abstract":"<jats:p>The signal reconstruction problem (SRP) is an important optimization problem where the objective is to identify a solution to an under-determined system of linear equations AX = b that is closest to a given prior. It has a substantial number of applications in diverse areas including network traffic engineering, medical image reconstruction, acoustics, astronomy and many more. Most common approaches for solving SRP do not scale to large problem sizes. In this paper, we propose a dual formulation of this problem and show how adapting database techniques developed for scalable similarity joins provides a significant speedup when the A matrix is sparse and binary. Extensive experiments on real-world and synthetic data show that our approach produces a significant speedup of up to 20x over competing approaches.<\/jats:p>","DOI":"10.1145\/3371316.3371327","type":"journal-article","created":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T18:56:07Z","timestamp":1572980167000},"page":"42-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Signal Reconstruction for a Broad Range of Applications"],"prefix":"10.1145","volume":"48","author":[{"given":"Abolfazl","family":"Asudeh","sequence":"first","affiliation":[{"name":"University of Illinois at Chicago, Chicago, IL, USA"}]},{"given":"Jees","family":"Augustine","sequence":"additional","affiliation":[{"name":"University of Texas at Arlington, Arlington, TX, USA"}]},{"given":"Azade","family":"Nazi","sequence":"additional","affiliation":[{"name":"Google Brain, , TX, USA"}]},{"given":"Saravanan","family":"Thirumuruganathan","sequence":"additional","affiliation":[{"name":"QCRI, HBKU, , TX, USA"}]},{"given":"Nan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, State College, PA, USA"}]},{"given":"Gautam","family":"Das","sequence":"additional","affiliation":[{"name":"University of Texas at Arlington, Arlington, TX, USA"}]},{"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs-Research, Florham Park, NJ, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,11,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Leveraging similarity joins for signal reconstruction. PVLDB, 11(10)","author":"Asudeh A.","year":"2018","unstructured":"A. Asudeh , A. Nazi , J. Augustine , S. Thirumuruganathan , N. Zhang , G. Das , and D. Srivastava . Leveraging similarity joins for signal reconstruction. PVLDB, 11(10) , 2018 . A. Asudeh, A. Nazi, J. Augustine, S. Thirumuruganathan, N. Zhang, G. Das, and D. Srivastava. Leveraging similarity joins for signal reconstruction. PVLDB, 11(10), 2018."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/WIO.2016.7745564"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562764.1562787"},{"key":"e_1_2_1_4_1","first-page":"21","volume-title":"SEQUENCES","author":"Broder A. Z.","year":"1997","unstructured":"A. Z. Broder . On the resemblance and containment of documents . In SEQUENCES , pages 21 -- 29 . IEEE, 1997 . A. Z. Broder. On the resemblance and containment of documents. In SEQUENCES, pages 21--29. IEEE, 1997."},{"key":"e_1_2_1_5_1","volume-title":"Time-varying network tomography: router link data. Journal of the American statistical association, 95(452):1063--1075","author":"Cao J.","year":"2000","unstructured":"J. Cao , D. Davis , S. Vander Wiel , and B. Yu . Time-varying network tomography: router link data. Journal of the American statistical association, 95(452):1063--1075 , 2000 . J. Cao, D. Davis, S. Vander Wiel, and B. Yu. Time-varying network tomography: router link data. Journal of the American statistical association, 95(452):1063--1075, 2000."},{"key":"e_1_2_1_6_1","volume-title":"Survey of network traffic models","author":"Chandrasekaran B.","year":"2009","unstructured":"B. Chandrasekaran . Survey of network traffic models . Waschington University in St. Louis CSE, 567, 2009 . B. Chandrasekaran. Survey of network traffic models. Waschington University in St. Louis CSE, 567, 2009."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453884"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1120.1610"},{"key":"e_1_2_1_10_1","first-page":"2","volume-title":"Identifying","author":"Gong Y.","year":"2005","unstructured":"Y. Gong . Identifying p 2 p users using traffic analysis. 2005 . www.symantec.com\/connect\/articles\/ identifying-p2p-users-using-traffic-analysis. Y. Gong. Identifying p2p users using traffic analysis. 2005. www.symantec.com\/connect\/articles\/ identifying-p2p-users-using-traffic-analysis."},{"key":"e_1_2_1_11_1","volume-title":"Three-dimensional image reconstruction in radiology and nuclear medicine","author":"Grangeat P.","year":"2013","unstructured":"P. Grangeat and J.-L. Amans . Three-dimensional image reconstruction in radiology and nuclear medicine , volume 4 . Springer Science & Business Media , 2013 . P. Grangeat and J.-L. Amans. Three-dimensional image reconstruction in radiology and nuclear medicine, volume 4. Springer Science & Business Media, 2013."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453883"},{"key":"e_1_2_1_13_1","volume-title":"numerical aspects of linear inversion","author":"Hansen P. C.","year":"1998","unstructured":"P. C. Hansen . Rank-deficient and discrete ill-posed problems : numerical aspects of linear inversion . SIAM , 1998 . P. C. Hansen. Rank-deficient and discrete ill-posed problems: numerical aspects of linear inversion. SIAM, 1998."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.brachy.2016.04.357"},{"key":"e_1_2_1_15_1","volume-title":"Big, deep, and smart data in scanning probe microscopy","author":"Kalinin S. V.","year":"2016","unstructured":"S. V. Kalinin , E. Strelcov , A. Belianinov , S. Somnath , R. K. Vasudevan , E. J. Lingerfelt , R. K. Archibald , C. Chen , R. Proksch , N. Laanait , Big, deep, and smart data in scanning probe microscopy , 2016 . S. V. Kalinin, E. Strelcov, A. Belianinov, S. Somnath, R. K. Vasudevan, E. J. Lingerfelt, R. K. Archibald, C. Chen, R. Proksch, N. Laanait, et al. Big, deep, and smart data in scanning probe microscopy, 2016."},{"key":"e_1_2_1_16_1","volume-title":"3d image reconstruction from compton camera data. arXiv:1604.03805","author":"Kuchment P.","year":"2016","unstructured":"P. Kuchment and F. Terzioglu . 3d image reconstruction from compton camera data. arXiv:1604.03805 , 2016 . P. Kuchment and F. Terzioglu. 3d image reconstruction from compton camera data. arXiv:1604.03805, 2016."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4236\/jcc.2017.55005"},{"key":"e_1_2_1_19_1","volume-title":"Dark matter maps reveal cosmic scaffolding. arXiv preprint astro-ph\/0701594","author":"Massey R.","year":"2007","unstructured":"R. Massey , J. Rhodes , R. Ellis , N. Scoville , A. Leauthaud , A. Finoguenov , P. Capak , D. Bacon , H. Aussel , J.-P. Kneib , Dark matter maps reveal cosmic scaffolding. arXiv preprint astro-ph\/0701594 , 2007 . R. Massey, J. Rhodes, R. Ellis, N. Scoville, A. Leauthaud, A. Finoguenov, P. Capak, D. Bacon, H. Aussel, J.-P. Kneib, et al. Dark matter maps reveal cosmic scaffolding. arXiv preprint astro-ph\/0701594, 2007."},{"key":"e_1_2_1_20_1","volume-title":"Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 26(3)","author":"Needell D.","year":"2009","unstructured":"D. Needell and J. A. Tropp . Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 26(3) , 2009 . D. Needell and J. A. Tropp. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 26(3), 2009."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100030401"},{"key":"e_1_2_1_22_1","volume-title":"SIAM","author":"Vogel C. R.","year":"2002","unstructured":"C. R. Vogel . Computational methods for inverse problems . SIAM , 2002 . C. R. Vogel. Computational methods for inverse problems. SIAM, 2002."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-2966.2009.14665.x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05368-9_5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/781027.781053"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863990"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2012.205"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371316.3371327","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371316.3371327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:05Z","timestamp":1750204385000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371316.3371327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,5]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,11,5]]}},"alternative-id":["10.1145\/3371316.3371327"],"URL":"https:\/\/doi.org\/10.1145\/3371316.3371327","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2019,11,5]]},"assertion":[{"value":"2019-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}