A Nearest Neighbor Data Structure for Graphics Hardware

摘要: Nearest neighbor search is a core computational task in database systems and throughout data analysis. It also major bottleneck, hence an enormous body of research has been devoted to structures algorithms for accelerating the task. Recent advances graphics hardware provide tantalizing speedups on variety tasks suggest alternate approach problem: simply run brute force massively parallel system. In this paper we marry approaches with novel structure that can effectively make use such as cards. The architectural complexities hardware—the high degree parallelism, small amount memory relative instruction throughput, single instruction, multiple design—present significant challenges design. Furthermore, applies perfectly hardware, leading one question whether intelligent algorithm or even hope outperform basic approach. Despite these misgivings, demonstrate our structure—termed Random Ball Cover—provides over GPUbased