Подтвердить что ты не робот

Управляемая разработка общих подструктур в большом наборе графиков

У меня есть большой ( > 1000) набор ориентированных ациклических графов с большим ( > 1000) набором вершин каждый. Вершины помечены, мощность ярлыка мала (< 30)

Я хочу идентифицировать (мои) подструктуры, которые часто появляются во всем наборе графиков.

  • Подструктура представляет собой график по крайней мере двух непосредственно связанных вершин с определенными метками. Такая субструктура может появляться один или несколько в одном или нескольких из приведенных входных графов. Например, "[вершина с меткой A с двумя непосредственно связанными дочерними элементами, помеченная B], появляется дважды на графике U и один раз на графике V".
  • Подструктура, которую мы ищем, должна подчиняться набору заданных правил, которые фильтруют метки ярлыков. В качестве примера: подструктура, содержащая вершину, помеченную A, интересна, если подграфом является "вершина, помеченная буквой A, которая имеет хотя бы один непосредственно связанный дочерний элемент, помеченный буквой B, и не является непосредственно связанным собором вершины с меткой U или V", Подструктуры, которые не соответствуют этим правилам, могут отображаться на входных графах, но не представляют интереса для поиска.

Вывод, который мы ищем, представляет собой список подструктур и их (количество) появлений на данных графиках.

Я попытался заглянуть в вещи и (как это всегда случается со мной) проблема NP-полная. Насколько я вижу, gSpan является наиболее распространенным алгоритмом для решения этой проблемы. Однако, как указано выше, я не ищу какую-либо общую подструктуру на графиках, а только те, которые подчиняются определенным правилам. Нужно иметь возможность использовать это, чтобы уменьшить пространство поиска.

Любое понимание того, как подойти к этой проблеме?

Обновление: я должен, вероятно, добавить, что вышеупомянутые правила могут быть рекурсивными до некоторой степени. Например, "вершина с меткой A с по меньшей мере двумя детьми, помеченными буквой B, каждая из которых имеет хотя бы один дочерний элемент, помеченный буквой A". Максимальная глубина рекурсии составляет от 1 до 10.

Обновление II: указывая на то, что мы не ищем известные или предпочтительные подструктуры, а добываем их. Нет иглы spoon.

4b9b3361

ОТВЕТЫ

Ответ 1

Я предполагаю в своем ответе, что вы пытаетесь свести к минимуму время работы и не хотите тратить слишком много времени на создание кода для этого. Одна вещь, с которой я боролся сначала, когда училась писать высокоэффективные алгоритмы, заключалась в том, что иногда несколько проходов могут быть более эффективными. В этом случае, я бы сказал, в принципе, вы хотите иметь два прохода:

Сначала создайте фильтр, который позволяет игнорировать большинство (если не все) не дублированных шаблонов. Для этого:

  • Выделить два битных массива (и при этом учитывать размеры кеша). Первый будет простым фильтром цветения. Второй будет дублирующим фильтром цветения.
  • Когда вы проходите структуру на первом проходе, для каждой индексируемой структуры вычисляйте хэш-значение. Выберите соответствующий бит в первом фильтре цветения и установите его. Если этот бит уже был установлен, также установите соответствующий бит в дубликатном фильтре цветения.

На вашем втором проходе вам нужно будет выполнить "тяжелый" процесс фактического подтверждения матчей. Для этого выполните следующие действия:

  • Снова сканируйте график и запишите любые структуры, которые соответствуют фильтру дублирования цветков, сгенерированному в первый проход.
  • Поместите те, которые соответствуют хэш-таблице (в идеале, используя разные биты из вычисленного хэша)
  • Когда обнаружен дубликат, сохраните эту информацию, где бы вы ее не собирали.

