Инструменты для использования vkontakte.ru в (не обязательно) злобных целях

Хотя даты установления связей конечно стоит держать отдельно.

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

Preread это такой вид кэша если что.

который выполнит ОС, ибо считывание будет идти страницами. А тебе надо объяснять, сколько в страницу памяти влезет списков таких в нашем случае?

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

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

ты сам понял, что сказал хоть?

К слову БД для графов нужны как раз для этих вещей. Это все выглядит

Я еще раз повторю: БД для графов не нужны, БД для графов не нужны, БД для графов не нужны, БД для графов не нужны.

К слову у них 100к операций чтения и 20к записи в секунду. Но это к делу не относится.

с такой скоростью использование алгоритмов для графов сразу становится просто чисто теоретической возможностью. (просисью: это просто фатально медленно для такого большого графа).

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

Если это держать в свопе, то работа с такой структурой данных будет Ъ ад.

Я еще раз повторяю: свойства вершин и ребер можешь держать где угодно и как угодно. Но для _самого_ графа БД никаким раком не впирается.

>>Перечитай еще раз. Ты опять не так понял. Вот этот граф:

Я так понял. Это относилось не к тому, что это за граф, а к способу его хранения.

тогда я в упор не понимаю, что ты имеешь в виду.

>который выполнит ОС, ибо считывание будет идти страницами. А тебе надо объяснять, сколько в страницу памяти влезет списков таких в нашем случае?
Который ОС выполнит неправильно, так как вершины френдов хранятся совсем в других местах. Если распределение френдов в памяти равномерное, то размер страницы чем меньше, тем лучше.

Я еще раз повторю: БД для графов не нужны, БД для графов не нужны, БД для графов не нужны, БД для графов не нужны.

Еще раз повторю, вы не отличаете разные модели данных в БД и путаете все с реляционной.

с такой скоростью использование алгоритмов для графов сразу становится просто чисто теоретической возможностью. (просисью: это просто фатально медленно для такого большого графа).

Но там именно граф. Суть здесь в том, что ИМЕННО для того, чтобы работать удобно работать с данными, в том числе обеспечивать репликацию и параллельную обработку хоть на сотне компьютеров - нужны специальные БД.

Я еще раз повторяю: свойства вершин и ребер можешь держать где угодно и как угодно. Но для _самого_ графа БД никаким раком не впирается.

Про свойства я уже написал чуть позже. Но итак будет 100 Гб структура, которая должна будет висеть в памяти.

тогда я в упор не понимаю, что ты имеешь в виду.

На это можно забить тогда, там была разница чисто формальная и важного ничего нет.

На всякий случай, вот список ненужных имплементаций ненужного. http://en.wikipedia.org/wiki/Graph_database

>>который выполнит ОС, ибо считывание будет идти страницами. А тебе надо объяснять, сколько в страницу памяти влезет списков таких в нашем случае?

Который ОС выполнит неправильно, так как вершины френдов хранятся совсем в других местах. Если распределение френдов в памяти равномерное, то размер страницы чем меньше, тем лучше.

вершина - это не более чем цифра. Загрузив список, ОС автоматически сразу загрузит и вершины френдов. Ибо это одно и то же.

с такой скоростью использование алгоритмов для графов сразу >становится просто чисто теоретической возможностью. (просисью: это просто фатально медленно для такого большого графа).

Но там именно граф. Суть здесь в том, что ИМЕННО для того, чтобы работать удобно работать с данными, в том числе обеспечивать репликацию и параллельную обработку хоть на сотне компьютеров - нужны специальные БД.

Хорошо, приведу пример: поиск кратчайшего пути от одной вершины к другой - O(n+m) примерно будет O(n) в нашем случае = 50e6. Поделив на 100k, как ты говоришь, получим как минимум 500 секунд. Некисло, правда?

На всякий случай, вот список ненужных имплементаций ненужного. http://en.wikipedia.org/wiki/Graph_database

это базы данных основынные на графах, но не базы данных _для_ графов.

>вершина - это не более чем цифра. Загрузив список, ОС автоматически сразу загрузит и вершины френдов. Ибо это одно и то же.
Ну тут уже глубина на которую грузить выбирается программистом.

Хорошо, приведу пример: поиск кратчайшего пути от одной вершины к другой - O(n+m) примерно будет O(n) в нашем случае = 50e6. Поделив на 100k, как ты говоришь, получим как минимум 500 секунд. Некисло, правда?

Ничего не понял, я говорил, про 100k операций в секунду. Но вообще, необязательно искать на полную глубину, иногда достаточно поиск на 4-5 уровней, а это уже вполне разумное время.

