Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / NoSQL, Big Data Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 СУБД для хранения графов/матрицы связности  [new]
Spinifex
Member

Откуда:
Сообщений: 55
Коллеги,
Ищу СУБД для хранения графа. Граф не направленный, не взвешенный, размерность графа не более 100 000 узлов.
По факту нужно хранить матрицу 100 000 на 100 000, где каждый бит указывает на наличие связи. Такую СУБД в принципе не долго и самому написать, но есть проблема, что пользоваться ей должны из нескольких приложений, написанных на разных языках. Так что какое-то готовое решение - предпочтительнее.


Сейчас храним данные в SQL сервер, для каждой связи - запись в таблице. Не устраивает скорость проверки наличия связи и скорость добавления новой связи, размер БД. Очевидно, что в случае с матрицей можно добиться наилучшей производительности.
Есть ли что-то похожее?

P.S. Сейчас смотрю в сторону графовых БД, но насколько понимаю они хранят данные не как матрицу... Могу ошибаться. Также стоит отметить, что у нас нет задач поиска кратчайших путей и т.п., так что этот функционал для нас избыточен.
17 фев 15, 14:06    [17276342]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
GregTk
Member

Откуда:
Сообщений: 991
Spinifex,

Так может в памяти держать если прямо такая простая задача и сделать доступ через REST?
17 фев 15, 14:14    [17276416]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
Spinifex
Member

Откуда:
Сообщений: 55
GregTk,

Да, как вариант, но опять же не верится что нет уже готового решения.
17 фев 15, 14:23    [17276512]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
GregTk
Member

Откуда:
Сообщений: 991
Spinifex,

А сейчас какие метрики на вставку и на выборку?
17 фев 15, 14:30    [17276568]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
gandjustas
Member

Откуда:
Сообщений: 857
Блог
Spinifex
Коллеги,
Ищу СУБД для хранения графа. Граф не направленный, не взвешенный, размерность графа не более 100 000 узлов.
По факту нужно хранить матрицу 100 000 на 100 000, где каждый бит указывает на наличие связи. Такую СУБД в принципе не долго и самому написать, но есть проблема, что пользоваться ей должны из нескольких приложений, написанных на разных языках. Так что какое-то готовое решение - предпочтительнее.


1) Зачем именно матрицу?
2) Какие запросы будут?
3) Не проще SQLite с таблицей ребер и индексами?
17 фев 15, 15:19    [17276928]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
Spinifex
Member

Откуда:
Сообщений: 55
gandjustas
Spinifex
Коллеги,
Ищу СУБД для хранения графа. Граф не направленный, не взвешенный, размерность графа не более 100 000 узлов.
По факту нужно хранить матрицу 100 000 на 100 000, где каждый бит указывает на наличие связи. Такую СУБД в принципе не долго и самому написать, но есть проблема, что пользоваться ей должны из нескольких приложений, написанных на разных языках. Так что какое-то готовое решение - предпочтительнее.


1) Зачем именно матрицу?
2) Какие запросы будут?
3) Не проще SQLite с таблицей ребер и индексами?


1) В моем представлении это самый эффективный способ из возможных.
2) Запросы очень простые. Проверка существования связи и вставка связи/пачки связей.
3) У нас сейчас так и реализовано (таблица с двумя ID узлов и индексы на ней в обе стороны). Например база с 65 тыс. узлов, где все связанны со всеми занимает порядка 10 Гб. В то время как матрица с битами должна занимать 512 Мб - вполне может поместится в памяти. Да, там можно тип данных для ID узла заменить на tiny int, но все равно матрица будет быстрее. Или вы так не считаете?
17 фев 15, 15:57    [17277207]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
gandjustas
Member

Откуда:
Сообщений: 857
Блог
Spinifex
gandjustas
пропущено...


1) Зачем именно матрицу?
2) Какие запросы будут?
3) Не проще SQLite с таблицей ребер и индексами?


