MongoDB: ищите людей на точной глубине

У меня есть графические соединения в MongoDB:

{ 
    from: ObjectID(user),
    to: ObjectID(user) 
}

если я хочу получить всех пользователей на глубине 1, это просто:

db.connections.find({from:ObjectID(myUser)});

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

e.g 
1->2 
2->1 
1->3
2->4
results of user(1).findDepth2() would be 2,1,3,4 instead of 4. 

Пример в псевдо node.js:

var myFriends = db.connections.find({from:ObjectID(myUser)});
var friendAtDepth2 = [];
for(friend in myFriends){
    // I find friends of each friend
    var frendsOfFriend = db.connections.find({from:ObjectID(friend)});
    for(friendOfFriend in frendsOfFriend){
        if(friendAtDepth2.indexof(friendOfFriend)==-1 
             && myFriends.indexof(friendOfFriend)==-1
             && myUser!=friendOfFriend){
             // I haven't already found this user, so I it is actually at depth 2
             friendAtDepth2.push(friendOfFriend);
        }
    }
}

Но таким образом я действительно выполняю много запросов, и я надеюсь, что существует своего рода запрос на соединение, как в mysql helipng, я делаю это только в одном запросе

Возможен ли такой запрос?


person rodi    schedule 02.07.2014    source источник
comment
Я думаю, вам действительно нужно добавить к этому наглядный пример. В вашем вопросе нет ничего, что демонстрирует произвольную глубину.   -  person Neil Lunn    schedule 02.07.2014
comment
Среднее значение: если вы найдете запрос для поиска людей на глубине 2, возможно также найти запрос для глубины 3 или 4.   -  person rodi    schedule 02.07.2014
comment
По-прежнему недостаточно информации. Образец документа для иллюстрации хорош. Лучше неудачная попытка кода. Просто пытаюсь посоветовать, как люди это закроют. Вам решать.   -  person Neil Lunn    schedule 02.07.2014
comment
Возможно, вместо того, чтобы комментировать вещи, которые не отвечают на ваш вопрос, вы могли бы сосредоточиться на объяснении вашего вопроса более четко, как вас просили.   -  person Neil Lunn    schedule 02.07.2014
comment
Вы можете сделать это, просматривая вашу коллекцию только один раз: 1. Вы просматриваете свою коллекцию и строите матрицу отношений 1 к 1 (симметричная или нет), 2. Вы возводите матрицу в квадрат. Это не оптимальная теоретическая сложность, но это двоичная матрица, и если вы примете во внимание время выполнения запросов, вы можете сэкономить много времени ...   -  person dgiugg    schedule 02.07.2014


Ответы (1)


Реализуйте алгоритм Breath-First Search, чтобы найти все узлы на расстоянии два от определенного узел.

Он имеет линейную временную сложность O (| E | + | V |), поэтому вы не можете добиться лучшего результата.

Если вам нужны все узлы на расстоянии два, три и т. Д., Вам может потребоваться изучить алгоритмы кратчайшего пути для всех пар и немного их настроить.

Под настройкой я подразумеваю, что вы должны запускать BFS с каждого узла и останавливаться на необходимой глубине. Если вам нужны конкретные примеры кода, вам следует взглянуть на аналогичный вопрос, например Все пути длины L от узла n с использованием python.

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

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

person Pio    schedule 02.07.2014
comment
Если вы не собираетесь показать какой-то код, как это сделать в этом случае, это не ответ. Ссылки имеют тенденцию меняться с течением времени, поэтому либо объясните ответ, либо согласитесь с тем, что вы предоставили неполный ответ. - person Neil Lunn; 02.07.2014
comment
Алгоритм поиска Breath First очень хорошо известен, я только что предоставил первый результат Google. Кроме того, вопрос не содержит четких структур данных, поэтому я не могу предоставить код для этого вопроса. Это теоретический ответ. - person Pio; 02.07.2014
comment
Ага. Только поиск Google - тоже не ответ. Вам нужно показать, как получить желаемый результат. Кто угодно может Google. Может быть, лучше в качестве комментария, если вы не покажете, как это сделать. Вот каков ответ. - person Neil Lunn; 02.07.2014
comment
да это очень известно, но как это реализовать? Как я уже сказал. Глупая идея - найти всех людей на глубине 1, а затем выполнить запрос, подобный предыдущему, для каждого человека. Практически нет реализации BFS, но это очень неэффективно - person rodi; 02.07.2014
comment
@rodi, может, я недостаточно откровенен. Проверьте мою правку в ответе. - person Pio; 02.07.2014
comment
Я очень хорошо знаю BFS и многие другие алгоритмы, касающиеся графов, а также neo4j. Но мне действительно нужно выяснить, как составить запрос на mongodb, чтобы выполнять тяжелые задания по уменьшению карты и агрегированию данных. Но я действительно не знаю, как это сделать - person rodi; 03.07.2014
comment
Я предлагаю сразу же выполнить работу на стороне базы данных. Я предполагаю, что вы используете Mongodb. Это структура агрегирования поддерживает Map-Reduce. В ближайшее время постараюсь сделать пример. - person Pio; 03.07.2014