Блог

Главная - Вопросы по программированию - Neo4j Java API: проблемы с производительностью алгоритма широчайшего пути

Neo4j Java API: проблемы с производительностью алгоритма широчайшего пути

#java #algorithm #neo4j #graph-databases

#java #алгоритм #neo4j #графические базы данных

Вопрос:

я использую neo4j-enterprise edition версии 2.1.2, и у меня есть график с 229626 узлами и 1667834 отношениями. Графовая модель описывает, какой человек знает другого человека с заданной меткой времени в отношениях (включая идентификаторы для каждого человека).

Я попытался определить алгоритм для задачи с широчайшим путем, используя существующую реализацию Дейкстры Neo4j Java Core API (встроенный режим). К сожалению, он работает очень медленно. Но сначала позвольте мне показать вам некоторые детали моей текущей реализации:

  1. Определение алгоритма с помощью пользовательского CostEvaluator и PathExpander

     PathFinder<WeightedPath> finder = GraphAlgoFactory
.dijkstra(new   TimestampPathExpander(RelationType.KNOWS,
Direction.BOTH, 1401746400, depth),  new RelationshipCostEvaluator());

    Число «1401746400» представляет временную метку. Каждое отношение с меньшим или равным ему должно быть проверено. Я также ввел глубину, чтобы минимизировать длину пути и затраты на поиск.

  2. TimestampPathExpander

       @Override public Iterable<Relationship> expand(Path path, BranchState<String> state) {
        List<Relationship> results = new ArrayList<Relationship>();

        if(path.length() >= depth) {
        return results;
        }

        for (Relationship r : path.endNode().getRelationships(relationshipType,
        direction)) {
            // Traverse only relations for the given timestamp
            long relationTime = (long) r.getProperty("timestamp");
            if (relationTime <= timestamp) {
             results.add(r);
            }
    }
    return results;
}

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

  3. Пользовательский оценщик затрат

     @Override
public Double getCost(Relationship relationship, Direction direction) {
   double measure = significance.edgeStrength(relationship);
   return measure > 0 ? Double.MAX_VALUE - measure : 0;
}

Мера используется как значение емкости и вычисляется в соответствии с метрикой, включающей начальный и конечный узлы, а также взаимосвязь обоих. Поскольку дейкстра не может обрабатывать отрицательные веса ребер, я просто вычитаю из большого количества (Double.Max_value) мера и достижение тем самым того, что большие значения интерпретируются «дешевле». Возврат нуля — это угловой случай, который не следует трогать.

Вот как я разогреваю свой кеш:

     for ( Node n : GlobalGraphOperations.at(db).getAllNodes() ) {
        n.getPropertyKeys();
        for ( Relationship relationship : n.getRelationships() ) {
            Node start = relationship.getStartNode();
        }
    }

Я также использую программный кэш и следующие свойства graph.db с индексом идентификатора узлов и началом и концом отношений:

 neostore.nodestore.db.mapped_memory=3G
neostore.relationshipstore.db.mapped_memory=2G
neostore.propertystore.db.mapped_memory=100M
neostore.propertystore.db.strings.mapped_memory=500M
neostore.propertystore.db.arrays.mapped_memory=100M

neostore.propertystore.db.index.keys.mapped_memory=500M
neostore.propertystore.db.index.mapped_memory=500M

use_memory_mapped_buffers=true

Вот некоторые показатели производительности всегда с разогретым кэшем:

 Cache warmup...    |   Cache warmup...
1742 ms            |   30056 ms
1106 ms            |   22696 ms
970 ms             |   24406 ms
849 ms             |   22842 ms
Angela Merkel      |   Angela Merkel
0.3                |   0.3
CDU                |   Wladimir Putin

Около 3 секунд только для перехода. Это довольно много. Есть ли какие-то приемы, которые я не знаю, чтобы улучшить эти результаты? Может быть, я сделал что-то не так? Надеюсь, кто-нибудь может помочь.

С уважением.

Комментарии:

1. Господи. Приемлемо быстрая реализация алгоритма Дейкстры занимает примерно столько же кода, сколько ваш «расширитель». У вас 200 тыс. узлов и чуть более миллиона ребер; нет причин не выгружать график и выполнять кратчайшие пути напрямую.

2. Может быть, я вас не понимаю, но мне нужен путь с максимальной пропускной способностью между двумя узлами, если этот путь короче или равен 4. Меня интересует интересный путь, который выражается через меру значимости. Числа выражают, насколько сильно связаны узлы, и я хочу получить интересные маршруты. Таким образом, алгоритм должен выбрать тот путь, где значимость будет максимизирована. Но если маршрут длиннее 4 прыжков, я могу просто выбрать кратчайший путь. Я думал, что neo4j может обрабатывать такие большие графики и обходы.

3. Это даже не большой график. Является ли значение аддитивным или вы хотите максимизировать минимальное значение вдоль пути или что? (Если он мультипликативный, то его логарифм является аддитивным. Если вы используете min-max, вы ищете алгоритм Prim, который … по сути, такой же, как у Дейкстры.)

4. Значение является аддитивным. Он выражает, насколько сильно связаны два узла. Путем поиска пути, в котором кумулятивная значимость максимальна, я могу получить путь, содержащий только «интересные» узлы, относящиеся к начальному узлу и конечному узлу. Мера значимости выглядит примерно так [1]

5.[1] en.wikipedia.org/wiki/Pointwise_mutual_information

Ответ №1:

Какова настройка вашей системы?

Кажется, что ваша конфигурация mmio слишком высока и потребляет всю вашу кучу, поэтому не оставляет кучи для алгоритма Neo4j? Сколько у вас всего памяти? Я думаю, что для вашего графика 10 м для узлов и 50 м для отношений более чем достаточно. Ваш прогрев должен также получить доступ к свойствам timestamp / cost, чтобы они были загружены.

 neostore.nodestore.db.mapped_memory=10M
neostore.relationshipstore.db.mapped_memory=100M
neostore.propertystore.db.mapped_memory=200M
neostore.propertystore.db.strings.mapped_memory=100M
neostore.propertystore.db.arrays.mapped_memory=0M

# remove both
neostore.propertystore.db.index.keys.mapped_memory=500M
neostore.propertystore.db.index.mapped_memory=500M

Можете ли вы также поделиться кодом этого метода? significance.edgeStrength(relationship); Интересно, повлияет ли ваша стоимость 0 на алгоритм отрицательно, поскольку меньшая стоимость приведет к рассмотрению большего количества путей, и если стоимость не изменится (все 0), тогда они будут одинаково взвешены…

Я бы создал ArrayList только в том случае, если ваша длина меньше вашего предела, в противном случае просто верните Collections.emptyList();