SCHEDULE: NOV 15-20, 2015

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

Performance Optimization for the K-Nearest Neighbors Kernel on x86 Architectures

SESSION: Data Clustering

EVENT TYPE: Papers

EVENT TAG(S): Applications, Analytics, Simulation

TIME: 11:00AM - 11:30AM

SESSION CHAIR(S): Vijay Gadepally

AUTHOR(S):Chenhan D. Yu, Jianyu Huang, Woody Austin, Bo Xiao, George Biros

ROOM:18CD

ABSTRACT:

Nearest neighbor search is a cornerstone problem in computational geometry, non-parametric statistics, and machine learning. For N points, exhaustive search requires quadratic work, but many fast algorithms reduce the complexity for exact and approximate searches. The common kernel (kNN kernel) in all these algorithms solves many small-size problems exactly using exhaustive search. We propose an efficient implementation and performance analysis for the kNN kernel on x86 architectures. By fusing the distance calculation with the neighbor selection, we are able to utilize memory throughput. We present an analysis of the algorithm and explain parameter selection. We perform an experimental study varying the size of the problem, the dimension of the dataset, and the number of nearest neighbors. Overall we observe significant speedups. For example, when searching for 16 neighbors in a point dataset with 1.6 million points in 64 dimensions, our kernel is over 4 times faster than existing methods.

Chair/Author Details:

Vijay Gadepally (Chair) - Massachusetts Institute of Technology|

Chenhan D. Yu - The University of Texas at Austin

Jianyu Huang - The University of Texas at Austin

Woody Austin - The University of Texas at Austin

Bo Xiao - The University of Texas at Austin

George Biros - The University of Texas at Austin

  Click here to download .ics calendar file

  Click here to download .vcs calendar file

  Click here to add event to your Google Calendar

Paper provided by the ACM Digital Library

Paper also available from IEEE Computer Society