HyperLogLog Javascript (js-hll) & Postgres (postgres-hll): making them talk to each other!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
hex_array = ["/x138b7f010101c101e3024104e1058305a105c3072207810922098209a209c30b220c410ce20e210e410e610ee11002106310a210e31323138513a213c2142114421463156115a115e416011661168316a216e1186218a31927194119611aa81b411b611be11c411d431dc21e22218121a121e122a322e12324236123c224c12641266127c3288329442a012a612b012be22cc52d412e612e812fa12fc1302131843282338133e335023541356235a23623364138233863388139813a023a623a823d033d413e613ea13f4140a1414141e242014322438143a24406458145a145e546e14721474248014822486249214a234ae14b414b614be34ca24cc14d424d614da14e214fa250225101514552e453215423548154c355c1564558e3590359415b215b415d625da25f225f836122614162426422648164a16681672367c168016822686168a169216943698169c56b426b816d016e616ee16f416fc17102718471e17326742474e177027742776277e2782378a27901794179817a027a617aa17b217b817c627ce57d817dc47e837ee3800280848181826582a382c1832584e18502854285628607864187e5880188618883898289e28a248a438aa18ac18ae28b028b218b818ca28e028ea58f278fe4904190e192c192e1932193e2940194e2958395c2962296a496e198229923994499e19a619aa59ae39be29ce29e219e419ee49f039f219f63a001a041a181a1c2a202a241a341a462a483a4e3a501a564a5c1a622a6e1a801a867a941a981aaa3aae1ab24abe1ac01acc2ad62ae01ae21afc1b001b082b0a2b103b182b1e2b2a2b2e2b321b3a2b541b581b5e4b6e1b7e1b804b821b922ba21ba41ba83bbe3bc41bc82be04bec3bf01c021c0a2c204c262c2e1c3c1c542c681c782c861c8a1c923ca21cac1cf61d042d0a2d1a2d222d3e1d5a1d5e2d681d6e2d741d7e1d822d961d9c2da03da61da81db42db63db81dc01dd27dd44dde3de22dea1dec4df69dfe1e043e082e162e281e301e321e3c7e521e562e5a2e6a8e6c4e721e742e764e782e821e8e1e925ea45eac2eb81eba5ecc1ece4edc2ede2ee02eea1eec3eee1ef83efa1f082f0a7f121f1c1f2c3f3c2f405f464f501f521f642f661f682f6a3f724f781f8e1f924f981f9a1fa01fbe1fc03fc41fcc2fdc2fe81fea1ffc3ffe1",
"/x128b7f94c64fc29302fedb95064f4594429faea211348181b84bf6a4de1a560e2cde5aae10a82d9b23d04cb37315171da42c7eb634d69b7206eda3b9f61329abd41006c3754ff2b383fe29c5293f8d8dc2dd0ac6e0d283ed4c464ecb1077494c2d63bed629d2966cf0f74ed6d1c433d793c977e7c3ef6d62b062dae87c30eb549046fbed1a115578bfd959f7defd537345d9dc02d1bcbb389f666a036c085757a5147d0bde87fd03cfff7c0c2f46328f046dc50df9247d5d7c02450e7e599707200bef1993af1b2a2520ce27ae169919eb38aa27e882def7ec080c2846cff817fe669530085d7134cb022b3176150ff4e07b5b339241a82324a9d54dbf805d46768d8955167824ea33a3fe55daffbb24f17f5a58c22d17fbba79b05aa808f534be42765f7e8940497ef0c0601e98e71202a33e6fa844e45f16e3f97ad2759531cfe48d7cb25be453a9c8b0",
"/x128b7f8592206f9f19e59c8fd86aefaa33159392aa0e34f0ec18369fe0b373f4f8fb0ea160a594697af83ca209824fdf11dc96a2691b9bdb7a5d68b27eec512b56e437b5a25cb801028cc2b708aa8ad616ef9db8ec683405749d5cbf1cb31e793ca24cc39099abfbdefae9c3b77288c737593bc5e8fbd70be21d25cbecf5f3fc316718ccc47bada8f1a802d0ecb268db22971edd5556b6ef9c83b3deb153736583554efa9f8831cd825d37fbaa507b619aa7f8fcd9e3c86352460202568446a3b4e7ab0baed2436665893018a5739a57a4afe81b57440b7edbb2801c9b4f2bb609d6291d2a2f4022fdf5b9228fe694968e225b232cb3ef34aa283929b266e071ff51d32cd41d8079ca04032f58fb7330727f962ff990b545c1aa3e341c639ae719f1fb392c8bdaf8e352b63eaa1a73ec6d0878407f68d908e2138840a56c50cb1d62db4adfed6510fd513a4f2e41693e7f609258fa6eb4cca8c8fa5c4637c28a62b27b5dec7b773dbc1d0560c2eafcc1e091236bde80216b9972156f4f9d7bda221f0e7b53f009355d4be47ccca7e798abb1267e1fda106584187a"]

