ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничный куб. Концепция.
100 сообщений из 100, показаны все 4 страниц
  все  
Вторничный куб. Концепция.
    #39652081
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Привет друзья.

Есть тема над которой я думаю последние несколько недель.
Я постараюсь не быть многословным (это мой косяк) и кидать snippets вместо множества букв.

1. Создание (Пишу на псевдо-языке который может быть C#/D/Rust/Java).
Код: sql
1.
Cube cube = new MCube(2580,2580,2580).withStaticAllocation();



2. Наполнение фактами . В данном случае предикат isMutuallySimple утверждает что тройка чисел - взаимно простые.
Код: sql
1.
2.
for(i in 0..2579) for (j in 0..2579) for (k in 0..2579) 
   if (isMutuallySimple(i,j,k)) cube.set(i,j,k);



3. Проверка куба .
Код: sql
1.
cube.check(7,9,16) == true


Дает истину т.к. 7 и 9 и 16 взаимно простые. Это просто пример. В предикате
может стоять ваша бизнес-логика. Проверка физ-лица. Предприятия. Тех-средства.

Фак.

Задлянафига. . Ответ - я искал аналог структурам данных типа HashTable. Возможный поинт - экономия.

Цифры. Для куба с расходом памяти в 2Gbyte. (~17 179 869 184 boolean элемента)
SizeDimensions1310722258033624
Переводя на наш язык. Хранение таблицы фактов с тремя колонками с кардинальностью
порядка 2 с половиной тысячи потребует в самом худшем случае 2Г оперативы.

Дальше - думайте. Прикидывайте.

Где применять. Хм... изначально я думал о кешах Хибернейт. Чуть позже задача стала более общая. Я стал думать о пользе кубиков.

Еще поинты.
Цифры - это не уныло. Нужен справочник строки - цифры.

Размерность куба должна быть гибкой. Ну... по крайней мере он не должен
падать при доступе к элементу с индексом 2581 в нашем кейсе. Я думаю над
этим.

Итератор. Собственно поддержать можно. Но будут накладные. Подумайте.

Что не ложится в куб. Вещественные величины. Даты. Время. Деньги.

Что круто ложится в куб. Перечисления. Справочники.

Ну вобщем все.

Пишите каменты. Имплементации пока нет.
...
Рейтинг: 0 / 0
29.05.2018, 22:01
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652209
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я так понимаю тоже самое можно получить создав тип
Код: sql
1.
2.
3.
4.
class my_type_t {
public:
  int i, j, k;
}


Прописать в нем необходимые операторы, а дальше использовать стандартные контейнеры. Например HashTable<my_type_t> или HashSet<my_type_t>

Или я что-то недопонимаю?
...
Рейтинг: 0 / 0
30.05.2018, 08:44
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652214
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЦифры. Для куба с расходом памяти в 2Gbyte. (~17 179 869 184 boolean элемента)
SizeDimensions1310722258033624
Переводя на наш язык. Хранение таблицы фактов с тремя колонками с кардинальностью
порядка 2 с половиной тысячи потребует в самом худшем случае 2Г оперативы.
ИМНО ты биткарту N-мерную изобрел, тут достаточно индекс из N-мерной к одномерной привести и пользоваться как обычно.

Например по данным твоего примера:
Код: plaintext
1.
   if (isMutuallySimple(i,j,k)) cube.set(i,j,k);


равносильно
Код: plaintext
1.
if (isMutuallySimple(i,j,k)) bitmap[i * 2580 * 2580 + j * 2580 + k] = true;
...
Рейтинг: 0 / 0
30.05.2018, 08:49
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652218
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да. Верно. Эта задача решается хеш-табличкой но в моем варианте схема хранения данных расходует 1 bit на каждую запись.

Вообще. Это не куб. В общем случае это многмерный параллелепипед.
...
Рейтинг: 0 / 0
30.05.2018, 08:53
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652224
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, я не изобрел многомерный массив. Я думаю о том как использовать всем известную структуру для храненя строковых ключей или ключей типа enum.
...
Рейтинг: 0 / 0
30.05.2018, 08:58
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652245
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima T, я не изобрел многомерный массив.
ИМХО именно его изобрел. Точнее многомерную биткарту изобрел, а она по сути обычный массив, только элемент 1 бит.
Т.е. в итоге получение индекса нужного элемента сведется к его расчету по тем же правилам, как и в многомерных массивах.
maytonЯ думаю о том как использовать всем известную структуру для храненя строковых ключей или ключей типа enum.
enum отлично вписывается в твою систему. Их надо просто пронумеровать 0 ... N-1
Похуже впишутся ID сгенеренные счетчиками, но можно пооптимизировать.

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

Я не понимаю куда можно применить изобретение твое? В терминах РСУБД ты изобрел проверку составного первичного ключа. Есть/нет.

Как понимаю в итоге твоя задача сводится к сравнению характеристик хэш-таблицы и биткарты. Или к изобретанию еще какого-то хранилища с похожими свойствами. Если так, то тут нет универсального решения, надо исходить из конкретного случая, т.е. нужна статистика использования конкретных данных.
...
Рейтинг: 0 / 0
30.05.2018, 09:33
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652265
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я не буду настаивать на универсализме. Его здесь нет. Я попробую вспомнить тот юзкейс с которого начал думать о биткарте.
...
Рейтинг: 0 / 0
30.05.2018, 09:53
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652319
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Вещь может быть нужная. Если не тупо маппинг "многомерный массив" - "одномерный", а какие нибудь структуры предназначенные для работы с разряженными данными a la компрессия на лету.

Если посмотреть на табличку mayton'а, становится понятным, что при кол-ве исмерений >= 4, простейший куб становится ну уж очень маленьким, для любых осмысленных бизнес задач.
...
Рейтинг: 0 / 0
30.05.2018, 11:10
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652444
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Лучше исходить из предположения что не все измерения одинаково большие. Поле gender будет иметь 2 значения male, female и это даст в хранилище просто удвоение биткарты. Но никак не умножение на 2000 как я нарисовал в учебном примере.
...
Рейтинг: 0 / 0
30.05.2018, 13:11
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652457
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Мне нужен был в свое время некое подобие Subj. Но не биткарта. а куб целых чисел.

Есть перелет на самолете. Есть набор его характеристик. Нужно из сотен миллионов вариантов перелета выбрать "оптимальный"

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

Другое дело, что мне хранение всех вариантов было не нужно. Просто при проходе расчетов хранил "100 лучших", все, что заведомо хуже этих "лучших", сразу же отбрасывал. Если менялись критерии оценки, запускал поиск на графе повторно.

Но если бы была возможность куда-то сложить хотя бы биткарту, наверное было бы полезно. Но размерность у таких кубов в реальных бизнес задачах должна быть "дикая" (в моем случае, наверное, >10 измерений).
...
Рейтинг: 0 / 0
30.05.2018, 13:33
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652637
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid Kudryavtsev,

Хм. Интересно. А насколько плотно ваш куб заполнялся внутри? И был-ли какой-то ранг его осей? Ну тесть. Мой вариант куба предполагает полное отсутствие критериев близости двух фактов.
...
Рейтинг: 0 / 0
30.05.2018, 15:58
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652663
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonLeonid Kudryavtsev,

Хм. Интересно. А насколько плотно ваш куб заполнялся внутри? И был-ли какой-то ранг его осей? Ну тесть. Мой вариант куба предполагает полное отсутствие критериев близости двух фактов.

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

Ранг и критерии были, в этом и была главная идея. Ранг (вес) отдельных характеристик менялись в зависимости от выбора пользователя/интерфейса (в прод не ушло, т.ч. дизайн был так себе). В том числе, вес можно было сделать "0" или "очень много", тогда система понимала, что все варианты с этой характеристикой нужно или отбросить как совсем неподходящие или, наоборот, пытаться искать варианты с такой характеристикой.

Большинство характеристик были представлены как дискретные значения по определенному измерению в кубе. Например цена - просто с шагом в 10$ (шаг динамически менялся, т.е. реализация была не настолько "топорно", но идея ровно такая), время - с шагом в 15 мин., кол-во пересадок от 0 до 7 (были найдены такие маршруты, где меньше чем за 8 рейсов "кусочков" не долететь!, конкуренты такие маршруты вообще находить не умели/ют).

Ряд характеристик передавал как список. Например аэропорты, где осуществляется пересадка. Т.ч. даже запросы типа "не хочу лететь через Лондон", выполнялись по той же схеме.

Собственно по итогам, критерий близости/дальности и получался. Собственно "близкие" варианты "схлопывались" (т.к. размерность была дискретной, близкие варианты просто попадали в одно "ячейку" и оставался наилучший), самые "левые/мусорные" - отбрасывались, остаток ранджировался.
...
Рейтинг: 0 / 0
30.05.2018, 16:17
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652673
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonплотно ваш куб заполнялся внутри
Совершенно не плотно.
...
Рейтинг: 0 / 0
30.05.2018, 16:27
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652746
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid Kudryavtsev,

Мощно. Это похоже на транспортную задачу. Но не в плоскости а в объеме.
...
Рейтинг: 0 / 0
30.05.2018, 17:56
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652772
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonLeonid Kudryavtsev,

Мощно. Это похоже на транспортную задачу. Но не в плоскости а в объеме.

Ну в общем задача и была "транспортой"

Найти маршрут из A в B

Проблема была в критериях. Т.к. изначально задача ставилась "самое дешевое", но по ходу работы выяснилось, что "кругосветный перелет с 5 пересадками в течение недели за 15 $ " - это круто, но для большинства пользователей, вряд ли нужная вещь )))

И критериев оценки стало очень много
...
Рейтинг: 0 / 0
30.05.2018, 18:36
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652797
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ViPRos
Участник
Leonid Kudryavtsev,

Это простая задача
...
Рейтинг: 0 / 0
30.05.2018, 19:29
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652810
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Она не простая в целевой функции. Быстро и дешево. Это уже набор взаимоисключающих критериев. И нужна новая целевая функция.
...
Рейтинг: 0 / 0
30.05.2018, 20:04
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652848
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ViPRos
Участник
mayton,

быстро потом дешево (самый дешевый из самых быстрых)
дешево потом быстро (самый быстрый из самых дешевых)
скорость * w1 + стоимость * w2 (тут надо очень хорошо подобрать w1;w2)
у меня еще и качество добавлено в расписании (семантически : выбраны лучшие - оборудование, материал, персонал из возможных)
...
Рейтинг: 0 / 0
30.05.2018, 21:47
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652863
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В продолжение темы кубика. Как вообще возникла постановка.

Кейс №1

Лет несколько назад я оптимизировал приложение. Крупный банк. Веб. Система управления HR.
Там была базейка. Схема безопасность. Связка таблиц многие-ко-многим. Через промежуточную.

Вобщем

Код: sql
1.
Entitlement <-> Entitlement2UiElement <-> UiElelement



Сущность Entitilement это что-то вроде роли или привилегии в системе. Или группы ролей хрен их знает.
Они связаны многие-ко-многим. Далее по теме меня могут спросить - асху яли... почему ты не сделал группы.
Я отвечу что это и есть группы. Просто все сложно.

Честь ентайтлментов была в работе. Часть сдохла. Часть дублировала другую честь. И были UI элементы которые
не имели вообще возможности отображаться. Не суть. Вобщем. Это матрица. Технически Хибернейт решал эту задачу.
Был Дао который извлекает пользователя потом его ентайтлмент и потом его графические элементы. Но поскольку
я - перфекционист то я думал о путях оптимизации. Биткарта - как частный случай. По сути Дао должен отвечать
на вопрос. Можно ли отобразить данный ID UI элемента для данного энтайтлмента данного пользователя.

Я не успел имплементировать матричное решение. Проект завершился. Но убежден что кеш на базе гипер-куба
был-бы удачен. Условия - были благоприятны. Политики ентайлтлемнтов менялись редко. Раз в сутки система перегружалась.
Тоесть даже без управления обновлениями кеш был-бы эффективен.

Кейс №2

Таблица с булевыми атрибутами. Следующая постановка - не реальна а скорее переосмысление.
Есть класс задач где индексы БД - неэффективны. Например физ-лица и некоторые атрибуты.

IDNameGenderIsClientCreditWorthyAdultDrawnToCriminalDrivingACarWasAbroadSocialClass0maytonmalennnnnnExtra1DimamaleyyyyynClassic2LeonidmaleynynynExtra
Имеет место 9-мерный куб с неравномерной кардинальностью. В 9-мерном пространстве - это
вытянутый "брусок" где наибольшая размерность соответствует ID пользователя. Далее - класс
соц-страхования (может быть 10-20 записей в справочнике хрен знает сколько но явно меньше
чем клиентов). Остальные атрибуты - двумерные. Несмотря на кажущуюся невообразимость
и сложность представления - биткарта хавает. И хранит весь объем информации достаточно
легко. Как я уже говорил данная структура данных плохо поддерживает итератор да нам и не надо.
Извлечение факта. Тоесть проверка к примеру того что Мэйтон не был судим и не был за границей
занимает - микросекунды и ложится умеренный объем ресурсов.

Технически БД решает эту задачу путем построение специальный bitmap-индексов.
Но (мы то знаем) что они эффективны только R/O и в совокупности с выборкой по другим
признакам. Вобщем БД - не рулит. Б-деревья плохо работают с выборкой низкой кардинальности.
Здесь можно долго теоретизировать но как факт - возьмите большую (овер миллиард записей)
таблицу и попробуйте проиндексировать совокупность признаков. Забегая вперед я скажу
что знаю еще один workaround типа фасетного поиска - но тема не об этом. Тема - кубики
и низкая кардинальность. Мы с вами можем разве-что разойтись в количественых оценках.
Кому 10 - низкая. А кому и 100 тысяч. Вобщем. Думайте.

Я прошу прощения за некую натянутость и синтетичность постановки но я далее ожидаю
предложений по использованию именно от вас. От мемберов форума.
...
Рейтинг: 0 / 0
30.05.2018, 22:14
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653073
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Как понимаю в обоих случаях задача сводится к проверке некоторых свойств конкретного объекта, причем набор свойств у каждого объекта одинаков.

Можно вместо многие-ко-многим свести к одной таблице: {id, name, attr1, attr2, attr3 ...}, собственно второй пример так показан. По-сути это обычная денормализация.

В целях экономии памяти можно пойти дальше, заменить {attr1, attr2, attr3 ...} на битовое представление, т.е. биткарту + описание структуры, например attr1 - 0й бит, attr2 - 1й и т.д. Для атрибутов не вмещающихся в один бит можно выделять несколько.

В итоге получаем что надо кэшировать {id, bitmap}, т.е. для организации кэша достаточно ассоциативного массива.
...
Рейтинг: 0 / 0
31.05.2018, 10:25
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653076
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
В общем я к тому что надо кэш хранить в виде: один объект - одна биткарта с его свойствами.
...
Рейтинг: 0 / 0
31.05.2018, 10:33
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653083
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonТехнически БД решает эту задачу путем построение специальный bitmap-индексов.
Но (мы то знаем) что они эффективны только R/O и в совокупности с выборкой по другим
признакам. Вобщем БД - не рулит. Б-деревья плохо работают с выборкой низкой кардинальности.
Здесь можно долго теоретизировать но как факт - возьмите большую (овер миллиард записей)
таблицу и попробуйте проиндексировать совокупность признаков. Забегая вперед я скажу
что знаю еще один workaround типа фасетного поиска - но тема не об этом. Тема - кубики
и низкая кардинальность. Мы с вами можем разве-что разойтись в количественых оценках.
Кому 10 - низкая. А кому и 100 тысяч. Вобщем. Думайте.
Как понимаю тут ты рассуждаешь над обратной задачей: найти объект(ы) по свойствам, если так то был такой топик
...
Рейтинг: 0 / 0
31.05.2018, 10:41
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653133
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я бы не хотел тащить сюда фасетный поиск. Его постановка другая. Мы находим множество товаров обладающих сетом свойств.

А куб просто проверяет что существует 1 такой бизнес факт. И все.
...
Рейтинг: 0 / 0
31.05.2018, 11:50
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653270
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
Считать всю ночь в СУБД, а утром задавать вопросы и получать ответы. Если подсчитывать на лету, в БД может быть постоянно актуальный кубешник
...
Рейтинг: 0 / 0
31.05.2018, 13:54
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653290
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я добавлю чего куб не любит.

1. Изменения размера осей. Тоесть реорганизация куба это в общем случае - пересоздание нового. Поэтому лучше заложить +20 длины осей про запас.

2. Редкое заполнение. В этом случае его польза неочевидна и программисту лучше взять hashtable.

3. Поиск по неполному набору атрибутов. Вместо поиска точки мы будем искать множество фактов на гипер-прямой или гиперплоскости и т д. O(1) превращается в линейный или полиномиальный.
...
Рейтинг: 0 / 0
31.05.2018, 14:16
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653334
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton3. Поиск по неполному набору атрибутов. Вместо поиска точки мы будем искать множество фактов на гипер-прямой или гиперплоскости и т д. O(1) превращается в линейный или полиномиальный.
Если набор атрибутов всегда полный, то я уже выше предлагал рассматривать биткарту как многомерный массив бит 21452572

При большом размере биткарты возможно фильтр Блума как-то подойдет.
...
Рейтинг: 0 / 0
31.05.2018, 14:47
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653351
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton, почитай про карту Карно.
https://ru.wikipedia.org/wiki/Карта_Карно Куб Карно́ — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок[1]. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определённую плоскую развертку n-мерного булева куба.
...
Рейтинг: 0 / 0
31.05.2018, 15:04
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653384
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЦифры. Для куба с расходом памяти в 2Gbyte. (~17 179 869 184 boolean элемента) ...
2 Гб много для оперативки, но если использовать мапинг файла в память, то можно 2 Тб легко задействовать. Дисковая память недорогая, для этой задачи хватит HDD.

Большие разреженные файлы из ноликов ОС умеют создавать, т.е. наполнение будет относительно быстрое. При использовании отображаться в память файл будет постранично, т.е. оперативки много не потребуется.
...
Рейтинг: 0 / 0
31.05.2018, 15:29
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653397
Roman Mejtes
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman Mejtes
Участник
maytonЯ добавлю чего куб не любит.
3. Поиск по неполному набору атрибутов. Вместо поиска точки мы будем искать множество фактов на гипер-прямой или гиперплоскости и т д. O(1) превращается в линейный или полиномиальный.
Одна из базовых основ кубов, это получение среза.... а не получения конкретной точки (Obs)
...
Рейтинг: 0 / 0
31.05.2018, 15:40
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653411
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Roman MejtesmaytonЯ добавлю чего куб не любит.
3. Поиск по неполному набору атрибутов. Вместо поиска точки мы будем искать множество фактов на гипер-прямой или гиперплоскости и т д. O(1) превращается в линейный или полиномиальный.
Одна из базовых основ кубов, это получение среза.... а не получения конкретной точки (Obs)
Вы говорите об OLAP. Я говорю о другой структуре данных.
...
Рейтинг: 0 / 0
31.05.2018, 15:58
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653414
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima Tmayton3. Поиск по неполному набору атрибутов. Вместо поиска точки мы будем искать множество фактов на гипер-прямой или гиперплоскости и т д. O(1) превращается в линейный или полиномиальный.
Если набор атрибутов всегда полный, то я уже выше предлагал рассматривать биткарту как многомерный массив бит 21452572

При большом размере биткарты возможно фильтр Блума как-то подойдет.
По первому пункту - да. 100%.

По фильтрам. Почти да. При условии что мы делаем частичное кеширование. Доступ к БД по прежнему нужен.

Я не против Блума но сначала хочу исчерпать возможности сваей первой постановки.
...
Рейтинг: 0 / 0
31.05.2018, 16:02
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653417
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima Tmayton, почитай про карту Карно.
https://ru.wikipedia.org/wiki/Карта_Карно Куб Карно́ — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок[1]. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определённую плоскую развертку n-мерного булева куба.
Карно - это графическое представление булевой функции. Сам же метод карно требует участия человека эксперта который эту минимизацию делает вручную.

Альтернатива это Квайн который автоматизирован но не факт что построит компактную функцию. Собственно здесь можно поставить вопрос о принципиальной возможности что то минимизировать.
...
Рейтинг: 0 / 0
31.05.2018, 16:07
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653547
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
Конкретная задача, пусть хотя бы для примера, сильно бы упростила бы поиск решения.
...
Рейтинг: 0 / 0
31.05.2018, 18:44
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653556
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ViPRos
Участник
hVosttКонкретная задача, пусть хотя бы для примера, сильно бы упростила бы поиск решения.
УГУ.
...
Рейтинг: 0 / 0
31.05.2018, 19:17
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653560
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima Tпропущено...

Если набор атрибутов всегда полный, то я уже выше предлагал рассматривать биткарту как многомерный массив бит 21452572

При большом размере биткарты возможно фильтр Блума как-то подойдет.
По первому пункту - да. 100%.
Если да, то у меня нет других идей, разве что заняться изобретательством выделения памяти под биткарту, т.к. ноликов там будет намного больше чем единичек. Один из вариантов уже предлагал 21457935
maytonПо фильтрам. Почти да. При условии что мы делаем частичное кеширование. Доступ к БД по прежнему нужен.

Я не против Блума но сначала хочу исчерпать возможности сваей первой постановки.
ИМХО на больших размерах Блум самое то что надо, пусть небольшую часть придется допроверить по БД, но иначе террабайтные биткарты.
...
Рейтинг: 0 / 0
31.05.2018, 19:25
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653576
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dima TmaytonПо фильтрам. Почти да. При условии что мы делаем частичное кеширование. Доступ к БД по прежнему нужен.

Я не против Блума но сначала хочу исчерпать возможности сваей первой постановки.
ИМХО на больших размерах Блум самое то что надо, пусть небольшую часть придется допроверить по БД, но иначе террабайтные биткарты.
Добавлю: мне кажется ты фильтр Блума изобретаешь, но такой который дает гарантированное "Есть/Нет" вместо "Возможно есть/Нет". Я бы пошел по пути повышения вероятности "Возможно есть".

Если так и исходные данные у тебя мало меняются, то можно поиграть функциями хэшей Блума, чтобы при "Возможно есть" был минимум "реально нет". Т.е. либо сразу получаешь ответ "нет", либо делаешь запрос к БД и минимизируешь ответ "Нет" за счет подбора функций хэшей.
...
Рейтинг: 0 / 0
31.05.2018, 19:48
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653584
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonЦифры. Для куба с расходом памяти в 2Gbyte. (~17 179 869 184 boolean элемента) ...
2 Гб много для оперативки, но если использовать мапинг файла в память, то можно 2 Тб легко задействовать. Дисковая память недорогая, для этой задачи хватит HDD.

Большие разреженные файлы из ноликов ОС умеют создавать, т.е. наполнение будет относительно быстрое. При использовании отображаться в память файл будет постранично, т.е. оперативки много не потребуется.
На файловой системе (random access) надо подумать об умной буферизации. При начальной инициализации.
...
Рейтинг: 0 / 0
31.05.2018, 19:54
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653593
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ViPRoshVosttКонкретная задача, пусть хотя бы для примера, сильно бы упростила бы поиск решения.
УГУ.
Я попробую сделать учебный пример. Но вы наверное не в курсе моей традиции создавать пятничные топики мозгового штурма. Я делюсь мыслями а не бизнес постановкой.

Вобщем не ждите от меня ТЗ. Фантазируйте. Дополняйте.
...
Рейтинг: 0 / 0
31.05.2018, 20:39
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653594
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima Tпропущено...

2 Гб много для оперативки, но если использовать мапинг файла в память, то можно 2 Тб легко задействовать. Дисковая память недорогая, для этой задачи хватит HDD.

Большие разреженные файлы из ноликов ОС умеют создавать, т.е. наполнение будет относительно быстрое. При использовании отображаться в память файл будет постранично, т.е. оперативки много не потребуется.
На файловой системе (random access) надо подумать об умной буферизации. При начальной инициализации.
Суть этой идеи в том что об этом будет думать ОС, т.е. не надо заморачиваться вопросом, который ты задал.
...
Рейтинг: 0 / 0
31.05.2018, 20:40
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653599
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima Tmaytonпропущено...

На файловой системе (random access) надо подумать об умной буферизации. При начальной инициализации.
Суть этой идеи в том что об этом будет думать ОС, т.е. не надо заморачиваться вопросом, который ты задал.
Не согласен.
...
Рейтинг: 0 / 0
31.05.2018, 20:56
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653601
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima Tпропущено...

Суть этой идеи в том что об этом будет думать ОС, т.е. не надо заморачиваться вопросом, который ты задал.
Не согласен.
Идею террабайтных биткарт конечно можно развивать, но это сложно и дорого, поэтому я и предложил воспользоваться тем что уже есть, т.е. средствами ОС.
...
Рейтинг: 0 / 0
31.05.2018, 21:01
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653603
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima Tmaytonпропущено...

Не согласен.
Идею террабайтных биткарт конечно можно развивать, но это сложно и дорого, поэтому я и предложил воспользоваться тем что уже есть, т.е. средствами ОС.
Давай идею файлового куба отложим на некоторое время. Просто у меня реально много мыслей по самой первой версии. И я их еще для себя не продумал.

Вернемся к диску потом. Позже.
...
Рейтинг: 0 / 0
31.05.2018, 21:06
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653606
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
maytonЯ попробую сделать учебный пример. Но вы наверное не в курсе моей традиции создавать пятничные топики мозгового штурма. Я делюсь мыслями а не бизнес постановкой.

Без примера решать задачи это из области принеси то, незнаю что.

Потому что первым же ответом от Dima T приводится законченное решение вашей задачи. Сколько угодно мерный массив в современной информационной системе будет именно одномерным массивом со смещениями, поэтому сказано про битовую карту -- это та голова, выше которой не прыгнешь. Технические вопросы, типа как обойти ограничение на ОЗУ, тоже предлагались -- отражение на файл.

Но если это всё не то, тогда давайте обсуждать в контексте какой-то конкретной задачи. Типа вот есть это и это, а надо так и так. Тогда будет смысл думать.

maytonВобщем не ждите от меня ТЗ. Фантазируйте. Дополняйте.

Тогда надо в область нейросететей, искусственного интеллекта, квантовых кубитов и т.п. Всё равно это невозможно проверить и ни в чём убедиться. Зато фантазировать -- сколько угодно :)
...
Рейтинг: 0 / 0
31.05.2018, 21:14
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653624
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
hVosttТогда надо в область нейросететей, искусственного интеллекта, квантовых кубитов и т.п. Всё равно это невозможно проверить и ни в чём убедиться. Зато фантазировать -- сколько угодно :)
Ну... на правах топик-стартера я всё-таки предлагаю ограничиться темой первого поста.
Но если вы имеете что сказать по ИИ или нейросетям - прошу создавайте новую ветку.
Я возможно подключусь.
...
Рейтинг: 0 / 0
31.05.2018, 23:32
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653634
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
По поводу фильтра Блума. Я привожу некий субъективный сравнительный анализ куба и фильтра Блума
в виде таблички. По каждому пункту я готов дать свою аргументацию. Некоторые пункты которые
я отметил звездочной (*) требуют детализации и я ее отпишу чуть позже по мере времени.
...
Рейтинг: 0 / 0
01.06.2018, 00:22
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653636
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Комментарии.

(*) Memory consuming MBHC определяется формулой. . Формулой произведения кардинальностей всех измерений кортежей.
Плюс накладные на использование справочников измерений.

Допустим у нас есть табличка фактов с 4 колонками на 80000 строк. Несмотря на большой объем
сегмента данных - раздельные величины кардинальностей равны 8, 5, 3, 10. Поля имеют различные
типы данных. Строка. Дата. Число. И еще одно число. Но тип нам не особо интересен. Мы создаём 4 справочника.
для отображения строк дат и уникальных чисел на ограниченный диапазон индексов (желательно начиная с нуля).
0..7, 0..4 e.t.c. Конструем куб с объемом на 8*5*3*10 = 1200 бит или 150 байт. Это и есть наш memory consuming
и некое сериализованное в памяти состояние 4 справочников размер которых я сейчас посчитать не могу
но вы можете прикинуть сами исходя из средних метрик для продуктовых баз. Что там? Имена? Коды товаров?
Придумайте сами.
...
Рейтинг: 0 / 0
01.06.2018, 00:35
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653637
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
(**) Поддержка интерфейа Итерации в многомерном булевом кубе возможна.

В самом начале топика я писал что невозможно. Или сложно.

Вобщем смотрите. Основное назначение куба - хранение и извлечение фактов в режиме жесткого OLTP.
Тоесть мы предполагаем точечные запросы вида

Код: sql
1.
2.
SELECT booleanValue FROM CUBE1 
WHERE (field1,field2,field3,field4) in (1,4,2,0)


Какой смысл делать переборные алгоритмы в таких условиях? Я не знаю. Может просто COUNT() всех фактов.

Придумайте сами. Временная сложность будет линейна если мы скипаем field1 и будет расти если отбрасывать
другие поисковые ограничители. Словом поиск по полному совпадению всех ключей кортежа - предпочтителен.
Итерация - возможна но куб теряет смысл. Тогда лучше искать в БД.
...
Рейтинг: 0 / 0
01.06.2018, 00:43
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653638
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
(***) Поддержка интервальных запросов.

В начале топика я упомянул о том что оси куба соответвтуют перечислимым величинам. Enumeration.
Но в принципе если наша величина - это средне-годовой доход то у нас появляется возможность
вести ранг или сравнение кортежей в кубе по одной оси.

Например выбрать все факты где средне-годовой доход в диапазоне от 50 000 $ до 950 000 $.
Разумеется оригинальный запрос должен будет быть трансформирован через справочних
классов доходов в некое целочисленное значение индекса. Здесь для достижения эффекта
мы должны физически организовать куб таким образом чтобы факты этого диапазона лежали рядом.
Код: sql
1.
2.
SELECT decodeDimension1(), decodeDimension2() FROM CUBE2 
WHERE map2Dimension4Range(50 000$, 950 000$)
...
Рейтинг: 0 / 0
01.06.2018, 00:52
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653639
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Далее (****) Расширение сегмента данных для фильтра Блума.

Я не буду здесь долго описывать теорию. Можете почитать Вики. Фильтр Блума принципиально не расширяется.
Его можно пересоздать заново и используя оригинальную БД прогрузить весь amount фактов в новый сегмент.
Добавление новых фактов - возможно но приводит к потере избирательности.

Я-бы ввел свою достаточно простую метрику. Количество нулевых и единичных битов в карте должны
быть примерно 50%. Как только единички достигают половины по мере заполнения - самое время дать
сигнал джобу на реорганизацию.

Здесь же. По поводу MBHC и расширения в одном измерении. Думаю возможно. Если в примере CUBE2
мы аллоцируем чуть больше памяти (с запасом) и порежем куб на гиперплоскости которые соответствуют средним годовым доходам. И при этом аллоцированная сырая память операционной системы заполнена кубом на 80% то нам ничто не мешает
отформатировать ее продолжение под следующую гиперплоскость и считать что куб растянулся.

Почему мы не аллоцировали все сразу? Предлагаю подумать и о возможном расширении других измерений
в условиях когда мы не знаем как будут расти справочные данные. Чисто технически - это просто движение
битов в биткарте (с учотом padding) и все прочее. Дело нудное и скушное и я сейчас просто не хочу
об этом думать но утверждаю что технически - возможно. Если сильно надо - то растянем.
...
Рейтинг: 0 / 0
01.06.2018, 01:06
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653641
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Далее (*****) Возможность сжатия.

Это больной вопрос. Можно сказать слабое место алгоритма. Я подведу под это практическую
базу. Мне только нужна учебная схема типа Борей и терпение чтобы оценить как лягут
таблички в куб. Сам куб я не буду строить пока. Для оценки мне достаточно к примеру
прогрузить тот-де Борей в SQLite и посчитать его кардинальности.

Чтобы не флудить словами я ввожу функцию
Код: sql
1.
def cubeCardinality(tableRef) = ....


и буду на нее ссылаться как на основную метрику КПД куба в части памяти.

Ну и для простоты еще число строк
Код: sql
1.
def rowCount(tableRef) = ....



Возможно большая часть табличек даже и не ляжет. Особенно это касается вещественных полей.
Вобщем юзкейс - не универсален.
...
Рейтинг: 0 / 0
01.06.2018, 01:14
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653709
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДалее (****) Расширение сегмента данных для фильтра Блума.

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

Я так понимаю речь про невозможно новые измерения добавлять. Тут можно вывернуться: если при добавлении нового измерения всем старым данным присвоить 0 для этого измерения, а после при расчете хэшей не включать это измерение в расчет если оно 0, тогда значения хэшей останутся такими же.
...
Рейтинг: 0 / 0
01.06.2018, 08:53
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653721
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНу... на правах топик-стартера я всё-таки предлагаю ограничиться темой первого поста.
Я никак не могу придумать реальное применение такому кубу. В твоих примерах 21455696 куб не применим, там обратная задача: компактно хранить атрибуты.

Обычно надо проверить что есть факты с заданными атрибутами и дальше что-то с ними делать, т.е. недостаточно ответа "такой факт точно есть", а куб никакой доп.инфы не дает, т.е. получив "есть" дальше надо лезть в БД.
Единственное преимущество над Блумом то, что можно проверить интервал значений по одному из измерений 21459456

А если в БД все равно лезть, то можно выкинуть куб и упростить задачу: сделать поле hash, по нему индекс и так использовать
Код: sql
1.
2.
h = my_hash(value1, value2, value3)
select ... from Table T where T.hash = h and T.attr1 = value1 and T.attr2 = value2 and T.attr3 = value3
...
Рейтинг: 0 / 0
01.06.2018, 09:20
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653740
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если мы захотим так вывернуться то это равносильно повторной загрузке всего объема.

Но если мы изначально складывали в блум кортежи в формате json (with field names) тогда ничего делать не надо.
...
Рейтинг: 0 / 0
01.06.2018, 09:55
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654264
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TЯ никак не могу придумать реальное применение такому кубу.



Не парься так сильно. Тема по сути пятничная.

Обычно надо проверить что есть факты с заданными атрибутами и дальше что-то с ними делать, т.е. недостаточно ответа "такой факт точно есть", а куб никакой доп.инфы не дает, т.е. получив "есть" дальше надо лезть в БД.
В примере №2 который я приводил выше был API который проверяет доступность UI элемента для отображения.

Было порядка 500 entitlements и порядка 2000 элементов UI. Связь - многие ко многим. Чтобы связать
в БД эти две сущности вводится промежуточная табличка entitlement2ui. Графически это можно
представить как булеву матрицу 500 на 2000 булевых элементов где каждый элемент говорит что
можно или нельзя отображать элемент UI для данного энтайтлмента. Далее еще была другая
промежуточная табличка пользователей которая была родительской по отношению к энтайтлментам
но это уже не важно в нашей задаче.

Вот откуда собственно и возникла у меня изначальная постановка.
...
Рейтинг: 0 / 0
02.06.2018, 00:45
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654266
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T
Код: sql
1.
2.
h = my_hash(value1, value2, value3)
select ... from Table T where T.hash = h and T.attr1 = value1 and T.attr2 = value2 and T.attr3 = value3



Еще думаю о такой реализации. Блум плохо хранит бесконечное множество. Грубо говоря нет гарантии
ложно-положительного ответа на новом случайно сгенерированном значении которое еще не входило
в исходных набор. Но. Беря во внимание счётность и ограниченность исходной выборки (да мы можем
в цифрах посчитать число элементов куба) мы можем сделать следующее.

Псевдокод.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
class BitmapCube : ICube {..... classic bitmap cube bla-bla-bla..... }

class AdvancedBloomCube : ICube {

   // Probabilistic data structure. 
   BloomFilter bloom;
   // Table contains false-positive values that should be avoided during check callback
   HashTable exceptions;
   
   public AdvancedBloomCube(double bloomFalsePositiveProbability) {
      .....

   }

   bool check(String jsonTuple) {
       if (bloom.contains(jsonTuple) and not (exceptionList.contains(jsonTuple))) return true;
       else return false;
   }
  
   // Initialize. Works a lot of time :). But needed :)
   void bulkLoadFromBitmapCube(ICube bitmapCube) {

       forAll(String json : bitmapCube.getIterator()) bloom.set(json);

       // Route over all combinations of original cube. Looks like for(...) for (...) for (...) {...}
       forAll(String json : bitmapCube.getDimensionsPermutations()) {
            if (bloom.contains(json) and not(bitmapCube.contains(json)) exceptions.add(json,true);
       }
   }
...
Рейтинг: 0 / 0
02.06.2018, 01:12
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654324
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,

я не сумел получить впечатление, что несомненно въехал в предмет вашего обсуждения.
Но, в части хеширования и поиска альтернатив фильтру Блума,
Есть фильтры Блума с подсчетом - они допускают удаление.

Вероятно сейчас разумнее сразу смотреть на кукушкино хеширование
и основанные на нём кукушкины фильтры как альтернативу блуму.

С созданием структуры для кукушкиных фильтров есть проблемы - insert лишь по вероятности O(1)
Но в остальном они кажутся предпочтительнее. В частности, могут гарантировать вероятность
ложноположительного срабатывания.

Это структуры умеренной новизны.
Ими с 14 года думают.

если не сталкивался - попробуй глянуть, начиная с вот здесь
https://brilliant.org/wiki/cuckoo-filter/
...
Рейтинг: 0 / 0
02.06.2018, 12:09
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654325
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
booby, ок спасибо.
...
Рейтинг: 0 / 0
02.06.2018, 12:17
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654340
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну.. Блум с подсчетом остается probabilistic data structure. Если-бы ячейка была бесконечно инкрементируемой
то пожалуй это был-би идеальный булевый хешмап. Но подсчет делает фильтр более прочным к false-positive
но не устраняет их совсем. Что для хеша - нормально. И для БД критично и недопустимо.

Но пожалуй я добавлю его к investigation на реальных данных.

По поводу хеширования кукушки. Ну я не знаю чем мне это поможет. Основной поинт топика - экономия
места. И здесь я не вижу чем особенно лучше будет кукушка против обычного массива списков. В обоих
случаях мы храним ключи.

По поводу данных. У меня сейчас нет под рукой БД которую я мог-бы публиковать.

Поэтому возьмем игрушечную БД типа NorthWind и попробуем оценить ее пригодность каждой таблички
для кубиков.
...
Рейтинг: 0 / 0
02.06.2018, 13:31
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654351
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Скриптов воздающих NorthWind существует огромное количество. Но я взял первый попавшийся под Sqlite3.

В схеме порядка десятка таблиц. Я взял самую толстую OrderDetail (порядка 600 тыс строк)
и посчитал кардинальности полей и вес этой таблички в виде куба

Код: sql
1.
621883*16818*77*116*68*11 = 69 876 854 232 861 984 bit ~7 944 Tb


8 тысяч терабайт. Вот такие пирожки.

Под катом некоторые скриптики:

 

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
sqlite> .tables
Category              EmployeeTerritory     Region              
Customer              Order                 Shipper             
CustomerCustomerDemo  OrderDetail           Supplier            
CustomerDemographic   Product               Territory           
Employee              ProductDetails_V   

sqlite> select count(*) from Category;
8
sqlite> select count(*) from Customer;
91
sqlite> select count(*) from CustomerCustomerDemo;
0
sqlite> select count(*) from CustomerDemographic;
0
sqlite> select count(*) from Employee;
9
sqlite> select count(*) from EmployeeTerritory;
49
sqlite> select count(*) from OrderDetail;
621883
sqlite> select count(*) from Product;
77
sqlite> select count(*) from ProductDetails_V;
77
sqlite> select count(*) from Region;
4
sqlite> select count(*) from Shipper;
3
sqlite> select count(*) from Supplier;
29
sqlite> select count(*) from Territory;
53



sqlite> .schema OrderDetail
CREATE TABLE IF NOT EXISTS "OrderDetail" 
(
  "Id" VARCHAR(8000) PRIMARY KEY, 
  "OrderId" INTEGER NOT NULL, 
  "ProductId" INTEGER NOT NULL, 
  "UnitPrice" DECIMAL NOT NULL, 
  "Quantity" INTEGER NOT NULL, 
  "Discount" DOUBLE NOT NULL 
);

sqlite> select count(*) from (select distinct Id id from OrderDetail);
621883
sqlite> select count(*) from (select distinct OrderID id from OrderDetail);
16818
sqlite> select count(*) from (select distinct ProductId from OrderDetail);
77
sqlite> select count(*) from (select distinct UnitPrice from OrderDetail);
116
sqlite> select count(*) from (select distinct Quantity from OrderDetail);
68
sqlite> select count(*) from (select distinct Discount from OrderDetail);
11




Довольно сильно портит картинку первое поле - которое суть первичный ключ.
Но даже без него размер все равно велик. И никак не соответствует размеру
базы в оригинале (32 Mb в формате .sqlite для всей базы с другими табличками).

Чуть позже я оценю размер Ордер-Детайлс в виде CSV чтоб были более точные
цифры по потреблению памяти.
...
Рейтинг: 0 / 0
02.06.2018, 15:17
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654366
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
mayton,

Поэтому и существуют такие индексы, как BRIN . В фасетном поиске, преимущественно используемом в интернет магазинах, используются интервалы значений. Никто не будет индексировать индивидуально каждую цену или дату.
...
Рейтинг: 0 / 0
02.06.2018, 17:30
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654371
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Посмотрите на фрагмент этой таблицы. И скажите есть ли признаки пригодности
укладывание ее в БРИН. Кроме того в теме я думаю не над индексированием
а над полной заменой таблицы. Ну тоесть индекс класса БРИН конечно интересен
но я не очень понимаю как он мне поможет в хранении собственно кортежей
самой таблички. Размер таблички будет уменьшен?

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
Id|OrderId|ProductId|UnitPrice|Quantity|Discount
10248/11|10248|11|14|12|0.0
10248/42|10248|42|9.8|10|0.0
10248/72|10248|72|34.8|5|0.0
10249/14|10249|14|18.6|9|0.0
10249/51|10249|51|42.4|40|0.0
10250/41|10250|41|7.7|10|0.0
10250/51|10250|51|42.4|35|0.15
10250/65|10250|65|16.8|15|0.15
10251/22|10251|22|16.8|6|0.05
10251/57|10251|57|15.6|15|0.05
10251/65|10251|65|16.8|20|0.0
10252/20|10252|20|64.8|40|0.05
10252/33|10252|33|2|25|0.05
10252/60|10252|60|27.2|40|0.0
10253/31|10253|31|10|20|0.0
10253/39|10253|39|14.4|42|0.0
10253/49|10253|49|16|40|0.0



Хотя я не против обсудить этот экзотический индекс отдельным тредом.
...
Рейтинг: 0 / 0
02.06.2018, 17:43
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654378
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вернусь к расчетам экспериментального AdvancedBloomCube. Разумеется куб там - это метафора.
Никакого куба нет. Но есть биткарта и хештабличка. Далее.

Я нашел сайт где есть онлайн калькулятор для расчетов. Спасибо некому Тому Харту.

https://hur.st/bloomfilter/?n=621883&p=0.97&m=&k=4

По сабжу выбор параметров (p,k) это та еще эвристика. Но я исхожу из предположения что
вероятность не ложно-позитивного срабатывания P=0.97 можно брать как некий стартовый
эталон и от него уже двигать выше или ниже.

Что мы точно знаем так это количество ключей. Это 621883. Оно участвует в формуле
как главный аргумент. Всё остальное - настройки. Значит согласно кальткулятору
нам понадобиться памяти



Где
MemoryBloom = 62k (по данным калькулятора).

MemoryHashTable = ?

Сколько будет MemoryHashTable? Это будут ложно позитивные кортежи из выборки в 620 тыс строк.



Считаем их



Итого 18 тысяч исключений. Которые надо положить в хеш-табличку чтобы отбить ложные срабатывания.

Но это еще не все.

Интерфейс имеет бесконечную мощность множества jsonTuple.

Код: javascript
1.
bool check(String jsonTuple)



Например. Для кортежа

Код: sql
1.
2.
Id|OrderId|ProductId|UnitPrice|Quantity|Discount
10248/11|10248|11|14|12|0.0



Мы можем дернуть как

Код: json
jsonTuple=" { Id : 10248/11 , OrderId : 10248,  ProductId : 11, UnitPrice : 14, Quantity : 12, Discount : 0.0 } "

(прошу прощения я пишу не в json a в более упрощенном виде чтоб было быстрее)

так и любое другое значение.

А этот факт осложняет нам генерацию таблички HashTable exceptions. Мы не учли в Блуме
что пользователь может лупить любые чеки и соотв мы должны гарантировать отсутствие
ложно-позитивных срабатываний не только на те которые уже были в 620 тыс учебной
таблички.

Но и учесть 69 876 триллионов битов (кортежей) о которых я писал выше. Они тоже
являются мощностью входящего множества.

Не бесконечного. Счетного. Но все таки достаточно большого.

Фух. Устал. Теперь слушаю ваши каменты.
...
Рейтинг: 0 / 0
02.06.2018, 18:41
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654384
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton8 тысяч терабайт. Вот такие пирожки.
С дуру сам знаешь что ломается. Зачем БД загонять целиком в память?
...
Рейтинг: 0 / 0
02.06.2018, 19:44
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654387
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЕще думаю о такой реализации....
Задумку не понял, поподробней опиши. Желательно по-русски.
...
Рейтинг: 0 / 0
02.06.2018, 19:52
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654390
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonЕще думаю о такой реализации....
Задумку не понял, поподробней опиши. Желательно по-русски.
Смотри. Исходник - это и есть описание. Если там где-то стоит многоточие - то эта часть не важна.
Но у меня не хватает слов чтобы это описывать. Выйдет Война и Мир 1-й Том. И я подобно
Геннадию Усову буду лабать посты с трехзначными номерами. Не хочу этово.

Поэтому отквотируй мой сорц и поставь вопросы и я на них отвечу.

Talk is cheap. Show me code (c) Один любитель пингвинов.
...
Рейтинг: 0 / 0
02.06.2018, 20:05
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654391
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
И опять мы уходим в сторону Блума, т.е. заменяем "точно да" на "скорее всего да". Второй случай требует перепроверки по БД. Он полезен если есть много ответов "нет", в остальном лишние вычисления.

Твой куб можно применить если он будет возвращать что-то полезное, в твоем примере про UI полезное показать/скрыть, но один бит можно заменить двумя и тогда можно закодировать писать/читать/скрыть и т.д.

В общем случае приходим к тому что есть f(i, j, k, ...) которая возвращает некоторое значение. Но дальше опять проблема как компактно хранить массив в памяти.
...
Рейтинг: 0 / 0
02.06.2018, 20:07
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654392
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima Tmayton8 тысяч терабайт. Вот такие пирожки.
С дуру сам знаешь что ломается. Зачем БД загонять целиком в память?
Кстати твой вариант с mmap здесь тоже не взлетит. Грубая оценка
показала что размер булевого кубика будет превышать разумные
пределы диска. Даже с отложенным сбросом страниц мы на 1% записей
положим весь раздел в "Disk out of space".
...
Рейтинг: 0 / 0
02.06.2018, 20:07
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654393
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TИ опять мы уходим в сторону Блума, т.е. заменяем "точно да" на "скорее всего да". Второй случай требует перепроверки по БД. Он полезен если есть много ответов "нет", в остальном лишние вычисления.
Перепроверка будет. Но не по базе. А по дополнительной структуре данных. Типа "список исключений".
А она не вероятностная а точная.
...
Рейтинг: 0 / 0
02.06.2018, 20:10
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654394
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonПоэтому отквотируй мой сорц и поставь вопросы и я на них отвечу.
Мне там всё непонятно. С англицким у меня плохо, помедитирую с гуглопереводом
...
Рейтинг: 0 / 0
02.06.2018, 20:10
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654395
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Там простой английский. И у меня не upper это точно.
...
Рейтинг: 0 / 0
02.06.2018, 20:12
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654396
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonТам простой английский. И у меня не upper это точно.
Завтра поизучаю, сейчас ребенок хочет в шахматы поиграть, некогда вобшем.
...
Рейтинг: 0 / 0
02.06.2018, 20:24
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654401
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ради бога. Я тоже не спешу.
...
Рейтинг: 0 / 0
02.06.2018, 21:28
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654455
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Понял суть твоего изобретения, ты повысил точность ответа "Нет", но это все-равно Блум, при первом появлении набора данных, которые есть в Блуме, но нет в БД можно узнать что их нет только обратившись в БД.

В случае если мало ответов "Нет" - пользы от такой конструкции ноль, а от твоего куба, о котором топик, польза есть, т.к. он дает ответ без обращения в БД.
...
Рейтинг: 0 / 0
03.06.2018, 11:45
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654461
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Куб как биткарта не влетит в том моём понимании которое я придумал изначально. Он мог взлететь
для 2х измерений (пример с entitlements (1000 штук) и UIelements (500 штук прибл.) где размер
поверхности куба был 1000 * 500 = 500 000 бит = 62 500 байт) но для большего числа измерений
кеширование теряет смысл. Кеш не может быть больше чем БД. Это абсурд. Поэтому
на данном посте я отказываюсь от многомерных биткарт.

Но от куба как от принципа доступа к проверке фактов я не отказываюсь. Просто многомерная биткарта
себя исчерпала и ее надо чем-то заменить.
...
Рейтинг: 0 / 0
03.06.2018, 12:10
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654659
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonпосчитал кардинальности полей и вес этой таблички в виде куба

Код: sql
1.
621883*16818*77*116*68*11 = 69 876 854 232 861 984 bit ~7 944 Tb


8 тысяч терабайт. Вот такие пирожки.

Я так понимаю в этой биткарте будет 621883 бит установлен в 1, остальные нолики. 1 Тб для хранения ~100 бит не очень эффективно.

Но если хранить в другом виде, например массив с индексами единичных битов, то потребуется 8 байт (int64) на одну запись.

ИМХО Если для значения конкретной записи можно вывести уникальный индекс, который никогда не пересечется с другими значениями, то такой индекс отличная замена хэшу, т.к. исключается возможность коллизий и как следствие не нужно хранение исходных данных, т.к. для сравнения двух записей достаточно сравнить индексы.
...
Рейтинг: 0 / 0
04.06.2018, 08:41
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654744
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T,

1. По первому пункту - да. Скорее всего. Массив очень разреженный. Терабайт или нет я не считал. Возможно больше.

2. По второму. Мысль интересная. Мне она напоминает арифметическое сжатие. Буду думать.
...
Рейтинг: 0 / 0
04.06.2018, 11:18
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39654882
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
hVosttmayton,

Поэтому и существуют такие индексы, как BRIN . В фасетном поиске, преимущественно используемом в интернет магазинах, используются интервалы значений. Никто не будет индексировать индивидуально каждую цену или дату.
Что-то в Wiki вроде погорячились поддержку BRIN индексов в Oracle Database вписать ))). Ссылки из Wiki только на описание Exadata, да и то, очень понятно как соотносящиеся с BRIN индексами.

Хотя, возможно, и ошибаюсь
...
Рейтинг: 0 / 0
04.06.2018, 14:02
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655268
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TИМХО Если для значения конкретной записи можно вывести уникальный индекс, который никогда не пересечется с другими значениями, то такой индекс отличная замена хэшу, т.к. исключается возможность коллизий и как следствие не нужно хранение исходных данных, т.к. для сравнения двух записей достаточно сравнить индексы.
Для таблички OrderDetail

Если существует функция типа

f(a,b,c,d,e,f)

которая отображает любой ключ на целое число (offset) в диапазоне от 0 до 70 тысяч триллионов
то мы можем представить таблицу как множество этих чисел. Для удобства поиска их можно
положить в хеш-табличку.

Но учитывая что все они длинные и (предположительно) могут иметь префикс то возможно
стоит подумать о какой-то структуре вроде префиксного дерева. Вообще... префиксность
еще надо доказать. Или просто предположить что данные в табличке похожи (к примеру
первое поле А имеет низкую кардинальность и содержит всего два значения {male, female}
и в формуле поле стоит на старшей позиции.

Отсюда кстати еще у меня возникает мысль о том что меняя порядок колонок можно
получить некоторые новые характеристики. Например

Код: sql
1.
2.
3.
4.
5.
6.
Id|OrderId|ProductId|UnitPrice|Quantity|Discount
10248/11|10248|11|14|12|0.0
10248/42|10248|42|9.8|10|0.0
10248/72|10248|72|34.8|5|0.0
10249/14|10249|14|18.6|9|0.0
10249/51|10249|51|42.4|40|0.0



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

Случайное сходство 10248/42 и 10248 это не более чем архитектурный нюанс. В других
БД этого может не быть.

Таким-же образом на 2 и 3 места можно передвинуть другие поля которые низко-кардинальны.
...
Рейтинг: 0 / 0
04.06.2018, 23:56
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655330
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДля таблички OrderDetail

Если существует функция типа

f(a,b,c,d,e,f)
Точно существует. Только надо знать кардинальность (количество возможных значений) каждого параметра.
Обозначим кардинальность A, B, C, D, E, F, тогда
Код: sql
1.
f(a,b,c,d,e,f) = ((((a*B + b) * C + c) * D + d) * E + e) * F + f
...
Рейтинг: 0 / 0
05.06.2018, 08:22
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655335
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Надо бы автоматизировать получение формулы для любого числа измеренмй.
...
Рейтинг: 0 / 0
05.06.2018, 08:39
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655337
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНадо бы автоматизировать получение формулы для любого числа измеренмй.
допустим i это значения, а K кардинальности, тогда формула для n измерений

Код: plaintext
f(i 0  ... i n ) = (...((i 0  * K 1  + i 1 ) * K 2  + i 2 ) ... ) * K n  + i n
...
Рейтинг: 0 / 0
05.06.2018, 08:51
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655343
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ИМХО тут другая проблема просматривается. Максимальное значение это произведение всех кардинальностей K 0 *...*K n , оно легко может выйти за пределы имеющихся целочисленных типов и тогда расчет станет достаточно ресурсоемким.
Во-вторых хэши в контейнерах обычно имеют размерность size_t, т.е. 32 и 64 бита для x32 и x64 соответственно, т.е. подмена хэша усложняется.
...
Рейтинг: 0 / 0
05.06.2018, 09:05
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655421
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давай пока не будем думать о разрядности. Нужно просто собрать макет и хотя-бы убедится что он
- работает
- дает приемлемое время отклика (не более секунды к примеру)
- занимает разумный объем памяти(не более гигабайт а)

Проблему числовой разрядности решим через arbitrary-precision арифметику.
...
Рейтинг: 0 / 0
05.06.2018, 11:11
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655520
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДавай пока не будем думать о разрядности. Нужно просто собрать макет и хотя-бы убедится что он
- работает
- дает приемлемое время отклика (не более секунды к примеру)
- занимает разумный объем памяти(не более гигабайт а)

Проблему числовой разрядности решим через arbitrary-precision арифметику.
Схематично так будет:

Инициализация: по каждому полю делаем приведение к виду 0 ... K-1, например для OrderId
Код: sql
1.
2.
OrderId["10248"] = 0
OrderId["10249"] = 1


В рабочем состоянии индекс определяем по OrderId, т.е.
Код: sql
1.
2.
if !OrderId.Contain(value) then throw "Unknown OrderId";
OrderId_idx = OrderId[value];


Для наполняемых счетчиками можно придумать алгоритм убирающий пропуски. В общем в итоге каждый параметр должен быть приведен к индексу в диапазоне 0 ... K-1, где K - кардинальность.

Отдельно выносим функцию
Код: sql
1.
2.
3.
int64 total_idx(OrderId_idx, ProductId_idx ...) {
   return ...
}


Затем заполняем таблицу
Код: sql
1.
HashSet.Add(total_idx(OrderId_idx, ProductId_idx ...))



В рабочем состоянии проверка - это получить *_idx каждого поля, затем проверить
Код: sql
1.
if HashSet.Contain(total_idx(OrderId_idx, ProductId_idx ...))


Сколько потребуется памяти можешь сам прикинуть.
...
Рейтинг: 0 / 0
05.06.2018, 12:49
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655918
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TИнициализация: по каждому полю делаем приведение к виду 0 ... K-1, например для OrderId
[src sql]
OrderId["10248"] = 0
OrderId["10249"] = 1

....

Да я ОК со всеми твоими тезисами. Только добавь плиз всместо int64 какой нить тип из Boost.Multiprecision.

По поводу разрядной сетки. Когда будешь генерить справочники - добавь плиз счетчики
для каждой полоски гистограммы. Надо их отсортировать по частоте.

Поинт вот в чем.

Самые частые популярные константы в колонке - надо закодить коротким целым числом. 0,1,2,3....
А самые редкие пойдут в .... 621882,621883. Это не Хаффман но что-то близкое.

Если будем хранить на диске в тесте или в Json - это даст экономию. Экономия будет
после использования формулы total_idx(..)

И в памяти тоже будет экономия если заюзаем BCD, String, или один из типов буста.
...
Рейтинг: 0 / 0
05.06.2018, 18:57
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655958
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonТолько добавь плиз всместо int64 какой нить тип из Boost.Multiprecision.
а как же
maytonДавай пока не будем думать о разрядности
Забудь и забей на страшное слово "буст". Это проблема сишников, не надо ее на других проецировать.
...
Рейтинг: 0 / 0
05.06.2018, 21:00
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655959
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonСамые частые популярные константы в колонке - надо закодить коротким целым числом. 0,1,2,3....

Похоже ты не понял о чем речь, перечитай что я писал. Не поймешь - переспроси.
...
Рейтинг: 0 / 0
05.06.2018, 21:04
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39655979
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonДавай пока не будем думать о разрядности
Забудь и забей на страшное слово "буст". Это проблема сишников, не надо ее на других проецировать.
Как будет угодно.
...
Рейтинг: 0 / 0
05.06.2018, 22:20
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39656075
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonСамые частые популярные константы в колонке - надо закодить коротким целым числом. 0,1,2,3....

Все надо надо закодить "коротким целым числом", иначе просто не заработает.
...
Рейтинг: 0 / 0
06.06.2018, 08:28
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39656130
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ты ввел искусственное ограничение. И говоришь что надо делать так. Мне этот ход непонятен.
...
Рейтинг: 0 / 0
06.06.2018, 09:39
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39656142
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonТы ввел искусственное ограничение. И говоришь что надо делать так. Мне этот ход непонятен.
Мы же вроде говорили о кэшировании неизменяемых (малоизменяемых) данных. В этом случае ограничение кардинальности уместно.
Можно небольшой запас добавить, т.е. оставить место на добавление нескольких значений в каждое измерение.

Если не ограничивать, то уйдем в сторону бесконечности, т.е. классические решения будут эффективнее как по производительности, так и по памяти.
...
Рейтинг: 0 / 0
06.06.2018, 09:52
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39656978
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Ещё раз проглядел топик, и кажется "уловил" предмет.
По крайней мере у меня сложилась какая-то модель, из которой предложения
от Dima T мне видны как ясные и понятные с точки зрения манеры реализации в виде конструкции,
положенной в реляционную БД.
(Мне так смотреть привычней).

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

Т.е., при создании такой структуры пункт 1) - зафиксировав последовательность входящих в "куб"
измерений, последовательно перенумеровать все допустимые значения всех используемых в нем категорий,
построив сплошной числовой уникальный идентификатор значений.
При 10 измерениях, пусть со 100 значениями в каждом из них, получим номера от 1 до 1000
Это, например, даст возможность формировать строковый ключ фиксированной длины,
позиционно кодирующий любую возможную комбинацию.
Это простая детерминированная функция, в примере 10*100 возвращающая строку в 40 символов,
являющаяся собственным свойством кубирующей комбинации переменных.

б) в части кодирования "малыми числами" комбинации значений набора переменных,
имхо, нужно отказаться от использования слова "функция" в смысле её детерминированности.

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

Это кодировка привязана к конкретно-историческому ходу процесса заполнения всей структуры.
Вошедшему в кубирующий автобус дается билет. Кто в автобус не вошел - тому билет не нужен.
Номер на отрывном талоне билета не напечатан в типографии, а рисуется вошедшему кондуктором прямо на талоне.

Если вошедший обладает тем же цветом глаз, волос и формой подбородка,
как и один из уже сидящих, номер на талоне такого берется из журнала зарегистрированных номеров присутствующих
в салоне комбинаций признаков.

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

Как теперь искать рыжих и одновременно бородатых?
В простом случае, когда всех выданных номеров "не очень много",
достаточно просмотреть записанные результаты регистрации поступивших признаков у которых в позициях
с 5й по 8ю стоит код '0075' - номер рыжего цвета в сплошной идентификации значений,
а в позициях с 14 по 17-ю '0153' - номер признака наличия бороды в той же нумерации,
выписать на листок выданные номера комбинаций, в которых он встречается и крикнуть в салон -
Поднять руки всем, у кого талоны с номерами 7 и 31.

При увеличении интенсивности пассажирооборота и удлинении маршрута,
возможно умнее параллельно поддерживать множества смежности поступивших признаков.
Может быть даже с весами присутствия, равными количеству зафиксированных экземпляров смежного признака.
Ластик тут будет полезен, чтобы стирать из множества смежности полностью выбывшие из салона признаки,
веса присутствия которых в списке смежности опустились до нуля.
Но работа эта дополнительная и степень её целесообразности требует специального суждения,
исходя из обстановки на маршруте.

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

Стирать ли в процессе рейса из журнала нумерации комбинаций строку, резервирующую ей номер
при полном выбытии комбинации - дело договоренности.

Я, вероятно, надеялся бы на повторное использование до конца рейса.
Но на конечной станции, по опустошении структуры салона, очистка всех журналов и заявление о том,
что рейс в обратную сторону - новый - вполне имеет право на существование.

как-то так.
...
Рейтинг: 0 / 0
07.06.2018, 02:40
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39657954
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonТы ввел искусственное ограничение. И говоришь что надо делать так. Мне этот ход непонятен.
Мы же вроде говорили о кэшировании неизменяемых (малоизменяемых) данных. В этом случае ограничение кардинальности уместно.
Можно небольшой запас добавить, т.е. оставить место на добавление нескольких значений в каждое измерение.

Если не ограничивать, то уйдем в сторону бесконечности, т.е. классические решения будут эффективнее как по производительности, так и по памяти.
Давай немножко шаг назад. Когда мы я говорил об ограничениях
- работает
- дает приемлемое время отклика (не более секунды к примеру)
- занимает разумный объем памяти(не более гигабайта)
я это постулировал как следующую цель. Я agree с тобой в части экономии ресурсов памяти и оптимизации.
Но зачем мне себя ограничивать в целочисленной арифметике сейчас? Мне нужно экспериментировать
с хранением в табличке произведений индексов справочников. Причем произведение будет не индексом
а значеним (value). Вместо хранения 1,1,1,1,1 в качестве первого кортежа я буду хранить
1*(k1 * k2 .... ) + ... + 1 = X. И жонглируя гистограммой я пытаюсь с этого получить какие-то
экономические выгоды в размере произведения. Мой мотив рационален? Рационален.
...
Рейтинг: 0 / 0
07.06.2018, 23:00
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39658047
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНо зачем мне себя ограничивать в целочисленной арифметике сейчас?
С большими числами можно проще поступить: округлять кардинальности до ближайшей большей степени двойки. В таком виде мы получаем битовую структуру, где под каждое измерение будет целое число бит. Работать с такой структурой просто, быстро и никаких ограничений на ее размер.

