29:null 2a:["$","title",null,{"children":"Probabilistic Filters | Laurens Debackere | Observable"}] 2f:Tc39, /** * JS Implementation of MurmurHash3 (r152) (as of May 10, 2013) * A classical, non-unrolled version. * The other, unrolled version obviously requires more code space in the CPU, * so you have to consider how often and on how long strings * you are going to call the hashing function. * * @author Roland Pihlakas * @see http://github.com/levitation/murmurhash-js * @author Austin Appleby * @see https://code.google.com/p/smhasher/ * * @param {string} key ASCII only * @param {number} seed positive integer only * @return {number} 32-bit positive integer hash */ function mrmr3(key, seed) { var keyLength, tailLength, bodyLength, h1, k1, i, c1_low, c1_high, c2_low, c2_high, c3; keyLength = key.length; tailLength = keyLength & 3; bodyLength = keyLength - tailLength; h1 = seed; //c1 = 0xcc9e2d51; c1_low = 0x2d51; c1_high = 0xcc9e0000; //c2 = 0x1b873593; c2_low = 0x3593; c2_high = 0x1b870000; c3 = 0xe6546b64; //---------- // body i = 0; while (i < bodyLength) { k1 = ((key.charCodeAt(i) & 0xff)) | ((key.charCodeAt(++i) & 0xff) << 8) | ((key.charCodeAt(++i) & 0xff) << 16) | ((key.charCodeAt(++i) & 0xff) << 24); ++i; //k1 *= c1; k1 = (c1_high * k1 | 0) + (c1_low * k1); //k1 = ROTL32(k1,15); k1 = (k1 << 15) | (k1 >>> 17); //k1 *= c2; k1 = (c2_high * k1 | 0) + (c2_low * k1); //h1 ^= k1; h1 ^= k1; //h1 = ROTL32(h1,13); h1 = (h1 << 13) | (h1 >>> 19); //h1 = h1*5+0xe6546b64; h1 = h1 * 5 + c3; } //while (i < bodyLength) { //---------- // tail k1 = 0; switch (tailLength) { case 3: k1 ^= (key.charCodeAt(i + 2) & 0xff) << 16; case 2: k1 ^= (key.charCodeAt(i + 1) & 0xff) << 8; case 1: k1 ^= (key.charCodeAt(i) & 0xff); //k1 *= c1; k1 = (c1_high * k1 | 0) + (c1_low * k1); //k1 = ROTL32(k1,15); k1 = (k1 << 15) | (k1 >>> 17); //k1 *= c2; k1 = (c2_high * k1 | 0) + (c2_low * k1); //h1 ^= k1; h1 ^= k1; } //switch (tailLength) { //---------- // finalization h1 ^= keyLength; //h1 = fmix32(h1); { //h ^= h >> 16; h1 ^= h1 >>> 16; //h1 *= 0x85ebca6b; h1 = (0x85eb0000 * h1 | 0) + (0xca6b * h1); //h ^= h >> 13; h1 ^= h1 >>> 13; //h1 *= 0xc2b2ae35; h1 = (0xc2b20000 * h1 | 0) + (0xae35 * h1); //h ^= h >> 16; h1 ^= h1 >>> 16; } return h1 >>> 0; //convert to unsigned int } 30:[{"id":"abc312153a771cfc0e57607f90e9a6563a436181291a2414d4d3d59b7f9427065f6dc7fbfcbd67c412627e74d36369a6655e814b49c01dcc112b456938e74d91","href":"https://static.observableusercontent.com/files/abc312153a771cfc0e57607f90e9a6563a436181291a2414d4d3d59b7f9427065f6dc7fbfcbd67c412627e74d36369a6655e814b49c01dcc112b456938e74d91","name":"afbeelding@3.png","type":"image/png","lastModified":1647770361973.259,"size":5123},{"id":"f0f559ba184ec1456790682ffa283aa02b49d789c7215008406518775aa0aa51169673f708a8bba2e72a60a59524eec01276e4bc08db0fb1ae436f0756f5c653","href":"https://static.observableusercontent.com/files/f0f559ba184ec1456790682ffa283aa02b49d789c7215008406518775aa0aa51169673f708a8bba2e72a60a59524eec01276e4bc08db0fb1ae436f0756f5c653","name":"Schermafbeelding 2022-03-20 om 13.36.39.png","type":"image/png","lastModified":1647779806405.654,"size":228719},{"id":"bbc732f3dbe551c52fdea096c63fc269eae2be4dc698bdc7b43304e65eda7c00131c1931031bbf9b72da494d13fd8baa0059370f3dbc0c659df6ddf14bf5ce36","href":"https://static.observableusercontent.com/files/bbc732f3dbe551c52fdea096c63fc269eae2be4dc698bdc7b43304e65eda7c00131c1931031bbf9b72da494d13fd8baa0059370f3dbc0c659df6ddf14bf5ce36","name":"afbeelding@1.png","type":"image/png","lastModified":1647769577646.385,"size":33977}] 2d:{"id":"b0723000e13584be","slug":"probabilistic-filters","title":"Probabilistic Filters","thumbnail":"36845fcaf386cfc3d1692f8eb6e056b11c617789282f6292e2a2823c7dc2f073","access_level":"public","create_time":"$D2022-03-14T09:34:45.775Z","update_time":"$D2022-03-27T09:43:01.273Z","view_time":null,"first_public_time":"$D2022-03-23T13:35:54.890Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"d6b18c54f51ce9e2","login":"laurensdeb","name":"Laurens Debackere","avatar_url":"https://avatars-next.observableusercontent.com/7d15871f6e8319cd1c1a86deb6bb62ad15086e9cff56c7f9acceeaec0d900285","tier":"starter_2024"},"version":624,"publish_version":624,"role":null,"authored":false,"authors":[{"type":"individual","id":"8a9aa62b2bb093d9","login":"laurensdeb","name":"Laurens Debackere","avatar_url":"https://avatars-next.observableusercontent.com/7d15871f6e8319cd1c1a86deb6bb62ad15086e9cff56c7f9acceeaec0d900285","tier":null}],"members":[{"type":"individual","id":"8a9aa62b2bb093d9","login":"laurensdeb","name":"Laurens Debackere","avatar_url":"https://avatars-next.observableusercontent.com/7d15871f6e8319cd1c1a86deb6bb62ad15086e9cff56c7f9acceeaec0d900285","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Probabilistic Filters","cells":[{"id":0,"value":"# Probabilistic Filters","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"## Bloom Filter\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":15,"value":"length = 10;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"hash_count = 3;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"value = \"tree\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"bitset = createBitset(length)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"showBitset = (bitset, highlight=false) => html`${bitset.map(value => ``).join('')}

${value?1:0}

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"showBitset(bitset)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"add = (value, bitset) => {\n const result = [...bitset]\n const length = bitset.length;\n for(let i = 0; i < hash_count; i++){\n result[mrmr3(value, i) % length] = true;\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"html`\n

Value: \"${value}\"

Hashes:

hash(\"${value}\", ${i}) = ${mrmr3(value, i) % length}

Value: \"${mark}\"

Hashes:

hash(\"${mark}\", ${i}) = ${mrmr3(mark, i) % length}

range(0, size).map(() => {return {occupied: false, continuation: false, shifted: false, remainder: 0}});\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":450,"value":"filter = new Object({count: 0, filter: quotientFilter(2**q)})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":253,"value":"![afbeelding@1.png](${await FileAttachment(\"afbeelding@1.png\").url()})","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":495,"value":"While Bloom filters only support the insertion and lookup operations, we can also **delete** items from a Quotient Filter.\n\nQuotient Filters, while bigger than Bloom Filters are typically faster because only a single hash function is executed.\n\nFurthermore Quotient Filters can be **merged** without affecting the False Positive rates.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":500,"value":"False~Positive~Rate:\n\nP \\leq (1/2^r)","pinned":false,"hidden":false,"mode":"tex","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":505,"value":"**Sources:**\n- https://www.gakhov.com/articles/quotient-filters.html\n- https://en.wikipedia.org/wiki/Quotient_filter","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":168,"value":"md`## Quckoo Filter`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":557,"value":"Quckoo Filters build on the concept of **Quckoo Hashing**, where not one but two hash functions are used in order to reduce the number of expected collisions for a bucket in a hash table.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":550,"value":"x \\in T \\iff T[h_1(x)] = x \\vee T[h_2(x)] = x","pinned":false,"hidden":false,"mode":"tex","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":562,"value":"If both of the buckets are non-empty, then upon insertion we will attempt to insert the element into the bucket h₂(x) and move the item that was already there to its alternative location. We repeat this process until we have shifted an item into an empty bucket or some maximum number of iterations was reached (to avoid cycles).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":568,"value":"![Schermafbeelding 2022-03-20 om 13.36.39.png](${await FileAttachment(\"Schermafbeelding 2022-03-20 om 13.36.39.png\").url()})","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":580,"value":"The Quckoo Filter follows a similar pattern, however now instead of storing the actual items into their respective buckets we construct a **fingerprint** *φ(x)* for the value to be stored which is an identifying string for the item that requires fewer bits.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":592,"value":"However when inserting a new value, under the Cuckoo Hashing scheme, we may have to move previously inserted items. Yet, we now no longer have access to the original element, but only the **fingerprint**.\n\nThus we are not able to choose the two locations for an item independently, rather we define them as:\n- Location 1: h₁(x)\n- Location 2: h₁(x) ⊕ h₂(φ(x))","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":599,"value":"This yields us with the following mathematical property:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":603,"value":"i \\oplus h_2(\\phi(x)) = \\left\\{\n \\begin{array}{lr}\n h_1(x) & \\iff i=h_1(x) \\oplus h_2(\\phi(x))\\\\\n h_1(x) \\oplus h_2(\\phi(x)) & \\iff i = h_1(x)\n \\end{array}\n\\right.\n","pinned":false,"hidden":false,"mode":"tex","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":573,"value":"**Sources:**\n- http://www.cs.toronto.edu/~noahfleming/CuckooHashing.pdf","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":51,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"range = (start, end, step = 1) => {\n let output = [];\n if (typeof end === 'undefined') {\n end = start;\n start = 0;\n }\n for (let i = start; i < end; i += step) {\n output.push(i);\n }\n return output;\n};","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":143,"value":"createBitset = (length) => Array(length).fill(false)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W30","stdlib":"1","titling":"auto"}} 2e:"$2d:body"