hex_array.reduce(function (first, second) {
   return first.union(
     hll.fromHexString(
       second.replace(/\\\\/g,"/"))
       .hllSet)}, new hll.HLL(11, 5)
    ).cardinality();
// 567

HyperLogLog is a fantastic algorithm to quickly count distinct elements in a set. As it consumes few memory and is really fast, it’s perfectly suited for big data. For a nice, visual explanation step over to the Redis guys on Youtube. However, this article is not about explaining HyperLogLog but rather understanding how to deal with backend/frontend communication between javascript and postgres by exchanging hexstrings between the two amazing libraries postgres-hll for postgres and js-hll for javascript.

Postgres-hll

Postgres-hll is a simple Postgres extension implementing the algorithm of the 2007 paper by Flajolet et al.. It’s very fast, convenient and wide-spread. Let’s get the cardinality of a sample hexstring

1
SELECT hll_cardinality('\x128b7f81efea02d36894df8294bb1a08ead3cb853f45a91146092985a88df68b6e3f2f8e16a5fc8cc2e7c8922b2da822fae58995c1a33b13ee5d029644bc5dcaa027729c4a7ac7e5b9ebde9d0b6d24dfc8b302a1ceafcb7a272e45a30047e00c2be0f0a41c7c878c40a166a6edb0566278f8c4a8ab4afcd4f9a1f0a9b7adca30eae3e8aa494229d507d863aa9ae566683322baadb747002db9d70fb2737a70a7ecc60fb95bfb5354d6cd87b9bbe961ef837463bd2bee81a647ad3ebdad480a48bed298c19728671afac162c329cad91b3fb953c3d85f55cdeb7b12c520e4fdc4365e5dc6a429a980ea7003cab67972d493f236cca2c69c250f62aecceb5075a5ffe8d6ce6f02f12adbf1d7d5118d60637947ced6715e4aa0f607ccd8062322161a0659d99acae0e87fda55dcb6ea49fc93609dde1455de1f9a0d90deb85b465b39b2afe2cb2fc1bcdc2750e4dc5d77ae5e1e9ce6fc8ffd9885d762edfbb484f41fcc58ee394a6aafc942fff00c3825d9fb04bcf0343b9ae635a515f39f9612327d248ef6f2ecd85996b7b0f721ce7e5c1dd0fc014ef235286c2aff023810775b774ac20400ab64105467c60454bed2f7bedaf4098a42f6813d4a5d0bc73bba3fd2acaf125ab6add5a439dd145f8f6e57375c4815e4e46ce8a5b6a71693cb7a1e26e46a1b6cd5da435e07381f973eca29d9c3b628b339db7386e11132329f6e0d9fe41e34c56953bed65f983b6f4a3eeab0161340937fa46bc735c9418cde3fce859117429a52ab617a309a44b8a5401bc1595b485c4496fd6385a853e96c081128fd335440ba390b23a97556b6187808cd29c257414d32ec44bb3a5c2d5625214a3636630c3d343cc7bd62663f42c51dbb98d86b57253654e6f3c26db8beb06b2c6e1c6e369287983814dc6f80bad5e3ae2f7d76057bd04447fce77772220deaeef27b77d5cf170a819dbc7ad427eb752986a57bb4c308738959637ce048f48bd76eaf')

