Enumeration problems aim at outputting, without repetition, the set of solutions to a given problem instance. However, outputting the entire solution set may be prohibitively expensive if it is too big. In this case, outputting a small, sufficiently diverse subset of the solutions would be preferable. This leads to the Diverse-version of the original enumeration problem, where the goal is to achieve a certain level d of diversity by selecting k solutions. In this paper, we look at the Diverse-version of the query answering problem for Conjunctive Queries and extensions thereof. That is, we study the problem if it is possible to achieve a certain level d of diversity by selecting k answers to the given query and, in the positive case, to actually compute such k answers.
翻译：点数问题旨在为特定问题实例输出一系列解决方案,而不重复。 但是, 输出整个解决方案集如果过于庞大, 可能费用太高, 实在太高。 在这种情况下, 输出一个小的、 足够多样化的解决方案子集是可取的。 这导致原始查点问题的多样化转化, 最初查点问题的目标是通过选择 k 解决方案达到一定的多样化程度 。 本文我们查看对连接查询及其扩展的查询解答问题的多样化转换 。 也就是说, 我们研究问题, 如果有可能通过选择 k 回答给定的询问来达到一定的多样化水平, 并在正面的情况下, 实际计算这样的 k 答案 。
相关内容
微信扫码咨询专知VIP会员