<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Utkarsh Upendra on Medium]]></title>
        <description><![CDATA[Stories by Utkarsh Upendra on Medium]]></description>
        <link>https://medium.com/@utkarsh-upendra?source=rss-e7f90322fdba------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*9Vc01KOe_yFcpaFRll-K_g.png</url>
            <title>Stories by Utkarsh Upendra on Medium</title>
            <link>https://medium.com/@utkarsh-upendra?source=rss-e7f90322fdba------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 05:58:51 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@utkarsh-upendra/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[System Design of a hotel reservation system — Part 3]]></title>
            <link>https://blog.stackademic.com/system-design-of-a-hotel-reservation-system-part-3-1f34e86f372b?source=rss-e7f90322fdba------2</link>
            <guid isPermaLink="false">https://medium.com/p/1f34e86f372b</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[microservices]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[cassandra]]></category>
            <category><![CDATA[software-architecture]]></category>
            <dc:creator><![CDATA[Utkarsh Upendra]]></dc:creator>
            <pubDate>Tue, 12 Sep 2023 06:45:40 GMT</pubDate>
            <atom:updated>2023-09-13T08:09:37.363Z</atom:updated>
            <content:encoded><![CDATA[<h3>System Design of a Hotel Reservation System — Part 3</h3><p>In the earlier parts, we have covered the design of the hotel side of the marketplace as well as how the customers can search for hotels.</p><p><a href="https://medium.com/@utkarsh-upendra/system-design-of-a-hotel-reservation-system-part-1-99ab8abb89dd">System Design of a hotel reservation system — Part 1</a></p><p><a href="https://medium.com/@utkarsh-upendra/system-design-of-a-hotel-reservation-system-part-2-7d0a1b06bbff">System Design of a hotel reservation system — Part 2</a></p><p>In this post, we will look at the design to support bookings for hotels by customers. Since the bookings will be larger in number and also more frequent, we can expect a higher traffic to this flow.</p><p>Let’s assume we expect 100 million monthly active customers globally, and on an average 50 million customers book hotel stays every month. This implies that we will get at least 50 million booking requests every month. Breaking it further down, we can expect around 2 million booking requests per day which translates to ~1400 requests per second on an average. Taking into account the peak bursts, we will need to design our system to handle at least 3x of this load, which means we can expect the peak traffic to be around ~5000 requests per second.</p><p>Lets look at the query patterns of the booking data. The booking data will need to be queried as a part of the following flows:</p><ol><li>User can see a list of past, current and/or future bookings</li><li>User can modify a booking</li><li>User can cancel a booking</li><li>Hotel can see a list of their bookings</li><li>Hotel can accept/reject a booking</li><li>Platform admins and analysts can see a list of bookings</li></ol><p>The above flows can be classified into the following categories:</p><ol><li>User flows — 1,2,3</li><li>Hotel flows — 4,5</li><li>Analytical flows — 6</li></ol><p>To ensure that we maintain the principle of segregation of responsibilities, we will create separate sub systems for each of the above categories.</p><p>Let’s look at the user flows now. The 3 flows that we have listed above will need the queries to be made wither by the user ID or the booking ID. Since our queries need to be just made on the 2 keys above, and because we want our system to scale over 5000 requests per second, we can consider using a NoSQL database like Cassandra. Cassandra with its distributed master-master architecture would allow us to scale to the required load and also help us maintain the schema that we need as its a columnar database.</p><p>We can use UserID as the primary key (or the partition key) and have the booking ID as the clustering key. This way, we will be able to efficiently run queries and updates on the user booking data. We can visualise a user booking record in Cassandra as follows:</p><pre>{<br>  &quot;user_id&quot;: &quot;user-uuid&quot;,<br>  &quot;booking_id&quot;: &quot;booking-uuid&quot;,<br>  &quot;start_date&quot;: &quot;10-10-2023&quot;,<br>  &quot;end_date&quot;: &quot;15-10-2023&quot;,<br>  &quot;hotel_id&quot;: &quot;hotel-uuid&quot;,<br>  &quot;room_type&quot;: &quot;DELUXE&quot;<br>  &quot;status&quot;: &quot;CREATED&quot;,<br>  &quot;payment_id&quot;: &quot;payment-uuid&quot;<br>}</pre><p>Lets look at the booking flow now. The user journey will look like this:</p><ol><li>User logs in to the app/website</li><li>User enters the location, dates and other preference</li><li>The app shows the user a list of hotels that are available on the given dates and match other preferences</li><li>User selects a hotel and chooses the room type</li><li>User makes the payment</li><li>Booking is confirmed</li></ol><p>In order to support this journey, the component diagram would look like the following:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/877/1*jyfW5eJwawX-8QnzfTdGog.png" /></figure><p>Here we have 5 micro-services:</p><ol><li>hotel-availability-service: This service takes the requested dates and a list of hotels and filters out the hotels that aren’t available on the given dates.</li><li>hotel-search-service: This was described in Part 2. This service takes the location or the search query and returns a list of hotels.</li><li>hotel-reviews-service: This service takes a list of hotels and returns the details of the ratings for those hotels.</li><li>booking-service: As the name suggests and as explained above, this will be backed by a Cassandra cluster and enable creating reservations.</li><li>payment-service: This service manages the payments for a requested reservation.</li></ol><p>In addition to the 5 microservices listed above, we also have an orchestration service which acts as a layer of abstraction over the above microservices. The orchestration service first queries the hotel-search-service to get a list of hotels relevant to the search term, it then passes this list of hotels to the requests to both hotel-availability-service and hotel-reviews-service in parallel in order to finally collate a list of hotels that are available on the given dates, tagged with their ratings.</p><p>The orchestration service sits behind an API gateway which acts as a reverse proxy for the server. Also, all the bookings that are created or modified are also published to the “bookings” topic.</p><p>We will cover in detail how the availability and review services will work in future posts.</p><p>At this point, we have a system that allows hotels to onboard into the platform and create their offering, and the users to search for hotels in a location and create bookings. In the next part, we will look at how the availability service would be designed to serve the use cases that we have defined in this series of posts. Thanks for reading!</p><h3>Stackademic</h3><p><em>Thank you for reading until the end. Before you go:</em></p><ul><li><em>Please consider </em><strong><em>clapping</em></strong><em> and </em><strong><em>following</em></strong><em> the writer! 👏</em></li><li><em>Follow us on </em><a href="https://twitter.com/stackademichq"><strong><em>Twitter(X)</em></strong></a><em>, </em><a href="https://www.linkedin.com/company/stackademic"><strong><em>LinkedIn</em></strong></a><em>, and </em><a href="https://www.youtube.com/c/stackademic"><strong><em>YouTube</em></strong></a><strong><em>.</em></strong></li><li><em>Visit </em><a href="http://stackademic.com/"><strong><em>Stackademic.com</em></strong></a><em> to find out more about how we are democratizing free programming education around the world.</em></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1f34e86f372b" width="1" height="1" alt=""><hr><p><a href="https://blog.stackademic.com/system-design-of-a-hotel-reservation-system-part-3-1f34e86f372b">System Design of a hotel reservation system — Part 3</a> was originally published in <a href="https://blog.stackademic.com/">Stackademic</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[System Design of a hotel reservation system — Part 2]]></title>
            <link>https://blog.devops.dev/system-design-of-a-hotel-reservation-system-part-2-7d0a1b06bbff?source=rss-e7f90322fdba------2</link>
            <guid isPermaLink="false">https://medium.com/p/7d0a1b06bbff</guid>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[elasticsearch]]></category>
            <category><![CDATA[microservices]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[software-architecture]]></category>
            <dc:creator><![CDATA[Utkarsh Upendra]]></dc:creator>
            <pubDate>Thu, 07 Sep 2023 11:38:02 GMT</pubDate>
            <atom:updated>2023-09-13T16:55:38.267Z</atom:updated>
            <content:encoded><![CDATA[<h3>System Design of a hotel reservation system — Part 2</h3><p>In Part 1, we described the system and the data model for the hotel side of the marketplace. If you haven’t read that already, I would highly recommend you do. The link to Part 1 is <a href="https://medium.com/@utkarsh-upendra/system-design-of-a-hotel-reservation-system-part-1-99ab8abb89dd">here</a>.</p><p><a href="https://medium.com/@utkarsh-upendra/system-design-of-a-hotel-reservation-system-part-1-99ab8abb89dd">System Design of a hotel reservation system — Part 1</a></p><p><a href="https://utkarsh-upendra.medium.com/system-design-of-a-hotel-reservation-system-part-3-1f34e86f372b">System Design of a hotel reservation system — Part 3</a></p><p>Coming to the customer side of the marketplace, the primary functional requirements which we also described in Part 1, are as follows:</p><ol><li>Search for hotels in a city/geo-location</li><li>See details of the hotel (room types, charges, availability)</li><li>Create a reservation</li><li>Cancel a reservation</li></ol><p>Let’s start with the first requirement i.e. the customers must be able to search for a hotel based on a city or geo-location. To enable this, we can use a search engine like Elasticsearch. With elasticsearch, we can make fuzzy queries. Additionally, we can also train a NLP model or use the default model to enable semantic search. We can also run geo_distance queries with elasticsearch. The data will flow into elasticsearch from the “hotels” topic described in Part 1. We can have a lambda (serverless function) that consumes messages from “hotels” topic and adds/updates records in elasticsearch index. Adding elasticsearch to our component diagram, it now looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/991/1*XtZaR0SIMKgPwxE50JqFtQ.png" /></figure><p>The elasticsearch index will store the hotel details as a composite object document, something like:</p><pre>{<br>  &quot;name&quot;: &quot;ABC&quot;,<br>  &quot;address&quot;: &quot;DEF&quot;,<br>  .<br>  .<br>  .<br>  &quot;contact&quot;: [<br>    {<br>      &quot;type&quot;: &quot;PHONE&quot;,<br>      &quot;value&quot;: &quot;9876543210&quot;<br>    }<br>  ],<br>  &quot;images&quot;: [<br>    &quot;ImageURL1&quot;,<br>    &quot;ImageURL2&quot;<br>  ],<br>  &quot;tags&quot;: [<br>    &quot;5 star&quot;,<br>    &quot;near airport&quot;,<br>    &quot;hygienic&quot;<br>  ]<br>}</pre><p>Now that we have our data ready to be searched, we need a service that exposes the search endpoint. So let’s now get into the client for the customers.</p><p>Customers can access the platform either via website or mobile app. We can have a service called hotel-search-service which internally queries the elasticsearch index based on the customer input.</p><p>With the new customer-search-service, our component diagram now looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/991/1*rqXIdpAlCxAfgSaYMz-gAQ.png" /></figure><p>The customer can enter his/her choice of city and this system in its current state will return a list of hotels with all the required details and image URLs. The clients can then make a call to CDN to download the images to be shown to the customers.</p><p>At this point, we have a system that serves as a hotel directory. We will build further on top of this to get a fully working reservation system ready, in the next post. Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7d0a1b06bbff" width="1" height="1" alt=""><hr><p><a href="https://blog.devops.dev/system-design-of-a-hotel-reservation-system-part-2-7d0a1b06bbff">System Design of a hotel reservation system — Part 2</a> was originally published in <a href="https://blog.devops.dev/">DevOps.dev</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[System Design of a hotel reservation system — Part 1]]></title>
            <link>https://utkarsh-upendra.medium.com/system-design-of-a-hotel-reservation-system-part-1-99ab8abb89dd?source=rss-e7f90322fdba------2</link>
            <guid isPermaLink="false">https://medium.com/p/99ab8abb89dd</guid>
            <category><![CDATA[software-architecture]]></category>
            <category><![CDATA[microservices]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[database]]></category>
            <dc:creator><![CDATA[Utkarsh Upendra]]></dc:creator>
            <pubDate>Wed, 06 Sep 2023 21:47:15 GMT</pubDate>
            <atom:updated>2024-07-30T04:33:17.203Z</atom:updated>
            <content:encoded><![CDATA[<h3>System Design of a hotel reservation system — Part 1</h3><p>Hotel reservation systems are one of the most discussed <a href="https://cz5h404.na1.hs-sales-engage.com/Ctc/RG+23284/cz5H404/JlFbTjqZW8wNnMl6lZ3pqW58PJhL2dRCB0W4J7lwc5zJqF9W8LwQhd6FgsrlW8v2SHW1ty5l-W2BsK9F9bnw7tW2gGNbF8nj17tN7wwXNBBTXTxW19fJvk3PZTxsW8RPzj379Mq2nV21-wf1p81gmW1FMgTz6jPSkGW7yKxp94KmL3VW5-78KT7MzTTKW6_3L-626mxTXW201Mjj3m7-HsVBShRv5TYK0vW74yDyG4cbG_MVjTlJZ3yc_qxW5Vhsq472HSgsW7QvTbr3k2MQlW6mct2z233QZ2W2xjKdt4hSRnNN9kz157jYGv0N1hPXLN13GlnW9ccMJy2Qd6wyW1Wy_DZ6xfJQrW4mZ8Y85xdvRGW13wdGg9fWlzKW1q0GVG5QTT07N5h-KFNybRqfW7F4TFn4ny7R8W95yXvg6tmxR0W1Q8hYd36gmHdW4w8Nxg2sMFxBW1ZqNw59219KfW1cgrTR3fCKbgW1-_BbS2WNH57W1kbD0b1vxFpvW2QRT038jLF_SN5KZ4LgM0wjgW4G5ls26lqNxJW369hv_6w9X5jW6w0cMv7sgKb8W6-wf1Q58LNQNW1M-ztG6q-08rW16tKBG399KdgMLCgHP27kgKW2cJVw59czBl0N4CmkfJ1f6qKW4gJqg04R8mN8W8Yth8G8gw-hTW9g0NDY5W5CYNW2Whqd22sxl2HW73jqC15Jn03xW6GrLWs5VgK_lW1RsS5d5XwYx-N4FQXrV3YjsxW3KCqLH2WX3-zW4cRWfB5Yk5ClW4ckYzh9lXYmKVjtN3z7Vt9CdW2SZYGR6V8p_FW3gwBB583KnDSW4mRZ7T2Ngc7nW1PpcwD7LNY6ZW5FkpMs5v0x3hW5_FMQD5SWq_mW6fSs1156D2gTW8Rvbmk93RmSGW7B_1Y51vHMl5W7M4gFn8bTMrhW6s9jJs4V-0_mW72DC8r44rGtGW76h4tn6-PsxRW3hDVMP8WCxlCW5rb7y81KdQLnW77T9Kw1M6PQFW1Zm4rN2Ps_ypW159djK6wnsFcN6VrdMrCb0jzV9yZJQ7nyZZjW9ffJzD87fg6kW1wDmJ12CPZhvW1bqVqn29gcwrV94KdQ1kgxhWW2BmLkr7bhN2xW5dNJ0y5SLZLvW73PbnJ14jDGfW3l8BcM5zBvBVW4V8NLp9jdZKHW88SVdm8PbG0SVhWgtj6vr4VNf6Dsmm204">system design problems in any engineering interview</a>. In this post, we are going to run through the design of a hotel reservation system like MakeMyTrip, Booking.com etc.</p><p>This is a series of posts, the links to each post are:</p><p><a href="https://utkarsh-upendra.medium.com/system-design-of-a-hotel-reservation-system-part-2-7d0a1b06bbff">System Design of a hotel reservation system — Part 2</a></p><p><a href="https://utkarsh-upendra.medium.com/system-design-of-a-hotel-reservation-system-part-3-1f34e86f372b">System Design of a hotel reservation system — Part 3</a></p><p>To begin with, let’s list down the functional requirements. There are 2 sides to the marketplace for which we are building this system. One is the hotel partners and the other is the end customers. On the hotels side, the functional requirements are as follows:</p><ol><li>Onboard a new hotel</li><li>Update details</li><li>Add/update images</li><li>View details</li></ol><p>On the customer side, the list of functional requirements would involve:</p><ol><li>Search for hotels in a city/geo-location</li><li>See details of the hotel (room types, charges, availability)</li><li>Create a reservation</li><li>Cancel a reservation</li></ol><p>Let’s go through the non functional requirements at this stage:</p><ol><li>The system should be highly consistent on the customer side i.e. a booking which has been created and paid for must reflect immediately on the customer’s view</li><li>On the customer’s side, the system should be able to scale to handle a large number of reads. This is because searching and viewing the restaurant details are the actions that exist at the top of the funnel and we should expect maximum traffic to these 2 flows.</li></ol><p>One assumption about the functional requirement that I am making here is that, a customer is not assigned an actual room when a reservation is made. The customer is just reserving a type of room, and the actual room will be allotted when he/she checks in to the hotel. This practical assumption vastly simplifies our data model, which will be described when we model the customer flows.</p><p>Let’s start defining the components of the system now.</p><p>To cater to the functional requirements for the hotel side of the marketplace, we will need one service possibly named as hotel-admin-service, which will expose the following endpoints:</p><ol><li>POST /hotel — This will onboard/create a new hotel on the platform. The request body will contain the hotel metadata in JSON format.</li><li>GET /hotel/&lt;id&gt; — This will return the consolidated details of the hotel. The response body will contain the hotel metadata in JSON format.</li><li>GET /hotel/images/&lt;id&gt; — This will return the list of image URLs for a hotel ID</li><li>PUT /hotel/&lt;id&gt; — This will update the hotel meta data. The request body will contain the hotel metadata in JSON format.</li><li>PUT /hotel/images — This will add/update the images. The request body will contain a list of image update requests, which an be modelled as follows:</li></ol><pre>[<br>  {<br>    imageURL: &quot;image-url&quot;,<br>    opType: &quot;ADD&quot;,<br>  },<br>  {<br>    imageURL: &quot;image-url-2&quot;,<br>    opType: &quot;DELETE&quot;,<br>  }<br>]</pre><p>Coming to the database considerations, we could model the data as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/921/1*lA-ijVbTmJI8TZgKRMaI-w.png" /></figure><p>Here, the columns marked as red are primary keys.</p><p>Some points to consider:</p><ol><li>A hotel can have multiple room types, and each room type can have multiple facilities. Each room type has an attribute called max_num which represents the total number of rooms of that type in a hotel.</li><li>A hotel can upload multiple images to be presented to the customer</li><li>A hotel can have multiple tags which can be used during search.</li><li>A hotel can have multiple contact options like email, phone etc. which are stored in hotel_contact table.</li></ol><p>The reason behind going for a relational database in this case is because of the following:</p><ol><li>We can ensure the integrity of data with a relational database using the system and user defined constraints.</li><li>NoSQL databases favour availability over consistency and are generally preferred in case of massive throughputs. We are dealing with a relatively lower scale here (on the hotel side of the marketplace) and hence relational databases should be able to sufficiently scale to handle this workload.</li><li>Using a relational database allows us to extend the system to be used in extended use case. For example, if the company wants to build an internal admin tool which lists all the hotels and lets admin filter and sort on the hotels, we could easily build that with the data model above. However, in case of non relational databases, the query patterns drive the data model.</li></ol><p>We can also set up read replicas for our database.</p><p>The high level component diagram on the hotel side of the system will look like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/741/1*pBBVvLWyyJhY-b57KdoVBw.png" /></figure><p>Here, we have a micro-service called hotel-admin-service that has been described above. It sits behind a load balancer which routes the requests to the containers of the service. On every add or update, the hotel-admin-service publishes a message to the hotels topic on kafka. We will delve more into the consumption off of this topic while working out the customer side of the system. The images that are uploaded to the service are uploaded to the CDN and the reference to the images are stored in the `hotel_images` table that was described in the data model above.</p><p>Having the images uploaded to CDN will massively simplify their rendering on the client side, as the clients can download the images from the nearest CDN server and the service itself is abstracted from maintaining the images.</p><p>For the sake of simplicity, the above design doesn’t consider any flows related to payments to hotels or commissions. But our data model is extendable to support these use cases too.</p><p>This wraps up the hotel side of our system. We will delve into the customer side of the system in the next post. Thanks for reading.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=99ab8abb89dd" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Image Recommendation with Approximate KNN using Collaborative Filtering with ANNoy!]]></title>
            <link>https://utkarsh-upendra.medium.com/image-recommendation-with-approximate-knn-using-collaborative-filtering-with-annoy-b2420d4b30b9?source=rss-e7f90322fdba------2</link>
            <guid isPermaLink="false">https://medium.com/p/b2420d4b30b9</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[spotify]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[collaborative-filtering]]></category>
            <category><![CDATA[knn]]></category>
            <dc:creator><![CDATA[Utkarsh Upendra]]></dc:creator>
            <pubDate>Fri, 28 Jan 2022 18:05:51 GMT</pubDate>
            <atom:updated>2022-02-02T07:19:49.498Z</atom:updated>
            <content:encoded><![CDATA[<p>I was recently working on an image recommendation engine which was to be based on a dataset that contains details of interaction of users with images i.e. which users “liked” a particular image. I have described about a Vanilla approach to this <a href="https://medium.com/@utkarsh.upendra/a-vanilla-implementation-of-collaborative-filtering-for-image-recommendation-system-804ebc6f3b3d">in this post</a>. In this article, I am going to discuss about how Approximate KNN works with ANNoy.</p><p>ANNoy is a python library created by folks at Spotify that provides abstraction over core ANN implementation. The basic idea behind ANNoy or any other Approximate Nearest Neighbors is to index the training data points in a form that they are efficiently searchable. For example, in case of ANNoy makes use of random projections to create hyperplanes which are used to determine a region where one or more points exist. Search only needs to be performed within this region. To understand more about how ANN works, <a href="https://towardsdatascience.com/comprehensive-guide-to-approximate-nearest-neighbors-algorithms-8b94f057d6b6">follow this link</a>.</p><p>Coming to the implementation, the first step was to re-arrange our data in a form that was easy to process.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b62a41562a99853f43e7e00ff7656b46/href">https://medium.com/media/b62a41562a99853f43e7e00ff7656b46/href</a></iframe><p>In the above code snippet, the input file is first read and the image identifiers are collected by grouping based on user_id. This prepares data in the following form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/502/1*tsyAO5dkctSMqCTP2XG9UA.png" /></figure><p>In addition to this, we have collected a couple more variables:</p><ul><li>item_id_set: This is a set of all the unique item_id values. We will use this to prepare vectors in the next step</li><li>backup_df: As the name suggests, this is supposed to act as a backup of our source data</li></ul><p>It’s also noteworthy that we have limited the number of users-item combination to 2000 to keep dimensionality in check.</p><p>In the next step, we convert the above form of data into vector form:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4400d314ff733c3c431c3dba3ae90a82/href">https://medium.com/media/4400d314ff733c3c431c3dba3ae90a82/href</a></iframe><p>The above code snippet converts the data set into the following vector form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/638/1*QXV805dUd1DjngsqvdwuLw.png" /></figure><p>choice_vector contains 1s for the item_id values that the user “liked” and 0s for the item_id values, that the user didn’t react to.</p><p>The choice vector here, has over 10000 dimensions which makes it very impractical to work with. Hence, the next step would be to reduce the dimensionality of these vectors. There are multiple ways of achieving this, but since our vectors are highly sparse, SVD or Singular Value Decomposition seems to be the best fit. To understand more about what SVD is and how it works, please <a href="https://www.geeksforgeeks.org/singular-value-decomposition-svd/">follow this link.</a></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b09015cd6d39317a6f62fc8aa65d6245/href">https://medium.com/media/b09015cd6d39317a6f62fc8aa65d6245/href</a></iframe><p>The above code snippet reduces the number of dimensions from over 10000 to 40, and leaves us with something like below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/846/1*5MU_rnhk7QlXqd6Zh4If-g.png" /></figure><p>Once, we have the dimensionality in check, let’s start with initialising an ANNoy index:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f58ce13761b7566ed39b05ec2013ea42/href">https://medium.com/media/f58ce13761b7566ed39b05ec2013ea42/href</a></iframe><p>The above code snippet does the following things:</p><ul><li>Initialises an AnnoyIndex with 40 dimensions i.e. the number of dimensions in our reduced vectors</li><li>Adds combination of all user_id and vectors to the index</li><li>Builds a forest of 20 trees to facilitate ANN</li><li>Saves the index to a file named ‘behance.ann’</li></ul><p>The next step would be to get the n nearest neighbors:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/420e8d016cf7a686036afa679220e345/href">https://medium.com/media/420e8d016cf7a686036afa679220e345/href</a></iframe><p>The above method needs to be called to identify the k nearest neighbors. Once we have the user_id of k nearest neighbors, we can do the following:</p><ol><li>Go to our backup data frame that we created in the first step</li><li>Get a list of items that the nearest neighbors liked</li><li>Remove any item_id that the current user has already liked</li><li>Return the list of item_id recommendations</li></ol><p>Compared to the vanilla approach discussed earlier, this is a significantly efficient and practical way to identify nearest neighbors which can then be extended to use cases like collaborative filtering, content filtering and many other classification systems.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b2420d4b30b9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Software Engineering is much more than just building APIs]]></title>
            <link>https://utkarsh-upendra.medium.com/software-engineering-is-much-more-than-building-apis-1c7e753a963f?source=rss-e7f90322fdba------2</link>
            <guid isPermaLink="false">https://medium.com/p/1c7e753a963f</guid>
            <category><![CDATA[engineering-culture]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Utkarsh Upendra]]></dc:creator>
            <pubDate>Tue, 18 Jan 2022 09:39:23 GMT</pubDate>
            <atom:updated>2022-01-18T14:23:54.987Z</atom:updated>
            <content:encoded><![CDATA[<p>With the advent of new and charming frameworks like Spring Boot and Hibernate, there has been an observed shift in the definition of “Software Engineering” and “skills” of a Software Engineer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VxeRaVHS9PGhjpWhHMQSTg.png" /></figure><p>Many of the resume that I come across have one or more of the following “skills” highlighted:</p><ul><li>Spring MVC</li><li>Spring Boot</li><li>Hibernate</li><li>JUnit</li><li>Jenkins</li></ul><p>It goes without saying that all of the above tools/frameworks barring Jenkins primarily work with Java, as most of the candidates that I interview come from the same background.</p><p>The thing which baffles me is the fact that how can “using” a framework become a skill. I can understand that these frameworks have made the lives of developers easy, because abstraction is the most valued Object Oriented Programming Principle among developers today. However, over time, we, as developers have failed to realise that this simplicity comes at a cost. Although most, if not all frameworks are open sourced, but there’s just a handful of developers who actually take that effort to dig into the source codebases and explore the work behind the scenes.</p><p>If I choose a software developer at random, and I ask him/her that how would they develop a HTTP based API. Chances are, that 2 out of the first 5 words in response would be “Spring” and “Boot”. Very few care about what an API is, or how does it get exposed over internet, resulting in us being able to access those as “ReST APIs”.</p><p>If a developer just knows about these frameworks without understanding the core concepts, then he/she inherently inherits the limitations of these frameworks. What I really wish these frameworks to do, is to take up the role of supporting cast i.e. the developers should learn and understand concepts, design patterns and coding conventions that concern them and then make use of these frameworks to reduce the overhead of writing boilerplate code.</p><p>Once this happens, the resume would start looking very different. The skills would be as follows:</p><ul><li>Designing a software subsystem using the established design patterns</li><li>Conversion of designs to functional code</li><li>Automated Quality assessment of the code</li><li>Setting up auto deployment pipelines</li></ul><p>Now this gives the interviewer a much better idea of what the candidate can do. This also creates an impression that the candidate isn’t tied to a single tool/framework to solve a problem.</p><p>I have always been of the opinion that Software Engineering is an art, which makes Software Engineers artists. Flexibility and adaptability is critical to an artist and the same goes for us as well. And getting hard wired to a tool, framework or even a language is certainly not the way to go.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1c7e753a963f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A vanilla implementation of Collaborative Filtering for Image Recommendation System]]></title>
            <link>https://utkarsh-upendra.medium.com/a-vanilla-implementation-of-collaborative-filtering-for-image-recommendation-system-804ebc6f3b3d?source=rss-e7f90322fdba------2</link>
            <guid isPermaLink="false">https://medium.com/p/804ebc6f3b3d</guid>
            <category><![CDATA[collaborative-filtering]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[recommendation-system]]></category>
            <category><![CDATA[knn-algorithm]]></category>
            <dc:creator><![CDATA[Utkarsh Upendra]]></dc:creator>
            <pubDate>Tue, 18 Jan 2022 08:01:07 GMT</pubDate>
            <atom:updated>2022-01-18T08:01:07.954Z</atom:updated>
            <content:encoded><![CDATA[<p>Recently, I came across a problem where I had to design an image recommendation system i.e. I had a dataset with 1 million user interaction points. These points were in the form of &lt;user_id, picture_id&gt; which represents that the user with the given user_id “liked” a picture with the given “picture_id”.</p><p>This was a classic use case for collaborative filtering, where all I had to do was, for a given user, find the users with most similar interests when it comes to pictures, and recommend what they “liked”. To understand more about collaborative filtering, see <a href="https://builtin.com/data-science/collaborative-filtering-recommender-system">this link</a>.</p><p>Coming to the implementation, the first step was to preprocess data in such a way that calculation of common “liked” pictures becomes simpler. One of the ways that I found to be effective was to create a dictionary with user_id as keys and a list of picture_id representing what pictures did that user like.</p><p>Given dataset was in the following form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/392/1*sIg_3plwNqGto1ap0tZWxw.png" /></figure><p>I had to get it into the following form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/632/1*Bvl_OQKz-VKebjZ_cWNTUg.png" /></figure><p>To achieve this, I read the tuples from a data frame and created a dictionary as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/914/1*DFUuGL4s11IuxNWqImlVwA.png" /></figure><p>Once I had the data in the form mentioned above, all that was needed was to compare similarities between users. I found K-Nearest Neighbours to be the relevant and suitable algorithm for this problem. To keep things simple, my measure of similarity between 2 users was set to the ratio of number of pictures liked by both the users to the total unique number of pictures that both the users have interacted with.</p><p>The following method was created to identify and store the details of k users closest to the given user.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7LC7Zk8Abw_B7EesTz8YJQ.png" /></figure><p>Once, the list of k most similar users was available, I just needed to fetch the list of pictures that those users had liked. This was fetched from the dictionary mentioned above. Of course, I had to eliminate the pictures that the given user has already liked so as to not recommend duplicates.</p><p>Points to note:</p><ul><li>The above explanation is <strong>not </strong>meant to describe a real world recommendation system. The objective was to understand and present the concepts of Collaborative Filtering and KNN.</li><li>KNN, while very effective isn’t very scalable. This is evident by the fact that to classify/calculate for a given input, the distance has to be calculated with all the other data points which becomes time and compute intensive as the data grows in volume.</li><li>The above model is intuitive and works well because we have only 2 dimensions in our data set. As the number of dimensions grow, visualisation becomes challenging and hence we seek help from mathematics rather than intuition.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=804ebc6f3b3d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Pagination spanning across databases]]></title>
            <link>https://utkarsh-upendra.medium.com/pagination-spanning-across-databases-408076625f83?source=rss-e7f90322fdba------2</link>
            <guid isPermaLink="false">https://medium.com/p/408076625f83</guid>
            <category><![CDATA[microservices]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[pagination]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[sql]]></category>
            <dc:creator><![CDATA[Utkarsh Upendra]]></dc:creator>
            <pubDate>Fri, 01 Oct 2021 10:26:33 GMT</pubDate>
            <atom:updated>2021-10-01T11:22:10.022Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/450/1*f2zOg4LKw7lNa_Yy8N8F2g.png" /></figure><p>Normally, enabling a paginated query on a <em>RDBMS</em> is as simple as adding “<em>limit</em>” and “<em>offset</em>” parameters to any “<em>select</em>” query. However, recently I came across a situation where a service was to get data from multiple databases (hosted on separate servers) and expose the same to the client in a paginated manner i.e. the client can make a request saying that it needs the first page containing <em>10</em> records, then the second page containing <em>10</em> records and so on.</p><p>I will not go into the details of what pagination is and why is it important. There are several articles out there that explain Pagination as a concept.</p><p>So. let’s go through the considerations first:</p><ol><li>There are <em>2</em> databases (Say <em>DB1</em> and <em>DB2</em>) which are abstracted by a service layer to any client that wants to interact.</li><li>If a record exists both on <em>DB1</em> and <em>DB2</em>, <em>DB2</em> takes precedence i.e. <em>DB1</em> record shouldn’t be returned.</li><li>There is no temporary/intermediate data store which can store aggregated data from both <em>DB1</em> and <em>DB2</em>.</li><li>There is no direct access to <em>DB1</em> i.e. we have to build another service (say <em>S1</em>) that exposes data from <em>DB1</em> so that the service running with <em>DB2</em> (say <em>S2</em>) can access it.</li><li>Client can only make a request to <em>S2</em> and <em>S2</em> has to internally connect with <em>DB2 and DB1 (</em>via <em>S1)</em> to prepare the data and respond to the client’s request.</li></ol><p>Let’s consider for example that client makes a request to <em>S2</em> asking for the first <em>10</em> records i.e.</p><blockquote>P = 0, S = 10</blockquote><p>where <em>P</em> stands for <em>Page</em> and <em>S</em> stands for <em>Size</em> of the page, which in this case is <em>10</em> records. Let’s assume that the table in <em>DB2</em> has <em>6</em> records that match the conditions specified by the client, which means that, to be able to return <em>10</em> records, I need to query just the first <em>4</em> records from the table in <em>DB1</em> via <em>S1</em>.</p><p>Hence the (pseudo) query on the table in <em>DB2</em> would be:</p><blockquote>SELECT * FROM &lt;table _name&gt; where &lt;client_conditions&gt; limit S offset (P*S)</blockquote><p>In addition to the above, we also need the total count of eligible records which means, we need to make the following query:</p><blockquote>SELECT COUNT(*) from &lt;table_name&gt; where &lt;client_conditions&gt;</blockquote><p>Once we get the result out of the above queries, we can check the size of the result set (<em>RS2</em>) and the result of count query (<em>C2</em>)which in this case would be <em>6 and 6</em>. Hence, to get the remaining <em>4</em> records from the table in <em>DB1</em>, the (pseudo) query would look like:</p><blockquote>SELECT * FROM &lt;table_name&gt; where &lt;client_conditions&gt; limit (S-length(RS2)) offset X</blockquote><p>where</p><blockquote>X = (P * S)-C2, if P &gt; 0 and floor((P*S)/C2) &gt; 0</blockquote><blockquote>X =0, for any other condition</blockquote><p>In the above example,</p><blockquote>length(RS2) = 6 and P = 0,</blockquote><blockquote>=&gt;limit = 0 and offset = 4</blockquote><p>To check the other case when the table in <em>DB2</em> has more than <em>S</em> records, let’s consider that the table in <em>DB2</em> has <em>12</em> records, which means to get the first page of <em>10</em> records, we wouldn’t make a query to <em>S1/DB1</em> since <em>DB2</em> already has <em>10</em> or more records.</p><p>To return the Second page, we get <em>2</em> records from <em>DB2</em> and the pagination parameters for the query to be made on <em>DB1</em> are calculated as follows:</p><blockquote>length(RS2) = 2</blockquote><blockquote>C2 = 12</blockquote><blockquote>floor((P*S)/C2) = floor(10/12) = 0</blockquote><blockquote>hence, limit = 8 and offset = 0</blockquote><p>Let’s pull in another page of records i.e.</p><blockquote>P = 2, S = 10</blockquote><blockquote>length(RS2) = 0</blockquote><blockquote>C2 = 12</blockquote><blockquote>floor(20/12) = 1</blockquote><p>Hence, limit and offset for query on DB1 will be calculated as follows:</p><blockquote>limit = 10, offset = 20–12 = 8</blockquote><p>For the next page,</p><blockquote>limit = 10, offset = 30–12 = 18</blockquote><p>and so on.</p><p>The above logic was implemented and tested to check for the coverage of the known scenarios, and it has worked well so far.</p><p>Thanks for the read. I will look forward to any feedback that you might have. Please glance over my other articles in case you are interested in software engineering concepts and case studies.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=408076625f83" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Hash trees (Merkle Trees)]]></title>
            <link>https://utkarsh-upendra.medium.com/hash-trees-merkle-trees-6ace7f86ff9b?source=rss-e7f90322fdba------2</link>
            <guid isPermaLink="false">https://medium.com/p/6ace7f86ff9b</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[merkle-tree]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[hashing]]></category>
            <dc:creator><![CDATA[Utkarsh Upendra]]></dc:creator>
            <pubDate>Mon, 27 Sep 2021 04:32:26 GMT</pubDate>
            <atom:updated>2021-09-27T04:32:26.126Z</atom:updated>
            <content:encoded><![CDATA[<p>Ever wondered how GitHub easily and accurately determines what changes have been made to each file, or how distributed database systems like Cassandra ensure proper replication of data across replicas?</p><p>The short answer to the above question is — they use Merkle trees. The long answer is well — that’s what this article is for!</p><p>Not until the last decade, sharing content over web wasn’t as easy as it is now. To put things in perspective, if I had to share my resume publicly, I basically had to spin up a server, get a domain, host my content on there and then share the address with people who I want to share my content with. At present, this task is as easy as making a post on Medium (like this one!).</p><p>However, Medium would still need to store my content on its servers and every time someone requests my content, it gets the content from its store and presents it to the requester. Sounds simple enough! But internally, there are challenges.</p><p>If the server that my content is on, is located in New York and I am based out of Hyderabad and the requestor is based out of Melbourne, then to make an update to the content, my update request will have to travel half way round the globe to reach the servers in New York, and for a reader making a read request, the content will again need to be sent over to the reader who is thousands of miles away. This also places a lot of responsibility on the servers in New York. In an event, when these servers fail, we don’t have an alternative.</p><p>To most of the challenges posed by these conventional highly concentrated server architectures, a reasonable solution is “decentralization” which in the literal sense means delegating your load on to multiple resources. In simple terms, this means that instead of having just one server in New York, Medium could have one server each in Hyderabad, Melbourne and New York and then, when I update my content, it first gets updated in the server in India, which is then internally synchronized across servers in Melbourne and New York. Now if my content is requested from let’s say Sydney which is much closer to Melbourne than the other two server locations, the read request would be served from Melbourne itself.</p><p>Another way could be to split up my content into multiple parts and storing those parts in multiple nearby servers. This way, when the content is requested, instead of getting all the content at once from a single server, the content would be extracted in pieces from multiple servers and then stitched together to create the original view of my content. This is specially helpful when the content files are too large. This actually forms the basis of how Hadoop works.</p><p>When we split our files into multiple pieces, another problem that inherently comes up is, how do we know if the content that we are reading is not corrupt. To ensure this, we can use hashes for the file content — this would mean that each chunk of the file could be assigned hashes based on the content within that chunk and then while querying we just verify by recalculating the content based hashes for each chunk. These content-based hashes could also be used as <a href="https://patentimages.storage.googleapis.com/b9/1b/58/e2efcb15e17e7b/US7373345.pdf">content-based addresses</a>, which can then be sent to the client. But we must understand, that even for this verification to happen, we would have to have a “trusted” server which actually stores the hashes of all the individual chunks of data. Any change in the content of any chunk would also alter the hash of that chunk which would then be communicated to the “trusted server”. The trusted server would then communicate this hash to the peer that requests the content. This sounds like a reasonably good solution, until it fails! Think of a scenario when your “trusted” server itself gets compromised or corrupt. In such an instance, not only would we lose the ability to verify any of the chunks, but also we would realize that even though we solved some of the major problems with centralized servers, there’s still some element of local centralized processing that is required and that comes with its own drawbacks.</p><p>The solution to the problem that we just saw above could be a chained hashing, which basically means the root hash of the file would actually be a function of content-based hashes of all the individual chunks. Now when a client requests content from the trusted server, the trusted server would return the full tree of hashes (hash tree) with the individual chunk hashes and the root hash. The client can then verify the content in the address from the content based hashes has been tampered with, or not by validating hashes of each of the chunks and also the root hash.</p><p>The below diagram illustrates the structure of a hash tree:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sYc4I_knPJeIJPYGDSaJhA.png" /></figure><p>As is evident from the diagram above, the data in every parent node is a hash function of data in its child nodes. The data in the leaf nodes are hash values of atomic chunks of data.</p><p>This solution forms the basis of how GitHub identifies changes made to files. Let’s imagine, we have 4 files in a directory and 1 of those is edited in a commit. To identify the changes made to the files, GitHub would first check the data in the root node to see if there are any changes at all. If the root hash calculated for our commit is different from what is is for the state before we made that commit, GitHub would know for sure that there has been some change in that commit. It then drills down checking the hash values at each level, finally reaching the atomic data chunks (files in this case, could also be chunks of a file) and then identifies what change has been made to which file.</p><p>Hash trees are also used to ensure consistency between replicas of a distributed database system like Apache Cassandra. If a write happens in one replica, Cassandra identifies which chunk got updated using Hash trees and then transmits only that chunk to the other replicas to ensure consistency between them. This makes it much more efficient than what it could be if it were to transmit the entire file every time an update happens.</p><p>There’s another very popular use case that we have been hearing a lot about for the last 3–4 years. Heard blockchain? I would leave that for the readers to explore themselves!</p><p><em>Originally published at </em><a href="https://www.linkedin.com/pulse/hash-trees-merkle-utkarsh-upendra/"><em>https://www.linkedin.com</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6ace7f86ff9b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding HyperLogLog]]></title>
            <link>https://blog.stackademic.com/understanding-hyperloglog-a38bbf2e6249?source=rss-e7f90322fdba------2</link>
            <guid isPermaLink="false">https://medium.com/p/a38bbf2e6249</guid>
            <category><![CDATA[hyperloglog]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[probablistic-ds]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Utkarsh Upendra]]></dc:creator>
            <pubDate>Sun, 26 Sep 2021 16:59:43 GMT</pubDate>
            <atom:updated>2023-09-13T08:09:47.330Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*DJa11089N3147oYZ" /><figcaption>Photo by <a href="https://unsplash.com/@markusspiske?utm_source=medium&amp;utm_medium=referral">Markus Spiske</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Imagine you go to a party and you want toknow how many people are at that party, how would you determine that? One way is to use brute force to manually and sequentially count each individual and get the total. But obviously, you don’t want to do that in a party, right? So, what are the other options? Just hold on for a moment and think about it.</p><p>Let’s assume you meet someone, and you ask his name, and the person replies “Tony”. You meet the next person and he introduces himself as “Steve”. At this point you think, what’s the probability that I meet a person whose name is “Tony” or “Steve”? It’s pretty high, since both these names are very common. So, how many people would you need to meet, to find someone whose name is “Tony” or “Steve”? It’s pretty low, right? For all you know, your next-door neighbor might have these names. But if you meet a person whose actual name is say “Iron Man” or “Captain America” (pardon my Marvel fandom), and following the same logic, you would get an interesting insight. To find someone, whose name is “Iron Man” or “Captain America”, you would probably need to talk to each person on earth and ask their names, since these names are just so rare (or borderline nonexistent). So, if you find someone with a name as rare as “Iron Man”, you are either meeting a person who had one too many, or you get a sense that the number of individuals in the party you are in, must be huge!</p><p>Okay, now putting the same understanding to binary numbers, assume you have a set of random binary numbers like:</p><pre>0011 <br>0001 <br>1001 <br>1101 <br>1111</pre><p>Here, let’s look at the number of preceding zeroes in each number:</p><pre>0011 - 2 <br>0001 - 3 <br>1001 - 0 <br>1101 - 0 <br>1111 - 0</pre><p>Now, let’s try to determine, to get a single preceding zero in a binary number, how many numbers would you need to scan through? The answer is 2. Because in a random distribution, half of the numbers would start form 0 and half would start from 1. Extending this further, the probability of getting 2 preceding zeroes would be 0.25, 3 preceding zeroes would be 0.125 and for k zeroes would be <em>1/(2^k).</em> Consequently, to encounter a binary number with 2 preceding zeroes, you would need to scan through roughly 2², 3 would be 2³ and for k preceding zeroes, this count would be <em>2^k</em>. This roughly forms the base of the HyperLogLog algorithm.</p><p>In the previous example, we could see that the maximum number of preceding zeroes was 3, which would mean there are roughly 2³ = 8 elements in our set. But there were actually 5. So, there’s a significant variance here. Obviously, if we have a larger and a randomized data-set, we would get a lower variance, but we still can’t trust this method as one freak entry would mess up the entire count (Similar to a situation where you are invited to a private party with Iron Man).</p><p>The solution to this would be to divide our set of numbers into various buckets. To decide these buckets, we could use any hash function. Let’s assume our hash function returns the last 2 digits of the input number. So, our buckets would look something like this:</p><pre>11 - 0011, 1111<br>01 - 0001, 1001, 1101 </pre><p>Now, we calculate the maximum number of preceding zeroes per bucket:</p><pre>11 - 2 <br>01 - 3 </pre><p>Now, instead of simply taking the maximum i.e. 3, we take the mean of bucket-wise maximum number of preceding zeroes, which gives us a mean max of (2+3)/2 = 2.5, which brings our count to 2^(2.5) = 5.6, which is quite close to the actual number.</p><p>This algorithm can be used to calculate the cardinality of a set or the count of distinct elements in a set in a constant time and log(log(N)) space. It has been found experimentally that it gives a constant error percentage determined by</p><blockquote><em>1.3/sqrt(m)</em></blockquote><p>Where m is the number of buckets. In our case, since we had 3 buckets, our error rate would be 1.3/1.732 = 0.75 %, which is almost like saying that, if you have a million elements in your data-set, this algorithm would tell you that you have around 992500 to 1007500 elements, which should be very acceptable in many use cases.</p><p>To get more accurate results, we could simply ignore the top 30% buckets with the highest number of preceding zeroes, which has been found to bring the error rate down to</p><blockquote><em>1.04/sqrt(m)</em></blockquote><p>So, the next time you are at an event and are curious to know, how many people are you surrounded with, start with asking names!</p><p>Ref:</p><ul><li><a href="https://engineering.fb.com/data-infrastructure/hyperloglog/">https://engineering.fb.com/data-infrastructure/hyperloglog/</a></li><li><a href="http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf">http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf</a></li><li><a href="https://odino.org/my-favorite-data-structure-hyperloglog/">https://odino.org/my-favorite-data-structure-hyperloglog/</a></li></ul><p><em>Originally published at </em><a href="https://www.linkedin.com/pulse/understanding-hyperloglog-utkarsh-upendra/?trackingId=qQvCuGGw4p48BRHEcLhxkg%3D%3D"><em>https://www.linkedin.com</em></a><em>.</em></p><h3>Stackademic</h3><p><em>Thank you for reading until the end. Before you go:</em></p><ul><li><em>Please consider </em><strong><em>clapping</em></strong><em> and </em><strong><em>following</em></strong><em> the writer! 👏</em></li><li><em>Follow us on </em><a href="https://twitter.com/stackademichq"><strong><em>Twitter(X)</em></strong></a><em>, </em><a href="https://www.linkedin.com/company/stackademic"><strong><em>LinkedIn</em></strong></a><em>, and </em><a href="https://www.youtube.com/c/stackademic"><strong><em>YouTube</em></strong></a><strong><em>.</em></strong></li><li><em>Visit </em><a href="http://stackademic.com/"><strong><em>Stackademic.com</em></strong></a><em> to find out more about how we are democratizing free programming education around the world.</em></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a38bbf2e6249" width="1" height="1" alt=""><hr><p><a href="https://blog.stackademic.com/understanding-hyperloglog-a38bbf2e6249">Understanding HyperLogLog</a> was originally published in <a href="https://blog.stackademic.com/">Stackademic</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Splitting a large matrix into smaller files]]></title>
            <link>https://utkarsh-upendra.medium.com/splitting-a-large-matrix-into-smaller-files-65b7568e3f43?source=rss-e7f90322fdba------2</link>
            <guid isPermaLink="false">https://medium.com/p/65b7568e3f43</guid>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[data-system]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[matrix]]></category>
            <dc:creator><![CDATA[Utkarsh Upendra]]></dc:creator>
            <pubDate>Sun, 26 Sep 2021 07:28:46 GMT</pubDate>
            <atom:updated>2021-09-26T07:28:46.644Z</atom:updated>
            <content:encoded><![CDATA[<p>Recently, I came across a problem to operate on a large matrix stored in the form of csv. I needed to split this large csv file into smaller files so that each of those smaller files can fit into main memory for any kind of processing. In this article, I am going to walk through the process that I followed to achieve the same.</p><p>Let’ s start with the considerations:</p><ul><li>The matrix must be split in such a way that the recreation of the original matrix is possible i.e. it must be a non destructive split.</li><li>In the process of splitting/merging, at no point can we bring the entire original matrix into the main memory.</li></ul><p>With the above 2 points in mind, there are two possible ways that we can work this out.</p><ol><li>Splitting by Row/Column: Here, we extract a certain number of rows/columns into a separate file and store the individual files in the correct order of the row/column number that they represent. Realistically, reading by rows from a file is more convenient as it is a O(n) operation w.r.t time complexity, whereas reading by column would be a O(n²) operation, since we can only read files by lines.</li><li>Splitting into smaller matrices: Here, we split a <strong><em>N x N</em></strong><em> </em>matrix into <strong><em>k²</em></strong> smaller <strong><em>M x M</em></strong><em> </em>matrices where <strong><em>N = kM</em></strong>. These smaller <strong><em>M x M</em></strong><em> </em>matrices are then stores as individual files numbered by the position of the smaller matrix in the original larger matrix (Example to follow).</li></ol><p>The problem with the first approach is that a single row/ column of the original matrix might itself be too large to fit into a computer’s main memory. Hence, I chose the second approach.</p><p>Now, let’s get into the details of the second approach. First of all we need to decide reasonable values for <em>M</em> and <em>k</em> such that <em>M²</em> elements can fit into main memory at a time.</p><p>Let’s assume the number of bytes in the main memory available for us to use is <em>x </em>and the original matrix contains only integers of size <em>4 bytes. </em>Hence, to fit <em>M²</em> elements in <em>x</em> bytes of memory with each element being of size <em>4</em> bytes, we land up with the following calculated value of <em>M</em>.</p><blockquote>M² = (x/4)</blockquote><p>Correspondingly, k can be calculated as:</p><blockquote>k = N/M</blockquote><p>Once, we have the values for <em>M</em> and <em>k</em>, we are good to start with the actual implementation of the algorithm.</p><p>Let’s take the following matrix as example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/280/1*1Gg_CsnEVw1aQEcGUOBROQ.png" /><figcaption>A 9 x 9matrix</figcaption></figure><p>Assuming I can have only <em>9</em> elements in my main memory at a time, we break it into smaller <em>3 x 3</em> matrices as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/437/1*g9x053SbSACZNYsQCVFTww.png" /><figcaption>9 x 9 matrix marked to split</figcaption></figure><p>Here, each colored section will be stored in a separate file. Now, the question is that how do we number these sections or blocks.</p><p>Let’s overlay the above matrix with a <em>3 x 3</em> matrix like below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/444/1*iTg4bm4itHGTFebOIPrNDA.png" /><figcaption>Overlain 3 x 3 Matrix</figcaption></figure><p>Now, we just follow the above numbering i.e. the first <em>3 x 3</em> matrix would be numbered<em> (0,0)</em>, the second would be numbered <em>(0,1)</em> and so on.</p><p>That’s about it for the storing the split sections of the original matrix. The following snippet can be used to implement it:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5a12812325f994e65551fbb5d38af984/href">https://medium.com/media/5a12812325f994e65551fbb5d38af984/href</a></iframe><p>Now to recreate the original matrix, all that we really need to do is arrange the smaller 3 x 3 matrices according to the order decided by their numbering and print those into a new file, which would be identical to the original matrix. The following snippet may be used to achieve this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cb68788d46d255ea4dfa6dec2cc5921c/href">https://medium.com/media/cb68788d46d255ea4dfa6dec2cc5921c/href</a></iframe><p>The thing to note in the snippet above is that a row of the original matrix can be created by just merging rows across horizontal blocks, which is where the inner loop must start from</p><blockquote>floor(row/BLOCK_ROW_COUNT)</blockquote><p>For example, row 5 of the matrix given above would be present in blocks (1,0), (1,1) and (1,2), and this row number can be determined by the above function i.e.</p><blockquote>floor(5/3) = 1</blockquote><p>As a part of the same problem, I needed to handle efficient storage of sparse matrices, which has to be a separate topic altogether.</p><p>Thanks for the read and please feel free to drop in any feedback that you might have.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=65b7568e3f43" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>