K 遗憾查询的几何方法

返回用户可能感兴趣的元组是多准则决策的最重要目标之一。顶部 k 查询和天际线查询都是两个具代表性的查询。顶部 k 查询其优点是向用户返回元组的数目有限，但需要用户给他们确切的效用函数。轮廓查询有其优点用户不需要给其确切的效用函数但没有控制着要返回的元组数目。在本文中，我们研究了 k 遗憾查询，最近提出的查询，综合两个具代表性的查询的优点。我们先找一些有趣的几何性质为 k 遗憾查询。我们基于这些属性，定义候选点称为快乐点 k 遗憾查询，不在文献中研究了一套。这一结果不仅所有现有的算法，还所有新算法，以针对 k 遗憾查询是非常基本并且互惠互利。自从发现快乐点数目很小，可以显著改善所有现有算法的效率。此外，基于其他的几何性质，提出了两种有效的算法，每一种比最著名最快的算法更有效地执行。我们的实验结果表明我们提出的算法比跑得快的最著名的方法在合成和真实数据集上。尤其是，在我们在真实数据集上的实验中，最著名的方法花了 3 小时的时间来回答 k 遗憾查询，但我们建议的方法之一，花了大约几分钟和另一次在一秒钟内