GENERALIZING NORMALIZATION FOR APPROXIMATE NEAREST NEIGHBOR ALGORITHMS

Content Files

SP23-ECE499-Thesis-Shitole, Viraj.pdf

Permalink

https://hdl.handle.net/2142/124798

Title: GENERALIZING NORMALIZATION FOR APPROXIMATE NEAREST NEIGHBOR ALGORITHMS
Author(s): Shitole, Viraj
Issue Date: 2023-05-01
Keyword(s): nearest neighbors; normalization; approximation algorithms
Date of Ingest: 2024-10-04T12:07:57-05:00
Abstract: The nearest neighbor search problem involves a database of embeddings and a set of queries where we aim to find the embedding closest to a query. Exact methods such as linear search and space partitioning demonstrate time complexity issues as we increase database and query set size. This has led to the development of approximation algorithms where we pick points some distance close to our query using methods such as navigable small worlds or vector quantization. However, while this increases speed, these methods bring up issues with accuracy when adapting algorithms to different datasets. In this research project, we determine if there is a normalization scheme that allows for perfect accuracy when using approximate nearest neighbor algorithms on any dataset. We draw initial conclusions from the current state-of-art approximation algorithm ScaNN and then generalize to other approximation algorithms.
Type of Resource: text
Genre of Resource: dissertation/thesis
Language: eng

The best of ECE undergraduate research