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

這篇paper是來自於SIGMOD 2006，主要是探討給定一些keyword query時，我們想要去某些document尋找相關的target object to match query，不過若是要進行完整的搜尋，事實上是很浪費時間且不切實際的，其實我們只需要找出最好的前k項就足夠了。因此，這篇paper就是以上述為目標，來進行如何計算object score與如何提升效能節省時間的early termination之研究。
在paper中主要分成下列幾點:
1.界定document與object，以及他們之間的關係。舉例來說，在expert finder的應用上，我們想要搜尋的document是paper，而我們想要找尋的target object，也就是user所要的答案，是paper的author。而我們會用一個table來記錄document與object之間的包含關係，也就是我們在某個document內發現哪些target object，這些紀錄有助於之後的分數計算。
2.接下來是System Overview。在這篇paper中，我們對於每個document搜尋符合keyword的方法，都是FTS(Full Text Search)。對於每個single keyword w，我們會得到一對應的ranked list，裡面包含了符合這keyword的document，並按照分數高低來排列。
3.作者提出了兩種scoring function，一個是row marginal class，另一個是column marginal class。Row marginal class是先對each document做所有的keyword分數之combine，再對combine後的分數作aggregation。而Column marginal class是先對each keyword做aggregation，再對所有的document分數做combination。在此篇paper中，我們用的是column marginal class。
4.接下來是此篇paper的重點，他們提出了一個early termination的觀念，也就是說當我們確定找出了最好的k個target object，而且之後所搜尋的object都不會比這k個更好的話，我們就可以停止搜尋並回傳結果了。其中又分為generate-prune approach and generate-only approach。generate-prune approach用的是先產生一size大於k的candidate set，再做pruning得到final k。而generate-only則是會不斷產生直到符合某stopping criterion為止。
最後實驗證明，使用early termination的generate-prune(GP)與generate-only(GO)的執行時間皆比原本的SQL好上幾倍，而GP比GO來得更好。因此，加入early termination的觀念能成功的縮短執行時間，而且回傳top K的結果，對使用者來說也算是足夠，畢竟使用者也不見得需要那麼多卻不一定相關的答案。
SIGMOD 2006 : Ranking Objects by Exploiting Relationships