Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonДалее (****) Расширение сегмента данных для фильтра Блума. Я не буду здесь долго описывать теорию. Можете почитать Вики. Фильтр Блума принципиально не расширяется. Его можно пересоздать заново и используя оригинальную БД прогрузить весь amount фактов в новый сегмент. Добавление новых фактов - возможно но приводит к потере избирательности. ИМХО невозможно удалить из Блума, а остальное решаемо. Я так понимаю речь про невозможно новые измерения добавлять. Тут можно вывернуться: если при добавлении нового измерения всем старым данным присвоить 0 для этого измерения, а после при расчете хэшей не включать это измерение в расчет если оно 0, тогда значения хэшей останутся такими же. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.06.2018, 08:53 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonНу... на правах топик-стартера я всё-таки предлагаю ограничиться темой первого поста. Я никак не могу придумать реальное применение такому кубу. В твоих примерах 21455696 куб не применим, там обратная задача: компактно хранить атрибуты. Обычно надо проверить что есть факты с заданными атрибутами и дальше что-то с ними делать, т.е. недостаточно ответа "такой факт точно есть", а куб никакой доп.инфы не дает, т.е. получив "есть" дальше надо лезть в БД. Единственное преимущество над Блумом то, что можно проверить интервал значений по одному из измерений 21459456 А если в БД все равно лезть, то можно выкинуть куб и упростить задачу: сделать поле hash, по нему индекс и так использовать Код: sql 1. 2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.06.2018, 09:20 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Если мы захотим так вывернуться то это равносильно повторной загрузке всего объема. Но если мы изначально складывали в блум кортежи в формате json (with field names) тогда ничего делать не надо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.06.2018, 09:55 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima TЯ никак не могу придумать реальное применение такому кубу. Не парься так сильно. Тема по сути пятничная. Обычно надо проверить что есть факты с заданными атрибутами и дальше что-то с ними делать, т.е. недостаточно ответа "такой факт точно есть", а куб никакой доп.инфы не дает, т.е. получив "есть" дальше надо лезть в БД. В примере №2 который я приводил выше был API который проверяет доступность UI элемента для отображения. Было порядка 500 entitlements и порядка 2000 элементов UI. Связь - многие ко многим. Чтобы связать в БД эти две сущности вводится промежуточная табличка entitlement2ui. Графически это можно представить как булеву матрицу 500 на 2000 булевых элементов где каждый элемент говорит что можно или нельзя отображать элемент UI для данного энтайтлмента. Далее еще была другая промежуточная табличка пользователей которая была родительской по отношению к энтайтлментам но это уже не важно в нашей задаче. Вот откуда собственно и возникла у меня изначальная постановка. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 00:45 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima T Код: sql 1. 2. Еще думаю о такой реализации. Блум плохо хранит бесконечное множество. Грубо говоря нет гарантии ложно-положительного ответа на новом случайно сгенерированном значении которое еще не входило в исходных набор. Но. Беря во внимание счётность и ограниченность исходной выборки (да мы можем в цифрах посчитать число элементов куба) мы можем сделать следующее. Псевдокод. Код: 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 01:12 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
mayton, я не сумел получить впечатление, что несомненно въехал в предмет вашего обсуждения. Но, в части хеширования и поиска альтернатив фильтру Блума, Есть фильтры Блума с подсчетом - они допускают удаление. Вероятно сейчас разумнее сразу смотреть на кукушкино хеширование и основанные на нём кукушкины фильтры как альтернативу блуму. С созданием структуры для кукушкиных фильтров есть проблемы - insert лишь по вероятности O(1) Но в остальном они кажутся предпочтительнее. В частности, могут гарантировать вероятность ложноположительного срабатывания. Это структуры умеренной новизны. Ими с 14 года думают. если не сталкивался - попробуй глянуть, начиная с вот здесь https://brilliant.org/wiki/cuckoo-filter/ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 12:09 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
booby, ок спасибо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 12:17 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Ну.. Блум с подсчетом остается probabilistic data structure. Если-бы ячейка была бесконечно инкрементируемой то пожалуй это был-би идеальный булевый хешмап. Но подсчет делает фильтр более прочным к false-positive но не устраняет их совсем. Что для хеша - нормально. И для БД критично и недопустимо. Но пожалуй я добавлю его к investigation на реальных данных. По поводу хеширования кукушки. Ну я не знаю чем мне это поможет. Основной поинт топика - экономия места. И здесь я не вижу чем особенно лучше будет кукушка против обычного массива списков. В обоих случаях мы храним ключи. По поводу данных. У меня сейчас нет под рукой БД которую я мог-бы публиковать. Поэтому возьмем игрушечную БД типа NorthWind и попробуем оценить ее пригодность каждой таблички для кубиков. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 13:31 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Скриптов воздающих NorthWind существует огромное количество. Но я взял первый попавшийся под Sqlite3. В схеме порядка десятка таблиц. Я взял самую толстую OrderDetail (порядка 600 тыс строк) и посчитал кардинальности полей и вес этой таблички в виде куба Код: sql 1. 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. Довольно сильно портит картинку первое поле - которое суть первичный ключ. Но даже без него размер все равно велик. И никак не соответствует размеру базы в оригинале (32 Mb в формате .sqlite для всей базы с другими табличками). Чуть позже я оценю размер Ордер-Детайлс в виде CSV чтоб были более точные цифры по потреблению памяти. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 15:17 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
mayton, Поэтому и существуют такие индексы, как BRIN . В фасетном поиске, преимущественно используемом в интернет магазинах, используются интервалы значений. Никто не будет индексировать индивидуально каждую цену или дату. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 17:30 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Посмотрите на фрагмент этой таблицы. И скажите есть ли признаки пригодности укладывание ее в БРИН. Кроме того в теме я думаю не над индексированием а над полной заменой таблицы. Ну тоесть индекс класса БРИН конечно интересен но я не очень понимаю как он мне поможет в хранении собственно кортежей самой таблички. Размер таблички будет уменьшен? Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. Хотя я не против обсудить этот экзотический индекс отдельным тредом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 17:43 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Вернусь к расчетам экспериментального 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. Например. Для кортежа Код: sql 1. 2. Мы можем дернуть как Код: json (прошу прощения я пишу не в json a в более упрощенном виде чтоб было быстрее) так и любое другое значение. А этот факт осложняет нам генерацию таблички HashTable exceptions. Мы не учли в Блуме что пользователь может лупить любые чеки и соотв мы должны гарантировать отсутствие ложно-позитивных срабатываний не только на те которые уже были в 620 тыс учебной таблички. Но и учесть 69 876 триллионов битов (кортежей) о которых я писал выше. Они тоже являются мощностью входящего множества. Не бесконечного. Счетного. Но все таки достаточно большого. Фух. Устал. Теперь слушаю ваши каменты. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 18:41 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
mayton8 тысяч терабайт. Вот такие пирожки. С дуру сам знаешь что ломается. Зачем БД загонять целиком в память? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 19:44 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonЕще думаю о такой реализации.... Задумку не понял, поподробней опиши. Желательно по-русски. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 19:52 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima TmaytonЕще думаю о такой реализации.... Задумку не понял, поподробней опиши. Желательно по-русски. Смотри. Исходник - это и есть описание. Если там где-то стоит многоточие - то эта часть не важна. Но у меня не хватает слов чтобы это описывать. Выйдет Война и Мир 1-й Том. И я подобно Геннадию Усову буду лабать посты с трехзначными номерами. Не хочу этово. Поэтому отквотируй мой сорц и поставь вопросы и я на них отвечу. Talk is cheap. Show me code (c) Один любитель пингвинов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 20:05 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
И опять мы уходим в сторону Блума, т.е. заменяем "точно да" на "скорее всего да". Второй случай требует перепроверки по БД. Он полезен если есть много ответов "нет", в остальном лишние вычисления. Твой куб можно применить если он будет возвращать что-то полезное, в твоем примере про UI полезное показать/скрыть, но один бит можно заменить двумя и тогда можно закодировать писать/читать/скрыть и т.д. В общем случае приходим к тому что есть f(i, j, k, ...) которая возвращает некоторое значение. Но дальше опять проблема как компактно хранить массив в памяти. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 20:07 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima Tmayton8 тысяч терабайт. Вот такие пирожки. С дуру сам знаешь что ломается. Зачем БД загонять целиком в память? Кстати твой вариант с mmap здесь тоже не взлетит. Грубая оценка показала что размер булевого кубика будет превышать разумные пределы диска. Даже с отложенным сбросом страниц мы на 1% записей положим весь раздел в "Disk out of space". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 20:07 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima TИ опять мы уходим в сторону Блума, т.е. заменяем "точно да" на "скорее всего да". Второй случай требует перепроверки по БД. Он полезен если есть много ответов "нет", в остальном лишние вычисления. Перепроверка будет. Но не по базе. А по дополнительной структуре данных. Типа "список исключений". А она не вероятностная а точная. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 20:10 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonПоэтому отквотируй мой сорц и поставь вопросы и я на них отвечу. Мне там всё непонятно. С англицким у меня плохо, помедитирую с гуглопереводом ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 20:10 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Там простой английский. И у меня не upper это точно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 20:12 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonТам простой английский. И у меня не upper это точно. Завтра поизучаю, сейчас ребенок хочет в шахматы поиграть, некогда вобшем. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 20:24 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Ради бога. Я тоже не спешу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2018, 21:28 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Понял суть твоего изобретения, ты повысил точность ответа "Нет", но это все-равно Блум, при первом появлении набора данных, которые есть в Блуме, но нет в БД можно узнать что их нет только обратившись в БД. В случае если мало ответов "Нет" - пользы от такой конструкции ноль, а от твоего куба, о котором топик, польза есть, т.к. он дает ответ без обращения в БД. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.06.2018, 11:45 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Куб как биткарта не влетит в том моём понимании которое я придумал изначально. Он мог взлететь для 2х измерений (пример с entitlements (1000 штук) и UIelements (500 штук прибл.) где размер поверхности куба был 1000 * 500 = 500 000 бит = 62 500 байт) но для большего числа измерений кеширование теряет смысл. Кеш не может быть больше чем БД. Это абсурд. Поэтому на данном посте я отказываюсь от многомерных биткарт. Но от куба как от принципа доступа к проверке фактов я не отказываюсь. Просто многомерная биткарта себя исчерпала и ее надо чем-то заменить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.06.2018, 12:10 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonпосчитал кардинальности полей и вес этой таблички в виде куба Код: sql 1. 8 тысяч терабайт. Вот такие пирожки. Я так понимаю в этой биткарте будет 621883 бит установлен в 1, остальные нолики. 1 Тб для хранения ~100 бит не очень эффективно. Но если хранить в другом виде, например массив с индексами единичных битов, то потребуется 8 байт (int64) на одну запись. ИМХО Если для значения конкретной записи можно вывести уникальный индекс, который никогда не пересечется с другими значениями, то такой индекс отличная замена хэшу, т.к. исключается возможность коллизий и как следствие не нужно хранение исходных данных, т.к. для сравнения двух записей достаточно сравнить индексы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.06.2018, 08:41 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=39654325&tid=1340101]: |
0ms |
get settings: |
8ms |
get forum list: |
12ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
160ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
67ms |
get tp. blocked users: |
1ms |
| others: | 12ms |
| total: | 276ms |

| 0 / 0 |
