Abstract
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.
- Asudeh, A., Augustine, J., Nazi, A., Thirumuruganathan, S., Zhang, N., Das, G., Srivastava, D. Scalable algorithms for signal reconstruction by leveraging similarity joins. VLDB J. 29, 2 (2020), 681--707.Google ScholarCross Ref
- 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.Google Scholar
- Beyer, K., Gemulla, R., Haas, P.J., Reinwald, B., Sismanis, Y. Distinct-value synopses for multiset operations. Commun. ACM 10, 52 (2009), 87--95.Google Scholar
- Broder, A.Z. On the resemblance and containment of documents. In SEQUENCES (1997), IEEE, 21--29.Google ScholarDigital Library
- Chaudhuri, S., Ganti, V., Kaushik, R. A primitive operator for similarity joins in data cleaning. In ICDE (2006). IEEE.Google ScholarDigital Library
- Cohen, E., Kaplan, H. Tighter estimation using bottom k sketches. PVLDB 1, 1 (2008), 213--224.Google Scholar
- Grangeat, P., Amans, J.-L. Three-Dimensional Image Reconstruction in Radiology and Nuclear Medicine, Vol. 4. Springer Science & Business Media, Springer Netherlands, 1996.Google ScholarCross Ref
- 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.Google Scholar
- Liu, Z., Shi, Z., Jiang, M., Zhang, J., Chen, L., Zhang, T., Liu, G. Using MC algorithm to implement 3d image reconstruction for yunnan weather radar data. J. Comput Commun. 05, 5 (2017), 50--61.Google ScholarCross Ref
- 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).Google Scholar
- Penrose, R. A generalized inverse for matrices. In Mathematical Proceedings of the Cambridge Philosophical Society, Volume 51 (1955), 406--413.Google ScholarCross Ref
- 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.Google Scholar
- Vogel, C.R. Computational methods for inverse problems. SIAM, 2002.Google ScholarCross Ref
- 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.Google Scholar
- Zhang, Y., Roughan, M., Duffield, N., Greenberg, A. Fast accurate computation of large-scale IP traffic matrices from link loads. In SIGMETRICS, Volume 31, 2003.Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Scalable signal reconstruction for a broad range of applications
Recommendations
Efficient Signal Reconstruction for a Broad Range of Applications
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 ...
SSRNet: Scalable 3D Surface Reconstruction Network
Learning-based surface reconstruction methods have received considerable attention in recent years due to their excellent expressiveness. However, existing learning-based methods lack scalability in processing large-scale point clouds. This paper proposes ...
Scalable Distributed Stream Join Processing
SIGMOD '15: Proceedings of the 2015 ACM SIGMOD International Conference on Management of DataEfficient and scalable stream joins play an important role in performing real-time analytics for many cloud applications. However, like in conventional database processing, online theta-joins over data streams are computationally expensive and moreover, ...
Comments