А вот еще над чем стоит подумать, есть такая проблема super-node, довольно частая кстати в практике, это когда у вершины очень много edges. Допустим есть две вершины по паре миллионов у каждой, и нужно проверить есть ли между ними связь. В матрице понятно стоимость такой операции минимальна и константа. А вот с листом это постоянная проблема, стоимость операции пропорциональна числу edges (меньшему)
Оу я использую edges обычно, форум русскоязычный просто :) я кстати пришел к оценочной формуле в этом споре, пусть граф 1млн вершин, матрица сравнивается с листом по памяти при 62.5тыс edges на вершину (1млн / 16). А вот при 500тыс. вершин это уже 31тыс. edges на вершину. Я так думаю лайкнуть 30тыс. девушек из 250тыс. вполне живая цифра.
Про "не существуют" :)) да сложно вообразить какие графы существуют без практики
А второй момент, конкретно Редис говорят про sparce matrices https://github.com/RedisGraph/RedisGraph я не смотрел еще имплементацию, благо код открытый можно глянуть, но название звучит как раз то что нужно
Мы обсуждали хранение граней, если что. Да, такая соцсеть неудачный пример, лайкают новые посты и число вершин будет расти. Есть графы где число вершин относительно стабильно и невелико, а число граней растет очень быстро. Мне пришел в голову пример соцсети типа Тиндер, где юзеры лайкают друг друга. Число вершин почти постоянно - это юзеры, невелико - граф локальный, например для москвы это будет миллион вершин, а вот налайкивают они там, я думаю просто с бешенной скоростью, 20 лайков в день далеко не предел. То есть понятно, что граней быстро станет очень много. А траверсал пускай будет рекомендация М->Ж<-М->Ж (если не брать "вырожденные" случаи М->М то работать будет :))
В математическом определении - нет. "Граф, в котором число рёбер E близко к максимально возможному у полного графа с числом V вершин" А практически получается что база растет на 30 ГБ в день (100m*20*16bytes), а с матрицей не растет вообще, там уже размечено false'ами все
Похож как только они лайкать начнут :) каждый будет лайкать по 20 постов новых в день и все. Вообще графы очень разные бывают, это от предметной области зависит.
Нет, не собираюсь, там была оговорка "это простейший случай когда нет свойств на грани и pointer прямо на вершину соседа" это для простоты подсчетов, можно сюда добавить что у дуг нет типов
А вот прямы ссылки на связанные вершины\ребра - надо хранить боксовыми указателями (или что вам нравится для необязательных ссылок).
Да, я подумал про Option, это будет безопасная проверка указателя на null в рантайме, причем всех указателей из adjacency list, каждый раз, и без надобности, это жесть. Надо чтобы сразу по указателю шло, ничего не проверяя
Даа :)) так построены как минимум ArangoDB и Azure CosmosDB (поверх их DocumentDB). Могу сказать это две чуть ли не самые медленные базы. Потом стоит задуматься как это все будет работать. То, что здесь называтется "хоп" это на самом деле операция I/O с диском. Допустим, нам нужно найти всех соседей на расстоянии 3. Берем первый "документ" vertex1, читаем с диска его данные, выбираем из этих данных ссылки на "документы" граней, идем за актуальными версиями для них, читаем сами документы, выбираем из них ссылки на вершины-соседы, идем за их актуальными версиями, читаем документы вершин-соседей... И это пока только первый шаг, а нам надо сделать еще два. Да нет эта идея жесть конечно. То, что набор свойств для вершины/грани похож на документ и его можно хранить отдельно. Да, можно, хотя бы ту часть свойств которая не используется в траверсалах, разгрузится графовая база. Но опять таки это перерасход места на 8 байт на объект как минимум и дополнительные I/O операции, лучше хранить скалярыне свойства прям на объекте вершины.
А еще один аргумент по поводу adjacency matrix. Я вспомнил в лекциях говорили что если граф неплотный, то лучше adjacency list, а если плотный - лучше adjacency matrix, плотность это количество граней на вершину. И понятно почему. В adjacency list для хранения грани нужно два pointer'а по 8 байт, с одной и с другой стороны, это простейший случай когда нет свойств на грани и pointer прямо на вершину соседа. Pointer это uint64 = 8 bytes, итого 16. А сколько нужно для каждой грани в adjacency matrix? bool в ячейке, есть/нет, т.е. 1 байт
СУБД предназаначены для вычислений (ответов на query), хранение это вторичная функция. Вычисления могут быть на GPU. Траверсить граф умножая матрицы это хорошая идея
Для матрицы я проблемы не вижу, поиск соседей это всегда выбор в двумерном массиве, О(1). А вот для листа, даже не для super-node, это всегда O(n). Причем это операция довольно частая, проверить связь между известными вершинами https://neo4j.com/docs/cypher-manual/current/execution-plans/operators/#query-plan-expand-into
это ценноге замечание, надо замерить
Не понял, зачем. Допустим query все соседи на расстоянии 1, разворачиваем лист. все на этом. Зачем знать что там дальше?
А вот еще над чем стоит подумать, есть такая проблема super-node, довольно частая кстати в практике, это когда у вершины очень много edges. Допустим есть две вершины по паре миллионов у каждой, и нужно проверить есть ли между ними связь. В матрице понятно стоимость такой операции минимальна и константа. А вот с листом это постоянная проблема, стоимость операции пропорциональна числу edges (меньшему)
как по мне это лишнее вычисление, причем оно будет для каждой грани в листе, и каждый раз
Лично мое мнение, должен быть комбинированный подход из этих двух пока возможных методов. Я думаю Редис думают так же.
Оу я использую edges обычно, форум русскоязычный просто :) я кстати пришел к оценочной формуле в этом споре, пусть граф 1млн вершин, матрица сравнивается с листом по памяти при 62.5тыс edges на вершину (1млн / 16). А вот при 500тыс. вершин это уже 31тыс. edges на вершину. Я так думаю лайкнуть 30тыс. девушек из 250тыс. вполне живая цифра.
Про "не существуют" :)) да сложно вообразить какие графы существуют без практики
А второй момент, конкретно Редис говорят про sparce matrices https://github.com/RedisGraph/RedisGraph я не смотрел еще имплементацию, благо код открытый можно глянуть, но название звучит как раз то что нужно
Мы обсуждали хранение граней, если что. Да, такая соцсеть неудачный пример, лайкают новые посты и число вершин будет расти. Есть графы где число вершин относительно стабильно и невелико, а число граней растет очень быстро. Мне пришел в голову пример соцсети типа Тиндер, где юзеры лайкают друг друга. Число вершин почти постоянно - это юзеры, невелико - граф локальный, например для москвы это будет миллион вершин, а вот налайкивают они там, я думаю просто с бешенной скоростью, 20 лайков в день далеко не предел. То есть понятно, что граней быстро станет очень много. А траверсал пускай будет рекомендация М->Ж<-М->Ж (если не брать "вырожденные" случаи М->М то работать будет :))
вот близкий пример https://rust-unofficial.github.io/too-many-lists/second-option.html еще через as_ref, as_mut можно
Очевидно что либо доставать документ грани, либо хранить два раза как "легковесную" и как обычную, для разных случаев :))
В математическом определении - нет. "Граф, в котором число рёбер E близко к максимально возможному у полного графа с числом V вершин" А практически получается что база растет на 30 ГБ в день (100m*20*16bytes), а с матрицей не растет вообще, там уже размечено false'ами все
А если грань не легковесная, а нам не нужны ее свойства, просто пройти дальше?
Похож как только они лайкать начнут :) каждый будет лайкать по 20 постов новых в день и все. Вообще графы очень разные бывают, это от предметной области зависит.
Нет, не собираюсь, там была оговорка "это простейший случай когда нет свойств на грани и pointer прямо на вершину соседа" это для простоты подсчетов, можно сюда добавить что у дуг нет типов
А вот прямы ссылки на связанные вершины\ребра - надо хранить боксовыми указателями (или что вам нравится для необязательных ссылок).
Да, я подумал про Option, это будет безопасная проверка указателя на null в рантайме, причем всех указателей из adjacency list, каждый раз, и без надобности, это жесть. Надо чтобы сразу по указателю шло, ничего не проверяя
Даа :)) так построены как минимум ArangoDB и Azure CosmosDB (поверх их DocumentDB). Могу сказать это две чуть ли не самые медленные базы. Потом стоит задуматься как это все будет работать. То, что здесь называтется "хоп" это на самом деле операция I/O с диском. Допустим, нам нужно найти всех соседей на расстоянии 3. Берем первый "документ" vertex1, читаем с диска его данные, выбираем из этих данных ссылки на "документы" граней, идем за актуальными версиями для них, читаем сами документы, выбираем из них ссылки на вершины-соседы, идем за их актуальными версиями, читаем документы вершин-соседей... И это пока только первый шаг, а нам надо сделать еще два. Да нет эта идея жесть конечно. То, что набор свойств для вершины/грани похож на документ и его можно хранить отдельно. Да, можно, хотя бы ту часть свойств которая не используется в траверсалах, разгрузится графовая база. Но опять таки это перерасход места на 8 байт на объект как минимум и дополнительные I/O операции, лучше хранить скалярыне свойства прям на объекте вершины.
А еще один аргумент по поводу adjacency matrix. Я вспомнил в лекциях говорили что если граф неплотный, то лучше adjacency list, а если плотный - лучше adjacency matrix, плотность это количество граней на вершину. И понятно почему. В adjacency list для хранения грани нужно два pointer'а по 8 байт, с одной и с другой стороны, это простейший случай когда нет свойств на грани и pointer прямо на вершину соседа. Pointer это uint64 = 8 bytes, итого 16. А сколько нужно для каждой грани в adjacency matrix? bool в ячейке, есть/нет, т.е. 1 байт
СУБД предназаначены для вычислений (ответов на query), хранение это вторичная функция. Вычисления могут быть на GPU. Траверсить граф умножая матрицы это хорошая идея
https://github.com/RedisGraph/RedisGraph/blob/master/README.md