On the I/O Complexity of the k-Nearest Neighbors Problem

Keyphrases

• I/O-complexity 100%
• K-nearest 100%
• Polynomial Space 66%
• Approximation Algorithms 33%
• Nearest Neighbor 33%
• Approximate Nearest Neighbor Search 33%
• Hamming Space 33%
• External Memory 33%
• New Lower Bound 33%
• Dimensionality Reduction 33%
• K-blocks 33%
• Block Transfer 33%
• Indivisibility 33%
• Memory Index 33%
• Indexing Scheme 33%
• Space-time Data 33%

Computer Science

• Input/Output 100%
• Polynomial Space 100%
• Data Structure 50%
• Approximation Algorithms 50%
• External Memory 50%