Хранения разные бывают, в RAM это может быть 1) матрица смежности, 2) листы смежности (поинтеров) на объектах нодов, ну и эмуляции 3) на таблицах и 4) на колоночных базах. А на диске, ну матрицу понятно так и хранить, как хранить adjacency list это у каждого коммерческий секрет, у neo4j они рассказывают свой, таблицы и колоночные сами сериализуют. Последные два способа для RAM самые меделнные из-за индексов. Второй способ (лист) самый популярный сейчас
Ну там GraphBLAS это вычисления этих матриц на GPU, перспективное направление, вершин может быть и несколько миллионов. Зато есть интересные феномены, я в лекциях видел, можно умножить матрицу смежности саму на себя - получатся все random walk
Кстати насчет Лиспа, I have thought, как говорится. Во-первых, этот подход не превносит в проблему ничего нового, мы можем в Расте сделать объект Граф, он будет владеть всеми вершинами, но тут проблема со временем жизни и ссылками друг на друга, вершины могут удаляться. Для это Computer Programs это и может подойдет, там граф не мутабельный (как правило, код программы статичен), а для данных - нет. А во-вторых, на самом деле граф не всегда имеет форму дерева, точнее почти никогда. Если задуматься над такими вопросами: 1) что если "лист" из одной ветви ссылается на "лист" из другой ветви? 2) Или например "лист" ссылается на самую верхнюю вершину? Я так понимаю, этот вопрос поднимается здесь https://coderoad.ru/23724226/ где ему отвечают что Лисп будет использовать CLOS (общая объектная система Lisp), т.е. ничего нового относительно других языков кроме Си и Раста, привет, сборщик мусора, который будет мониторить ВСЕ объекты.
ну это самый дубовый подход, скажем так, на каждом шаге обхода графа нужно дергать следующую грань по индексу, т.е. получится ничем не лучше табличных баз. Пока что два академических подхода существует - adjacency list и adjacency matrix. В первом объект вершины хранит на себе указатели на соседей (что я пытаюсь сделать, это подход neo4j https://youtu.be/LSKa3as_S7I?t=635), второй пока что только Редис прорабатывают, там можно почитать https://oss.redis.com/redisgraph/
Ну я практик, графовые базы моя специализация. Примеров можно придумать много. Например, граф телефонных номеров и звонков между ними - абоненты вершины, на них свойство "номер", факт звонка грань, на ней counter сколько раз звонили. Каждый звонок может добавлять вершины (если абонента еще нет в графе), создавать грани (если до этого еще не звонили друг другу), и обновлять грани (инкрементить counter для уже существующих). И в реальном времени это все пишем.
Спасибо. Хочется прям adjacency list на поинтерах конечно, про контейнеры я уже думал. Меня, если честно, еще очень волнует вопрос можно ли как то обойтись без итераторов, neo4j тоже вся на итераторах, реализации графов на расте, которые я нашел поиском тоже
По Лиспу буду рад каким-то пояснениям или ссылочкам, я знаю подход TerminusDB, она на прологе, там скажем так "версионирование" (ничего никогда не удаляется), но это нереально сейчас с нормальным размером графа
А что имеется ввиду под этим кодом? Код, который пользуется графом максимально прост: 1) добавить вершин штук n со свойствами 2) добавить граней между ними со свойствами на гранях 3) найти вершину по значению свойства и от нее сделать 10 хопов с фильтром по значению свойства на грани
Я не уверен насчет этой фразы "язык, который наиболее близок к грядущему GQL стандарту" Уж скорее он будет ближе к Cypher, все таки 95% community это юзеры Neo4j и 5% это Gremlin. Хотя это не точно, Tigergraph'у больше всех надо.
Описание сильно урезанное потому что это пока что проект для DARPA HIVE :) Можно еще гуглом поискать, есть вот это https://arxiv.org/pdf/2010.06277.pdf и некоторые картинки из презентаций интересные находит.
Производительность в 10-100 раз, да, немного, но это для графовых задач +10 хопов и сейчас это будет очень существенно.
Я к тому что:
1) все в итоге приходят к shared memory и это будущее, а не спарк на moderate hardware как пишут некоторые комментаторы
Да, получается так и есть, отрицание сложнее задать. Если это вероятностная модель, то скажем верный ответ по черным спискам она будет давать в 99% случаев. Я бы сказал, если это будет работать в 99% случаев и "Результаты очень многообещающие: рост производительности в разы, а размер индекса становится меньше в тысячу раз.", то это точно будут использовать в тех же финансах к примеру. В крайнем случае можно поставить триггер на операции по всем заблокированным картам, ваша модель даже еще и обучится. Т.е. потенциальные потери могут быть меньше чем стоимость владения старым способом. Я думаю, к этому можно относиться как к измерению с погрешностью в физике, только на больших данных.
Так вроде и проверяет в примере с картой. Модель и говорит "ключ может быть примерно там", проверит там, проверит окрестность, нет. Значит нет. У банка номер карты кодирует отделение к примеру.
Хранения разные бывают, в RAM это может быть 1) матрица смежности, 2) листы смежности (поинтеров) на объектах нодов, ну и эмуляции 3) на таблицах и 4) на колоночных базах. А на диске, ну матрицу понятно так и хранить, как хранить adjacency list это у каждого коммерческий секрет, у neo4j они рассказывают свой, таблицы и колоночные сами сериализуют. Последные два способа для RAM самые меделнные из-за индексов. Второй способ (лист) самый популярный сейчас
Ну там GraphBLAS это вычисления этих матриц на GPU, перспективное направление, вершин может быть и несколько миллионов. Зато есть интересные феномены, я в лекциях видел, можно умножить матрицу смежности саму на себя - получатся все random walk
Ну да, и примеры, скажем так, позавчерашнего дня
Кстати насчет Лиспа, I have thought, как говорится. Во-первых, этот подход не превносит в проблему ничего нового, мы можем в Расте сделать объект Граф, он будет владеть всеми вершинами, но тут проблема со временем жизни и ссылками друг на друга, вершины могут удаляться. Для это Computer Programs это и может подойдет, там граф не мутабельный (как правило, код программы статичен), а для данных - нет. А во-вторых, на самом деле граф не всегда имеет форму дерева, точнее почти никогда. Если задуматься над такими вопросами: 1) что если "лист" из одной ветви ссылается на "лист" из другой ветви? 2) Или например "лист" ссылается на самую верхнюю вершину? Я так понимаю, этот вопрос поднимается здесь https://coderoad.ru/23724226/ где ему отвечают что Лисп будет использовать CLOS (общая объектная система Lisp), т.е. ничего нового относительно других языков кроме Си и Раста, привет, сборщик мусора, который будет мониторить ВСЕ объекты.
ну это самый дубовый подход, скажем так, на каждом шаге обхода графа нужно дергать следующую грань по индексу, т.е. получится ничем не лучше табличных баз. Пока что два академических подхода существует - adjacency list и adjacency matrix. В первом объект вершины хранит на себе указатели на соседей (что я пытаюсь сделать, это подход neo4j https://youtu.be/LSKa3as_S7I?t=635), второй пока что только Редис прорабатывают, там можно почитать https://oss.redis.com/redisgraph/
Ну я практик, графовые базы моя специализация. Примеров можно придумать много. Например, граф телефонных номеров и звонков между ними - абоненты вершины, на них свойство "номер", факт звонка грань, на ней counter сколько раз звонили. Каждый звонок может добавлять вершины (если абонента еще нет в графе), создавать грани (если до этого еще не звонили друг другу), и обновлять грани (инкрементить counter для уже существующих). И в реальном времени это все пишем.
:))
Спасибо. Хочется прям adjacency list на поинтерах конечно, про контейнеры я уже думал. Меня, если честно, еще очень волнует вопрос можно ли как то обойтись без итераторов, neo4j тоже вся на итераторах, реализации графов на расте, которые я нашел поиском тоже
По Лиспу буду рад каким-то пояснениям или ссылочкам, я знаю подход TerminusDB, она на прологе, там скажем так "версионирование" (ничего никогда не удаляется), но это нереально сейчас с нормальным размером графа
А что имеется ввиду под этим кодом? Код, который пользуется графом максимально прост: 1) добавить вершин штук n со свойствами 2) добавить граней между ними со свойствами на гранях 3) найти вершину по значению свойства и от нее сделать 10 хопов с фильтром по значению свойства на грани
Это коммент 100%)) я попытался граф на расте написать, вообще непонятно кто чем владеет. а уж если гиперграф то полный аут
Про алгоритмы, да нормально, в некоторых вещах даже больше чем на гремлине можно сделать
Я не уверен насчет этой фразы "язык, который наиболее близок к грядущему GQL стандарту" Уж скорее он будет ближе к Cypher, все таки 95% community это юзеры Neo4j и 5% это Gremlin. Хотя это не точно, Tigergraph'у больше всех надо.
Описание сильно урезанное потому что это пока что проект для DARPA HIVE :) Можно еще гуглом поискать, есть вот это https://arxiv.org/pdf/2010.06277.pdf и некоторые картинки из презентаций интересные находит.
Производительность в 10-100 раз, да, немного, но это для графовых задач +10 хопов и сейчас это будет очень существенно.
Я к тому что:
1) все в итоге приходят к shared memory и это будущее, а не спарк на moderate hardware как пишут некоторые комментаторы
2) Судя по их родмапу все должно быть уже готово
Всем стоит взглянуть на идеи Intel PIUMA https://info.tigergraph.com/graph-ai-summit-spring-2021-hardware-considerations-for-faster-and-deeper-insights-from-your-large-scale-graph
Да, получается так и есть, отрицание сложнее задать. Если это вероятностная модель, то скажем верный ответ по черным спискам она будет давать в 99% случаев. Я бы сказал, если это будет работать в 99% случаев и "Результаты очень многообещающие: рост производительности в разы, а размер индекса становится меньше в тысячу раз.", то это точно будут использовать в тех же финансах к примеру. В крайнем случае можно поставить триггер на операции по всем заблокированным картам, ваша модель даже еще и обучится. Т.е. потенциальные потери могут быть меньше чем стоимость владения старым способом. Я думаю, к этому можно относиться как к измерению с погрешностью в физике, только на больших данных.
Ясно :) А я бы порекомендовал вот это недавнее выступление https://vimeo.com/623756277#t=2100s
Так вроде и проверяет в примере с картой. Модель и говорит "ключ может быть примерно там", проверит там, проверит окрестность, нет. Значит нет. У банка номер карты кодирует отделение к примеру.
Что, как ученый, можете сказать про графовые БД?
Автор этой книги также автор основного учебника по ОТО в MIT https://ocw.mit.edu/courses/physics/8-962-general-relativity-spring-2020/readings/