Этот алгоритм будет работать очень быстро на больших наборах данных, поскольку он значительно снизит давление на соответствующий уровень кеша. Есть также несколько улучшений, которые вы можете сделать, чтобы сделать его лучше в разных обстоятельствах.

  • Чтобы повысить производительность многопоточной системы, на самом деле безопасно распараллеливать первый шаг. Чтобы сделать это, дайте каждому потоку (или компьютеру в кластере) фрагмент графика. Каждый должен вычислить свою собственную копию двух цветов. Затем цветки можно объединить в последний цвет. Функция восстановления справедлива (присутствует, дублируется) = (present1 ИЛИ present2, duplicate1 ИЛИ duplicate2 OR (present1 AND present2)). Этот шаг очень быстрый.
  • Также безопасно распараллелить второй шаг, но его нужно немного изменить. Чтобы сделать это, вы берете дублирующий фильтр цветения с первого шага и используете его как фильтр на втором этапе, как и раньше. Однако вы не можете завершить окончательное сравнение так же легко. Вместо этого вы должны поместить потенциальные дубликаты в хэш-ведра. Затем, после того, как каждый осколок данных был записан в собственный список потенциальной повторяющейся хеш-таблицы, разделите данные вверх на хэш-ведро и на третьем шаге найдите дубликаты. Каждое хэш-ведро (с любого выхода на втором этапе) должно обрабатываться одним и тем же работником.
  • В случаях, когда у вас есть большое количество структур, которые вы индексируете, вы можете повысить производительность за счет рекурсивного применения вышеуказанного алгоритма. Настройка состоит в том, что вы используете каждую подходящую категорию для выхода из вышеуказанного алгоритма в качестве вашего ввода в рекурсивный проход. Например, если вы индексируете только структуры, которые имеют до 5 элементов в первом запуске алгоритма, вы можете, когда вы рекурсируете, взять каждый набор дублированных подграфов и запустить алгоритм только на этих субграфах. Это было бы необходимо только с очень большими наборами данных, очевидно.
  • Еще одна настройка, которую вы можете рассмотреть, если график очень большой, чтобы повысить эффективность ваших фильтров цветения, нужно перебирать алгоритм. Например, в первом проходе вы можете рассматривать только субграфы, которые имеют первую метку в качестве базы субграфа. Это уменьшит размер, необходимый вашим фильтрам цветка, и/или позволит вам отфильтровать больше субграфов на первом проходе.

Несколько примечаний для настройки выше:

  • Учитывайте размеры кеша. Например, на чипе Intel Haswell каждое ядро ​​имеет 32K в кэше L1 и 256K в кэше L2. Каждая строка кэша будет содержать 512 бит, поэтому, если вы пополните 1% фильтра цветения, будет затронута большая часть строк кэша. В зависимости от того, насколько быстро выполняются другие части алгоритма, и что другие вещи используют эти кеши, вы можете безопасно создать фильтр цветения, который содержит около 512 * 1024 записей (8 записей на бит на фильтр = 128k, на гиперпотоковых системах, что сколько L2 вы получаете) и по-прежнему поддерживают большую часть данных, установленных в кэше L2, и действительно активные элементы в L1. Для меньших наборов данных держите это число вниз, потому что нет смысла делать его большим. Если вы только отмечаете функции как потенциальные дубликаты, когда они составляют не менее 1% времени, это совершенно нормально.
  • Параллелизация этого снова снова очень полезна в тех случаях, когда у вас есть тонны данных. Я предполагаю, что вы могли бы. Если вы распараллеливаете, вы должны рассмотреть геометрию. Использование этого алгоритма будет работать с частичными наборами данных на каждом компьютере. Затем вы можете запускать каждую итерацию (в варианте № 4) на каждом компьютере. В тех случаях, когда у вас есть огромные наборы данных, которые не позволят передавать все данные на все компьютеры.

В любом случае, чтобы подвести итог заявлению о сложности выполнения, я скажу, что это действительно зависит. Многие люди игнорируют тот факт, что увеличение рабочего набора данных приведет к тому, что доступ к памяти не будет одинаковым по стоимости. В сущности, вышеприведенный алгоритм, хотя и высокоэффективный, если он настроен соответствующим образом, будет работать очень быстро на небольшом наборе данных, но он действительно сияет с гораздо большими наборами данных, поскольку он позволяет эффективно использовать рабочий набор данных на любом уровне кеша (L1, L2, L3, ОЗУ, локальный диск, локальная сеть и т.д.). Сложность алгоритма будет зависеть от данных, но я не верю, что алгоритм намного быстрее может быть создан. Я не обращал внимания на то, как вы представляете подграфы, и там есть работа над достижением оптимального алгоритма, но, не зная большего, я не могу определить лучший способ сохранить эту информацию.

