basis/cuckoo-filters/cuckoo-filters-docs.factor

   1 USING: byte-arrays checksums help.markup help.syntax kernel ;
   2 IN: cuckoo-filters
   3
   4 HELP: cuckoo-insert
   5 { $values { "bytes" byte-array } { "cuckoo-filter" cuckoo-filter } { "?" boolean } }
   6 { $description "Insert the data into the " { $snippet "cuckoo-filter" } ", returning " { $link t } " if the data was inserted." }
   7 { $notes "Attempting to insert data twice will result in the hashed fingerprint of the data appearing twice and the " { $link cuckoo-filter } " size being incremented twice." } ;
   8
   9 HELP: cuckoo-lookup
  10 { $values { "bytes" byte-array } { "cuckoo-filter" cuckoo-filter } { "?" boolean } }
  11 { $description "Lookup the data from the " { $snippet "cuckoo-filter" } ", returning " { $link t } " if the data appears to be a member. This is a probabilistic test, meaning there is a possibility of false positives." } ;
  12
  13 HELP: cuckoo-delete
  14 { $values { "bytes" byte-array } { "cuckoo-filter" cuckoo-filter } { "?" boolean } }
  15 { $description "Remove the data from the " { $snippet "cuckoo-filter" } ", returning " { $link t } " if the data appears to be removed." } ;
  16
  17 ARTICLE: "cuckoo-filters" "Cuckoo Filters"
  18 "Cuckoo Filters are probabilistic data structures similar to Bloom Filters that provides support for removing elements without significantly degrading space and performance."
  19 $nl
  20 "Instead of storing the elements themselves, it stores a fingerprint obtained by using a " { $link checksum } ". This allows for item removal without false negatives (assuming you do not try and remove an item not contained in the filter."
  21 $nl
  22 "For applications that store many items and target low false-positive rates, Cuckoo Filters can have a lower space overhead than Bloom Filters."
  23 $nl
  24 "More information is available in the paper by Andersen, Kaminsky, and Mitzenmacher titled \"Cuckoo Filter: Practically Better Than Bloom\":"
  25 $nl
  26 { $url "http://www.pdl.cmu.edu/PDL-FTP/FS/cuckoo-conext2014.pdf" } ;
  27
  28 ABOUT: "cuckoo-filters"