это базы данных основынные на графах, но не базы данных _для_ графов.

General graph databases that can store any graph are distinct from specialized graph databases such as triplestores and network databases.

Ну и вообще их именно для этого и применяют. Кроме твиттера, тот же гугл еще например, у него есть такой параметр page rank который определяет вес страницы и он зависит от ссылок на эту страницу, поэтому эти данные у него хранятся в виде распределенного(при том, что у них за трллион страниц перевалило уже 3 года назад, по другому нельзя) графа.

>>вершина - это не более чем цифра. Загрузив список, ОС автоматически сразу загрузит и вершины френдов. Ибо это одно и то же.

Ну тут уже глубина на которую грузить выбирается программистом.

ну и на какую грузить? А главное, зачем?

Хорошо, приведу пример: поиск кратчайшего пути от одной вершины к другой - O(n+m) примерно будет O(n) в нашем случае = 50e6. Поделив на 100k, как ты говоришь, получим как минимум 500 секунд. Некисло, правда?

Ничего не понял, я говорил, про 100k операций в секунду. Но вообще, необязательно искать на полную глубину, иногда достаточно поиск на 4-5 уровней, а это уже вполне разумное время.

обязательно. Ибо иначе нельзя найти пути между двумя узлами. А если ты хочешь строить дерево длинной в пять ребер, то вычисление того, что надо подгружать _уже_ будет этим алгоритмом => избыточно.

Ну и вообще их именно для этого и применяют. Кроме твиттера, тот же гугл еще например, у него есть такой параметр page rank который определяет вес страницы и он зависит от ссылок на эту страницу, поэтому эти данные у него хранятся в виде распределенного(при том, что у них за трллион страниц перевалило уже 3 года назад, по другому нельзя) графа.

и причем здесь сам этот граф?

Можно ли на этом графе с помощью этой БД провести стандартные алгоритмы за вменяемое время? Если нет, то тогда это не БД для графов, а БД, _некоторым образом_ использующая графы.

>обязательно. Ибо иначе нельзя найти пути между двумя узлами. А если ты хочешь строить дерево длинной в пять ребер, то вычисление того, что надо подгружать _уже_ будет этим алгоритмом => избыточно.
Не всегда нужен путь между двумя узлами, и тем более не всегда нужен точный. Чтобы просто вывести список людей, кого вы возможно знаете, достаточно глубины в 3-4 слоя. Чтобы определить в какой группе сидит больше всего членов этой группы надо вообще 1 слой.

и причем здесь сам этот граф?

При том, что он как раз и хранится в этой БД, как у твиттера в FlockDB.

Можно ли на этом графе с помощью этой БД провести стандартные алгоритмы за вменяемое время? Если нет, то тогда это не БД для графов, а БД, _некоторым образом_ использующая графы.

А если текст 10Гб и на нем нельзя использовать стандартный алгоритм поиска наибольшей общей подстроки, то это что, не текст чтоли?
Гугловская БД находит все кратчайшие пути из одного источника при 1 миллиарде вершин и 80 миллиарде граней за 200 секунд при распараллеливании на 480 многоядерных компьютеров.

>Гугловская БД находит все кратчайшие пути из одного источника при 1 миллиарде вершин и 80 миллиарде граней за 200 секунд при распараллеливании на 480 многоядерных компьютеров.

Что может говорит о том, что граф хранится отдельно от БД.

и причем здесь сам этот граф?

При том, что он как раз и хранится в этой БД, как у твиттера в FlockDB.

ну хранится и что?

обязательно. Ибо иначе нельзя найти пути между двумя узлами. А если >ты хочешь строить дерево длинной в пять ребер, то вычисление того, что надо подгружать _уже_ будет этим алгоритмом => избыточно.

Не всегда нужен путь между двумя узлами, и тем более не всегда нужен точный. Чтобы просто вывести список людей, кого вы возможно знаете, достаточно глубины в 3-4 слоя. Чтобы определить в какой группе сидит больше всего членов этой группы надо вообще 1 слой.

достаточно. Но зачем тогда нужен какой-то специальный граф? можно просто в обычной БД хранить ссылки.

>Что может говорит о том, что граф хранится отдельно от БД.
Кхм. Это БД нужна именно и только для графа. Для других данных есть BigTable.

достаточно. Но зачем тогда нужен какой-то специальный граф? можно просто в обычной БД хранить ссылки.

FlockDB вообще использует в качестве бэкэнда mysql. Специальная БД поверх нужна для того, чтобы с этим быстро и эффективно работать. Шардинг там всякий, хождение по графу и прочее.