计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2013年
5期
986-997
,共12页
蒋涛%张彬%高云君%乐光学
蔣濤%張彬%高雲君%樂光學
장도%장빈%고운군%악광학
算法%Topk查询%动态Skyline%可逆Skyline%相互Skyline
算法%Topk查詢%動態Skyline%可逆Skyline%相互Skyline
산법%Topk사순%동태Skyline%가역Skyline%상호Skyline
Top-k相互Skyline查询返回相互Skyline查询中的前k个对象.这种查询是数据分析者寻找有意义对象进行决策支持的一种重要直觉工具.然而,这种查询还没有引起研究社区足够的注意力.介绍了几种新颖的算法,包括Topk-TBBS,Topk-dMBBS,Topk-wMBBS.主要的思想是信息重用和高效的修剪策略.特别地,Topk-wMBBS算法由于完全重用了搜索中的节点信息,并利用了最好优先BF搜索策略.因而它获得了最好的性能.同时证明了该算法有最优的I/O访问效率.最后,使用了2个真实数据集和4个服从不同分布的合成数据集进行了集中实验.实验结果表明,提出的算法无论是变化参数k的大小、数据集的尺寸和Cache尺寸都是有效的,且具有很高的效率,尤其Topk-wMBBS具有最小的I/O访问次数.
Top-k相互Skyline查詢返迴相互Skyline查詢中的前k箇對象.這種查詢是數據分析者尋找有意義對象進行決策支持的一種重要直覺工具.然而,這種查詢還沒有引起研究社區足夠的註意力.介紹瞭幾種新穎的算法,包括Topk-TBBS,Topk-dMBBS,Topk-wMBBS.主要的思想是信息重用和高效的脩剪策略.特彆地,Topk-wMBBS算法由于完全重用瞭搜索中的節點信息,併利用瞭最好優先BF搜索策略.因而它穫得瞭最好的性能.同時證明瞭該算法有最優的I/O訪問效率.最後,使用瞭2箇真實數據集和4箇服從不同分佈的閤成數據集進行瞭集中實驗.實驗結果錶明,提齣的算法無論是變化參數k的大小、數據集的呎吋和Cache呎吋都是有效的,且具有很高的效率,尤其Topk-wMBBS具有最小的I/O訪問次數.
Top-k상호Skyline사순반회상호Skyline사순중적전k개대상.저충사순시수거분석자심조유의의대상진행결책지지적일충중요직각공구.연이,저충사순환몰유인기연구사구족구적주의력.개소료궤충신영적산법,포괄Topk-TBBS,Topk-dMBBS,Topk-wMBBS.주요적사상시신식중용화고효적수전책략.특별지,Topk-wMBBS산법유우완전중용료수색중적절점신식,병이용료최호우선BF수색책략.인이타획득료최호적성능.동시증명료해산법유최우적I/O방문효솔.최후,사용료2개진실수거집화4개복종불동분포적합성수거집진행료집중실험.실험결과표명,제출적산법무론시변화삼수k적대소、수거집적척촌화Cache척촌도시유효적,차구유흔고적효솔,우기Topk-wMBBS구유최소적I/O방문차수.
