Show simple item record

dc.contributor.advisorBalcan, Maria-Florina
dc.contributor.advisorGray, Alexander G.
dc.contributor.authorRam, Parikshit
dc.date.accessioned2013-09-20T13:30:03Z
dc.date.available2013-09-20T13:30:03Z
dc.date.created2013-08
dc.date.issued2013-07-02
dc.date.submittedAugust 2013
dc.identifier.urihttp://hdl.handle.net/1853/49112
dc.description.abstractNearest-neighbor search is a very natural and universal problem in computer science. Often times, the problem size necessitates approximation. In this thesis, I present new paradigms for nearest-neighbor search (along with new algorithms and theory in these paradigms) that make nearest-neighbor search more usable and accurate. First, I consider a new notion of search error, the rank error, for an approximate neighbor candidate. Rank error corresponds to the number of possible candidates which are better than the approximate neighbor candidate. I motivate this notion of error and present new efficient algorithms that return approximate neighbors with rank error no more than a user specified amount. Then I focus on approximate search in a scenario where the user does not specify the tolerable search error (error constraint); instead the user specifies the amount of time available for search (time constraint). After differentiating between these two scenarios, I present some simple algorithms for time constrained search with provable performance guarantees. I use this theory to motivate a new space-partitioning data structure, the max-margin tree, for improved search performance in the time constrained setting. Finally, I consider the scenario where we do not require our objects to have an explicit fixed-length representation (vector data). This allows us to search with a large class of objects which include images, documents, graphs, strings, time series and natural language. For nearest-neighbor search in this general setting, I present a provably fast novel exact search algorithm. I also discuss the empirical performance of all the presented algorithms on real data.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectSimilarity search
dc.subjectNearest-neighbor search
dc.subjectComputational geometry
dc.subjectAlgorithms and analysis
dc.subject.lcshNearest neighbor analysis (Statistics)
dc.subject.lcshApproximation algorithms
dc.subject.lcshSearch theory
dc.titleNew paradigms for approximate nearest-neighbor search
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentComputational Science and Engineering
thesis.degree.levelDoctoral
dc.contributor.committeeMemberLebanon, Guy
dc.contributor.committeeMemberClarkson, Kenneth L.
dc.contributor.committeeMemberVempala, Santosh S.
dc.date.updated2013-09-20T13:30:08Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record