|
|
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
Приветствую! Нужно в общем виде решить следующую задачу: имеется очень большой граф (узлы со свойствами, попарные связи со свойствами). Нужно максимально быстро сделать выборку узлов/связей по заданным условиям и построить граф, все узлы которого непосредственно и/или опосредовано связаны со стартовым. На данном этапе нужно определиться - браться или нет за нее. Опыта работы с подобными задачи не имею, и для решения была бы полезна любая информация, как то: личный опыт, ознакомительная литература, готовые средства и т.п. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2021, 22:41 |
|
||
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
Не совсем понятна постановка. Нужно выбрать узлы/связи по каким-то условиям плюс доп. условие - находящиеся в одном связном подграфе со стартовым узлом? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.02.2021, 01:20 |
|
||
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис Нужно в общем виде решить следующую задачу: имеется очень большой граф (узлы со свойствами, попарные связи со свойствами). Посмотри в сторону neo4j ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.02.2021, 04:57 |
|
||
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис Приветствую! Нужно в общем виде решить следующую задачу: имеется очень большой граф (узлы со свойствами, попарные связи со свойствами). Нужно максимально быстро сделать выборку узлов/связей по заданным условиям и построить граф, все узлы которого непосредственно и/или опосредовано связаны со стартовым. На данном этапе нужно определиться - браться или нет за нее. Опыта работы с подобными задачи не имею, и для решения была бы полезна любая информация, как то: личный опыт, ознакомительная литература, готовые средства и т.п. ИМХО в начале пучить теорию. Графы, алгебру, работа с матрицей. Тут работа скорее для математика, чем для БД. Т.к. велика вероятность вляпаться в NP-полную задачу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.02.2021, 07:52 |
|
||
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
softwarer Не совсем понятна постановка. Нужно выбрать узлы/связи по каким-то условиям плюс доп. условие - находящиеся в одном связном подграфе со стартовым узлом? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.02.2021, 08:52 |
|
||
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
mad_nazgul ИМХО в начале пучить теорию. Графы, алгебру, работа с матрицей. Тут работа скорее для математика, чем для БД. Т.к. велика вероятность вляпаться в NP-полную задачу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.02.2021, 09:06 |
|
||
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис softwarer Не совсем понятна постановка. Нужно выбрать узлы/связи по каким-то условиям плюс доп. условие - находящиеся в одном связном подграфе со стартовым узлом? Тогда, мне кажется, ключевой вопрос - насколько часто граф модифицируется относительно операций поиска. Если достаточно редко для того, чтобы иметь возможность предрассчитать атрибут "номер связного подграфа", задача становится тривиально-реляционной. Если же нет... тогда, видимо, стоит искать СУБД, которая умеет эффективно просчитывать связность на лету. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.02.2021, 10:17 |
|
||
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
Если задача вырождается в NP-полную, то веры в "СУБД, которая умеет эффективно просчитывать связность на лету" у меня как-то особо нет. Эффективнее взять нормальный низкоуровневый язык (C,Java) и банальным перебором/рекурсией. Это если задача должна выполняться на "обычных" компьютерах. Можно конечно библиотеки для работы с графами поискать, но явно что производительность будет на порядки медленнее. Ну и непонятно, что значит "очень большой граф". Я искал варианты полетов/маршрута/билетов на самолете (около 10 тыс. аэропортов /узлы/, около 100 тыс. рейсов в день по миру /связи/), на дешевеньком сервере от Amazon (4 Gb Ram) варианты перелетов в одну сторону считались вполне успешно (online, секунда-десяток секунд на ответ; "туда и обратно" не осилили) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.02.2021, 13:45 |
|
||
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
Соколинский БорисДля графов теории как таковой особо и нет. Есть, есть, куда ж она денется. И туева хуча алгоритмов с именами изобретателей к ней прилагается. Вышеописанную задачу, например, решает какой-нибудь Форд-Фалкерсон или Flood Fill. Единственное условие, что граф (а точнее список вершин) должен помещаться в ОЗУ. Так что пока ваш "большой граф" в пределах пары миллиардов вершин - волноваться особо не о чем. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.02.2021, 14:16 |
|
||
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Ну и непонятно, что значит "очень большой граф". Dimitry Sibiryakov Есть, есть, куда ж она денется. И туева хуча алгоритмов с именами изобретателей к ней прилагается. Вышеописанную задачу, например, решает какой-нибудь Форд-Фалкерсон или Flood Fill. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.02.2021, 15:24 |
|
||
|
Графовая СУБД для чайника
|
|||
|---|---|---|---|
|
#18+
Соколинский БорисFlood Fill - обычная рекурсия на стеке, там никакой суперхитрости нет. Подозреваю, что в первом тоже. Рекурсия не требуется, но так-то да, в готовых алгоритмах никакой хитрости уже не остаётся, просто берёшь и применяешь их. Четыре байта на узел в упомянутых алгоритмах дают потребление в 40 мегабайт ОЗУ на предварительное ТЗ и 400 - на возможную реальную задачу. Не вижу проблем с решением грубой силой. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.02.2021, 15:35 |
|
||
|
|
start [/forum/topic.php?fid=32&gotonew=1&tid=1539816]: |
0ms |
get settings: |
18ms |
get forum list: |
17ms |
check forum access: |
1ms |
check topic access: |
1ms |
track hit: |
59ms |
get topic data: |
8ms |
get first new msg: |
3ms |
get forum data: |
1ms |
get page messages: |
384ms |
get tp. blocked users: |
1ms |
| others: | 301ms |
| total: | 794ms |
| 0 / 0 |
