Ranking Objects by Exploiting Relationships:Computing Top-K over Aggregation

這篇paper是來自於SIGMOD 2006，主要是探討給定一些關鍵字查詢時，所得到的查詢結果(文件)中的target object如何進行評分及排序，同時考慮在不需進行完整計算的可能性，因為我們只需要找出最好的前k項target object就足夠了。因此，這篇paper就是以上述為目標，並提出一個計算target object 分數，節省時間的演算法(called early termination)。

論文中首先界定document與object，以及他們之間的關係。舉例來說，在找尋領域專家的應用上，我們可以輸入代表此領域的關鍵字，從而得到相關論文paper (document)，而我們想要找尋的target object，則是paper的author。document與target object間的包含關係，我們可以用一個table來記錄，也就是我們在某個document內發現哪些target object。

假設以全文檢索來做keyword查詢，當關鍵字不只一個時。對於每個single keyword w，我們會得到一對應的ranked list，裡面包含了符合這keyword的document，並按照分數高低來排列。而計算target object分數的方式(scoring function)，即可透過加總取得，可以是row marginal或是column marginal。Row marginal class是先對每個document做所有的keyword分數之combine，再對combine後的分數作aggregation。而Column marginal class是先對每個keyword做aggregation，再對所有的document分數做combination。在此篇paper中，我們用的是column marginal class。

在這樣的模式運作下，作者提出了一個early termination的觀念，也就是說當我們確定找出了最好的k個target object，而且之後所搜尋的object都不會比這k個更好的話，我們就可以停止搜尋並回傳結果了。其中又分為generate-prune approach and generate-only approach。generate-prune approach用的是先產生一size大於k的candidate set，再做pruning得到最終 k。而generate-only則是會不斷產生candidate，直到符合某stopping criterion為止。

最後實驗證明，使用early termination的generate-prune(GP)與generate-only(GO)的執行時間皆比原本的SQL好上幾倍，而GP比GO來得更好。因此，加入early termination的觀念能成功的縮短執行時間，而且回傳top K的結果，對使用者來說也算是足夠，畢竟使用者也不見得需要那麼多卻不一定相關的答案。

Proceedings of the 2006 ACM SIGMOD international conference on Management of data (SIGMOD) 2006