有效集合相交-决定相交是否大于k

|| 我面临一个问题，我必须计算一组集合中所有对之间的交点。这些集合都不比小常数k小，我只对两个集合的交点是否大于k-1个元素感兴趣。我不需要实际的交集，也不需要确切的交集，只需要它是否大于k-1即可。有什么聪明的预处理技巧或整洁的交集算法可以用来加快速度吗？ 更多有助于回答问题的信息： 这些集合代表一个大型的，无向的，稀疏图中的最大集团。集合的数量可以在数万个或更多的数量级，但是大多数集合可能很小。 这些集合已经被排序，每个集合的成员以递增的顺序排列。实际上，它们是排序列表-我从底层库以这种方式接收它们，以实现最大的集团搜索。 关于集合中元素的分布一无所知（即它们是否紧密聚集）。 大多数设置交集很可能是空的，因此理想的解决方案是一个聪明的数据结构，该结构可以帮助我减少必须制作的设置交集的数量。     
2020-01-05 5 条评论
分享

没有找到相关结果

    已邀请:

    体悉

    考虑将所有大小为k的集合作为键的映射，并将集合中包含该键作为子集的所有集合的列表的对应值。有了这种映射，您就不需要执行任何交集测试：对于每个键，列表中的所有对集的交集大小都至少为k。这种方法可以多次产生同一对集合，因此需要进行检查。 映射很容易计算。对于集合中的每个集合，计算所有大小为k的子集，并将原始集合附加到该密钥集的列表中。但这实际上更快吗？一般来说，没有。这种方法的性能将取决于集合中集合大小的分布以及k的值。在集合中有d个不同的元素时，您最多可以选择d个选择k个键，这可能非常大。 但是，基本思想可用于减少交叉点的数量。与其使用大小为k的集合，不如使用固定大小为q的较小集合作为键。这些值再次是将键作为子集的所有集合的列表。现在，从列表中测试每对集合的交集。因此，使用q = 1时，您仅测试那些具有至少一个共同元素的集合对，使用q = 2时，您仅测试那些具有至少两个共同元素的集合对，依此类推。我认为，q的最佳值将取决于集合大小的分布。 对于所讨论的集合，一个很好的选择可能是q = 2。然后，关键点只是图形的边缘，从而为映射提供了可预测的大小。由于大多数集合预计是不相交的，因此q = 2应该消除很多比较而没有太多额外开销。     
    2020-01-05 0 0
    分享

    曝匿弄罚

    每个集合中包含的值范围越小，一种可能的优化越有效： 创建所有集合的列表，并按其kth-greatest元素排序（这很容易找到，因为您已经拥有每个集合及其元素的顺序）。将此列表称为L。 对于任何两个集合A和B，如果A中的第k个最大元素小于B中的最小元素，则它们的交集最多可以包含k个元素。 因此，对于每个集合，依次仅计算其与L相关部分中的集合的交集。 您可以使用相同的事实从计算任意两个集合的相交处提前退出-如果其中只有一个要比较的n-1个元素，而到目前为止该相交最多包含k-n个元素，则停止。上面的过程只是简单地将此规则立即应用于L中的所有集合（n = k），此时我们正在看集合B的最小元素和A的第k个最大元素。     
    2020-01-05 0 0
    分享

    倪蕊悲潍

    以下策略应该非常有效。在很多情况下，我使用了这种形式的变体来相交升序。 首先，我假设您有某种优先级队列可用（如果没有，则滚动自己的堆非常容易）。快速键/值查找（btree，哈希等）。 话虽如此，这是一种算法的伪代码，该算法应该可以有效地完成您想要的操作。 
    # Initial setup
sets = array of all sets
intersection_count = key/value lookup with keys = (set_pos, set_pos) and values are counts.
p_queue = priority queue whose elements are (set[0], 0, set_pos), organized by set[0]

# helper function
def process_intersections(current_sets):
    for all pairs of current_sets:
        if pair in intersection_count:
            intersection_count[pair] += 1
        else:
            intersection_count[pair] = 1

# Find all intersections
current_sets = []
last_element = first element of first thing in p_queue
while p_queue is not empty:
    (element, ind, set_pos) = get top element from p_queue
    if element != last_element:
        process_intersections(current_sets)
        last_element = element
        current_sets = []
    current_sets.append(set_pos)
    ind += 1
    if ind < len(sets[set_pos]):
        add (sets[set_pos][ind], ind, set_pos) to p_queue
# Don\'t forget the last one!
process_intersections(current_sets)

final answer = []
for (pair, count) in intersection_count.iteritems():
    if k-1 < count:
        final_answer.append(pair)
    运行时间为
    O(sum(sizes of sets) * log(number of sets) + count(times a point is in a pair of sets)
    。特别要注意的是，如果两个集合没有交集，则永远不要尝试将它们相交。     
    2020-01-05 0 0
    分享

    磐剩

    如果您使用预测性子集作为预选资格该怎么办。预排序，但将子集交集用作阈值条件。如果子集交集> n％，则完成交集，否则放弃。然后，n变为您的舒适水平的倒数，并且有可能出现误报。 您还可以按较早计算出的子集交集（m）排序，然后开始运行按m降序排列的完整交集。因此，大概最高的m个交叉点的大部分可能会在整个子集上超过k个阈值，并且达到k个阈值的可能性可能会不断降低。 这真的开始将问题视为NP-Complete。     
    2020-01-05 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.037804126739502