Существует ли реализация частного фильтра с открытым исходным кодом?

См. http://en.wikipedia.org/wiki/Quotient_filter. Я еще не нашел ни одной реализации, и я хотел бы с чем-то поиграть, объяснение в Википедии, на мой вкус, немного суховато.


data-structures bloom-filter
person Janus Troelsen    schedule 31.08.2012    source источник
comment
Я думаю, тебе следует прочитать статью Бендера. Просто из определения AMQ в Википедии должно быть ясно, что фильтр Блума уже является AMQ, поэтому выберите любую реализацию фильтра Блума.   -  person hroptatyr    schedule 31.08.2012
comment
И фильтры Блума, и частные фильтры являются примерами AMQ (приблизительный запрос на членство), но они используют разные структуры данных для своей реализации. Оба подходят для основной памяти, но, согласно статье, частные фильтры больше подходят для флэш-накопителей.   -  person Stefan L    schedule 09.10.2012

Ответы (2)


arrow_upward
2
arrow_downward

Я реализовал факторный фильтр на C (ссылка). Он поддерживает следующие операции;

  • Вставить (qf, ключ)
  • May-Contain(qf, ключ)
  • Remove(qf, key) (с оговоркой, см. документацию в qf.h)
  • Слияние (qf1, qf2) -> qfout
  • Итерация (qf)

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

person vedantk    schedule 02.09.2014

arrow_upward
1
arrow_downward

Я реализовал один на PHP, чтобы поиграть с ним. Он не завершен, но добавление/содержит реализовано. Это не защита от дурака и даже не защита от ошибок.

https://github.com/dsx724/php-quotient-filter

Надеюсь это поможет.

person dsx724    schedule 27.11.2013
comment
Какую ссылку (бумагу?) вы использовали для этой реализации? - person Janus Troelsen; 01.12.2013
comment
Это не бумага Бендера с 3-битным отпечатком пальца. Я разделил отпечаток пальца и остаток на две разные структуры данных для простоты, но по сути это одно и то же. Я не сортировал остатки, как указано в бумаге. - person dsx724; 17.12.2013