{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T04:32:13Z","timestamp":1768105933232,"version":"3.49.0"},"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":[[2018,6]]},"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 including network traffic engineering, medical image reconstruction, acoustics, astronomy and many more. Most common approaches for 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. 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.14778\/3231751.3231752","type":"journal-article","created":{"date-parts":[[2018,7,27]],"date-time":"2018-07-27T12:21:07Z","timestamp":1532694067000},"page":"1276-1288","source":"Crossref","is-referenced-by-count":3,"title":["Leveraging similarity joins for signal reconstruction"],"prefix":"10.14778","volume":"11","author":[{"given":"Abolfazl","family":"Asudeh","sequence":"first","affiliation":[{"name":"University of Michigan and University of Texas at Arlington"}]},{"given":"Azade","family":"Nazi","sequence":"additional","affiliation":[{"name":"Microsoft Research and University of Texas at Arlington"}]},{"given":"Jees","family":"Augustine","sequence":"additional","affiliation":[{"name":"University of Texas at Arlington"}]},{"given":"Saravanan","family":"Thirumuruganathan","sequence":"additional","affiliation":[{"name":"QCRI, HBKU"}]},{"given":"Nan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Pennsylvania State 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":[[2018,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562764.1562787"},{"key":"e_1_2_1_2_1","volume-title":"Elander","author":"Bjerhammar A.","year":"1951","unstructured":"A. Bjerhammar . Application of calculus of matrices to method of least squares: with special reference to geodetic calculations . Elander , 1951 . A. Bjerhammar. Application of calculus of matrices to method of least squares: with special reference to geodetic calculations. Elander, 1951."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007279"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"Boyd S.","year":"2004","unstructured":"S. Boyd and L. Vandenberghe . Convex optimization . Cambridge university press , 2004 . S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004."},{"key":"e_1_2_1_5_1","first-page":"21","volume-title":"Proceedings","author":"Broder A. Z.","year":"1997","unstructured":"A. Z. Broder . On the resemblance and containment of documents. In Compression and Complexity of Sequences 1997 . Proceedings , pages 21 -- 29 . IEEE, 1997 . A. Z. Broder. On the resemblance and containment of documents. In Compression and Complexity of Sequences 1997. Proceedings, pages 21--29. IEEE, 1997."},{"key":"e_1_2_1_6_1","volume-title":"Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics, 59(8):1207--1223","author":"Candes E. J.","year":"2006","unstructured":"E. J. Candes , J. K. Romberg , and T. Tao . Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics, 59(8):1207--1223 , 2006 . E. J. Candes, J. K. Romberg, and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics, 59(8):1207--1223, 2006."},{"key":"e_1_2_1_7_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_8_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_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453884"},{"key":"e_1_2_1_11_1","volume-title":"Inverse problems in astronomy: a guide to inversion strategies for remotely sensed data. Research supported by SERC","author":"Craig I. J.","year":"1986","unstructured":"I. J. Craig and J. C. Brown . Inverse problems in astronomy: a guide to inversion strategies for remotely sensed data. Research supported by SERC . Bristol, England and Boston, MA, Adam Hilger, Ltd ., 1986 , 159 p., 1986. I. J. Craig and J. C. Brown. Inverse problems in astronomy: a guide to inversion strategies for remotely sensed data. Research supported by SERC. Bristol, England and Boston, MA, Adam Hilger, Ltd., 1986, 159 p., 1986."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564719"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1938545.1938550"},{"key":"e_1_2_1_14_1","volume-title":"Beyond moore-penrose part ii: The sparse pseudoinverse. arXiv:1706.08701","author":"Dokmani\u0107 I.","year":"2017","unstructured":"I. Dokmani\u0107 and R. Gribonval . Beyond moore-penrose part ii: The sparse pseudoinverse. arXiv:1706.08701 , 2017 . I. Dokmani\u0107 and R. Gribonval. Beyond moore-penrose part ii: The sparse pseudoinverse. arXiv:1706.08701, 2017."},{"issue":"1","key":"e_1_2_1_15_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erdos P.","year":"1960","unstructured":"P. Erdos and A. R\u00e9nyi . On the evolution of random graphs . Publ. Math. Inst. Hung. Acad. Sci , 5 ( 1 ): 17 -- 60 , 1960 . P. Erdos and A. R\u00e9nyi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17--60, 1960.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2002.1003042"},{"key":"e_1_2_1_17_1","volume-title":"A note on the complexity of l","author":"Ge D.","year":"2011","unstructured":"D. Ge , X. Jiang , and Y. Ye . A note on the complexity of l p minimization. Mathematical programming, 129(2), 2011 . D. Ge, X. Jiang, and Y. Ye. A note on the complexity of l p minimization. Mathematical programming, 129(2), 2011."},{"key":"e_1_2_1_18_1","first-page":"1063","volume-title":"Internet Statistics and Metrics Analysis (ISMA) Workshop","author":"Goldschmidt O.","year":"2000","unstructured":"O. Goldschmidt . Isp backbone traffic inference methods to support traffic engineering . In Internet Statistics and Metrics Analysis (ISMA) Workshop , pages 1063 -- 1075 , 2000 . O. Goldschmidt. Isp backbone traffic inference methods to support traffic engineering. In Internet Statistics and Metrics Analysis (ISMA) Workshop, pages 1063--1075, 2000."},{"key":"e_1_2_1_19_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_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.1995.502798"},{"key":"e_1_2_1_21_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_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453883"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719697","volume-title":"Rank-deficient and discrete ill-posed problems: 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_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.brachy.2016.04.357"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064042"},{"key":"e_1_2_1_26_1","volume-title":"Optimal regularisation for acoustic source reconstruction by inverse methods. Journal of sound and vibration, 275(3):463--487","author":"Kim Y.","year":"2004","unstructured":"Y. Kim and P. Nelson . Optimal regularisation for acoustic source reconstruction by inverse methods. Journal of sound and vibration, 275(3):463--487 , 2004 . Y. Kim and P. Nelson. Optimal regularisation for acoustic source reconstruction by inverse methods. Journal of sound and vibration, 275(3):463--487, 2004."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882952"},{"key":"e_1_2_1_28_1","volume-title":"M\u00e9canique analytique","author":"Lagrange J. L.","year":"1853","unstructured":"J. L. Lagrange . M\u00e9canique analytique , volume 1 . Mallet-Bachelier , 1853 . J. L. Lagrange. M\u00e9canique analytique, volume 1. Mallet-Bachelier, 1853."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_31_1","volume-title":"Technical report","author":"McMahan B.","year":"2017","unstructured":"B. McMahan and D. Ramage . Federated learning: Collaborative machine learning without centralized training data. Technical report , Technical report , Google , 2017 . B. McMahan and D. Ramage. Federated learning: Collaborative machine learning without centralized training data. Technical report, Technical report, Google, 2017."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/964725.633041"},{"key":"e_1_2_1_33_1","first-page":"394","article-title":"On the reciprocal of the general algebraic matrix, abstract","volume":"26","author":"Moors E.","year":"1920","unstructured":"E. Moors . On the reciprocal of the general algebraic matrix, abstract . Bull. Amer. Math. Soc. , 26 : 394 -- 395 , 1920 . E. Moors. On the reciprocal of the general algebraic matrix, abstract. Bull. Amer. Math. Soc., 26:394--395, 1920.","journal-title":"Bull. Amer. Math. Soc."},{"key":"e_1_2_1_34_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_35_1","volume-title":"A survey of software-defined networking: Past, present, and future of programmable networks","author":"Nunes B. A. A.","year":"2014","unstructured":"B. A. A. Nunes , M. Mendonca , X.-N. Nguyen , K. Obraczka , and T. Turletti . A survey of software-defined networking: Past, present, and future of programmable networks . IEEE Communications Surveys & Tutorials , 16(3), 2014 . B. A. A. Nunes, M. Mendonca, X.-N. Nguyen, K. Obraczka, and T. Turletti. A survey of software-defined networking: Past, present, and future of programmable networks. IEEE Communications Surveys & Tutorials, 16(3), 2014."},{"key":"e_1_2_1_36_1","first-page":"406","volume-title":"Mathematical proceedings of the Cambridge philosophical society","author":"Penrose R.","year":"1955","unstructured":"R. Penrose . A generalized inverse for matrices . In Mathematical proceedings of the Cambridge philosophical society , volume 51 , pages 406 -- 413 . Cambridge University Press , 1955 . R. Penrose. A generalized inverse for matrices. In Mathematical proceedings of the Cambridge philosophical society, volume 51, pages 406--413. Cambridge University Press, 1955."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1998.10473707"},{"key":"e_1_2_1_38_1","first-page":"89871","article-title":"Numerical linear algebra. philadelphia: Society for industrial and applied mathematics. Technical report","volume":"978","author":"Trefethen L. N.","year":"1997","unstructured":"L. N. Trefethen and D. Bau III . Numerical linear algebra. philadelphia: Society for industrial and applied mathematics. Technical report , ISBN 978-0 - 89871 - 89361 -9, 1997 . L. N. Trefethen and D. Bau III. Numerical linear algebra. philadelphia: Society for industrial and applied mathematics. Technical report, ISBN 978-0-89871-361-9, 1997.","journal-title":"ISBN"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687722"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2667522.2667536"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898717570","volume-title":"Computational methods for inverse problems","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_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2877204"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/885651.781053"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863990"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3231751.3231752","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:39:10Z","timestamp":1672223950000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3231751.3231752"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":44,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.14778\/3231751.3231752"],"URL":"https:\/\/doi.org\/10.14778\/3231751.3231752","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}