This will return 88.

Js-hll

Js-hll is a really good implementation of the algorithm in javascript. It works reliably and fast but most importantly for this article it is compatible with Postgres as it can take hexstrings as input! And it works as easy as this:

1
2
3
hllHexString = "/x128b7f81efea02d36894df8294bb1a08ead3cb853f45a91146092985a88df68b6e3f2f8e16a5fc8cc2e7c8922b2da822fae58995c1a33b13ee5d029644bc5dcaa027729c4a7ac7e5b9ebde9d0b6d24dfc8b302a1ceafcb7a272e45a30047e00c2be0f0a41c7c878c40a166a6edb0566278f8c4a8ab4afcd4f9a1f0a9b7adca30eae3e8aa494229d507d863aa9ae566683322baadb747002db9d70fb2737a70a7ecc60fb95bfb5354d6cd87b9bbe961ef837463bd2bee81a647ad3ebdad480a48bed298c19728671afac162c329cad91b3fb953c3d85f55cdeb7b12c520e4fdc4365e5dc6a429a980ea7003cab67972d493f236cca2c69c250f62aecceb5075a5ffe8d6ce6f02f12adbf1d7d5118d60637947ced6715e4aa0f607ccd8062322161a0659d99acae0e87fda55dcb6ea49fc93609dde1455de1f9a0d90deb85b465b39b2afe2cb2fc1bcdc2750e4dc5d77ae5e1e9ce6fc8ffd9885d762edfbb484f41fcc58ee394a6aafc942fff00c3825d9fb04bcf0343b9ae635a515f39f9612327d248ef6f2ecd85996b7b0f721ce7e5c1dd0fc014ef235286c2aff023810775b774ac20400ab64105467c60454bed2f7bedaf4098a42f6813d4a5d0bc73bba3fd2acaf125ab6add5a439dd145f8f6e57375c4815e4e46ce8a5b6a71693cb7a1e26e46a1b6cd5da435e07381f973eca29d9c3b628b339db7386e11132329f6e0d9fe41e34c56953bed65f983b6f4a3eeab0161340937fa46bc735c9418cde3fce859117429a52ab617a309a44b8a5401bc1595b485c4496fd6385a853e96c081128fd335440ba390b23a97556b6187808cd29c257414d32ec44bb3a5c2d5625214a3636630c3d343cc7bd62663f42c51dbb98d86b57253654e6f3c26db8beb06b2c6e1c6e369287983814dc6f80bad5e3ae2f7d76057bd04447fce77772220deaeef27b77d5cf170a819dbc7ad427eb752986a57bb4c308738959637ce048f48bd76eaf"
var hllSet = hll.fromHexString(hllHexString).hllSet;
hllSet.cardinality()

Returning 89. Not bad! Note that it’s a probabilistic model and that there is always a low error rate involved. The difference here can be explained by a conversion from explicit to probabilistic mode.

Explicit vs. probablistic

As jdmaturen pointed out in this issue, hll-js is converting the explicit model to a probabilistic one. This means slightly inaccurate values (+-1) for low values <250 but isn’t noteworthy for bigger values >250. The provided example illustrates it well:

1
2
3
4
5
var hllSet = hll.fromHexString("\\x128b7faaebcf97601e5541533f6046eb7f610e").hllSet; // returns 2 in postgres-hll
hllSet.cardinality();
// 3
hllSet.toHexString();
// "/x148b000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000060000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000080000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"

So let’s try with a bigger hexstring:

