Invertible Bloom Lookup Tables http://arxiv.org/pdf/1101.2245v2.pdf "We present a version of the Bloom filter data structure that supports not only the insertion, deletion, and lookup of key-value pairs, but also allows a complete listing of the pairs it contains with high probability, as long the number of keyvalue pairs is below a designed threshold. Our structure allows the number of keyvalue pairs to greatly exceed this threshold during normal operation. Exceeding the threshold simply temporarily prevents content listing and reduces the probability of a successful lookup. If entries are later deleted to return the structure below the threshold, everything again functions appropriately."
@larhat: есть несколько алгоритмов, свойства которых напоминают волшебные — этот один из таких. ‎- псы в рапиде
Ну bloom filter - это вообще magic. По крайней мере, так звучит для нас ламеров. ‎- other people liked this
блум фильтр ещё ничего, но вот я абстракт этой папиры читаю — магия реально! ‎- адский хардлайн в засаде
@aguyfrompokernight: one-way тикет до вероятностных алгоритмов это норм., c hyperloglog все смирились. но оно умеет назад! ‎- псы в рапиде
^ нужен тег для такого, мне кажется. сюда и к тому алгоритму волшебному про сжатие, про который ты писал как-то. #fucksecondlawofthermodynamics только про CS. ‎- адский хардлайн в засаде
@larhat: ты про Burrows–Wheeler transform? Он скорее не про сжатие (хотя это отдельное недоумение!), он про поиск, в том числе нечеткий. ‎- псы в рапиде
^ ага, про него. да, в этом тоже дополнительная фишка, согласен. типа "случайно" сделали магию :) ‎- адский хардлайн в засаде

2015-2016 Mokum.place