ACM通信
研究突出了
技术视角:大规模解决信号重构问题
当问题扩展到“大数据”时，研究人员必须经常提出新的解决方案，利用来自多个研究领域的想法——正如我们经常在今天的机器学习、生物信息学和数据可视化等大数据技术和工具中看到的那样。除了这些被大量研究的主题之外，还有其他类别的普遍问题必须大规模地重新思考。其中一个问题就是大规模信号重建：4取一组相对低维的观测数据，用它们重构高维的未知信号。当我们只能观察想要建模的复杂环境的一个子集时，就会出现这类问题——例如，放置几个传感器并使用它们的读数来重建环境的温度，或监视网络中的多个点并使用读数来估计端到端网络流量，或使用2D切片来重建3D图像。
下面这篇论文值得注意，因为它以一种干净、深刻和系统的方式，可伸缩性地解决了一个服务不足的问题，并产生了实际影响。
这信号重构问题(SRP)通常被视为一个优化任务，在该任务中，我们搜索高维信号，将其与信号的已知属性进行比较，使损失函数最小化。先前的SRP解决方案使用了线性代数技术4或者说期望最大化2去寻找解决方案。然而，在规模上，信号的维数足够高，使这种优化技术过于昂贵。在接下来的论文中，Asudeh等人展示了关于SRP的算法洞察，结合类似连接和草图等数据库技术，可以用于可伸缩地解决信号重构问题。本文创造性地集成了查询处理、近似和线性代数技术。
作者首先注意到SRP是二次规划的一个特例，他们通过解决原始问题的拉格朗日对偶公式来利用它。在此基础上，它们连接到查询处理:算法的关键部分是计算一个(通常非常稀疏的)矩阵的乘积一个对于它的转置，AAT．反过来，该计算的大部分值来自于的少量元素一个．
作者创造性地利用这一观察结果，通过集合交叉原语实现矩阵乘法来处理巨大的矩阵。它们建立在集合相似连接的基础上，并应用基于阈值的技术3.对矩阵乘积的值进行定界，从而提出一种快速逼近算法。最后，他们展示了如何使用最小哈希草图1为了接近集合，允许进一步权衡精度与性能(和空间)。实验分析表明，这些技术可以很好地预测大型P2P网络中的端到端路由，这比之前的解决方案所能处理的要大好几个数量级。
这篇论文之所以引人注目，是因为它以一种干净、深刻和系统的方式，可伸缩性地解决了一个服务不足的问题，并产生了实际影响。它有几个关键贡献。首先，它展示了如何利用对线性代数计算的洞察来提高效率(与二次规划的联系，它允许通过拉格朗日对偶来求解)。随后，它对从查询处理和草图开发近似算法的技术进行了深刻的连接。最后，作者进行了大规模的实验研究，证明了高性能。它们说明了将重要优化问题与数据库近似查询处理技术联系起来的潜在好处。
参考文献
1.关于文件的相似性和包含性。序列的压缩与复杂性．Ieee(1997)， 21-29。
2.Cao, J.， Davis, D.， Wiel, S.V.和Yu, B.时变网络断层扫描:路由器链路数据。美国统计学会，95， 452(2000)， 1063-1075。
3.Chaudhuri, S.， Ganti, V.和Kaushik, R.数据清理中相似度联接的原语算子。ICDE．Ieee(2006)， 5。
数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc.
没有找到条目