Show simple item record

dc.contributor.authorAhmed, Jaim
dc.date.accessioned2014-03-04T16:22:56Z
dc.date.available2014-03-04T16:22:56Z
dc.date.issued2009-05
dc.identifier.otherahmed_jaim_200905_ms
dc.identifier.urihttp://purl.galileo.usg.edu/uga_etd/ahmed_jaim_200905_ms
dc.identifier.urihttp://hdl.handle.net/10724/25368
dc.description.abstractWe introduce a new algorithm for K-nearest neighbor queries that uses clustering and caching to improve performance. The main idea is to reduce the distance computation cost between the query point and the data points in the data set. We use a divide-and-conquer approach. First, we divide the training data into clusters based on similarity between the data points in terms of Euclidean distance. Next we use linearization for faster lookup. The data points in a cluster can be sorted based on their similarity (measured by Euclidean distance) to the center of the cluster. Fast search data structures such as the B-tree can be utilized to store data points based on their distance from the cluster center and perform fast data search. The B-tree algorithm is good for range search as well. We achieve a further performance boost by using B-tree based data caching. In this work we provide details of the algorithm, an implementation, and experimental results in a robot navigation task.
dc.languageeng
dc.publisheruga
dc.rightspublic
dc.subjectK-Nearest Neighbors
dc.subjectExecution
dc.subjectCaching
dc.titleEfficient K-nearest neighbor queries using clustering with caching
dc.typeThesis
dc.description.degreeMS
dc.description.departmentComputer Science
dc.description.majorComputer Science
dc.description.advisorMaria Hybinette
dc.description.committeeMaria Hybinette
dc.description.committeeKhaled Rasheed
dc.description.committeeEileen T. Kraemer


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record