1
'/x138b7f010101c101e3024104e1058305a105c3072207810922098209a209c30b220c410ce20e210e410e610ee11002106310a210e31323138513a213c2142114421463156115a115e416011661168316a216e1186218a31927194119611aa81b411b611be11c411d431dc21e22218121a121e122a322e12324236123c224c12641266127c3288329442a012a612b012be22cc52d412e612e812fa12fc1302131843282338133e335023541356235a23623364138233863388139813a023a623a823d033d413e613ea13f4140a1414141e242014322438143a24406458145a145e546e14721474248014822486249214a234ae14b414b614be34ca24cc14d424d614da14e214fa250225101514552e453215423548154c355c1564558e3590359415b215b415d625da25f225f836122614162426422648164a16681672367c168016822686168a169216943698169c56b426b816d016e616ee16f416fc17102718471e17326742474e177027742776277e2782378a27901794179817a027a617aa17b217b817c627ce57d817dc47e837ee3800280848181826582a382c1832584e18502854285628607864187e5880188618883898289e28a248a438aa18ac18ae28b028b218b818ca28e028ea58f278fe4904190e192c192e1932193e2940194e2958395c2962296a496e198229923994499e19a619aa59ae39be29ce29e219e419ee49f039f219f63a001a041a181a1c2a202a241a341a462a483a4e3a501a564a5c1a622a6e1a801a867a941a981aaa3aae1ab24abe1ac01acc2ad62ae01ae21afc1b001b082b0a2b103b182b1e2b2a2b2e2b321b3a2b541b581b5e4b6e1b7e1b804b821b922ba21ba41ba83bbe3bc41bc82be04bec3bf01c021c0a2c204c262c2e1c3c1c542c681c782c861c8a1c923ca21cac1cf61d042d0a2d1a2d222d3e1d5a1d5e2d681d6e2d741d7e1d822d961d9c2da03da61da81db42db63db81dc01dd27dd44dde3de22dea1dec4df69dfe1e043e082e162e281e301e321e3c7e521e562e5a2e6a8e6c4e721e742e764e782e821e8e1e925ea45eac2eb81eba5ecc1ece4edc2ede2ee02eea1eec3eee1ef83efa1f082f0a7f121f1c1f2c3f3c2f405f464f501f521f642f661f682f6a3f724f781f8e1f924f981f9a1fa01fbe1fc03fc41fcc2fdc2fe81fea1ffc3ffe1'

This will return 472.556945513764 in Postgres (double precision) and 473 in javascript. Perfect!

Talking to each other

Well thats the core principle already. Now one can simply pass hexstrings around, intersect them or perform unions.

For example, let’s say you want to enable users to query something in your frontend but would prefer less server workload. In this case you could just pass your hexstrings directly to the frontend and let the user’s browser perform unions. Actually, Js-hll is quite performant as well, so you don’t need to worry about high browser workloads. When the user performed a union, s/he can just pass it back to the postgres backend as a hexstring and save it as-is!

There might be plenty of cases where this probably wouldn’t make much sense as even for postgres unions are little workload. However, as in my particular case, I had a nice leaflet package I wanted to use, performing many geometric on-the-fly unions at once to calculate hexbins radiuses and colors where it was just the most convenient way avoiding complicated on:zoom logic and asynchronous requests.

Js-hll unions

Javascript hyperLogLog unions are straight forward:

1
hllSet1.union(hllSet2)

Batch unions with js-hll

With js-hll you can only union two sets at a time. So if you run into the same situation like me where you need to quickly union up to a couple of thousand at once, there is a quick one-liner to do so. The below function reduces the arry and iteratively unions the first with the second element.

1
2
3
hll_array = [hllSet1,hllSet2, hllSet3]
var hllSet = hll_array.reduce(function (first, second) { return first.union(second)});
hllSet.cardinality()

