高效交集 - 決定交集是否大於k

我遇到了一個問題，我必須計算集合集合中所有對之間的交集。沒有一個集合小於一個小常量，我只關心兩組是否具有大於或不是大於零的交集。我不需要實際的交叉點，也不需要確切的尺寸，只需要是否大於k -1。是否有一些聰明的預處理技巧或我可以用來加快速度的整潔交集算法？高效交集 - 決定交集是否大於k

更多信息，可以是有用的回答這個問題：

的集代表在一個大的，無向，稀疏圖最大派系。套的數量可以是幾萬或更多的數量級，但是大多數套可能很小。
~~集已經排序~~ 每套成員的升序排列。實際上，它們是排序列表 - 我從底層庫以這種方式接收它們以進行最大集團搜索。
對組中元素的分佈（即它們是否緊密團塊）沒有任何瞭解。
大多數設置的交叉點很可能是空的，所以理想的解決方案將是一個聰明的數據結構，它可以幫助我減少我必須設置的交集的數量。

來源

2011-04-27 Tamás

每套的內容基本上是隨機的嗎？如果不是這樣，也許你可以用最大的元素排列左邊的集合，用最小的順序排列集合，從而避免考慮很多空的交點。如果大多數集合都包含一堆附近的值，那麼這將工作得很好，而且如果大多數集合都包含最小和最大可能元素，那麼這將非常有效...... – 2011-04-27 11:34:13

呃......也許這個問題並不清楚;沒有「左」或「右」的一面，我只有一套集合。這些集合實際上是圖中頂點的最大集合，我正在尋找具有至少* k *個頂點的交集的集合對。 – 2011-04-27 12:03:21

比較兩組時，任意將其中一個稱爲「左」，另一個稱爲「右」。 – 2011-04-27 12:51:01

考慮一個mapping，其中所有的大小爲k的集合作爲鍵和集合中包含該鍵作爲子集的所有集合的列表的對應值。給定這個映射，你不需要執行任何交集測試：對於每個關鍵字，列表中的所有集合對都會有一個至少爲k的交集。這種方法可以不止一次地產生相同的一組數據，因此需要進行檢查。

映射很容易計算。對於集合中的每個集合，計算所有size-k子集，並將原始集合追加到該集合的列表中。但是這實際上更快嗎？一般來說，沒有。這種方法的性能取決於集合中集合大小的分佈和k的值。在集合中有d個不同的元素時，可以有多達d個選擇k個鍵，這可能非常大。

然而，基本思想是可用的，以減少交叉點的數量。不要使用大小爲k的集合，而應使用固定大小爲q的小數字作爲關鍵字。這些值又是所有將密鑰作爲子集的集合的列表。現在，從列表中測試每對交集。因此，在q = 1的情況下，您只測試那些至少有一個共同元素的集合對，q = 2時只測試那些至少有兩個共同元素的集合對，等等。我認爲，q的最佳值取決於組的大小分佈。

對於有問題的集合，一個好的選擇可能是q = 2。這些鍵就是圖的邊緣，給映射提供可預測的大小。由於大多數集合預計不相交，因此q = 2應該消除大量比較而沒有太多額外開銷。

來源

2011-04-29 13:59:17

最後我還有一段時間來實施和測試這個版本，結果證明這是迄今爲止發佈的所有解決方案中最快的。對於20K的派系來說，它比亞軍快了近10倍。 – 2011-05-05 20:11:26

@Tamás很高興爲你效勞！你爲q使用了什麼價值？ – 2011-05-06 06:41:00

q = 2完美無缺 - 至今我還沒有嘗試過q = 3。 – 2011-05-06 08:29:36

一個可能的優化，這是更有效的較小包含在每個組值範圍：

創建的所有組的列表，由他們進行排序的第k最大元素（這是很容易找到，因爲你已經有了每一組元素）。調用此列表L.
對於任何兩個集合A和B，它們的交集不能有多達它k個元素，如果A中的第k最大元素小於最小元素B.
所以，依次計算其交集，只計算與其相關部分集合的交集。

您可以使用相同的事實早日退出計算任意兩個集合的交集 - 如果只有n-1在其中一組中進行比較的元素以及到目前爲止的交集至多包含kn元素，然後停止。上述過程簡單地適用於L中的所有集合，其中n = k，在我們正在查看集合B的最小元素和A的第k個最大元素的點處。

來源

2011-04-29 13:04:42

這個很好用;我設法將7.61s（對於20000個派系）的不那麼幼稚的執行壓縮到5.8s;這些時間是每次三次試驗中最好的。我正在研究其他提議的解決方案，但這確實很有前途（也很簡單）。 – 2011-05-04 21:28:14

以下策略應該非常有效。我已經在很多場合使用了這種變化來交叉遞增序列。

首先，我假設你有一些優先隊列可用（如果沒有，滾動自己的堆很容易）。快速鍵/值查找（btree，hash，無論）。這就是說，這裏是一個算法的僞代碼，它應該能夠非常有效地做你想做的事情。

# 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)。特別要注意的是，如果兩組沒有交集，你就不會嘗試相交它們。

來源

2011-04-29 17:17:29 btilly

如果可以的話，我會贊成這兩次;我設法用C++實現了這個，它非常快。我會在一天左右發佈一些基準測試結果。 – 2011-05-05 08:43:46

如果您使用預測子集作爲預選者，該怎麼辦？預先排序，但使用子集交集作爲閾值條件。如果子集相交> n％，則完成交集，否則放棄。那麼n就會成爲你的舒適度的倒數，並有可能出現假陽性。

您也可以按先前計算的子集交點（m）進行排序，然後開始運行由m降序排列的完整交叉點。所以大概你最高的m個交叉點中的大多數可能會跨過你的k個門檻，並且你的k門檻可能會持續下降。

這真的開始把這個問題當成NP-Complete。

來源

2011-05-05 20:08:56 Rikon

高效交集 - 決定交集是否大於k

回答

相關問題