1) В моем представлении это самый эффективный способ из возможных.
2) Запросы очень простые. Проверка существования связи и вставка связи/пачки связей.
3) У нас сейчас так и реализовано (таблица с двумя ID узлов и индексы на ней в обе стороны). Например база с 65 тыс. узлов, где все связанны со всеми занимает порядка 10 Гб. В то время как матрица с битами должна занимать 512 Мб - вполне может поместится в памяти. Да, там можно тип данных для ID узла заменить на tiny int, но все равно матрица будет быстрее. Или вы так не считаете?


Узлы добавляться не будут? Тогда просто матрицу сериализуйте в файл и все.
Если будут, то никак матрицу хранить не выйдет, придется её восстанавливать из списка смежных вершин (по сути той же таблицы, что у вас).
17 фев 15, 23:09    [17278889]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
servit
Member

Откуда: г. Кишинёв, Республика Молдова
Сообщений: 3124
Блог
Spinifex
GregTk,

Да, как вариант, но опять же не верится что нет уже готового решения.
Решения есть, но готовы ли платить и изучать новые технологии?
GregTk
Spinifex,

А сейчас какие метрики на вставку и на выборку?
Spinifex,

Присоединяюсь к GregTk: всё-таки можно узнать Ваши текущие метрики?

Вот, что получилось у меня:

(CPU: Intel Core i5-2400, HDD: Seagate Barracuda 7200.12)

Создал 65000 записей по 65000 бит в каждой, итого - 4225000000 бит:
  • размер данных = 0.74 Mб (используется автоматическое сжатие битовых строк, поэтому при любом раскладе 4225000000 бит займут менее чем 504 Мб)
  • время заполнения всех бит:
    ~185 с. (без оптимизаций)
    ~0.036 с. (с оптимизацией)
  • время считывания всех бит (по одному) = ~111 с.


Сообщение было отредактировано: 18 фев 15, 09:45
18 фев 15, 09:41    [17279620]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
DirksDR
Member

Откуда: Пермь
Сообщений: 340
Spinifex
Сейчас храним данные в SQL сервер, для каждой связи - запись в таблице. Не устраивает скорость проверки наличия связи и скорость добавления новой связи, размер БД.

Насколько хотите увеличить скорость "проверки наличия связи"?
В 2 раза? В 10 раз? В 100 раз? Решения будут разные.
Если в 2 раза, можно таблицу сделать индексной (кластерной в смысле MS SQL) -убираем обращение к области данных таблицы, данные хранятся в структуре индекса.
До 10 раз помогут глобалные массивы (В-деревья) в СУБД Cache или другой "key-value" NoSQL СУБД.
Если в 100 раз, то надо рассматривать in-memory решения, и не обязательно СУБД.

А размер БД почему большой? Сколько записей в таблице? Приведите структуру записи.
19 фев 15, 12:47    [17286788]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
servit
Member

Откуда: г. Кишинёв, Республика Молдова
Сообщений: 3124
Блог
DirksDR
А размер БД почему большой? Сколько записей в таблице? Приведите структуру записи.
17277273
DirksDR
Насколько хотите увеличить скорость "проверки наличия связи"?
В 2 раза? В 10 раз? В 100 раз? Решения будут разные.
Вы не первый, кто просит ТС показать текущие метрики.
Похоже, ТС уже нашёл решение.
19 фев 15, 13:06    [17286965]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34534
Spinifex,

ну у нас например примерно такого же объема матрица тоже лежит в реляционной таблице, никаких проблем нет.

сто тысяч записей не так уж и много...
таблица простая, (ид матрицы, номер строки, номер столбца => значение )
и индексы (ид матрицы, номер строки, номер столбца) и (ид матрицы, номер столбца) - и все будет просто летать .
31 мар 15, 08:27    [17452667]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
servit
Member

Откуда: г. Кишинёв, Республика Молдова
Сообщений: 3124
Блог
MasterZiv
сто тысяч записей не так уж и много...
ТС жаловался в том числе на размер БД:
Spinifex
Не устраивает скорость проверки наличия связи и скорость добавления новой связи, размер БД.
Сколько у Вас занимает матрица сто тысяч на сто тысяч вместе с индексами, где все связаны со всеми?