A real working example could look like this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
var hllSet1 = hll.fromHexString("/x138b7f010101c101e3024104e1058305a105c3072207810922098209a209c30b220c410ce20e210e410e610ee11002106310a210e31323138513a213c2142114421463156115a115e416011661168316a216e1186218a31927194119611aa81b411b611be11c411d431dc21e22218121a121e122a322e12324236123c224c12641266127c3288329442a012a612b012be22cc52d412e612e812fa12fc1302131843282338133e335023541356235a23623364138233863388139813a023a623a823d033d413e613ea13f4140a1414141e242014322438143a24406458145a145e546e14721474248014822486249214a234ae14b414b614be34ca24cc14d424d614da14e214fa250225101514552e453215423548154c355c1564558e3590359415b215b415d625da25f225f836122614162426422648164a16681672367c168016822686168a169216943698169c56b426b816d016e616ee16f416fc17102718471e17326742474e177027742776277e2782378a27901794179817a027a617aa17b217b817c627ce57d817dc47e837ee3800280848181826582a382c1832584e18502854285628607864187e5880188618883898289e28a248a438aa18ac18ae28b028b218b818ca28e028ea58f278fe4904190e192c192e1932193e2940194e2958395c2962296a496e198229923994499e19a619aa59ae39be29ce29e219e419ee49f039f219f63a001a041a181a1c2a202a241a341a462a483a4e3a501a564a5c1a622a6e1a801a867a941a981aaa3aae1ab24abe1ac01acc2ad62ae01ae21afc1b001b082b0a2b103b182b1e2b2a2b2e2b321b3a2b541b581b5e4b6e1b7e1b804b821b922ba21ba41ba83bbe3bc41bc82be04bec3bf01c021c0a2c204c262c2e1c3c1c542c681c782c861c8a1c923ca21cac1cf61d042d0a2d1a2d222d3e1d5a1d5e2d681d6e2d741d7e1d822d961d9c2da03da61da81db42db63db81dc01dd27dd44dde3de22dea1dec4df69dfe1e043e082e162e281e301e321e3c7e521e562e5a2e6a8e6c4e721e742e764e782e821e8e1e925ea45eac2eb81eba5ecc1ece4edc2ede2ee02eea1eec3eee1ef83efa1f082f0a7f121f1c1f2c3f3c2f405f464f501f521f642f661f682f6a3f724f781f8e1f924f981f9a1fa01fbe1fc03fc41fcc2fdc2fe81fea1ffc3ffe1").hllSet;

var hllSet2 = 
hll.fromHexString("/x128b7f94c64fc29302fedb95064f4594429faea211348181b84bf6a4de1a560e2cde5aae10a82d9b23d04cb37315171da42c7eb634d69b7206eda3b9f61329abd41006c3754ff2b383fe29c5293f8d8dc2dd0ac6e0d283ed4c464ecb1077494c2d63bed629d2966cf0f74ed6d1c433d793c977e7c3ef6d62b062dae87c30eb549046fbed1a115578bfd959f7defd537345d9dc02d1bcbb389f666a036c085757a5147d0bde87fd03cfff7c0c2f46328f046dc50df9247d5d7c02450e7e599707200bef1993af1b2a2520ce27ae169919eb38aa27e882def7ec080c2846cff817fe669530085d7134cb022b3176150ff4e07b5b339241a82324a9d54dbf805d46768d8955167824ea33a3fe55daffbb24f17f5a58c22d17fbba79b05aa808f534be42765f7e8940497ef0c0601e98e71202a33e6fa844e45f16e3f97ad2759531cfe48d7cb25be453a9c8b0").hllSet;