Причина, по которой алгоритм не может работать намного быстрее, чем тот, который я представил, заключается в том, что для первого прохода потребуется гораздо меньше работы, чем для второго, потому что он не требует разветвления и меньше работы побитовые операции. Поэтому мы можем сказать, что он мало добавляет к общей работе, которую мы делаем. Второй этап также настолько эффективен, насколько это возможно. Вы должны (запретить способ идеально описать каждую возможность с помощью конечного набора битов, который я объясню в секунде) фактически сравнить каждую функцию графика и записать информацию где-нибудь. Единственной переменной является то, сколько работы нужно проверить, нужно ли вам это делать. Проверка бит, в которой вы можете произвольно масштабировать частоту ошибок до 0%, так же хороша, как вы можете получить.

Для небольших наборов данных причина, по которой два прохода приносит вам пользу, заключается в том, что у вас может быть гораздо большее количество мощности цветения в меньшем объеме памяти. Но для действительно небольших наборов данных вы можете просто использовать второй шаг и игнорировать первый. Но, как минимум, вам нужно будет сохранить указатель для каждой хэш-цели. Это означает, что вам нужно будет записать в 32 или 64 раза больше данных для того же уровня фильтрации. Для небольших наборов данных это не имеет значения, потому что чтение является чтением, а запись - записью, но для более крупных наборов данных это может позволить вам выполнить тот же уровень фильтрации, оставаясь на заданном уровне кеширования. В тех случаях, когда вы должны работать на нескольких компьютерах или потоках, механизм, предусмотренный в этом алгоритме, будет более эффективным, поскольку данные могут быть объединены намного быстрее, и гораздо больше информации о возможных совпадениях можно обменять.

Теперь, наконец, как я уже говорил, вы можете быть немного лучше, если количество функций, которые вы проверяете на каждой итерации, будет уменьшено. Например, если вы проверяете только 32 возможных ярлыка и количество детей с определенной меткой в ​​каждом проходе (и это ограничено 1024), вы можете представить это с 15 бит. Если вы ограничили число до 255, вы можете сохранить эту информацию с 32K. Чтобы это сделать в вашем случае, вам нужно будет использовать стратегии итерации, рекурсии и осколки, о которых я говорил выше, и вам нужно будет также отслеживать исходный граф и другую информацию. Я, честно говоря, сомневаюсь, что это будет хорошо работать, за исключением очень ограниченных ситуаций, но я включаю его для полноты.

Во всяком случае, это мой первый ответ на Stack Overflow, так что не слишком сильно на меня. Надеюсь, это было полезно!

Ответ 2

Как я прочитал ваш вопрос, вам может понадобиться что-то вроде кода ниже. Он находит все соответствующие подграфы в DAG в линейном времени. Он не поддерживает фильтры, но вы можете проверить результаты после их обнаружения и отфильтровать их вручную. Он также может найти графики с некоторыми деталями. Предположим, что вы ищете дерево a((b|c)|(c|d)), тогда он может найти подграф, где c node разделяется между двумя поддеревами. Опять же, вы можете проверить результаты и отфильтровать результаты, подобные этому. Выполнение такой проверки, конечно, возможно только в том случае, если размер вывода не слишком велик. Для этого вам понадобятся некоторые эксперименты на ваших собственных графиках.

from collections import namedtuple, defaultdict
Node = namedtuple('Node', ['label', 'children', 'id'])

# Simple tree patternA(B|AB)
pattern = Node('A', (Node('B', (), 1),
                     Node('A', (Node('B', (), 3),), 2)), 0)