MasterZiv
таблица простая, (ид матрицы, номер строки, номер столбца => значение )
и индексы (ид матрицы, номер строки, номер столбца) и (ид матрицы, номер столбца) - и все будет просто летать.
Spinifex
У нас сейчас так и реализовано (таблица с двумя ID узлов и индексы на ней в обе стороны). Например база с 65 тыс. узлов, где все связанны со всеми занимает порядка 10 Гб.
Странно, почему у ТС не летает. Наверное, всё-таки MSSQL и Sybase были по-разному "приготовлены".

Сообщение было отредактировано: 31 мар 15, 10:19
31 мар 15, 10:16    [17453026]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34534
servit
MasterZiv
сто тысяч записей не так уж и много...
ТС жаловался в том числе на размер БД:
Spinifex
Не устраивает скорость проверки наличия связи и скорость добавления новой связи, размер БД.
Сколько у Вас занимает матрица сто тысяч на сто тысяч вместе с индексами, где все связаны со всеми?


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

но лучше конечно у него спросить.

MasterZiv
таблица простая, (ид матрицы, номер строки, номер столбца => значение )
и индексы (ид матрицы, номер строки, номер столбца) и (ид матрицы, номер столбца) - и все будет просто летать.
Spinifex
У нас сейчас так и реализовано (таблица с двумя ID узлов и индексы на ней в обе стороны). Например база с 65 тыс. узлов, где все связанны со всеми занимает порядка 10 Гб.
Странно, почему у ТС не летает. Наверное, всё-таки MSSQL и Sybase были по-разному "приготовлены".


а кто говорил про MSSQL и Sybase ?

хотя на самом деле это все равно, хоть mysql.
31 мар 15, 11:52    [17453540]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
servit
Member

Откуда: г. Кишинёв, Республика Молдова
Сообщений: 3124
Блог
MasterZiv
а кто говорил про MSSQL и Sybase ?
Про MSSQL - ТС
Spinifex
Сейчас храним данные в SQL сервер
, про Sybase - это было моё предположение, исходя из Вашего профиля.

И всё же, каков будет размер БД в Вашей СУБД для озвученных размеров матрицы?
31 мар 15, 12:09    [17453627]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34534
servit
про Sybase - это было моё предположение, исходя из Вашего профиля.


Предположение было неверное.
Матрица у меня в БД на Oracle. Но ещё раз -- это всё равно. Там будут незначительные нюансы, но в общем, всё равно.
31 мар 15, 15:40    [17455041]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
GVF112GVF
Guest
Spinifex,

Есть такая база данных Distributed Graph Database Titan -
http://thinkaurelius.github.io/titan/

С уважением,
Вадим.
6 апр 15, 20:16    [17480751]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
Winnipuh
Member [заблокирован]

Откуда: Київ
Сообщений: 10436
Neo4j
7 апр 15, 09:01    [17481810]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
anryal
Member

Откуда:
Сообщений: 145
OrientDB
20 апр 15, 12:56    [17538897]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: СУБД для хранения графов/матрицы связности  [new]
конечно Вася
Member

Откуда: Брянщина
Сообщений: 181
Winnipuh
Neo4j


Кто-нибудь из русскоговорящих остался в коммньюнити neo4j?
19 июн 18, 10:21    [21502197]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 3151
Spinifex
Коллеги,
Ищу СУБД для хранения графа. Граф не направленный, не взвешенный, размерность графа не более 100 000 узлов.
По факту нужно хранить матрицу 100 000 на 100 000, где каждый бит указывает на наличие связи. Такую СУБД в принципе не долго и самому написать, но есть проблема, что пользоваться ей должны из нескольких приложений, написанных на разных языках. Так что какое-то готовое решение - предпочтительнее.


Сейчас храним данные в SQL сервер, для каждой связи - запись в таблице. Не устраивает скорость проверки наличия связи и скорость добавления новой связи, размер БД. Очевидно, что в случае с матрицей можно добиться наилучшей производительности.
Есть ли что-то похожее?

P.S. Сейчас смотрю в сторону графовых БД, но насколько понимаю они хранят данные не как матрицу... Могу ошибаться. Также стоит отметить, что у нас нет задач поиска кратчайших путей и т.п., так что этот функционал для нас избыточен.


