Не понимаю, кто будет убивать КЦ красных. Желтый сеткой поймал снайпера синих внизу, красный робот поймал синего бойца рядом с КЦ, а желтый снайпер отвернулся от КЦ.
Порядок действительно один — O(n), где n — размер фильтра.
Для Bloom filter количество бит, задействованных на хранение одного элемента, <= количество хэш-функций(меньше потому, что 1 бит может быть использован для хранения сразу нескольких элементов — произошла коллизия в одной из хэш-функций). Не знаю, лично я не слышал про кол-во хэш-функций > 15.
Для Quotient filter количество бит, задействованных на хранение одного элемента, ~= 60.
Написал всё это и увидел дополнение
(естественно, при одинаковой вероятности ошибки)
В quotient filter используется только одна хэш-функция. В этом смысле Bloom filter с набором хэш-функций всегда будет впереди. При использовании в Bloom filter только одной хэш-функции получаем 1 бит на элемент, тогда как в quotient filter всё те же ~= 60 бит.
Правда, в quotient filter допускаются коллизии, вставляется просто еще одна копия хэша.
Кстати, формула вероятности ошибки для quotient filter выводится в [1], стр. 4
4. Не знаю, с такой точки зрения на частное — остаток я не смотрел. В принципе, можно и так сделать.
5. Авторы предлагают держать в памяти таблицу размера q0(размер таблицы ограничен размером оперативной памяти). Когда она сильно заполняется, она сливается с таблицей размера q1 > q0, которая хранится на SSD. А таблица в оперативной памяти очищается. Если при слиянии таблица с размером q1 тоже заполнилась, то она сливается с другой таблицей с размером q2 > q1, которая тоже хранится на SSD, а затем очищается. И т. д.
Насколько помню, размер таблиц не фиксирован.
Вообще, этот cascade filter из quotient filters основан на другой структуре — cache-oblivious lookahead array(COLA) (подробнее здесь supertech.csail.mit.edu/papers/sbtree.pdf). Надеюсь, кто-нибудь напишет и об этом)) Я пока не изучал эту тему.
Огромное спасибо за замечания!
1, 2 и 3 вроде исправил.
4. Жаль, я потерял линк на реализацию на С от авторов. В других реализациях(например github.com/vedantk/quotient-filter) используются 64-битные хэши.
Может имеет смысл поменять местами остаток и частное
Как я уже писал, размеры частного и остатка можно менять, всё зависит от ситуации, данных и их количества.
5. Авторы проводят тесты с миллионами элементов, так что структуру действительно нет смысла использовать на очень маленьких выборках. При большом количестве элементов, когда коэффициент заполнения(load factor) становится высоким, можно организовать каскад фильтров. Это описано в [1], стр. 6
The jury at the Supreme Court of Victoria agreed that this was a reasonable argument, but only up to the point that Google had received the complaint about its picture results.
It indicated that the content should have been removed at that point, and as a result the search firm was liable for defamation.
However, the jury found that Google was not liable for the web search results since Mr Trkulja had incorrectly filled out a complaint form, missing out the web address of the content to which he had objected.
Mr Trkulja later told journalists he felt vindicated by the ruling.
Человек подал в Гугл заявку с формулировкой «чтобы поисковик удалил из выдачи все слухи про него, включая изображения» без всяких ссылок, Гугл отказался. За это Гугл признали виновным в клевете, но невиновным за поисковые выдачи, т. к. человек не предоставил список ссылок.
И этот Trkulja профессиональный тролль — отсудил у Yahoo $250,000 (£155,000) за какую-то ссылку.
Написал клевету Али-баба — не него и подавайте. А что сразу на Гугл-то подавать? Это как отрубать голову гонцу, принесшему плохие вести. Гонец их сам не сделал.
А если в Яндексе выдается, то и на Яндекс сразу? Это у патентных троллей перенимаете практику?
Если бы было как: «В 2009 году он потребовал, чтобы поисковик удалил из выдачи все слухи про него, включая изображения.» Он был бы послан подальше и судом. А сейчас точно было нормальное основание
По ссылке не ходи, комментарий пиши.
In October 2009, Trkulja demanded that Google remove the rumors, including images, but the company denied the request and recommended he contact the website owners. The court ruled that Google’s innocence is only justifiable until the point when someone asks them to remove content.
Хотел уже записываться, глянул линк — а там облом.
A centre for 'terminator studies', where leading academics will study the threat that robots pose to humanity, is set to open at Cambridge University.
Это не курсы, а центр.
Буду с нетерпением ждать, когда появятся курсы. Интересно, каким методам противодействия там будут учить? Стрельба по-македонски?
Берем 3 команды: A, B, C.
A выигрывает у B, B выигрывает у C, C выигрывает у A.
Кто победитель?
Вот пример моего решения: Гегемония — 1, Молох — -1, Борго — 0.
Для Bloom filter количество бит, задействованных на хранение одного элемента, <= количество хэш-функций(меньше потому, что 1 бит может быть использован для хранения сразу нескольких элементов — произошла коллизия в одной из хэш-функций). Не знаю, лично я не слышал про кол-во хэш-функций > 15.
Для Quotient filter количество бит, задействованных на хранение одного элемента, ~= 60.
Написал всё это и увидел дополнение
В quotient filter используется только одна хэш-функция. В этом смысле Bloom filter с набором хэш-функций всегда будет впереди. При использовании в Bloom filter только одной хэш-функции получаем 1 бит на элемент, тогда как в quotient filter всё те же ~= 60 бит.
Правда, в quotient filter допускаются коллизии, вставляется просто еще одна копия хэша.
Кстати, формула вероятности ошибки для quotient filter выводится в [1], стр. 4
Это только моё личное мнение, я могу ошибаться.
5. Авторы предлагают держать в памяти таблицу размера q0(размер таблицы ограничен размером оперативной памяти). Когда она сильно заполняется, она сливается с таблицей размера q1 > q0, которая хранится на SSD. А таблица в оперативной памяти очищается. Если при слиянии таблица с размером q1 тоже заполнилась, то она сливается с другой таблицей с размером q2 > q1, которая тоже хранится на SSD, а затем очищается. И т. д.
Насколько помню, размер таблиц не фиксирован.
Вообще, этот cascade filter из quotient filters основан на другой структуре — cache-oblivious lookahead array(COLA) (подробнее здесь supertech.csail.mit.edu/papers/sbtree.pdf). Надеюсь, кто-нибудь напишет и об этом)) Я пока не изучал эту тему.
1, 2 и 3 вроде исправил.
4. Жаль, я потерял линк на реализацию на С от авторов. В других реализациях(например github.com/vedantk/quotient-filter) используются 64-битные хэши.
Как я уже писал, размеры частного и остатка можно менять, всё зависит от ситуации, данных и их количества.
5. Авторы проводят тесты с миллионами элементов, так что структуру действительно нет смысла использовать на очень маленьких выборках. При большом количестве элементов, когда коэффициент заполнения(load factor) становится высоким, можно организовать каскад фильтров. Это описано в [1], стр. 6
Человек подал в Гугл заявку с формулировкой «чтобы поисковик удалил из выдачи все слухи про него, включая изображения» без всяких ссылок, Гугл отказался. За это Гугл признали виновным в клевете, но невиновным за поисковые выдачи, т. к. человек не предоставил список ссылок.
И этот Trkulja профессиональный тролль — отсудил у Yahoo $250,000 (£155,000) за какую-то ссылку.
А если в Яндексе выдается, то и на Яндекс сразу? Это у патентных троллей перенимаете практику?
По ссылке не ходи, комментарий пиши.
Хотел уже записываться, глянул линк — а там облом.
Это не курсы, а центр.
Буду с нетерпением ждать, когда появятся курсы. Интересно, каким методам противодействия там будут учить? Стрельба по-македонски?