PNNU: parallel nearest-neighbor units for learned dictionaries
Abstract
We present a novel parallel approach, parallel nearest neigh-
bor 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 ... -
DLA stock location policy |ba case study of high priority requisitions from NADEP, North Island
Thon, Scott R. (Monterey, California. Naval Postgraduate School, 1993-12);As a consequence of recent Defense Management Review Decisions the Department of Defense (DoD) has consolidated the physical distribution functions for wholesale consumable materiel under the management of the Defense ...