搜尋的速度是影響使用者對一個搜尋引擎體驗的一個因素,對於活在2019的你來說,很難想像在Google Search時你要等兩秒(不包含網路封包傳送的時間)才能等到搜尋引擎幫你找到你要的東西。
我們若用Day 10所說到的BM25(一個效率很高的搜尋演算法)來計算一個檔案的分數,理論上大約需要100奈秒(ns, 10^(-9)s
),這已經很快了!然而,我們若要從兩千五百萬個檔案中找到同時符合查詢字的查詢(像是英文裡的定冠詞"the"幾乎會出現在每一個檔案裡面),那麼,
25,000,000 x 100 ns = 2.5 sec
大約就需要等兩秒,何況真實世界有不只兩千五百萬個檔案。
硬體上的改善的方法包含了增加硬體的數量或換更好的硬體設備。對於增加硬體的數量這個考量,雖然伺服器本身不貴,但更複雜的系統架構和更高的能源消耗卻非我們所樂見;換更好的硬體設備則意味著更高的伺服器成本,同時,伺服器的硬體也不可能無止境的增強。因此,我們從軟體面進行考慮,改進的方法有一個基本的思路:
我們假設多數搜尋引擎使用者不會點到Top-K以後的檔案,既然這樣,搜尋引擎的本身也就只需要準備到Top-K檔案。
所以我們的作法就是:不計算所有文檔的分數,僅計算有機會進到Top-K Ranking List的文件就夠了。
這個方法稱為WAND Algorithm,我們明天會加以介紹。