An Application of Storage-Optimal MatDot Codes for Coded Matrix Multiplication: Fast k-Nearest Neighbors Estimation
An Application of Storage-Optimal MatDot Codes for Coded Matrix Multiplication: Fast k-Nearest Neighbors Estimation
复制标题
DOI：
10.1109/bigdata.2018.8622429
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Utsav Sheth;Sanghamitra Dutta;Malhar Chaudhari;Haewon Jeong;Yaoqing Yang;J. Kohonen;Teemu Roos;P. Grover
中科院分区：
文献类型：
--
作者：
Utsav Sheth;Sanghamitra Dutta;Malhar Chaudhari;Haewon Jeong;Yaoqing Yang;J. Kohonen;Teemu Roos;P. Grover
我们提出了一种使用 MatDot 代码（Fahim 等人，Allerton’17）将编码计算应用于最近邻估计问题的新颖应用，已知该代码在存储限制下的恢复阈值方面对于矩阵乘法来说是最佳的。在近似最近邻算法中，通常构建高效的内存索引来提高查询响应时间。其中一种策略是多重随机投影树 (MRPT)，它减少了执行欧几里德距离计算的候选点集。然而，这可能会导致较高的内存占用，并且可能会导致大型或高维数据的分页惩罚。在这里，我们提出了两种并行化 MRPT 的技术，它们分别通过在分布式计算集群中的不同节点之间划分数据存储和计算工作来利用数据和模型并行性。当单个计算节点无法在内存中保存完整的数据集时，这一点尤其重要。我们还针对模型并行架构提出了一种基于 MatDot 代码的新型编码计算策略，该策略在容易掉队的环境中实现存储最佳恢复阈值，即服务查询所需的节点数量。我们通过实验证明，在没有拖沓的情况下，我们的分布式方法比在单个处理节点上执行需要更少的查询时间，从而提供了相对于工作节点数量的近线性加速。我们在具有模拟掉队的真实系统上进行的实验还表明，在容易出现掉队的环境中，我们的策略比未编码的策略实现了更快的查询执行速度。
We propose a novel application of coded computing to the problem of the nearest neighbor estimation using MatDot Codes (Fahim et al., Allerton’17) that are known to be optimal for matrix multiplication in terms of recovery threshold under storage constraints. In approximate nearest neighbor algorithms, it is common to construct efficient in-memory indexes to improve query response time. One such strategy is Multiple Random Projection Trees (MRPT), which reduces the set of candidate points over which Euclidean distance calculations are performed. However, this may result in a high memory footprint and possibly paging penalties for large or high-dimensional data. Here we propose two techniques to parallelize MRPT that exploit data and model parallelism respectively by dividing both the data storage and the computation efforts among different nodes in a distributed computing cluster. This is especially critical when a single compute node cannot hold the complete dataset in memory. We also propose a novel coded computation strategy based on MatDot codes for the model-parallel architecture that, in a straggler-prone environment, achieves the storage-optimal recovery threshold, i.e., the number of nodes that are required to serve a query. We experimentally demonstrate that, in the absence of straggling, our distributed approaches require less query time than execution on a single processing node, providing near-linear speedups with respect to the number of worker nodes. Our experiments on real systems with simulated straggling, we also show that in a straggler-prone environment, our strategy achieves a faster query execution than the uncoded strategy.