Leveraging Similarity Joins for Signal Reconstruction
Leveraging Similarity Joins for Signal Reconstruction
复制标题
DOI：
10.14778/3231751.3231752
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Abolfazl Asudeh;Azade Nazi;Jees Augustine;Saravanan Thirumuruganathan;Nan Zhang;Gautam Das;D. Srivastava
中科院分区：
文献类型：
--
作者：
Abolfazl Asudeh;Azade Nazi;Jees Augustine;Saravanan Thirumuruganathan;Nan Zhang;Gautam Das;D. Srivastava
信号重构问题（SRP）是一个重要的优化问题，其目标是识别与给定先验最接近的欠定线性方程组的解。它在不同的领域有大量的应用，包括网络流量工程、医学图像重建、声学、天文学等等。大多数常见的SRP方法不能扩展到大的问题规模。在本文中，我们提出了这个问题的双重表述，并展示了为可扩展相似连接开发的数据库技术如何提供显著的加速。在真实世界和合成数据上的大量实验表明，我们的方法比竞争方法产生了高达20倍的显著加速。
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.