Show simple item record

dc.contributor.authorKung, H.T.
dc.contributor.authorMcDaniel, Bradley
dc.contributor.authorTeerapittayanon, Surat
dc.date.accessioned2017-03-29T00:03:30Z
dc.date.available2017-03-29T00:03:30Z
dc.date.issued2015
dc.identifier.citationH.T. Kung, B. McDaniel, S. Teerapittayanon, "PNNU: Parallel Nearest-Neighbor Units for Learned Dictionaries," International Workshop on Languages and Compilers for Parallel Computing, Springer International Publishing, 2015.
dc.identifier.urihttp://hdl.handle.net/10945/52424
dc.description.abstractWe 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.en_US
dc.description.sponsorshipFunded by Naval Postgraduate Schoolen_US
dc.description.sponsorshipIntel Corporationen_US
dc.format.extent16 p.en_US
dc.publisherSpringeren_US
dc.rightsCopyright is reserved by the copyright owner.en_US
dc.titlePNNU: parallel nearest-neighbor units for learned dictionariesen_US
dc.typeArticleen_US
dc.contributor.corporateHarvard University
dc.subject.authorNearest neighboren_US
dc.subject.authorNNUen_US
dc.subject.authorPNNUen_US
dc.subject.authorData analyticsen_US
dc.subject.authorSparse codingen_US
dc.subject.authorLearned dictionaryen_US
dc.subject.authorParallel processingen_US
dc.subject.authorMulti-core programmingen_US
dc.subject.authorSpeedupen_US
dc.subject.authorMatching pursuiten_US
dc.subject.authorSignal processingen_US
dc.subject.authorComputer visionen_US
dc.subject.authorKTHen_US
dc.subject.authorCIFARen_US
dc.description.funderAgreement no. N00244-15-0050 (NPS)en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record