Я тут задумался... обычно алгоритмы поиска в графе предполагают что весь граф доступен в рамках одного адресного пространства. А как задача решается для случаев, когда граф просто не влезает в память?
Вопрос возник из чистого любопытства, т.к. как работают распределенные не графовые базы данных вполне понятно, но вот что с графами происходит
Здравствуйте, kaa.python, Вы писали:
KP>Я тут задумался... обычно алгоритмы поиска в графе предполагают что весь граф доступен в рамках одного адресного пространства. А как задача решается для случаев, когда граф просто не влезает в память?
KP>Вопрос возник из чистого любопытства, т.к. как работают распределенные не графовые базы данных вполне понятно, но вот что с графами происходит
Я когда движок СУБД писал, понимал, что индексы целиком могут не влезть в память, как по ним искать? чуть мозг не сломал, но сделал оконное чтение файлов индексов. Обрадовался, а потом понял, что тупо завелосипедил функциональность Memory Mapped Files. Которая в винде есть. Надеюсь руки дойдут когда-нибудь этот ненужный велосипед разобрать.
Здравствуйте, kaa.python, Вы писали:
KP>обычно алгоритмы поиска в графе предполагают что весь граф доступен в рамках одного адресного пространства...
Не обязательно. Можно рассмотреть и неявные графы, которые вообще в памяти никак не представлены, а генерируются по ходу работы алгоритма.
Много алгоритмов требуют от графа всего две функции:
• по дуге получить голову (это «половина» функции инцидентности графа),
• по вершине получить последовательность исходящих дуг.
Эта последовательность исходящих дуг, как и набор вершин, не обязаны в явном виде находиться где-то в памяти, и вообще быть ограниченными.
Представь себе граф, заданный ходами коня на шахматной доске. Какая модель этого графа? Понятно, ты не будешь «хранить» клетки этой доски, или ссылки между ними. Вся твоя модель — это просто размер доски (в том числе бесконечный).
Или более общий граф, представляющий собой дерево позиций настольной игры. Вершины — позиции, дуги — ходы. Обходы этого графа вполне успешно работают в алгоритмах AI типа альфа-бета-отсечения; хотя, очевидно, полный граф шахмат или го ни в какую память не влезет.
Здравствуйте, Qbit86, Вы писали:
Q>Представь себе граф, заданный ходами коня на шахматной доске. Какая модель этого графа? Понятно, ты не будешь «хранить» клетки этой доски, или ссылки между ними. Вся твоя модель — это просто размер доски (в том числе бесконечный).
Давай возьмём более приземленный граф. У нас есть дохулиард пользователей и связи между ними. Надо найти наиболее краткий путь связей от пользователя к пользователю. И вот как будет работать поиск кратчайшего пути в таком распределенном на кластере графе я бы и хотел понять
KP>Давай возьмём более приземленный граф. У нас есть дохулиард пользователей и связи между ними. Надо найти наиболее краткий путь связей от пользователя к пользователю. И вот как будет работать поиск кратчайшего пути в таком распределенном на кластере графе я бы и хотел понять
А вот такие графы не являются произвольными.
Давно ведутся исследования по графовым моделям инета.
И графы с пользователями — это так называемые графы тесного мира.
Погугли — найдешь кучу ссылок даже на русском.
Например, по моделям графов инета есть работы Райгородского.
Восходят к случайным графам — венгры первые начали еще аж в 1956 году.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, kaa.python, Вы писали:
KP>Вопрос возник из чистого любопытства, т.к. как работают распределенные не графовые базы данных вполне понятно, но вот что с графами происходит
Т.е. как работают распределенные джойны понятно? А если сделать следующий шаг, например, БД реляционная и надо посчитать транзитивное замыкание отношения, а таблица горизонтально партицирована? Если это понятно, то до алгоритмов на графах остается совсем недалеко.
По-моему проще всего почитать как работает Гугловский Pregel. Там очень простой принцип основанный на обмене сообщениями (как и вообще многое в распределенных системах).
Здравствуйте, LaptevVV, Вы писали:
LVV>Погугли — найдешь кучу ссылок даже на русском. LVV>Например, по моделям графов инета есть работы Райгородского. LVV>Восходят к случайным графам — венгры первые начали еще аж в 1956 году.
Профессор, если бы я хотел погуглить, я бы тут тему не заводил. Я хочу кратенький ответ от того кто в теме получить
KP>Профессор, если бы я хотел погуглить, я бы тут тему не заводил. Я хочу кратенький ответ от того кто в теме получить
Я не то, чтобы очень в теме, но знаю, что и где искать, если потребуется всерьез.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, kaa.python, Вы писали:
KP>Давай возьмём более приземленный граф. У нас есть дохулиард пользователей и связи между ними. Надо найти наиболее краткий путь связей от пользователя к пользователю. И вот как будет работать поиск кратчайшего пути в таком распределенном на кластере графе я бы и хотел понять
Тыж специалист по сеткам IP пакеты как-то находят адресата- по пути, близкому к оптимальному. А оптимальный путь построить нереально за полиномиальное время.
Здравствуйте, Тёмчик, Вы писали:
Тё>Тыж специалист по сеткам IP пакеты как-то находят адресата- по пути, близкому к оптимальному. А оптимальный путь построить нереально за полиномиальное время.
Даже если бы я пал на столько низко, что стал бы писать на JS, то и то постеснялся б такое писать на форуме как бы программистов
Здравствуйте, Тёмчик, Вы писали:
Тё>Тыж специалист по сеткам IP пакеты как-то находят адресата- по пути, близкому к оптимальному. А оптимальный путь построить нереально за полиномиальное время.
Ну ващет IP пакеты ходят, как им админ настроит. Оне могут и через Австралию вашу ходить от меня в соседний подъезд, если у провайдерских админов руки из жопэ растут
Здравствуйте, kaa.python, Вы писали:
KP>Здравствуйте, Qbit86, Вы писали:
Q>>Представь себе граф, заданный ходами коня на шахматной доске. Какая модель этого графа? Понятно, ты не будешь «хранить» клетки этой доски, или ссылки между ними. Вся твоя модель — это просто размер доски (в том числе бесконечный).
KP>Давай возьмём более приземленный граф. У нас есть дохулиард пользователей и связи между ними. Надо найти наиболее краткий путь связей от пользователя к пользователю. И вот как будет работать поиск кратчайшего пути в таком распределенном на кластере графе я бы и хотел понять
Фигово будет работать, в общем случае
Можно конечно уточнить примерный диапазон "охулиарда", но если нет никаких ограничений на количество связей, то с производительностью такого алгоритма все будет не очень хорошо.
Обычно в реальных приложениях (скажем соц сеть), возможность такого поиска ограничена максимальными расстоянием.
Возьмем например LinkedIn — он может определить что вы знакомы через 2 других звена.
Какой-нибудь Facebook — что только через одно.
У обоих сетей есть ограничение на количество друзей "первого уровня".
Через произвольное количество звеньев я не видел.
Через одно звено сделать довольно просто даже на реляционной базе, храня списки смежных вершин, никаких особых проблем там быть не должно.
Через два звена чуток посложнее, с реляционной базой там могут получиться плохие граничные случаи.
Но введя определенные дополнительные ограничения плюс если считать не real-time а в фоновом режиме и с кешированием, можно и с этой проблемой разобраться.
В таких приложениях не требуется находить кратчайший путь впрочем, но требуется показать если человек находится в первом, втором или третьем круги знакомых.
KP>Я тут задумался... обычно алгоритмы поиска в графе предполагают что весь граф доступен в рамках одного адресного пространства. А как задача решается для случаев, когда граф просто не влезает в память? KP>Вопрос возник из чистого любопытства, т.к. как работают распределенные не графовые базы данных вполне понятно, но вот что с графами происходит
В каждом случае по-разному, комбинируя по-разному разные известные методы. Некоего единого оптимального решения существовать не может. Даже на одном компе разные решения будут в зависимости от того, каккие диски, какая память, какой процессор.
V>В каждом случае по-разному, комбинируя по-разному разные известные методы. Некоего единого оптимального решения существовать не может. Даже на одном компе разные решения будут в зависимости от того, каккие диски, какая память, какой процессор.
Здравствуйте, VladiCh, Вы писали:
VC>Какой-нибудь Facebook — что только через одно. VC>У обоих сетей есть ограничение на количество друзей "первого уровня".
Мне вообще кажется, что в Фейсбуке работают приближённые методы для этого. Например, их faiss кластеризует всех пользователей, а потом ищет предложения подружиться только в твоём кластере или с неким радиусом в получившемся пространстве.
VC>Через произвольное количество звеньев я не видел.
Для вконтактика раньше такая фишка была — можно было строить граф рукопожатий до любого из пользователей.
, для информации, так сказать.
Какой вопрос, такой ответ. Если бы ты привел конкретные ограничения и возможности, то уже можно было бы что-то придумывать. А так у тебя вопрос о "некоем смысле жизни вообще".
Повторю еще раз "Некоего единого оптимального решения существовать не может."
Здравствуйте, Vzhyk2, Вы писали:
V>Какой вопрос, такой ответ. Если бы ты привел конкретные ограничения и возможности, то уже можно было бы что-то придумывать. А так у тебя вопрос о "некоем смысле жизни вообще". V>Повторю еще раз "Некоего единого оптимального решения существовать не может."
Могу научить читать тексты, дорого не возьму
Алгоритмы поиска в распределенном графе: как задача решается для случаев, когда граф просто не влезает в память?
Ну ты это, хоть что-то по делу напиши, а то пока только раздувание щёк и игра в КО наблюдается
Причем я бы поверил что вопрос кривой, если бы ответов по делу не было, но они есть раз
Алгоритмы поиска в распределенном графе: как задача решается для случаев, когда граф просто не влезает в память?
Простейший вариант замапить файл с графом на память. Более сложный — порезать граф на части, которые влазят в память и после объединить результаты, полученные по каждой части.
Здравствуйте, kaa.python, Вы писали:
KP>Я тут задумался... обычно алгоритмы поиска в графе предполагают что весь граф доступен в рамках одного адресного пространства. А как задача решается для случаев, когда граф просто не влезает в память?
KP>Вопрос возник из чистого любопытства, т.к. как работают распределенные не графовые базы данных вполне понятно, но вот что с графами происходит
Насколько я помню всю эту теорию, то для большинства графовых операций, они могут быть заменены матрично-векторными над соответсвующим лапласианами или матрицами смежности (например, https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.712.846&rep=rep1&type=pdf ). А соответствующие операции параллелятся хорошо известным способом.
Здравствуйте, kaa.python, Вы писали:
KP>Вопрос возник из чистого любопытства, т.к. как работают распределенные не графовые базы данных вполне понятно, но вот что с графами происходит https://research.google/pubs/pub44216/
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
IP пакеты как-то находят адресата- по пути, близкому к оптимальному. А оптимальный путь построить нереально за полиномиальное время.