var hllSet3 = 
hll.fromHexString("/x128b7f8592206f9f19e59c8fd86aefaa33159392aa0e34f0ec18369fe0b373f4f8fb0ea160a594697af83ca209824fdf11dc96a2691b9bdb7a5d68b27eec512b56e437b5a25cb801028cc2b708aa8ad616ef9db8ec683405749d5cbf1cb31e793ca24cc39099abfbdefae9c3b77288c737593bc5e8fbd70be21d25cbecf5f3fc316718ccc47bada8f1a802d0ecb268db22971edd5556b6ef9c83b3deb153736583554efa9f8831cd825d37fbaa507b619aa7f8fcd9e3c86352460202568446a3b4e7ab0baed2436665893018a5739a57a4afe81b57440b7edbb2801c9b4f2bb609d6291d2a2f4022fdf5b9228fe694968e225b232cb3ef34aa283929b266e071ff51d32cd41d8079ca04032f58fb7330727f962ff990b545c1aa3e341c639ae719f1fb392c8bdaf8e352b63eaa1a73ec6d0878407f68d908e2138840a56c50cb1d62db4adfed6510fd513a4f2e41693e7f609258fa6eb4cca8c8fa5c4637c28a62b27b5dec7b773dbc1d0560c2eafcc1e091236bde80216b9972156f4f9d7bda221f0e7b53f009355d4be47ccca7e798abb1267e1fda106584187a").hllSet;

hll_array = [hllSet1,hllSet2, hllSet3]
var hllSet = hll_array.reduce(function (first, second) { return first.union(second)});
hllSet.cardinality()
// 567

Working with hexstring arrays

However, most likely you won’t deal with a list of hllSets as data is passed via hexstrings. So you will have an array of hexstrings instead you first need to convert to hllSets.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
hex_array = ["/x138b7f010101c101e3024104e1058305a105c3072207810922098209a209c30b220c410ce20e210e410e610ee11002106310a210e31323138513a213c2142114421463156115a115e416011661168316a216e1186218a31927194119611aa81b411b611be11c411d431dc21e22218121a121e122a322e12324236123c224c12641266127c3288329442a012a612b012be22cc52d412e612e812fa12fc1302131843282338133e335023541356235a23623364138233863388139813a023a623a823d033d413e613ea13f4140a1414141e242014322438143a24406458145a145e546e14721474248014822486249214a234ae14b414b614be34ca24cc14d424d614da14e214fa250225101514552e453215423548154c355c1564558e3590359415b215b415d625da25f225f836122614162426422648164a16681672367c168016822686168a169216943698169c56b426b816d016e616ee16f416fc17102718471e17326742474e177027742776277e2782378a27901794179817a027a617aa17b217b817c627ce57d817dc47e837ee3800280848181826582a382c1832584e18502854285628607864187e5880188618883898289e28a248a438aa18ac18ae28b028b218b818ca28e028ea58f278fe4904190e192c192e1932193e2940194e2958395c2962296a496e198229923994499e19a619aa59ae39be29ce29e219e419ee49f039f219f63a001a041a181a1c2a202a241a341a462a483a4e3a501a564a5c1a622a6e1a801a867a941a981aaa3aae1ab24abe1ac01acc2ad62ae01ae21afc1b001b082b0a2b103b182b1e2b2a2b2e2b321b3a2b541b581b5e4b6e1b7e1b804b821b922ba21ba41ba83bbe3bc41bc82be04bec3bf01c021c0a2c204c262c2e1c3c1c542c681c782c861c8a1c923ca21cac1cf61d042d0a2d1a2d222d3e1d5a1d5e2d681d6e2d741d7e1d822d961d9c2da03da61da81db42db63db81dc01dd27dd44dde3de22dea1dec4df69dfe1e043e082e162e281e301e321e3c7e521e562e5a2e6a8e6c4e721e742e764e782e821e8e1e925ea45eac2eb81eba5ecc1ece4edc2ede2ee02eea1eec3eee1ef83efa1f082f0a7f121f1c1f2c3f3c2f405f464f501f521f642f661f682f6a3f724f781f8e1f924f981f9a1fa01fbe1fc03fc41fcc2fdc2fe81fea1ffc3ffe1",
"/x128b7f94c64fc29302fedb95064f4594429faea211348181b84bf6a4de1a560e2cde5aae10a82d9b23d04cb37315171da42c7eb634d69b7206eda3b9f61329abd41006c3754ff2b383fe29c5293f8d8dc2dd0ac6e0d283ed4c464ecb1077494c2d63bed629d2966cf0f74ed6d1c433d793c977e7c3ef6d62b062dae87c30eb549046fbed1a115578bfd959f7defd537345d9dc02d1bcbb389f666a036c085757a5147d0bde87fd03cfff7c0c2f46328f046dc50df9247d5d7c02450e7e599707200bef1993af1b2a2520ce27ae169919eb38aa27e882def7ec080c2846cff817fe669530085d7134cb022b3176150ff4e07b5b339241a82324a9d54dbf805d46768d8955167824ea33a3fe55daffbb24f17f5a58c22d17fbba79b05aa808f534be42765f7e8940497ef0c0601e98e71202a33e6fa844e45f16e3f97ad2759531cfe48d7cb25be453a9c8b0",
"/x128b7f8592206f9f19e59c8fd86aefaa33159392aa0e34f0ec18369fe0b373f4f8fb0ea160a594697af83ca209824fdf11dc96a2691b9bdb7a5d68b27eec512b56e437b5a25cb801028cc2b708aa8ad616ef9db8ec683405749d5cbf1cb31e793ca24cc39099abfbdefae9c3b77288c737593bc5e8fbd70be21d25cbecf5f3fc316718ccc47bada8f1a802d0ecb268db22971edd5556b6ef9c83b3deb153736583554efa9f8831cd825d37fbaa507b619aa7f8fcd9e3c86352460202568446a3b4e7ab0baed2436665893018a5739a57a4afe81b57440b7edbb2801c9b4f2bb609d6291d2a2f4022fdf5b9228fe694968e225b232cb3ef34aa283929b266e071ff51d32cd41d8079ca04032f58fb7330727f962ff990b545c1aa3e341c639ae719f1fb392c8bdaf8e352b63eaa1a73ec6d0878407f68d908e2138840a56c50cb1d62db4adfed6510fd513a4f2e41693e7f609258fa6eb4cca8c8fa5c4637c28a62b27b5dec7b773dbc1d0560c2eafcc1e091236bde80216b9972156f4f9d7bda221f0e7b53f009355d4be47ccca7e798abb1267e1fda106584187a"]

