搜尋過濾器及應用之研究

Abstract

本文主要評估搜尋過濾器之執行效益。文中提出三個新的搜尋過濾器，並分析該三方 法之執行效益，我們證明其中之一優於過去學者所提出的方法。 我們所提出之方法主要根基於如下兩個基本概念﹕多重赫序與記憶體分段。對於搜尋 過濾器執行效益之評估，我們根據一些相關之效益評估參數詳細分析其中之權衡關係 。主要考慮的效益評估參數為以下四個﹕(1) 赫序空間之中小，(2) 資料集中資料之 數目，(3) 測試一資料平均所花之時間，以及(4) 錯誤率。文中藉著分析與詳細的證 明，我們發現，允許重複碰撞之搜尋過濾器於過去學者所曾提出之方法。文中也以數 學理論說明了如何求得一最佳的允許量複碰撞之搜尋過濾器。一般來說，不同的操作 環境( 赫序空間與資料集 )下，最佳的允許重複碰撞之搜尋過濾器可能不同；換句話 說，允許重複碰撞之搜尋過濾器的最佳解取決於操作環境。 最後，本文大略描述搜尋過濾器適用的一些應用模式。在這些應用範例中，不難發現 ，允許重複碰撞之搜尋過濾器確實比以前學者所提出之方法更適用且更具效率。