SQL Server 2017?
20 июн 18, 17:15    [21507478]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
Eleanor
Member

Откуда:
Сообщений: 2387
Ролг Хупин,

Посмотрела документацию MS по SQL Graph-у - даже там внизу несколько негативных отзывов: MS всего лишь создал "синтаксический сахар" поверх реляционной по сути реализации.
В результате получатся ровно те же таблицы, что у ТС, с похожим размером и похожей производительностью.
21 июн 18, 19:10    [21510660]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 3151
Eleanor
Ролг Хупин,

Посмотрела документацию MS по SQL Graph-у - даже там внизу несколько негативных отзывов: MS всего лишь создал "синтаксический сахар" поверх реляционной по сути реализации.
В результате получатся ровно те же таблицы, что у ТС, с похожим размером и похожей производительностью.


мэм, что-то я про сахар не нашел там, однако, хорошая фича.
Негативные отзывы будут всегда и обо всём, я, например, могу вам написать десяток матерных негативных отзывов про FTS, и даже для 2017.
22 июн 18, 11:18    [21512334]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
Eleanor
Member

Откуда:
Сообщений: 2387
Ролг Хупин
что-то я про сахар не нашел там

I see no section about indexing and why this is better/different from implementing it traditionally. Is this merely syntactic sugar?

Ролг Хупин
однако, хорошая фича

"Хорошая" - это в текущей версии Sql Server 2017 или в будущем? Уже ей пользовались?

ТС спрашивал про размер и производительность:

- Графы MS пока что используют традиционные таблицы с традиционными индексами.
Если залить данные ТС в граф, то это будут те же таблицы, что у него есть, но с опциями AS NODE и AS EDGE и несколькими скрытыми полям (2 и 8 полей). Объем данных в итоге увеличится.

- Синтаксис MATCH эквивалентен нескольким JOIN, в планах выполнения запросов будут JOIN-ны. Производительность запросов немного выше, т.к. строятся другие планы выполнения.

Возможно, ТС есть смысл перелить данные в граф MS, но лишь потому что он уже хранит их в Sql Server.
22 июн 18, 13:12    [21512897]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 3151
Eleanor
Ролг Хупин
что-то я про сахар не нашел там

I see no section about indexing and why this is better/different from implementing it traditionally. Is this merely syntactic sugar?

Ролг Хупин
однако, хорошая фича

"Хорошая" - это в текущей версии Sql Server 2017 или в будущем? Уже ей пользовались?

ТС спрашивал про размер и производительность:

- Графы MS пока что используют традиционные таблицы с традиционными индексами.
Если залить данные ТС в граф, то это будут те же таблицы, что у него есть, но с опциями AS NODE и AS EDGE и несколькими скрытыми полям (2 и 8 полей). Объем данных в итоге увеличится.

- Синтаксис MATCH эквивалентен нескольким JOIN, в планах выполнения запросов будут JOIN-ны. Производительность запросов немного выше, т.к. строятся другие планы выполнения.

Возможно, ТС есть смысл перелить данные в граф MS, но лишь потому что он уже хранит их в Sql Server.


про сахар там вопрос, но в принципе многие возможности в скл сервер можно обозвать сахаром. Да и хранение - в базе, традиционно, но тут нао определиться, а что - это не устраивает?
Они , например, и иерархию сделали через сахар+реализацию, очень неплохо.
22 июн 18, 14:20    [21513174]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения графов/матрицы связности  [new]
Eleanor
Member

Откуда:
Сообщений: 2387
Ролг Хупин
Да и хранение - в базе, традиционно, но тут надо определиться, а что - это не устраивает?
Они, например, и иерархию сделали через сахар+реализацию, очень неплохо.

Скорее всего пользователи ждали специализированное решение, увидев громкое название Graph Database - высокую производительность, запросы в несколько раз быстрее. Ожидания не оправдались.
10 – 15 percent performance advantage, как в ссылке выше... подозреваю, это не то, на что надеялся ТС.
22 июн 18, 15:57    [21513576]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / NoSQL, Big Data Ответить