hex_array.reduce(function (first, second) {
   return first.union(
     hll.fromHexString(
       second.replace(/\\\\/g,"/"))
       .hllSet)}, new hll.HLL(11, 5)
    ).cardinality();
// 567

The new hllSet on the very right needs to have the same specs at postgres-hll, i.e. new hll.HLL(11/log2m/, 5/registerWidth/). Also note that in postgres-hll the strings will come with a backslash in the beginning like \x128b7f859.... When passing this string to javascript, it gets escaped (\ -> \\), but is not handled well, so we need to replace it with a normal slash to make it work smoothly.

If you want to export the respective hexstring instead of estimating the cardinality, simply pass the hllSet to the hexstring function instead.

1
2
3
4
5
6
hex_array.reduce(function (first, second) {
   return first.union(
     hll.fromHexString(
       second.replace(/\\\\/g,"/"))
       .hllSet)}, new hll.HLL(11, 5)
    ).toHexString();

It will return the hexstring, ready to be received by postgres!

1
'/x148b00000200004008000080230002000000000000000000000000010000018460000000002000800080000000000000008001086000000000000080000000000200000200000000000042100001080200000010003008030000000000000600000000c002884000443000000002100404080011880100000000001000200c0001c2100060000000200000021000010002000000000600004000800000000002000000000000000000000084010000000c0101001000400000200040000000000008021000000004100060000001800000080000000800100000084000000200000000a000020000000000108001000000042000400000000000020000000001000000000080030000000000100220080008c2000000000000000000c03080000000008000100021040000000080000000000000180200000000001004000002200000000000040000020000020800000800008000880030000000000000608405000000000100440000200880202000004001800000c0000001000230000300000008200004100400004000008000002008001080000000080a0000000000000004004000000000c00080600000000020000a000040000000000000000000031802000000000000000000463000000000000000004020080000000000000080018000000000000000820000200004000000000000000000800084000000000000000000800000c0000060088010040000460080a00000000000000410800000000000000800000000000010000100020000200000000000100002000100000000000180000000010000000100000000000000500000100420006200c000080008020080001000100400004000800000002080050000008081000001802300c0000060100072000000000080000000500c2001400000000000000001100420000038020000030000000005080011800000000100020106000422104000800000000008000000000000100000140001c000082400020000010000000c00000000002100400000020800000002000001804000800010010000000000008200000000c800000100001014030000000002000000000200000000000042000004184030000008020004000002008040100200000000020000000000218403080040002000800000010000000000080070000000020080400000000c0101000080010800000040080020000008400000000000000020080001080018400100020000200802004001880000001000000002008004000000000100800000012040000400008000000000420180000000000003000201000000000000002000000060080000000000480008000000000000200020000100000000200000000000008400000000000080000000010000000010040000c0000080004000002000020000000000000000000600000000000000000000100000000400080000000008000080000c00000000000100000000000000000402000000800200020000010080000000000010004018001080000004308000080000000001c80000030080000480000090000100060100000000200020000000800018400000e0000000000000402008000000002080004441000000400000010140000040000a000040000200940000000000240000000042100000046100000184000000011c00004000002000000000600000000440280040000008403000200004110c00010000800000000000010100008400080000000000000000011802000040080000004000000084001800000061'

