{"id":84,"date":"2023-11-17T15:33:02","date_gmt":"2023-11-17T15:33:02","guid":{"rendered":"https:\/\/gpt-jordan.com\/?p=84"},"modified":"2023-11-17T15:33:02","modified_gmt":"2023-11-17T15:33:02","slug":"bloomed-perfect-hashing","status":"publish","type":"post","link":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/","title":{"rendered":"Bloomed Perfect Hashing"},"content":{"rendered":"\n\t<style type=\"text\/css\">rect { stroke: #000; fill: #fff; shape-rendering: crispEdges; }\n\trect.on { fill: #fc0; }\n\trect.off { fill: #0cf; }\n    path { stroke: #000; fill: none; }\n\t<\/style>\n\t<script src=\"d3.min.js\"><\/script>\n\t<style type=\"text\/css\">\n\t<\/style>\n<h3>Abstract<\/h3>\n\n<p>Perfect Bloom (PBS) is a probabilistic structure that uses a perfect hash function of a static set S of keys to map all keys in S to distict locations with no collision. The PBS uses an additional bitvector to tell if a key is inserted so far or not. When all input keys are restricted to S, the PBS will return &quot;Definitely Not Found&quot; quickly. Otherwise if the key is in S, at least one entry will have a count of 1, returns &quot;Definitely Found&quot;, and the perfect hash function will return its associated value. <a href=\"http:\/\/iswsa.acm.org\/mphf\/mphf.html\">Order Preserving&nbsp;Perfect Bloom Structures<\/a> can maintain any prior order as well.<\/p>\n\n<p><\/p>\n\n<h3>Perfect Bloom Structure Algorithm<\/h3>\n\n<p>The steps of the algorithm for constructing a PBS are:<\/p>\n\n<p><\/p>\n\n<ol>\n\t<li>\n\t<p>You have K keys, that you want to store perfectly<\/p>\n\t<\/li>\n\t<li>\n\t<p>Choose a number N larger than K. This is the number of vertices in a random graph G (must be 1-orientable or acyclic), and also the size of the resulting Bloom array.<\/p>\n\t<\/li>\n\t<li>\n\t<p>Pick two simple random hash functions f1, f2, that return values from 0 .. N-1.<\/p>\n\t<\/li>\n\t<li>\n\t<p>Now, for all keys, you draw an edge between vertices f1(key) and f2(key) of the graph G, and associate the desired hash value with that edge.<\/p>\n\t<\/li>\n\t<li>\n\t<p>G must be 1-orientable or acyclic; if not, go back to step 2.<\/p>\n\t<\/li>\n\t<li>\n\t<p>Assign values to each vertex such that, for each key (edge), you can add the values for the two vertices and get the desired (hash) value for that key. If the graph is acyclic: pick a vertex, and assigne to it a value of 0. Then do a depth-first search, assigning values to new vertices so that they sum up properly.<\/p>\n\t<\/li>\n\t<li>\n\t<p>f1, f2, and the vertex values of G now make up a perfect hash function and the Bloom array is a perfect Bloom.<\/p>\n\t<\/li>\n<\/ol>\n\n<p>For example, let S be the keys that are the abbreviations for the 50 states in uppercase, and their associated values chosen to be from 0 to 49.<\/p>\n\n<pre>\n  <code>\n  S(Key, Value) = {\n     (AL, 0), (AK, 1), (AZ, 2), (AR, 3), (CA, 4),\n     (CO, 5), (CT, 6), (DE, 7), (FL, 8), (GA, 9),\n     (HI,10), (ID,11), (IL,12), (IN,13), (IA,14),\n     (KS,15), (KY,16), (LA,17), (ME,18), (MD,19),\n     (MA,20), (MI,21), (MN,22), (MS,23), (MO,24),\n     (MT,25), (NE,26), (NV,27), (NH,28), (NJ,29),\n     (NM,30), (NY,31), (NC,32), (ND,33), (OH,34),\n     (OK,35), (OR,36), (PA,37), (RI,38), (SC,39),\n     (SD,40), (TN,41), (TX,42), (UT,43), (VT,44),\n     (VA,45), (WA,46), (WV,47), (WI,48), (WY,49)\n     }\n     <\/code>\n     <\/pre>\n\n<p>To construct a perfect Bloom PBS which is equivalent to an acyclic random graph, we set N = 66. Next, we choose two simple random hash functions f1 and f2:<\/p>\n\n<pre>\n  <code>f1(key) = 15 * key[0] + 29 * key[1]   (mod N)<\/code><\/pre>\n\n<p><\/p>\n\n<pre>\n  <code>f2(key) = 50 * key[0] + 61 * key[1]   (mod N)\n  <\/code>\n  <\/pre>\n\n<p>Where <code>key[0]<\/code> and <code>key[1]<\/code> represent the integer (ASCII) value of the first and second letter in the key. For example:<\/p>\n\n<pre>\n  <code>\n  key      f1   f2\n  ----------------\n  AL  (0)  11   32\n  CO  (5)  62   51\n  SD (40)  49   48\n  TN (41)  24   48\n  WY (49)  58   11\n  <\/code>\n  <\/pre>\n\n<p>The (mod N) is used to return values in the range 0 to 65 for all keys in S. Note also that even for the set of keys, the functions are not unique, e.g. f2(<code>SD<\/code>) = F2(<code>TN<\/code>) = 48.<\/p>\n\n<p>Final distinct location for the Key K in S (note that values are actually chosen so that so keys are kept in sorted order; however values can be anything):<\/p>\n\n<pre>\n    <code>\n    perfect_hash(key) = G[f1(key)] + G[f2(key)]    (mod N)\n    <\/code>\n    <\/pre>\n\n<p>The Perfect Bloom structure will use the same hash functions to build a counting bloom filter (CBF). Each key in S will have at least one distinct location. So when checking for the key K if we find that an entry has a count of 1, then the BPS will report &quot;definitely there&quot; at location computed by perfect_hash(key) instead of &quot;probably there&quot;. If the key is not in the Perfect Bloom Structure then at least one entry will have a count of 0 and the PBS will report &quot;definitely not there&quot;.<\/p>\n\n<p>You can add keys from S to the Perfect Bloom PBS with an array of size 66:<\/p>\n\n<p><label for=\"key\">Key:<\/label> <input id=\"key\" type=\"text\" \/><button class=\"first last\" id=\"add\">Add<\/button><\/p>\n\n<div id=\"vis\" style=\"position: relative;\"><svg height=\"800\" width=\"700\"> <defs> <marker id=\"arrow\" markerheight=\"10\" markerwidth=\"6\" orient=\"auto\" refx=\"10\" refy=\"0\" viewbox=\"0 -5 10 10\"> <path d=\"M0,-5L10,0L0,5Z\" style=\"fill: #000000;\"> <\/path> <\/marker> <\/defs> <g transform=\"translate(10,10)\"> <rect class=\"off\" height=\"12\" width=\"12\" x=\"394\" y=\"0\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"12\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"24\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"36\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"48\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"60\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"72\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"84\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"96\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"108\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"120\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"132\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"144\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"156\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"168\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"180\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"192\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"204\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"216\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"228\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"240\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"252\"> <\/rect> <rect class=\"off\" height=\"12\" width=\"12\" x=\"394\" y=\"264\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"276\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"288\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"300\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"312\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"324\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"336\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"348\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"360\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"372\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"384\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"396\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"408\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"420\"> <\/rect> <rect class=\"off\" height=\"12\" width=\"12\" x=\"394\" y=\"432\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"444\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"456\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"468\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"480\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"492\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"504\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"516\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"528\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"540\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"552\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"564\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"576\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"588\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"600\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"612\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"624\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"636\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"648\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"660\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"672\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"684\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"696\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"708\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"720\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"732\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"744\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"756\"> <\/rect> <rect height=\"12\" width=\"12\" x=\"394\" y=\"768\"> <\/rect> <path class=\"query\" d=\"M100,-10C247,-10 247,-294 394,-294\" marker-end=\"url(#arrow)\" transform=\"translate(800,390)scale(-1,1)\"> <\/path> <path class=\"query\" d=\"M100,-10C247,-10 247,-30 394,-30\" marker-end=\"url(#arrow)\" transform=\"translate(800,390)scale(-1,1)\"> <\/path> <path class=\"query\" d=\"M100,-10C247,-10 247,138 394,138\" marker-end=\"url(#arrow)\" transform=\"translate(800,390)scale(-1,1)\"> <\/path> <\/g> <\/svg>\n\n<div style=\"position: absolute; left: 700px; top: 50%; margin-top: -1.5em;\"><input type=\"text\" \/> <span> Definitely not there.<\/span><\/div>\n<\/div>\n\n<script>\n\t\t(function(exports) {\n\t\t  exports.BloomFilter = BloomFilter;\n\t\t  \/\/exports.fnv_1a = fnv_1a;\n\t\t  \/\/exports.fnv_1a_b = fnv_1a_b;\n\n\t\t  var typedArrays = typeof ArrayBuffer !== \"undefined\";\n\n\t\t  \/\/ Creates a new bloom filter with *m* bits and *k* hashing functions.\n\t\t  function BloomFilter(m, k) {\n\t\t   \/\/alert(\"created bloom\");\n\t\t\tthis.m = m;\n\t\t\tthis.k = k;\n\t\t\tvar n = Math.ceil(m \/ 32);\n\t\t\tif (typedArrays) {\n\t\t\t  var buffer = new ArrayBuffer(32 * n),\n\t\t\t\t  kbytes = 1 << Math.ceil(Math.log(Math.ceil(Math.log(m) \/ Math.LN2 \/ 8)) \/ Math.LN2),\n\t\t\t\t  array = kbytes === 1 ? Uint8Array : kbytes === 2 ? Uint16Array : Uint32Array,\n\t\t\t\t  kbuffer = new ArrayBuffer(kbytes * k);\n\t\t\t  this.buckets = new Uint32Array(buffer);\n\t\t\t  this._locations = new array(kbuffer);\n\t\t\t} else {\n\t\t\t  var buckets = this.buckets = [],\n\t\t\t\t  i = -1;\n\t\t\t  while (++i < n) buckets[i] = 0;\n\t\t\t  this._locations = [];\n\t\t\t  \/\/alert(\"created bloom\");\n\t\t\t}\n\t\t  }\n\n\t\t  \/\/ See http:\/\/willwhim.wordpress.com\/2011\/09\/03\/producing-n-hash-functions-by-hashing-only-once\/\n\t\t  BloomFilter.prototype.locations = function(v) {\n\t\t\tvar k = this.k,\n\t\t\tm = this.m,\n\t\t\tr = this._locations;\n\t\t\tr[0] = (15 * v.charCodeAt(0) + 29 * v.charCodeAt(1))% m;\n\t\t\tr[1] = (50 * v.charCodeAt(0) + 61 * v.charCodeAt(1))% m;\n\t\t\t\/\/alert(\"r(\"+r[0]+\",\"+r[1]+\")\");\n\t\t\treturn r;\n\t\t  };\n\n\t\t  BloomFilter.prototype.add = function(v) {\n\t\t\tvar l = this.locations(v),\n\t\t\t\ti = -1,\n\t\t\t\tk = this.k,\n\t\t\t\tbuckets = this.buckets;\n\t\t\twhile (++i < k) buckets[Math.floor(l[i] \/ 32)] |= 1 << (l[i] % 32);\n\t\t  };\n\n\t\t  BloomFilter.prototype.test = function(v) {\n\t\t\tvar l = this.locations(v),\n\t\t\t\ti = -1,\n\t\t\t\tk = this.k,\n\t\t\t\tb,\n\t\t\t\tbuckets = this.buckets;\n\t\t\twhile (++i < k) {\n\t\t\t  b = l[i];\n\t\t\t  if ((buckets[Math.floor(b \/ 32)] &#038; (1 << (b % 32))) === 0) {\n\t\t\t\treturn false;\n\t\t\t  }\n\t\t\t}\n\t\t\treturn true;\n\t\t  };\n\t\t})(typeof exports !== \"undefined\" ? exports : this);\n\n\t\tvar w = 800,\n\t\t\th = 600;\n\n\t\tvar bloom = new BloomFilter(66, 2),\n\t\t\tkeys = [],\n\t\t\tkeySet = {},\n\t\t\tcolour = d3.scale.category20c();\n\n\t\tvar bw = h \/ bloom.m,\n\t\t\tdy = 20;\n\n\t\tvar queryText = \"\";\n\n\t\tvar diagonal = d3.svg.diagonal()\n\t\t\t.projection(function(d) { return [d.y, d.x]; })\n\t\t\t.source(function(d) { return {y: 100, x: d.from * dy}; })\n\t\t\t.target(function(d) { return {y: (w - bw) \/ 2, x: (d.to + .5) * bw}; });\n\n\t\td3.select(\"#vis\").selectAll(\"*\").remove();\n\t\tvar svg = d3.select(\"#vis\").append(\"svg\")\n\t\t\t.attr(\"width\", w - 100)\n\t\t\t.attr(\"height\", h + 20);\n\n\t\tsvg.append(\"svg:defs\")\n\t\t  .append(\"svg:marker\")\n\t\t\t.attr(\"id\", \"arrow\")\n\t\t\t.attr(\"viewBox\", \"0 -5 10 10\")\n\t\t\t.attr(\"refX\", 10)\n\t\t\t.attr(\"refY\", 0)\n\t\t\t.attr(\"markerWidth\", 6)\n\t\t\t.attr(\"markerHeight\", 10)\n\t\t\t.attr(\"orient\", \"auto\")\n\t\t  .append(\"svg:path\")\n\t\t\t.style(\"fill\", \"#000\")\n\t\t\t.attr(\"d\", \"M0,-5L10,0L0,5Z\");\n\n\t\tvar vis = svg.append(\"g\")\n\t\t\t.attr(\"transform\", \"translate(10,10)\");\n\n\t\tvar div = d3.select(\"#vis\")\n\t\t\t.style(\"position\", \"relative\")\n\t\t  .append(\"div\")\n\t\t\t.style(\"position\", \"absolute\")\n\t\t\t.style(\"left\", (w - 100) + \"px\")\n\t\t\t.style(\"top\", \"50%\")\n\t\t\t.style(\"margin-top\", \"-1.5em\");\n\t\tdiv.append(\"input\")\n\t\t\t.attr(\"type\", \"text\")\n\t\t\t.on(\"keyup\", function() {\n\t\t\t  queryText = this.value;\n\t\t\t  update();\n\t\t\t});\n\t\tvar result = div.append(\"span\");\n\n\t\tupdate();\n\n\t\tvar keyInput = d3.select(\"#key\")\n\t\t\t.on(\"keyup\", function() {\n\t\t\t  if (d3.event.keyCode === 13) add();\n\t\t\t});\n\t\td3.select(\"#add\").on(\"click\", add);\n\n\t\tfunction add() {\n\t\t  var key = keyInput.property(\"value\");\n\t\t  if (!(key in keySet)) {\n\t\t\tkeySet[key] = 1;\n\t\t\tbloom.add(key);\n\t\t\tkeys.push({key: key, value: locations(bloom, key)});\n\t\t\tupdate();\n\t\t  }\n\t\t  keyInput.property(\"value\", \"\");\n\t\t}\n\n\t\tfunction update() {\n\t\t  var offLocations = locations(bloom, queryText);\n\n\t\t  var rect = vis.selectAll(\"rect\")\n\t\t\t  .data(buckets(bloom, offLocations));\n\t\t  rect.enter().append(\"rect\")\n\t\t\t  .attr(\"width\", bw)\n\t\t\t  .attr(\"height\", bw)\n\t\t\t  .attr(\"x\", (w - bw) \/ 2)\n\t\t\t  .attr(\"y\", function(d, i) { return i * bw; });\n\t\t  rect.exit().remove();\n\t\t  rect.attr(\"class\", function(d) { return d === 1 ? \"on\" : d === -1 ? \"off\" : null; });\n\n\t\t  var key = vis.selectAll(\"text.key\")\n\t\t\t  .data(keys);\n\t\t  key.enter().append(\"text\")\n\t\t\t  .attr(\"class\", \"key\")\n\t\t\t  .attr(\"x\", 100)\n\t\t\t  .attr(\"text-anchor\", \"end\")\n\t\t\t  .attr(\"dx\", \"-.3em\")\n\t\t\t  .attr(\"dy\", \".2em\")\n\t\t\t  .text(function(d) { return d.key; });\n\t\t  key.exit().remove();\n\t\t  key.attr(\"y\", function(d, i) { return h \/ 2 + (i - keys.length \/ 2) * dy; });\n\n\t\t  var link = vis.selectAll(\"path.location\")\n\t\t\t  .data(links(bloom, keys));\n\t\t  link.enter().append(\"path\")\n\t\t\t  .attr(\"class\", \"location\")\n\t\t\t  .attr(\"marker-end\", \"url(#arrow)\")\n\t\t\t  .attr(\"transform\", \"translate(0,\" + h \/ 2 + \")\");\n\t\t  link.exit().remove();\n\t\t  link.attr(\"d\", diagonal);\n\n\t\t  var link = vis.selectAll(\"path.query\")\n\t\t\t  .data(links(bloom, [{key: queryText, value: offLocations}]));\n\t\t  link.enter().append(\"path\")\n\t\t\t  .attr(\"class\", \"query\")\n\t\t\t  .attr(\"marker-end\", \"url(#arrow)\")\n\t\t\t  .attr(\"transform\", \"translate(\" + w + \",\" + h \/ 2 + \")scale(-1,1)\");\n\t\t  link.exit().remove();\n\t\t  link.attr(\"d\", diagonal);\n\t\t  result.text(bloom.test(queryText) ? \" Probably there.\" : \" Definitely not there.\");\n\t\t}\n\n\t\tfunction links(bloom, list) {\n\t\t  var a = [];\n\t\t  list.forEach(function(d, i) {\n\t\t\tvar b = {};\n\t\t\td.value.forEach(function(target) {\n\t\t\t  b[target] = 1;\n\t\t\t});\n\t\t\tfor (var target in b) {\n\t\t\t  a.push({from: +i - list.length \/ 2, to: +target - bloom.m \/ 2});\n\t\t\t}\n\t\t  });\n\t\t  return a;\n\t\t}\n\n\t\tfunction buckets(bloom, off) {\n\t\t  var d = bloom.buckets,\n\t\t\t  a = [],\n\t\t\t  m = bloom.m,\n\t\t\t  k,\n\t\t\t  x,\n\t\t\t  n;\n\t\t  for (var i = 0, j = 0; i < m; i += 32, j++) {\n\t\t\tx = d[j];\n\t\t\tn = Math.min(m - i, 32);\n\t\t\tk = -1; while (++k < n) {\n\t\t\t  a.push((x >> k) & 1);\n\t\t\t}\n\t\t  }\n\t\t  off.forEach(function(i) {\n\t\t\tif (a[i] === 0) a[i] = -1;\n\t\t  });\n\t\t  return a;\n\t\t}\n\n\t\tfunction locations(bloom, key) {\n\t\t  var l = bloom.locations(key),\n\t\t\t  k = bloom.k,\n\t\t\t  i = -1,\n\t\t\t  a = [];\n\t\t  while (++i < k) a[i] = l[i];\n\t\t  return a;\n\t\t}\n\n    <\/script>\n\n<p>Drawing all the edges between the vertices f1(key) and f2(key) using SVG, we have:<\/p>\n\n<p><!-- Title: G Pages: 1 --><svg height=\"872pt\" viewbox=\"0 0 761 872\" width=\"761pt\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\"> <g class=\"graph\" id=\"graph0\" style=\"font-family:Times-Roman;font-size:0.6em;\">\n<title><\/title>\n<!-- v1 --> <g class=\"node\" id=\"node2\">\n<title><\/title>\n<ellipse cx=\"69\" cy=\"357\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"69\" y=\"361\">1: 0<\/text> <\/g> <!-- v2 --> <g class=\"node\" id=\"node4\">\n<title><\/title>\n<ellipse cx=\"537\" cy=\"196\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"537\" y=\"200\">2: 0<\/text> <\/g> <!-- v3 --> <g class=\"node\" id=\"node6\">\n<title><\/title>\n<ellipse cx=\"240\" cy=\"709\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"240\" y=\"713\">3: 0<\/text> <\/g> <!-- v4 --> <g class=\"node\" id=\"node8\">\n<title><\/title>\n<ellipse cx=\"355\" cy=\"852\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"355\" y=\"857\">4: 18<\/text> <\/g> <!-- v5 --> <g class=\"node\" id=\"node10\">\n<title><\/title>\n<ellipse cx=\"62\" cy=\"75\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"62\" y=\"79\">5: 0<\/text> <\/g> <!-- v7 --> <g class=\"node\" id=\"node12\">\n<title><\/title>\n<ellipse cx=\"649\" cy=\"148\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"649\" y=\"152\">7: 2<\/text> <\/g> <!-- v9 --> <g class=\"node\" id=\"node14\">\n<title><\/title>\n<ellipse cx=\"262\" cy=\"591\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"262\" y=\"595\">9: 19<\/text> <\/g> <!-- v10 --> <g class=\"node\" id=\"node16\">\n<title><\/title>\n<ellipse cx=\"127\" cy=\"81\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"127\" y=\"85\">10: 16<\/text> <\/g> <!-- v10&#45;&#45;v5 --> <g class=\"edge\" id=\"edge58\">\n<title><\/title>\n<path d=\"M102,79C96,78 90,78 84,77\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"93\" y=\"74\">KY: 16<\/text> <\/g> <!-- v11 --> <g class=\"node\" id=\"node18\">\n<title><\/title>\n<ellipse cx=\"114\" cy=\"308\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"114\" y=\"313\">11: 32<\/text> <\/g> <!-- v11&#45;&#45;v1 --> <g class=\"edge\" id=\"edge60\">\n<title><\/title>\n<path d=\"M102,322C95,328 87,337 81,344\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"102\" y=\"348\">NC: 32<\/text> <\/g> <!-- v12 --> <g class=\"node\" id=\"node20\">\n<title><\/title>\n<ellipse cx=\"141\" cy=\"198\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"141\" y=\"202\">12: 21<\/text> <\/g> <!-- v14 --> <g class=\"node\" id=\"node22\">\n<title><\/title>\n<ellipse cx=\"600\" cy=\"680\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"600\" y=\"684\">14: 0<\/text> <\/g> <!-- v15 --> <g class=\"node\" id=\"node24\">\n<title><\/title>\n<ellipse cx=\"593\" cy=\"171\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"593\" y=\"175\">15: 43<\/text> <\/g> <!-- v15&#45;&#45;v2 --> <g class=\"edge\" id=\"edge62\">\n<title><\/title>\n<path d=\"M573,180C567,183 561,185 556,188\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"569\" y=\"200\">UT: 43<\/text> <\/g> <!-- v15&#45;&#45;v7 --> <g class=\"edge\" id=\"edge64\">\n<title><\/title>\n<path d=\"M614,163C620,161 625,158 630,156\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"627\" y=\"175\">VA: 45<\/text> <\/g> <!-- v16 --> <g class=\"node\" id=\"node26\">\n<title><\/title>\n<ellipse cx=\"50\" cy=\"198\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"50\" y=\"202\">16: 61<\/text> <\/g> <!-- v17 --> <g class=\"node\" id=\"node28\">\n<title><\/title>\n<ellipse cx=\"168\" cy=\"477\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"168\" y=\"481\">17: 36<\/text> <\/g> <!-- v18 --> <g class=\"node\" id=\"node30\">\n<title><\/title>\n<ellipse cx=\"374\" cy=\"143\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"374\" y=\"147\">18: 38<\/text> <\/g> <!-- v19 --> <g class=\"node\" id=\"node32\">\n<title><\/title>\n<ellipse cx=\"596\" cy=\"508\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"596\" y=\"512\">19: 0<\/text> <\/g> <!-- v20 --> <g class=\"node\" id=\"node34\">\n<title><\/title>\n<ellipse cx=\"424\" cy=\"180\" rx=\"25\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"424\" y=\"184\">20: 36<\/text> <\/g> <!-- v20&#45;&#45;v18 --> <g class=\"edge\" id=\"edge66\">\n<title><\/title>\n<path d=\"M409,168C403,164 396,159 390,154\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"391\" y=\"176\">FL: 8<\/text> <\/g> <!-- v21 --> <g class=\"node\" id=\"node36\">\n<title><\/title>\n<ellipse cx=\"731\" cy=\"418\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"731\" y=\"422\">21: 53<\/text> <\/g> <!-- v22 --> <g class=\"node\" id=\"node38\">\n<title><\/title>\n<ellipse cx=\"208\" cy=\"216\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"208\" y=\"220\">22: 4<\/text> <\/g> <!-- v23 --> <g class=\"node\" id=\"node40\">\n<title><\/title>\n<ellipse cx=\"553\" cy=\"642\" rx=\"25\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"553\" y=\"646\">23: 24<\/text> <\/g> <!-- v23&#45;&#45;v14 --> <g class=\"edge\" id=\"edge68\">\n<title><\/title>\n<path d=\"M568,654C574,659 580,664 586,669\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"568\" y=\"677\">MO: 24<\/text> <\/g> <!-- v24 --> <g class=\"node\" id=\"node42\">\n<title><\/title>\n<ellipse cx=\"261\" cy=\"390\" rx=\"25\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"261\" y=\"394\">24: 34<\/text> <\/g> <!-- v25 --> <g class=\"node\" id=\"node44\">\n<title><\/title>\n<ellipse cx=\"162\" cy=\"137\" rx=\"25\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"162\" y=\"141\">25: 64<\/text> <\/g> <!-- v25&#45;&#45;v10 --> <g class=\"edge\" id=\"edge70\">\n<title><\/title>\n<path d=\"M153,123C147,115 141,103 136,95\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"130\" y=\"121\">IA: 14<\/text> <\/g> <!-- v25&#45;&#45;v12 --> <g class=\"edge\" id=\"edge72\">\n<title><\/title>\n<path d=\"M157,152C154,162 149,174 145,183\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"136\" y=\"166\">MD: 19<\/text> <\/g> <!-- v26 --> <g class=\"node\" id=\"node46\">\n<title><\/title>\n<ellipse cx=\"201\" cy=\"578\" rx=\"25\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"201\" y=\"582\">26: 53<\/text> <\/g> <!-- v26&#45;&#45;v9 --> <g class=\"edge\" id=\"edge74\">\n<title><\/title>\n<path d=\"M226,583C231,584 236,585 241,587\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"232\" y=\"599\">CT: 6<\/text> <\/g> <!-- v27 --> <g class=\"node\" id=\"node48\">\n<title><\/title>\n<ellipse cx=\"313\" cy=\"807\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"313\" y=\"811\">27: 2<\/text> <\/g> <!-- v27&#45;&#45;v4 --> <g class=\"edge\" id=\"edge76\">\n<title><\/title>\n<path d=\"M324,820C330,826 337,834 343,839\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"323\" y=\"844\">MA: 20<\/text> <\/g> <!-- v28 --> <g class=\"node\" id=\"node50\">\n<title><\/title>\n<ellipse cx=\"672\" cy=\"428\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"672\" y=\"432\">28: 15<\/text> <\/g> <!-- v28&#45;&#45;v21 --> <g class=\"edge\" id=\"edge78\">\n<title><\/title>\n<path d=\"M696,424C700,423 704,422 707,422\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"703\" y=\"437\">AZ: 2<\/text> <\/g> <!-- v29 --> <g class=\"node\" id=\"node52\">\n<title><\/title>\n<ellipse cx=\"30\" cy=\"404\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"30\" y=\"409\">29: 10<\/text> <\/g> <!-- v29&#45;&#45;v1 --> <g class=\"edge\" id=\"edge80\">\n<title><\/title>\n<path d=\"M40,391C46,385 53,377 58,370\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"61\" y=\"395\">HI: 10<\/text> <\/g> <!-- v30 --> <g class=\"node\" id=\"node54\">\n<title><\/title>\n<ellipse cx=\"496\" cy=\"481\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"496\" y=\"485\">30: 47<\/text> <\/g> <!-- v31 --> <g class=\"node\" id=\"node56\">\n<title><\/title>\n<ellipse cx=\"147\" cy=\"20\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"147\" y=\"24\">31: 61<\/text> <\/g> <!-- v31&#45;&#45;v10 --> <g class=\"edge\" id=\"edge82\">\n<title><\/title>\n<path d=\"M142,34C139,44 135,57 131,66\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"122\" y=\"50\">ID: 11<\/text> <\/g> <!-- v32 --> <g class=\"node\" id=\"node58\">\n<title><\/title>\n<ellipse cx=\"80\" cy=\"252\" rx=\"25\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"80\" y=\"256\">32: 34<\/text> <\/g> <!-- v32&#45;&#45;v11 --> <g class=\"edge\" id=\"edge84\">\n<title><\/title>\n<path d=\"M88,266C94,274 100,285 106,294\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"84\" y=\"293\">AL: 0<\/text> <\/g> <!-- v32&#45;&#45;v16 --> <g class=\"edge\" id=\"edge86\">\n<title><\/title>\n<path d=\"M72,238C68,230 63,220 58,212\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"79\" y=\"221\">NJ: 29<\/text> <\/g> <!-- v34 --> <g class=\"node\" id=\"node60\">\n<title><\/title>\n<ellipse cx=\"449\" cy=\"345\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"449\" y=\"349\">34: 9<\/text> <\/g> <!-- v35 --> <g class=\"node\" id=\"node62\">\n<title><\/title>\n<ellipse cx=\"437\" cy=\"404\" rx=\"22\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"437\" y=\"409\">35: 6<\/text> <\/g> <!-- v35&#45;&#45;v34 --> <g class=\"edge\" id=\"edge88\">\n<title><\/title>\n<path d=\"M440,390C442,381 444,369 446,360\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"427\" y=\"377\">KS: 15<\/text> <\/g> <!-- v36 --> <g class=\"node\" id=\"node64\">\n<title><\/title>\n<ellipse cx=\"305\" cy=\"217\" rx=\"25\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"305\" y=\"221\">36: 36<\/text> <\/g> <!-- v37 --> <g class=\"node\" id=\"node66\">\n<title><\/title>\n<ellipse cx=\"226\" cy=\"509\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"226\" y=\"514\">37: 60<\/text> <\/g> <!-- v37&#45;&#45;v17 --> <g class=\"edge\" id=\"edge90\">\n<title><\/title>\n<path d=\"M208,500C201,495 193,491 186,487\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"191\" y=\"509\">NM: 30<\/text> <\/g> <!-- v37&#45;&#45;v26 --> <g class=\"edge\" id=\"edge92\">\n<title><\/title>\n<path d=\"M221,524C217,536 210,552 206,564\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"199\" y=\"542\">WV: 47<\/text> <\/g> <!-- v38 --> <g class=\"node\" id=\"node68\">\n<title><\/title>\n<ellipse cx=\"464\" cy=\"285\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"464\" y=\"290\">38: 18<\/text> <\/g> <!-- v38&#45;&#45;v34 --> <g class=\"edge\" id=\"edge94\">\n<title><\/title>\n<path d=\"M460,300C458,309 455,322 452,331\" style=\"fill:none;stroke:#ff0000;\"><\/path> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"472\" y=\"324\">NV: 27<\/text> <\/g> <!-- v39 --> <g class=\"node\" id=\"node70\">\n\n<ellipse cx=\"131\" cy=\"573\" rx=\"24\" ry=\"14\" style=\"fill:#a0e0ee;stroke:#a0e0ee;\"><\/ellipse> <text style=\"font-size:11.49;\" text-anchor=\"middle\" x=\"131\" y=\"578\">39: 47<\/text> <\/g> <!-- v39&#45;&#45;v26 --> <g class=\"edge\" id=\"edge96\">\n","protected":false},"excerpt":{"rendered":"<p>Abstract Perfect Bloom (PBS) is a probabilistic structure that uses a perfect hash function of a static set S of keys to map all keys in S to distict locations [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":568,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"_EventAllDay":false,"_EventTimezone":"","_EventStartDate":"","_EventEndDate":"","_EventStartDateUTC":"","_EventEndDateUTC":"","_EventShowMap":false,"_EventShowMapLink":false,"_EventURL":"","_EventCost":"","_EventCostDescription":"","_EventCurrencySymbol":"","_EventCurrencyCode":"","_EventCurrencyPosition":"","_EventDateTimeSeparator":"","_EventTimeRangeSeparator":"","_EventOrganizerID":[],"_EventVenueID":[],"_OrganizerEmail":"","_OrganizerPhone":"","_OrganizerWebsite":"","_VenueAddress":"","_VenueCity":"","_VenueCountry":"","_VenueProvince":"","_VenueState":"","_VenueZip":"","_VenuePhone":"","_VenueURL":"","_VenueStateProvince":"","_VenueLat":"","_VenueLng":"","_VenueShowMap":false,"_VenueShowMapLink":false,"footnotes":""},"categories":[30],"tags":[],"class_list":["post-84","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-succinct-data-structures"],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v23.7 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Bloomed Perfect Hashing - Innovative Digital Transformation Jordan<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Bloomed Perfect Hashing - Innovative Digital Transformation Jordan\" \/>\n<meta property=\"og:description\" content=\"Abstract Perfect Bloom (PBS) is a probabilistic structure that uses a perfect hash function of a static set S of keys to map all keys in S to distict locations [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/\" \/>\n<meta property=\"og:site_name\" content=\"Innovative Digital Transformation Jordan\" \/>\n<meta property=\"article:published_time\" content=\"2023-11-17T15:33:02+00:00\" \/>\n<meta name=\"author\" content=\"Editor\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Editor\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/\"},\"author\":{\"name\":\"Editor\",\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/#\/schema\/person\/260ed75841f0c76d83d1b2bc3121f6f6\"},\"headline\":\"Bloomed Perfect Hashing\",\"datePublished\":\"2023-11-17T15:33:02+00:00\",\"dateModified\":\"2023-11-17T15:33:02+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/\"},\"wordCount\":595,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/#organization\"},\"image\":{\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2023\/11\/perfect-bloom.jpg\",\"articleSection\":[\"Succinct Data Structures\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/\",\"url\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/\",\"name\":\"Bloomed Perfect Hashing - Innovative Digital Transformation Jordan\",\"isPartOf\":{\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2023\/11\/perfect-bloom.jpg\",\"datePublished\":\"2023-11-17T15:33:02+00:00\",\"dateModified\":\"2023-11-17T15:33:02+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#primaryimage\",\"url\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2023\/11\/perfect-bloom.jpg\",\"contentUrl\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2023\/11\/perfect-bloom.jpg\",\"width\":617,\"height\":659,\"caption\":\"This acyclic tree depicts a combination of a bloom and a order preserving hash. The search becomes an addition and unsuccessful search terminated as a result of the addition! The necessary condition for accomplishing this is generating 1-orientable random graph which is almost surely when number of graph node is slightly higher than the number of keys n.\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Bloomed Perfect Hashing\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/#website\",\"url\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/\",\"name\":\"Innovative Digital Transformation Jordan\",\"description\":\"Improve Your Life with NetBookLM\",\"publisher\":{\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/#organization\",\"name\":\"Innovative Digital Transformation Jordan\",\"url\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2024\/09\/cropped-cropped-Designer-1.jpeg\",\"contentUrl\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2024\/09\/cropped-cropped-Designer-1.jpeg\",\"width\":70,\"height\":70,\"caption\":\"Innovative Digital Transformation Jordan\"},\"image\":{\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/#\/schema\/person\/260ed75841f0c76d83d1b2bc3121f6f6\",\"name\":\"Editor\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g\",\"caption\":\"Editor\"},\"url\":\"https:\/\/idtjo.hosting.acm.org\/wordpress\/author\/editor\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Bloomed Perfect Hashing - Innovative Digital Transformation Jordan","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/","og_locale":"en_US","og_type":"article","og_title":"Bloomed Perfect Hashing - Innovative Digital Transformation Jordan","og_description":"Abstract Perfect Bloom (PBS) is a probabilistic structure that uses a perfect hash function of a static set S of keys to map all keys in S to distict locations [&hellip;]","og_url":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/","og_site_name":"Innovative Digital Transformation Jordan","article_published_time":"2023-11-17T15:33:02+00:00","author":"Editor","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Editor","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#article","isPartOf":{"@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/"},"author":{"name":"Editor","@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/#\/schema\/person\/260ed75841f0c76d83d1b2bc3121f6f6"},"headline":"Bloomed Perfect Hashing","datePublished":"2023-11-17T15:33:02+00:00","dateModified":"2023-11-17T15:33:02+00:00","mainEntityOfPage":{"@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/"},"wordCount":595,"commentCount":0,"publisher":{"@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/#organization"},"image":{"@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#primaryimage"},"thumbnailUrl":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2023\/11\/perfect-bloom.jpg","articleSection":["Succinct Data Structures"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/","url":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/","name":"Bloomed Perfect Hashing - Innovative Digital Transformation Jordan","isPartOf":{"@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/#website"},"primaryImageOfPage":{"@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#primaryimage"},"image":{"@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#primaryimage"},"thumbnailUrl":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2023\/11\/perfect-bloom.jpg","datePublished":"2023-11-17T15:33:02+00:00","dateModified":"2023-11-17T15:33:02+00:00","breadcrumb":{"@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#primaryimage","url":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2023\/11\/perfect-bloom.jpg","contentUrl":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2023\/11\/perfect-bloom.jpg","width":617,"height":659,"caption":"This acyclic tree depicts a combination of a bloom and a order preserving hash. The search becomes an addition and unsuccessful search terminated as a result of the addition! The necessary condition for accomplishing this is generating 1-orientable random graph which is almost surely when number of graph node is slightly higher than the number of keys n."},{"@type":"BreadcrumbList","@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/bloomed-perfect-hashing\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/idtjo.hosting.acm.org\/wordpress\/"},{"@type":"ListItem","position":2,"name":"Bloomed Perfect Hashing"}]},{"@type":"WebSite","@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/#website","url":"https:\/\/idtjo.hosting.acm.org\/wordpress\/","name":"Innovative Digital Transformation Jordan","description":"Improve Your Life with NetBookLM","publisher":{"@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/idtjo.hosting.acm.org\/wordpress\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/#organization","name":"Innovative Digital Transformation Jordan","url":"https:\/\/idtjo.hosting.acm.org\/wordpress\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/#\/schema\/logo\/image\/","url":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2024\/09\/cropped-cropped-Designer-1.jpeg","contentUrl":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2024\/09\/cropped-cropped-Designer-1.jpeg","width":70,"height":70,"caption":"Innovative Digital Transformation Jordan"},"image":{"@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/#\/schema\/person\/260ed75841f0c76d83d1b2bc3121f6f6","name":"Editor","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/idtjo.hosting.acm.org\/wordpress\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","caption":"Editor"},"url":"https:\/\/idtjo.hosting.acm.org\/wordpress\/author\/editor\/"}]}},"jetpack_featured_media_url":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-content\/uploads\/2023\/11\/perfect-bloom.jpg","_links":{"self":[{"href":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-json\/wp\/v2\/posts\/84","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-json\/wp\/v2\/comments?post=84"}],"version-history":[{"count":0,"href":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-json\/wp\/v2\/posts\/84\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-json\/wp\/v2\/media\/568"}],"wp:attachment":[{"href":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-json\/wp\/v2\/media?parent=84"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-json\/wp\/v2\/categories?post=84"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/idtjo.hosting.acm.org\/wordpress\/wp-json\/wp\/v2\/tags?post=84"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}