ICDM—–Continuous KNN Join Processing for Real-time Recommendation

社交网中用户生成的内容数据爆炸式地增长,使得向用户推荐他/她感兴趣的内容这一功能变得必要。这些推荐在出现新内容时,必须实时地呈现给用户,因为在用户浏览推荐内容的时候,是否“最新”是一个非常重要的考虑因素。

在高维空间中,用户和内容被表示成特征向量,我们可以把实时推荐问题转换成计算每个用户间的最近邻(KNN)值,这就是我们常说的近邻连接(KNN join)。

面对数量庞大的用户和数据,最大的挑战就是:在新内容出现时,如何更新近邻连接值。现有求解数据流中增量近邻连接的方法都不能解决维度灾难和搜索时需要过多占用内存的问题。

在这篇论文中,作者提出了一个解决办法:在新内容出现时,首先识别那些KNN值被影响的用户,对这些用户的KNN值进行逐个更新。为了更有效地找到这些被影响的用户,我们提出了一个新的索引结构——HDR-tree。

为了实现高效率搜索,HDR-tree通过聚类和主成分分析(PCA)来削减维度。此外,为了进一步提高反应时间,作者提出了一个HDR-tree的变体——HDR*-tree,这样可以提高效率但是只是求出近似解。

经过多次实验结果检验,作者的方法比基线法有效。

anyShare分享到:
This entry was posted in 新闻动态. Bookmark the permalink.

发表评论