Let’s test it in postgres et voilà!

1
2
select  hll_cardinality('\x148b00000200004008000080230002000000000000000000000000010000018460000000002000800080000000000000008001086000000000000080000000000200000200000000000042100001080200000010003008030000000000000600000000c002884000443000000002100404080011880100000000001000200c0001c2100060000000200000021000010002000000000600004000800000000002000000000000000000000084010000000c0101001000400000200040000000000008021000000004100060000001800000080000000800100000084000000200000000a000020000000000108001000000042000400000000000020000000001000000000080030000000000100220080008c2000000000000000000c03080000000008000100021040000000080000000000000180200000000001004000002200000000000040000020000020800000800008000880030000000000000608405000000000100440000200880202000004001800000c0000001000230000300000008200004100400004000008000002008001080000000080a0000000000000004004000000000c00080600000000020000a000040000000000000000000031802000000000000000000463000000000000000004020080000000000000080018000000000000000820000200004000000000000000000800084000000000000000000800000c0000060088010040000460080a00000000000000410800000000000000800000000000010000100020000200000000000100002000100000000000180000000010000000100000000000000500000100420006200c000080008020080001000100400004000800000002080050000008081000001802300c0000060100072000000000080000000500c2001400000000000000001100420000038020000030000000005080011800000000100020106000422104000800000000008000000000000100000140001c000082400020000010000000c00000000002100400000020800000002000001804000800010010000000000008200000000c800000100001014030000000002000000000200000000000042000004184030000008020004000002008040100200000000020000000000218403080040002000800000010000000000080070000000020080400000000c0101000080010800000040080020000008400000000000000020080001080018400100020000200802004001880000001000000002008004000000000100800000012040000400008000000000420180000000000003000201000000000000002000000060080000000000480008000000000000200020000100000000200000000000008400000000000080000000010000000010040000c0000080004000002000020000000000000000000600000000000000000000100000000400080000000008000080000c00000000000100000000000000000402000000800200020000010080000000000010004018001080000004308000080000000001c80000030080000480000090000100060100000000200020000000800018400000e0000000000000402008000000002080004441000000400000010140000040000a000040000200940000000000240000000042100000046100000184000000011c00004000002000000000600000000440280040000008403000200004110c00010000800000000000010100008400080000000000000000011802000040080000004000000084001800000061')
--567

Read in my next post how to effectively use js-hll for on-the-fly unions in combination with leaflet-hexbins in a real-world application!

Contents