----- 郵件 -----
日期: Thu, 05 Mar 2015 17:54:37 +0800
寄件人: Kun-Mao Chao
主旨: 元宵燈謎
收件人: ACB

嗨！各位ACB夥伴：

元宵節快樂！陳琨寫了一個隨機燈謎程式，想自嗨的可到這裡瞧瞧：

https://www.csie.ntu.edu.tw/~kmchao/bcc18spr/Lantern/ (燈謎程式以Chrome瀏覽為佳 ；2018因http-->https而改版)

另外，介紹一篇好論文與大家分享，該論文探討在多元化指標下，如何快速找尋使用者定義的總戰力為前k大的物件，想自虐的可到這裡瞧瞧：

http://researcher.watson.ibm.com/researcher/files/us-fagin/jcss03.pdf

學業順利！

坤茂

----- 轉寄的郵件 -----
日期: Fri, 6 Mar 2015 00:55:54 +0800
寄件人: 劉效飛
主旨: Re: [ACB] 元宵燈謎

謝謝老師的分享, 很有意思的論文。

之前看到 Lucene 中使用了一種 TF-IDF 的變形作為 scoring function:
研究完這個變形的 scoring function 與傳統 TF-IDF 的差異後,
心裡閃過一個疑惑, search engine 對回應時間的要求也很高,
對於一個 multi-term query,
Lucene 應該不會真的把所有相關的結果都用這個 scoring function 計算後,
再回傳前 k 大的結果吧?

雖然我沒有去 trace code,
不過如果 stackoverflow 的解答是正確的,
Lucene 好像真的是這樣做:
http://stackoverflow.com/questions/10324050/lucenes-algorithm

雖然沒有自虐到想去看懂論文中的分析證明,
但 Threshold Algorithm 本身還蠻簡單易懂的,
容我將這篇文章轉寄給公司負責 Lucene 的同事,
也須他們可以實作看看, performance 可能會增進不少 :)

Thanks for sharing!

效飛

----- 轉寄的郵件 -----
日期: Fri, 06 Mar 2015 17:10:23 +0800
寄件人: Kun-Mao Chao
主旨: Re: [ACB] 元宵燈謎

謝謝效飛的follow-up，讓我看到了另一個應用面，更大的收穫是終於花些時間定心讀論文。

> Threshold Algorithm 本身還蠻簡單易懂的

這句話大大激勵了我這老糊塗，終於把該方法搞懂。Threshold Algorithm (TA) 改善了原先的 Fagin's Algorithm (FA)，這兩個方法在論文中都提到。擷取物件的各個attribute有兩種access mode：sorted access (依attribute順序擷取)及random access (直接取得給定物件的attribute)，我剛讀的時候有幾個地方沒搞清楚，在此也提供有興趣讀這篇的夥伴參考：

1. FA: "At least k objects such that each of these objects has been seen in each of the m lists"。(意指至少有k個物件的所有attributes在sorted access過程都被看過。)

2. TA: 第二步的threshold值來自於各個attribute的SORTED ACCESS最後面的值，它可以做為搜尋過程中未被看到物件的上限，一旦我們有k個物件達到這上限，後面就不必再搜尋下去了。

下面這份投影片做得很好，值得臨摹學習。

http://www.cs.ucr.edu/~tsotras/cs236/W15/Top-k.ppt

該投影片後面還提到 sorted access 或 random access不可行時的變通方式，也讓人雙目了然。

週末快樂！

坤茂