An Introduction to HyperLogLog
Have you ever wondered how HyperLogLog works? Or have you never heard of it at all? In this post I explain the wonderful algorithm of Flajolet et al. from scratch and in a very simple manner.
Tag: hll-union
Using HyperLogLog with Leaflet-Hexbins
Leaflet-Hexbins is a powerful tool to aggregate data and visualize it quickly on a map. It can size the hexbin radius based on a feature values. But what if we used HyperLogLog data to preserve user-privacy? This post will provide a convenient way to quickly perform on-the-fly HyperLogLog unions for leaflet-hexbins. No more backend-constraint for HyperLogLog There are many HyperLogLog implementations out there but few work as well as postgres-hll and js-hll. They can even talk to each other by exchanging hexstrings! Usually postgres-hll is pretty much the standard extension to use, when dealing with HyperLogLog but is obviously bound to a postgres database running somewhere. With js-hll, the backend-constraint for HyperLogLog is gone, just so that users can perform any HyperLogLog action in their frontend!
HyperLogLog Javascript (js-hll) & Postgres (postgres-hll): making them talk to each other!
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.
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
