PANDA: Extreme Scale Parallel K-Nearest Neighbor on Distributed Architectures
Patwary, Satish, Sundaram, Liu, Sadowski, Racah · cs.DC · 2016-07-27 · 原文
Computing k-Nearest Neighbors (KNN) is one of the core kernels used in many machine learning, data mining and scientific computing applications. Although kd-tree based O(\log n) algorithms have been proposed for computing KNN, due to its inherent sequentiality, linear algorithms are being used in practice. This limits the applicability of such methods to millions of data points, with limited scalability for Big Data analytics challenges in the scientific domain. In this paper, we present parallel and highly optimized kd-tree based KNN algorithms (both construction and querying) suitable for distributed architectures. Our algorithm includes novel approaches for pruning search space and improving load balancing and partitioning among nodes and threads. Using TB-sized datasets from three science applications: astrophysics, plasma physics, and particle physics, we show that our implementation can construct kd-tree of 189 billion particles in 48 seconds on utilizing \sim50,000 cores. We also demonstrate computation of KNN of 19 billion queries in 12 seconds. We demonstrate almost linear speedup both for shared and distributed memory computers. Our algorithms outperforms earlier im
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
Computing k-Nearest Neighbors (KNN) is one of the core kernels used in many machine learning, data mining and scientific computing applications.
Although kd-tree based O(\log n) algorithms have been proposed for computing KNN, due to its inherent sequentiality, linear algorithms are being used in practice.
2. 领域脉络
本文类目：cs.DC，属于其所在研究脉络的最新进展。
3. 机制拆解
Our algorithm includes novel approaches for pruning search space and improving load balancing and partitioning among nodes and threads.
4. 证据与数字
Using TB-sized datasets from three science applications: astrophysics, plasma physics, and particle physics, we show that our implementation can construct kd-tree of 189 billion particles in 48 seconds on utilizing \sim50,000 cores.
We also demonstrate computation of KNN of 19 billion queries in 12 seconds.
5. 反例与边界
This limits the applicability of such methods to millions of data points, with limited scalability for Big Data analytics challenges in the scientific domain.
In this paper, we present parallel and highly optimized kd-tree based KNN algorithms (both construction and querying) suitable for distributed architectures.
We demonstrate almost linear speedup both for shared and distributed memory computers.
6. 跨领域连接与意外收获
思考本文机制能否迁移到你正在跟进的问题。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。