Performance analysis of a k ‐nearest neighbor searching technique
Chin‐Chen Chang, Jenn Liang · Journal of the Chinese Institute of Engineers · 1985
Shen and Lee (1) suggested to use multiple key hashing functions in searching k nearest neighbors of a query record. In this paper, we will apply the concept of the geometric probability to analyze the performance of the method suggested by Shen and Lee. Besides, we shall explore the expected number of buckets which should be examined for a k‐nearest‐neighbor search query. We shall use the theory of minimal N‐tuple proposed by Chang, Lee and Du to help us design two attribute file systems based upon multiple key hashing functions which are suitable for k‐nearest‐neighbor searching technique.