# Generate random DAG
import random
labels = 'ABCDE'
dag = []
for _ in range(1000):
    label = random.choice(labels)
    children = tuple(random.sample(dag, min(len(dag)//2, 10)))
    dag.append(Node(label, children, len(dag)))

# Helper
def subtrees(pattern):
    yield pattern
    for sub in pattern.children:
        yield from subtrees(sub)

colors = defaultdict(list)
# Iterate the nodes in topologically sorted order
for node in dag:
    # Check if the node is the head of some sub-pattern
    for sub in subtrees(pattern):
        if node.label == sub.label \
                and all(any(sc.id in colors[nc.id]
                    for nc in node.children) for sc in sub.children):
            # If so, color the node with that sub-pattern color
            colors[node.id].append(sub.id)

matches = [node for node in dag if pattern.id in colors[node.id]]
print('Found {} matches.'.format(len(matches)))

Я считаю, что это очень похоже на подход, который имел в виду Штефан Хаустейн.

Ответ 3

Изменить. Вот что я хотел бы начать с:

  • Создайте индекс 30x30 возможных комбинаций родительских/дочерних элементов с соответствующими узлами
  • Пересечение совпадений для данной подструктуры
  • Проверить дополнительные условия вручную

(Исходный пост):

  • Найти способ создания хеш-ключей для подструктур
  • Создание хэш-карты от подструктур до соответствующих узлов
  • Найти кандидатов с помощью хэш-карты, проверить подробные условия вручную

Ответ 4

Ваш вопрос:

У вас есть - набор графиков и набор правил (пусть назовем правило шаблоном подструктуры).

Вы хотите - подсчет появления каждой из подструктур в наборе графиков.

Так как диаграммы являются DAG, в поиске подструктуры вы не будете пойманы в цикле.

Псевдокод простого решения:

for each graph G {                           //Sub-problem 4
    for each node N {                        //Sub-problem 3
        for each substructure pattern P {    //Sub-problem 2
            if N structure is like P {     //Sub-problem 1
                PatternCountMap.Get(G).Get(P)++;
            }
        }
    }
}

В каждом месте я помечен подзадачей, которую нужно обработать.

Если вы не знаете Map-Reduce, мое решение не будет полностью вам понятным. Дайте мне знать, если это произойдет. В общем случае код Map-Reduce всегда можно запускать в общем режиме программирования, за исключением того, что для больших данных потребуется больше времени.

Под-проблема 1

Эта проблема может быть просто записана как:

Учитывая "корень" node и заданный шаблон P, соответствует ли дерево, представленное этим node, как root, следующему шаблону?

Эта проблема разрешима. Просто пройдите вниз по графику, начиная с "root" и посмотрите, соблюдается ли шаблон. Если это так, увеличьте его количество в PatternCountMap, в противном случае перейдите к следующему шаблону и посмотрите, следует ли "корень" следовать следующему шаблону.

PatternCountMap - это HashMap > который отображает графики в другую HashMap, которая отображает Patterns на их частоту. Итак, если P найден в графах G 1 и G 2, 12 и 17 раз соответственно, тогда PatternCountMap.Get(G 1). Get (P) будет равен 12 и PatternCountMap.Get(G 2). Get (P) будет равен 17 в конце выполнения этого алгоритма.

Полезный совет: поскольку вы не хотите слишком много усваивать, используйте итеративные решения. Если вам нужно выполнить DFS, выполните итеративную DFS, используя стек. Итеративный алгоритм DFS довольно прост.

Суб-проблема 2

Здесь мы просто перебираем каждый шаблон (или правила). Здесь нет волшебства. Для каждого правила мы видим, что node N графа G следует правилу.

Полезный совет: предварительная обработка правил. Например, если следовать одному правилу, см., Какие другие правила могут быть обязательно соблюдены, чтобы пропустить их. Или, если после одного шаблона означает, что за ним может следовать еще один, посмотрите, может ли сокращаться второе правило из-за проверки, уже сделанной как часть первого.

Подзадача 3 и 4

Эти два являются простыми петлями снова, как Sub-problem 2. Но есть одна идея, которая может быть применена здесь. И это Map-Reduce (хотя [1] Map-Reduce не соответствует 100% для этих проблем).

У вас есть многочисленные узлы из множества разных графиков. Пока вы можете определить граф, к которому принадлежит node, если конкретный node следует за определенным шаблоном, вы можете испустить <N_G, P>, что означает, что node N в графе G следует шаблону (aka rule ) P.

Выходные данные карты могут быть собраны в редукторах, которые могут заполнять значения PatternCountMap. Большая часть из них обрабатывается картой Map-Reduce, поэтому многие вещи будут заботиться о вас автоматически.

После создания PatternCountMap у вас есть счет каждого полезного шаблона на каждом графике, и именно это вы хотели.

[1] Map-Reduce - это проблемы, которые могут быть решены на товарном оборудовании. Если правила, которые вы используете, являются сложными, тогда товарное оборудование может быть не таким, на котором вы хотите запустить свой алгоритм.