K-Robust Nearest Neighbor Search and Classification
Date
2016
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Advisor
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Haverford users only
Terms of Use
Tripod URL
Identifier
Abstract
The nearest neighbor problem is one of the most important problems in computational geometry. Many of the solutions to this problem suffer from the "curse of dimensionality" that makes the runtime increase exponentially with the dimensionality of the point set. We explore the relaxing of the problem to the approximate nearest neighbor problem and briefly discuss its solutions before moving on to the approximate near neighbor problem. We take a detailed look at the locality sensitive hashing data structure that solves the approximate near neighbor problem. Finally, we look at a new problem: the k-robust nearest neighbor problem. We present and analyze one algorithm that solves this problem before continuing on to experiments to examine if there is any noticeable improvement in the balanced classification rate or accuracy for the k-robust nearest neighbor problem.