Как Titan добивается постоянного поиска времени с использованием HBase/Cassandra?

В O'Reilly книга «Graph Базе данных» в главе 6, который, как Neo4j хранит базу данных графа он говорит:Как Titan добивается постоянного поиска времени с использованием HBase/Cassandra?

Чтобы понять, почему родная обработка график настолько гораздо более эффективным, чем графика, основанную на тяжелая индексация, рассмотрим следующее. В зависимости от реализации индексные запросы могут быть O (log n) в алгоритмической сложности по сравнению с O (1) для поиска непосредственных отношений. Чтобы преодолеть сеть из m шагов, стоимость индексированного подхода, на O (m log n), затмевает стоимость O (m) для реализации, которая использует бесконтактную смежность.

Затем объяснен, что Neo4j достигает этот постоянная время поиска путем сохранения всех узлов и связей в виде записей фиксированного размера:

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

Последнее предложение вызывает мой вопрос: как Titan, использующий Cassandra или HBase в качестве хранилища для хранения данных, достигает этих приростов производительности или компенсирует это?

источник

2014-09-24 Lodewijk Bogaards

И я бы проголосовал за тот же вопрос для OrientDB! –

Хороший вопрос, да. OrientDB обрабатывает собственное хранилище, поэтому я предполагаю, что у них что-то похожее на Neo4j, но я бы с удовольствием узнал. –

Neo4j является O (1) алгоритмической сложностью независимо от того, обращаетесь ли вы к кешированному объекту или к одному на диске, потому что он просто преследует указатели, а не вызывает какой-то внешний индекс для обхода отношений. Neubauer и Rodriguez (см. Выше) называют это «бесступенчатой смежностью», и я подозреваю, что он является центральным для всех разумных графических баз данных. –

Neo4j только достигает O (1), когда данные находятся в памяти в той же JVM. Когда данные находятся на диске, Neo4j медленный из-за того, что на диске гоняется указатель (у них плохое представление диска).

Titan только достигает O (1), когда данные находятся в памяти в одной JVM. Когда данные находятся на диске, Titan быстрее, чем Neo4j, потому что он имеет лучшее представление на диске.

Пожалуйста, обратитесь к следующей записи в блоге, что объясняет выше количественно: http://thinkaurelius.com/2013/11/24/boutique-graph-data-with-titan/

Таким образом, важно понять, когда люди говорят, что O (1) какая часть иерархии памяти, они находятся в Когда вы в. единственная JVM (одиночная машина), ее легкость быть быстрой, как и Neo4j, так и Titan с их соответствующими механизмами кэширования. Когда вы не можете поместить весь график в память, вам нужно полагаться на интеллектуальные макеты дисков, распределенные кеши и тому подобное.

Пожалуйста, смотрите следующие два блога для получения дополнительной информации:

http://thinkaurelius.com/2013/11/01/a-letter-regarding-native-graph-databases/ http://thinkaurelius.com/2013/07/22/scalable-graph-computing-der-gekrummte-graph/

источник

2014-09-24 21:20:05

Чтобы расширить, Neo4j не поддерживает O (1) во всех обходах. Предположим, что предикат края. Для получения последнего друга вершины v стоит O (| out (v) |) в Neo4j (т. Е. Линейное сканирование с вершинами). Зачем? Поскольку Neo4j не сортирует свои данные в памяти (и не на диске). Neo4j должен перебирать все исходящие границы-друга v, чтобы определить, какая из них имеет самую последнюю временную метку. В Титане это (может быть) операция O (1). Вы можете узнать больше здесь: http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/ Это продвижение реализовано как на диске, так и в памяти с Titan. –

Я считаю, что вы там не правы. В последних версиях Neo4j (2.1.x) Neo4j также реализует так называемый «индекс, ориентированный на вершину», чтобы решить эту проблему. –

Neo4j всегда алгоритмически O (1), так как это расчет смещения id *, который дает запись. Механически, как и при любом усталом подходе к хранению, существуют более короткие и длинные пути. Хит кешированный объект, и вы коротко замыкаете путь от базы данных к диску и обратно; ударил холодные кеши, и вы пойдете на диск. Это все еще O (1). Нет индекса или другого O (log n) или худшего поиска для выполнения. Это огромная выгода от того, чтобы быть естественным на всем протяжении стека. –

OrientDB использует подобный подход, при котором отношения управляются без индексов (индекс свободного смежности), а с прямыми указателями (ССЫЛКИ) между вершинами. Это как в указателях памяти, но на диске. Таким образом, OrientDB достигает O (1) при перемещении в памяти и на диске.

Но если у вас есть вершина «Город» с тысячами ребер к вершинам «Лицо», и вы ищете всех людей с возрастом> 18, то OrientDB использует индексы, потому что запрос задействован, поэтому в в этом случае это O (log N).

источник

2014-09-25 23:50:34 Lvca

Как Titan добивается постоянного поиска времени с использованием HBase/Cassandra?

ответ

Смежные вопросы