利用多鍵語赫序函數尋找K 個最鄰點之效益分析

Abstract

Shen與Lee 曾經提出利用多鍵語赫序法則（multiple key hashing）來尋找查詢點的 k 個最鄰近點（k-nearest neighbors ）。本文將利用幾何機率（geometricprobabi lity）的觀念，分析他們所提的方法，對於一個查詢點平均須要檢查的區段數之可能 範圍。並且我們將探討在某些條件下，對於k 個最鄰近點找尋（k-nearest neithbor search ）所須檢查的最少區段數。另外，我們也將探討如何利用最小N 字元（mini mal N-tuple ）的理論，來幫助我們建造一個最適合用來找尋查詢點的k 個最鄰近點 的多鍵語赫序法則式之最佳檔案庫系統。