COMPLEXITY ANALYSIS FOR NEAREST NEIGHBOR SEARCH. EXECUTIVE SUMMARY ONLY

PDF

Authors
  1. Zakarauskas, P.
  2. Ozard, J.M.
Corporate Authors
Defence Research Establishment Atlantic, Dartmouth NS (CAN)
Abstract
In this technical memorandum we present cost estimates for finding the k-nearest neighbors to a test pattern according to a Minkowski p-metric, as a function of the size of the buckets in partitioning searching algorithms. Prior to finding the nearest neighbor, the search space must be ordered using either product or hierarchical partitioning. It is known that fast nearest neighbors algorithms find the k stored patterns closest to a test pattern in a time which is asymptotically constant with the total number of patterns. The asymptotic total cost is derived explicitly for four types of searches based on three different partitioning schemes: the k-d tree partitioning, the ordered partitioning, and the product partitioning. The asymptotic expected number of operations performed to find the nearest neighbor is presented as a function of the average number of patterns per bucket n and the dimensionality of the search space d, and is shown to contain a global minimum. Total cost is explicitly calculated for the Euclidian metrick, k = 1, and realistic computation costs. The optimum value of n is weakly dependent on d, but differs between algorithms. A computer simulation with a uniform distribution of patterns supports the theoretical results.
Keywords
Complexity analysis;Nearest neighbor;Euclidean metric;Tree partitioning;Product partitioning;Search algorithms
Report Number
DREA-TM-97-240-EXE-SUMM — Technical Memorandum Executive Summary
Date of publication
01 Jun 1997
Number of Pages
5
DSTKIM No
98-00417
CANDIS No
507187
Format(s):
Hardcopy;Document Image stored on Optical Disk

Permanent link

Document 1 of 1

Date modified: