powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничный куб. Концепция.
25 сообщений из 100, страница 3 из 4
Вторничный куб. Концепция.
    #39653709
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДалее (****) Расширение сегмента данных для фильтра Блума.

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

Я так понимаю речь про невозможно новые измерения добавлять. Тут можно вывернуться: если при добавлении нового измерения всем старым данным присвоить 0 для этого измерения, а после при расчете хэшей не включать это измерение в расчет если оно 0, тогда значения хэшей останутся такими же.
...
Рейтинг: 0 / 0
Вторничный куб. Концепция.
    #39653721
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
Вторничный куб. Концепция.
    #39653740
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если мы захотим так вывернуться то это равносильно повторной загрузке всего объема.

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



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

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

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

Вот откуда собственно и возникла у меня изначальная постановка.
...
Рейтинг: 0 / 0
Вторничный куб. Концепция.
    #39654266
Фотография 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
Вторничный куб. Концепция.
    #39654324
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

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

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

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

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

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

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

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

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

Поэтому возьмем игрушечную БД типа NorthWind и попробуем оценить ее пригодность каждой таблички
для кубиков.
...
Рейтинг: 0 / 0
Вторничный куб. Концепция.
    #39654351
Фотография 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
Вторничный куб. Концепция.
    #39654366
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Поэтому и существуют такие индексы, как BRIN . В фасетном поиске, преимущественно используемом в интернет магазинах, используются интервалы значений. Никто не будет индексировать индивидуально каждую цену или дату.
...
Рейтинг: 0 / 0
Вторничный куб. Концепция.
    #39654371
Фотография 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
Вторничный куб. Концепция.
    #39654378
Фотография 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
Вторничный куб. Концепция.
    #39654384
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton8 тысяч терабайт. Вот такие пирожки.
С дуру сам знаешь что ломается. Зачем БД загонять целиком в память?
...
Рейтинг: 0 / 0
Вторничный куб. Концепция.
    #39654387
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЕще думаю о такой реализации....
Задумку не понял, поподробней опиши. Желательно по-русски.
...
Рейтинг: 0 / 0
Вторничный куб. Концепция.
    #39654390
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TmaytonЕще думаю о такой реализации....
Задумку не понял, поподробней опиши. Желательно по-русски.
Смотри. Исходник - это и есть описание. Если там где-то стоит многоточие - то эта часть не важна.
Но у меня не хватает слов чтобы это описывать. Выйдет Война и Мир 1-й Том. И я подобно
Геннадию Усову буду лабать посты с трехзначными номерами. Не хочу этово.

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

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

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

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

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

Но от куба как от принципа доступа к проверке фактов я не отказываюсь. Просто многомерная биткарта
себя исчерпала и ее надо чем-то заменить.
...
Рейтинг: 0 / 0
Вторничный куб. Концепция.
    #39654659
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
25 сообщений из 100, страница 3 из 4
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничный куб. Концепция.
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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