ИМХО эта избыточность не критична если общая кардинальность (произведение всех кардинальностей) выходит за разумные пределы, т.е. для биткарты много и как хэш нельзя использовать.

В общем случае получается сжатие исходных данных и не более того, т.е. экономия памяти за счет того что сжатая форма занимает меньше места.
Дальше используем сжатую форму стандартными способами. Например в хэш-таблице.

maytonМне нужно экспериментировать с хранением в табличке произведений индексов справочников.
Причем произведение будет не индексом а значеним (value).
У тебя как-то перепутаны индекс и значение. Индекс это расположение в кубе, составной ключ в терминологии РСУБД, он никуда не девается, а value оно и сейчас есть, только выше у нас оно однобитное, но ничто не мешает сделать его N-бит, т.е. любого размера.

maytonВместо хранения 1,1,1,1,1 в качестве первого кортежа я буду хранить
1*(k1 * k2 .... ) + ... + 1 = X. И жонглируя гистограммой я пытаюсь с этого получить какие-то
экономические выгоды в размере произведения. Мой мотив рационален? Рационален.
Если в моей формуле 21468543 скобки раскрыть то получим твою.

Код: plaintext
f(i 0  ... i n ) = (i 0  * K 1  * ... * K n ) + (i 1  * K 2  * ... * K n ) + ... + i n


ИМХО вроде всё понятно: то что чаще повторяется надо выносить влево, т.е. в i 0 . Или по другому: чем меньше кардинальность - тем левее.

Но это полезно если потом в биткарте использовать или вместо хэша в хэш-таблице, в этом случае есть смысл "скучковывания" индексов. Если общая кардинальность велика (см. выше) то пользы от этого ноль.
...
Рейтинг: 0 / 0
08.06.2018, 08:27
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39659288
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonНо зачем мне себя ограничивать в целочисленной арифметике сейчас?
С большими числами можно проще поступить: округлять кардинальности до ближайшей большей степени двойки. В таком виде мы получаем битовую структуру, где под каждое измерение будет целое число бит. Работать с такой структурой просто, быстро и никаких ограничений на ее размер.
Я вот думаю что может быть я был не прав насчет произведения ключей. Когда я стал имплементировать -
оказалось что на этапе загрузки данных я еще не знаю кардинальностей пока данные загружаются.
Тоесть алгоритм получается двух-фазный.
1) Анализ кардинальностей и генерация справочников.
2) Собственно наполнение хеш-таблички (или биткарты или куба не имеет значения) произведениями кодов.

Вобщем если так делать то реляционная работа будет выглядеть как процесс ETL. А это усложняет
использование.

Я планировал так (это несуществующий псевдо язык просто чтоб показать концепцию):

Код: sql
1.
2.
3.
4.
5.
mcube> create cube orders(Id,OrderId,ProductId,UnitPrice,Quantity,Discount) organization by compressed hashtable;
mcube> insert into cube orders values (fromcsv('10248/11|10248|11|14|12|0.0'));
mcube> select * from cube orders where attributes= fromcsv('10248/11|10248|11|14|12|0.0'));
Selected 1 row:
YES


Здесь на 3-й строке куб должен быть уже инициализирован чтобы можно было сделать фактологический запрос.
А я не могу делать расчет произведений пока не будет загружен весь amount 600 тысяч строк. В противном
случае формула будет неверна т.к. не все кардинальности еще расчитаны.
...
Рейтинг: 0 / 0
10.06.2018, 15:21
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39659299
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TУ тебя как-то перепутаны индекс и значение. Индекс это расположение в кубе, составной ключ в терминологии РСУБД, он никуда не девается, а value оно и сейчас есть, только выше у нас оно однобитное, но ничто не мешает сделать его N-бит, т.е. любого размера.

Да. Я уже в коде раза 3 перепутал все. Нужен agreement по терминологии. Поэтому. В данном топике

Cube - многомерная структура данных которая является аналогом таблицы в БД. Поддерживает
базовые операции DML такие как insert/update/delete. Выборка также поддерживается хотя сильно
зависит от cube organization.

Cube хрантся в оперативной памяти приложения.

Cube organization(СО) - внутренняя архитектура куба. Представляет собой совокупность алгоритмов
и структур данных нацеленных на реализацию базовых операций. В реализации нет ограничений кроме
разумных рамок использования оперативной памяти, heap, стека.

R/O data - данные из БД которые по своему смыслу - read/only в рамках решаемой прикладной
задачи. Например - справочники стран. Языков. Почтовых кодов. Адресов. Гео-объектов. Классификаторы.
(Данная трактовка достаточно широкая. В частности системы справочников работающие с суточным жизненным циклом
могут также быть кандидатом в R/O data даже если они обновляются если их обновление технологически
не нарушает бизнес-логики и укладывается в парадигму топика).

Свойство R/O data является важной и неотъемлемой части постановки. Автор топика считает что отклонение
от этого пункта - в корне меняет задачу вплоть до создания отдельных топиков или форков от темы.

Primary goal - основная цель (топика). Исследовать возможности кеширования баз данных на стороне
клиента для R/O data.

Cube population process(CPP) - важная часть процесса. Предполагается что основной объем
вычислений данной задачи будет исполнен в фазе наполнения таблицы source data.

Source data size (SDS) - фактический объем данных (в байтах или символах) которые необходимо
закешировать. (Здесь я рекомендую просто брать физический размер CSV-файла т.к. все прочие
метрики хранения эти данных в БД могут быть спорными. Сегмент file-БД обычно разрежённый и Inmemory
DBMS тоже хранят данные далеко не компактно).

Destination data size (DDS) - объем оперативной памяти который необходимо потратить на наполнение Cube.

Cube positive effect (CPE) - соотношение (SDS - DDS) / SDS. Грубо говоря если мы получили 1Мб куба на исходных 32М
то (32 - 1) / 32 = 0.95 = 96%. Разумеется куб ушедший в отрицательный сегмент % CPE - нам не интересен.
Он - не лучше чем БД.

Other Cube time optons (CTO) - прочие свойства куба которые мы сформулируем чуть позже. Сюда в частности
войдут характеристики отклика поисковых операций и стоимости cube population.

Secondary goals - совокупность вторичных целей топика. Предполагается что помимо создания куба
мы (участники) можем отклонятся от задачи и исследовать пользу от применения экзотических (стохастичных)
структур данных для достижения основной цели.

Cardinality - в контексте поля таблички БД или Cube кардинальность несет тот-же смысл что и в БД.
Мощность уникального множества значений (values) которое хранит поле.

Dictionary (Dict) - справочник уникальных значений поля. Число значений в справочнике == кардинальность.

Языки программирования Cube - любые ЯП доступные пользователям sql.ru.
(разумеется ЯП должен быть практичен для решения данной задачи. Брать к
примеру javascript не имеет особого смысла)

Прочие поинты.

1) В фазе CPP когда куб еще строится у разработчика есть большой арсенал возможностей по оптимизации размера.
Биткарты, деревья, графы, конечные автоматы, хеш-таблички списки и прочее. Задача архивации - не ставится.
Структура данных куба обязана сохранять приемлемые свойства отклика для поиска произвольного факта.

2) Итерируемость и поддержка полноценного интерфейса выборки. SELECT * FROM. Iterator. Iterable. e.t.c.

3) Анализ свойств куба. В процессе генерации СО можно делать глубокий анализ данных. Искать явные зависимости
между полей. Детектировать булевы признаки. Низко-кардинальные. Интервальные признаки (диапазон дат).

4) Связи с OLAP. В констатирующей части можно заявить что технология ОЛАП не имеет никакого отношения
к данному топику. Терминология в части кубов - случайное совпадение. Olap в оригинальной постановке
хранит результат аналитики а данная задача оперирует исходными данными.



Плюсаните если ОК. Или добавте ваши пожелания по улучшению.
...
Рейтинг: 0 / 0
10.06.2018, 16:51
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39659301
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Cube index (CI) - число. В декартовой форме организации куба CI уникально идентифицирует одну точку (ячейку)
где лежит значение true/false. Существует формула перехода от измерений куба к CI и обратно.
...
Рейтинг: 0 / 0
10.06.2018, 17:11
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39659311
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Source Table (ST) - исходные данные которые мы будем обрабатывать.
...
Рейтинг: 0 / 0
10.06.2018, 18:31
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39659330
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я в отпуске на неделю. Дети убили походный ноут, пишу с планшета, писать неудобно. Отвечу как вернусь.
...
Рейтинг: 0 / 0
10.06.2018, 21:12
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39659338
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, без проблем.
...
Рейтинг: 0 / 0
10.06.2018, 21:45
| Ответить | Цитировать | Написать  
100 сообщений из 100, показаны все 4 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничный куб. Концепция.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]