Back to search

Georgia Institute of Technology

Approximate Nearest Neighbor Search for Multiple Distance Metrics: Algorithms, Index Structures, and Applications

Abstract

dc:description.abstract

Approximate nearest neighbor search (ANNS) is a fundamental problem in information retrieval, recommendation, computer vision, machine learning, and vector databases. Although locality-sensitive hashing (LSH) and graph indexes provide effective solutions for standard metrics, high-dimensional search remains challenging when the target distance is non-Euclidean, expensive to compute, or specified only at query time. This dissertation studies ANNS for multiple distance metrics by using compact, reusable, or lightweight intermediate information to reduce query time, index space, or exact distance-computation costs while preserving search quality. The core of the dissertation develops three ANNS techniques. First, iDEC is a framework of indexable distance estimating codes for Hamming and edit distances. It maps high-dimensional objects to low-dimensional codes, indexes the codes with standard multidimensional search structures, and verifies only promising original objects. Second, MP-RW-LSH is a multi-probe random-walk LSH scheme for the Manhattan distance. By replacing Cauchy projections with random-walk projections, it restores the concentration needed by multi-probe LSH and improves the tradeoff between index size and query efficiency. Third, U-HNSW supports universal Lp search, in which each query may specify a different value of p. It maintains two reusable HNSW graphs under L1 and L2, selects a suitable base graph for candidate generation, and performs target-Lp computations during selective verification. The dissertation also studies two broader systems extensions of this design pattern. OddEEC is a sketch-based error estimating code for wireless bit-error-rate estimation. It adapts Odd Sketch to estimate the Hamming distance between transmitted and received packets, combines bit sampling with maximum-likelihood estimation to handle corrupted codewords, and provides low decoding latency with compact precomputed tables. Query-centric optimization of AI workflows expresses model-heavy operations as queries with expensive predicates or scoring functions. It applies approximate query processing and lightweight proxy models to reduce reward-model or AI-pipeline invocations while preserving the required query quality. Together, these results show how distance-estimating codes, candidate-generation mechanisms, reusable graph indexes, compact sketches, samples, and proxy models can retain the information needed by a task without reproducing every step of full processing. They improve ANNS across several important distance metrics and extend the same broader systems viewpoint to networking measurement and AI workflow optimization.

Degree

thesis:*
Name thesis:degree_name
Computer Science, PhD
Department thesis:degree_department
Computer Science
Grantor
Georgia Institute of Technology
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wang, Huayi
Advisor dc:contributor.advisor
  • Xu, Jun (Jim)
Committee members dc:contributor.committeemember
  • Arulraj, Joy
  • Rong, Kexin
  • Ogihara, Mitsunori
  • Chan, Gromit Yeuk-Yin
ORCID person:identifier.orcid

Rights

Language dc:language.iso
English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/82127

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Wang, Huayi. Approximate Nearest Neighbor Search for Multiple Distance Metrics: Algorithms, Index Structures, and Applications. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/82127