PNNU: parallel nearest-neighbor units for learned dictionaries
Abstract
We present a novel parallel approach, parallel nearest neighbor unit (PNNU), for finding the nearest member in a learned dictionary of high-dimensional features. This is a computation fundamental to machine learning and data analytics algorithms such as sparse coding for feature extraction. PNNU achieves high performance by using three techniques: (1) PNNU employs a novel fast table look up scheme to identify a small number of atoms as candidates from which the nearest neighbor of a query data vector can be found; (2) PNNU reduces computation cost by working with candidate atoms of reduced dimensionality; and (3) PNNU performs computations in parallel over multiple cores with low inter-core communication overheads. Based on e cient computation via techniques (1) and (2), technique (3) attains further speed up via parallel processing. We have implemented PNNU on multi-core ma- chines. We demonstrate its superior performance on three application tasks in signal processing and computer vision. For an action recognition task, PNNU achieves 41x overall performance gains on a 16-core compute server against a conventional serial implementation of nearest neighbor computation. Our PNNU software is available online as open source.
Rights
Copyright is reserved by the copyright owner.Collections
Related items
Showing items related by title, author, creator and subject.
-
Differential benefits of cardiac care regionalization based on driving time to percutaneous coronary intervention
Shen, Yu-Chu; Hsia, Renee Y. (AEM, 2020-09);Background. Patients with ST-elevation myocardial infarction (STEMI) require timely reperfusion, and percutaneous coronary intervention (PCI) decreases morbidity and mortality. Regionalization of STEMI care has increased ... -
Nearest neighbor classification using a density sensitive distance measurement [electronic resource]
Burkholder, Joshua Jeremy (Monterey, California. Naval Postgraduate School, 2009-09);This work proposes a density sensitive distance measurement that takes into account the density of an underlying dataset to better represent the shape of the data when measuring distance. Kernel density estimation, using ... -
Changes in Geographical Access to Trauma Centers for Vulnerable Populations in the United States, Author Manuscript
Hsia, Renee Y.; Yu-Chu, Shen (2011-10);Closures of trauma centers have accelerated since 2001. These closures may be disproportionately affecting disadvantaged communities. We evaluate how driving time between ZIP codes and nearest trauma centers changed ...