一种处理Top-k逆向查询的分支界定算法  

A Branch-and-Bound Algorithm for Processing Reverse Top-k Queries

作　　者：刘亦韬 胡维华[1] 

机构地区：[1]杭州电子科技大学计算机院,浙江杭州310018

出　　处：《杭州电子科技大学学报（自然科学版）》2014年第6期76-79,共4页Journal of Hangzhou Dianzi University：Natural Sciences

摘　　要：Top-k逆向查询在现实生活中有着广泛应用。目前,计算Top-k逆向集最有效的算法是逆向Top-k算法。该算法的效率在处理Top-k逆向查询时受到明显的限制。为了解决这些限制,提出一种直观的分支定界算法来高效地处理Top-k逆向查询,并讨论新颖的优化方法以提其高能。实验评估表明,该算法的效率远胜于逆向Top-k算法。Reverse Top-k queries have already attracted significant interest in research, due to numerous real-life applications such as market analysis and product placement. Currently, the most efficient algorithm for computing the reverse Top-k set is reverse Top-k algorithm （RTA）. However RTA has some drawbacks when processing a reverse Top-k query. To address these limitations, in this paper, we identify useful properties for processing reverse Top-k queries without accessing each user＇s individual preferences or executing the Top-k query. An intuitive branch-and-bound algorithm is proposed for processing reverse Top-k queries efficiently while discussing novel optimizations to boost its performance. Experimental evaluation demonstrates the efficiency of the proposed algorithm that outperforms RTA by a large margin.

关 键 词：Top—k逆向查询 分支界定算法 逆向 TOP-K 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]