math - Compressed Bloom Filters with fixed false positive probability -


i trying implement compressed bloom filter implementation according paper compressed bloom filters michael mitzenmacher. need calculate m - number of bits , k - number of hash functions given fixed false positive probability. example: know if have n = 1000 elements(to inserted in bloom filter) , given probability p = 0.01, "optimal" number of bits bloom filter (-n * math.log(p) / (math.log(2) * math.log(2))) = 9585 , need k = (9585/1000)*math.log(2) = 7 - hash functions. is, false positive rate 0.01. "compress" bloom filter need build more "sparse" filter - lesser hash functions , more number of bits in vector. did not idea how calculate number of hash functions , number of bits sparse filter. if decrease k 1 how increase number of bits? ratio?

well, did not find concrete ratio between number of hash functions , number of bits fixed false positive rate. have found precalculated table of such values. here can find values of number of hash functions , bit vector length corresponding false positive rate. since have such table can find number of hash functions(less optimal) , corresponding bit vector length false positive rate less or equal given. here implementation building "sparse" bloom filters. hope save someone`s time in future.


Comments

Post a Comment

Popular posts from this blog

aws api gateway - SerializationException in posting new Records via Dynamodb Proxy Service in API -

i getting "__type": "com.amazon.coral.service#serializationexception" as reply in postman & in test console in api gateway trying post record directly dynamodb using api proxy services.. referring aws article - https://aws.amazon.com/blogs/compute/using-amazon-api-gateway-as-a-proxy-for-dynamodb/ here's mapping { "tablename": "tablenamegoeshere", "item": { "id" : "$context.requestid" "eventname" : "$input.path('$.eventname')", "timestamp" : $input.path('$.timestamp'), "answers": "$util.parsejson($input.path('$.answers'))" } } update: did asked ... , worked if try add array of json objects gives me above same error - here's trying now. please - couldnt find on google well #set($inputroot = $input.path('$')) { "tablename": "answer", "item": {
Read more

asp.net - Problems sending emails from forum -

i have been redesigning site has message board, has been written guy looked after site. it has few problems , written in .asp , uses .mdb files database. you can see whole thing here . feel free post if helps, test thing have set using original files , new database. the basic problem when posts message, supposed email sent them, have posted it. when replies, originator supposed message, replier has been posted. i’d have thought @ point in process there should script/file in postmessage.asp? the postmessage.asp page below. <% option explicit %> <!-- #include virtual="common/adovbs.inc" --> <html> <head> <meta http-equiv="content-type" content="text/html; charset=windows-1252"> <meta name="generator" content="microsoft frontpage 4.0"> <meta name="progid" content="frontpage.editor.document"> <title>new page 2</title> <base target="_self"
Read more