廈門大學(xué)數(shù)據(jù)庫實(shí)驗(yàn)室論文進(jìn)展報(bào)告（4）

1、廈門大學(xué)數(shù)據(jù)庫實(shí)驗(yàn)室廈門大學(xué)數(shù)據(jù)庫實(shí)驗(yàn)室論文進(jìn)展報(bào)告（論文進(jìn)展報(bào)告（4 4）報(bào)告人：謝榮東指導(dǎo)老師：林子雨2015年8月7日論文概述論文概述u論文題目：Multi-query diversification in microblogging postsu論文參考文獻(xiàn)格式：Cheng S, Arvanitis A, Chrobak M, et al. Multi-Query Diversification in Microblogging PostsC/EDBT. 2014: 133-144.u時(shí)間：2014年EDBT會(huì)議論文概述論文概述u解決的問題：基于微博的多元素查詢下的多樣性問題u與以前的

2、不同：以前都是考慮單一關(guān)鍵詞或者單一元素下的多樣性問題u解決方法：引入動(dòng)態(tài)規(guī)劃的方法，不斷迭代得到最優(yōu)解動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃概念定義概念定義uL：query的集合，即查詢關(guān)鍵詞的集合，set of auP：結(jié)果集合，每個(gè)查詢結(jié)果都至少關(guān)聯(lián)一個(gè)關(guān)鍵詞，set of pu：閾值，界定結(jié)果在某一個(gè)維度上之間的相關(guān)關(guān)系u ：表示Pi在關(guān)鍵詞a的關(guān)聯(lián)度上被Pj包含舉例說明舉例說明P1，P2，P3，P4即各個(gè)查詢結(jié)果，a、b、c為查詢的關(guān)鍵詞我們?cè)O(shè)為各分片間的時(shí)間距離。則可知：問題定義問題定義u定義一:(Post cover)設(shè)一個(gè)結(jié)果子集Z為部分結(jié)果的集合，對(duì)于某個(gè)結(jié)果Pi，如果對(duì) Z中都存在一個(gè)Pj，使得u定義二:(Set -cover)P是一個(gè)有限的集合，它是查詢結(jié)果的全集， 且 。若P中任意Pi，均有問題定義問題定義uMQDP問題：給定輸入（P，）,求關(guān)于P的最小集合Z，基于問題集合L，能夠包含P。OPTOPT算法算法u定義1：各個(gè)結(jié)果之間用時(shí)間進(jìn)行排序，即對(duì)與P1，P2Pn，有t1t2tn.時(shí)間越大，表示結(jié)果越新。u定義2：label(Pi)表示Pi所關(guān)聯(lián)的關(guān)鍵字。增加一個(gè)新的元素P0，且label(P0)=L。u定義3：f(j):與tj相差不超過的最大結(jié)果tj的序號(hào)ju定義4： ，示例示例u起始條件：u遞進(jìn)條件：u最優(yōu)