论文部分内容阅读
Top-k查询和反Top-k是数据库领域中两类重要的查询。给定一个用户偏好向量和一个产品数据集,Top-k查询在数据集中搜索用户最喜欢的k个产品返回给用户;给定一个目标产品、一个产品数据集和一个用户偏好向量集合,反Top-k查询在用户偏好向量集合中搜索目标产品出现在哪些用户的Top-k查询结果中。反Top-k查询的结果反映了用户集合中目标产品的潜在用户,在市场分析领域有重要应用价值。当商家使用反Top-k查询计算某产品的潜在用户时,若某些老客户没有出现在查询结果中,商家通常会提出Why-not问题,希望知道为什么这些客户没有出现在查询结果中?如何做才能使这些用户重新出现在查询结果中。这是Why-not反Top-k查询的一类典型应用场景,也是本文的研究动机之一。本文旨在设计高效准确的算法向商家提供查询修改建议,使得在修改后的查询中,目标客户群体出现在目标产品的反Top-k查询结果中,同时使得商家付出的成本最低。本文将通过两种方法求解Why-not反Top-k查询问题:(1)修改用户偏好向量集合W_m,(2)修改用户偏好向量集合W_m和参数k。对于修改W_m问题:本文提出P-CTA-I算法,在用户偏好空间建立完整索引然后搜索最优解;BFS-I算法在此基础上根据问题特性,通过优化搜索顺序,只构建偏好空间中的问题相关部分,提升了算法性能;进一步,RH-I算法使用优先队列索引用户偏好空间,使用超平面过滤技术进一步提升了算法的性能。对于修改W_m和k问题,本文将其规约为修改W_m问题,然后根据问题特性提出了P-CTA-II算法、BFS-II算法、RH-II算法。最后在真实数据集和随机数据集上进行了大量实验,在不同的参数下分析和验证了优化的有效性和算法的性能。本文的主要贡献列举如下:(1)首次提出通过修改用户偏好向量集合W_m解决Why-not反Top-k查询问题;(2)首次提出修改W_m、修改W_m和k两种求解方式的最优解算法,据我们所知,目前国内外仍没有通过这两种求解方式解决Why-not反Top-k问题最优解算法;(3)在最优解算法的上做出有效优化提升了算法性能;(4)通过真实数据集和随机数据集上的大量实验测试了算法的性能。