<?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 Ismail Afiff on Medium]]></title>
        <description><![CDATA[Stories by Ismail Afiff on Medium]]></description>
        <link>https://medium.com/@ismail-afiff?source=rss-f694ed3fc3a3------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*wjfpW3FRpi37SsWFQT0e2A.jpeg</url>
            <title>Stories by Ismail Afiff on Medium</title>
            <link>https://medium.com/@ismail-afiff?source=rss-f694ed3fc3a3------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 01:10:23 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@ismail-afiff/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[Bye-bye Callback! Welcome Coroutines!]]></title>
            <link>https://medium.com/traveloka-engineering/bye-bye-callback-welcome-coroutines-4c8d6109833?source=rss-f694ed3fc3a3------2</link>
            <guid isPermaLink="false">https://medium.com/p/4c8d6109833</guid>
            <category><![CDATA[asynchronous]]></category>
            <category><![CDATA[mobile]]></category>
            <category><![CDATA[coroutine]]></category>
            <category><![CDATA[async]]></category>
            <category><![CDATA[kotlin]]></category>
            <dc:creator><![CDATA[Ismail Afiff]]></dc:creator>
            <pubDate>Tue, 23 Jun 2020 05:37:56 GMT</pubDate>
            <atom:updated>2020-06-24T06:26:36.371Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/0*9uOP0SCg2tLvcZpk" /><figcaption><a href="https://blog.jetbrains.com/kotlin/2018/10/kotlin-1-3/">Figure 1. Don’t block, keep moving</a></figcaption></figure><p><em>Editor’s Note: Today, we hear from Ismail Afiff, a Principal Software Engineer with the Universal Search team, on his experience discovering the pain points of using asynchronous or non-blocking programming pattern to achieve concurrency via Callback and tackling its shortcomings to achieve feature and performance parity with its counterpart — Coroutines while delivering better expression of asynchronity in terms of safety, lucidity, conciseness, and adaptability.</em></p><p><em>The Universal Search team is responsible for delivering solutions that allow users to fulfill their travel and lifetstyle needs through smart query understanding and recognition.</em></p><h3>The Challenge of Writing Async Code</h3><p><em>Asynchronicity</em> or <em>non-blocking</em> function is one of Traveloka’s Backend Engineering’s staples. In fact, a lot of performance-intensive parts of Traveloka use <em>async</em> patterns heavily for high performance reasons (including the commonly used <em>REST Client</em>).</p><p>In Traveloka, <em>async</em> or <em>non-blocking</em> is generally expressed via<em> </em><a href="https://en.wikipedia.org/wiki/Callback_(computer_programming)"><em>Callback</em></a><em> — a Continuation </em>function passed into the calling function as an argument. Although using <em>Callback</em> has solved the high-performance challenge of serving millions of customers, our codebase still progressively becomes more difficult to understand, error-prone, and inflexible as it grows 10x.</p><p>Therefore, in this article, I will discuss how<em> </em>we utilized <em>non-blocking</em> function and <em>asynchronicity </em>and improved their application that is tailored to our use cases to solve our pain points.</p><h3>A Typical Problem</h3><p>Let’s take a <em>Customer</em>-<em>Review Translation</em> process as an example. It can be simplified as followed:</p><ol><li>Get a <em>single</em> review.</li><li>Translate the review into <em>multiple</em><strong> </strong>languages. The translation function is essentially a simple <em>REST </em>call to a translation server that can also be run <em>concurrently</em> for every translated language. Since network is prone to failure, add <em>Time limit </em>and <em>Retry</em> up to three times.</li><li>Finally, if <em>all</em> translation tasks for every language are successful, combine the results and save. If <em>any</em> translation task fails, <em>end </em>or <em>return </em>the process and log the exception. (Partially translated review is of no use.)</li></ol><p>Seems like a common problem, right?</p><h3>Expressing Non-Blocking Function in Traveloka</h3><p><strong>Translating Function</strong></p><p>The distinguishing feature of the <em>translate</em> function is its <em>non-blocking </em>signature<em> </em>as opposed to <em>regular </em>and<em> blocking</em> function. The reason is that the <em>translate </em>function calls a <em>REST </em>endpoint behind the scene, hence the function is more performant if done in a <em>non-blocking</em> way.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ac819825dd32ce959d93a71f15b3c491/href">https://medium.com/media/ac819825dd32ce959d93a71f15b3c491/href</a></iframe><p>The standard way of writing <em>non-blocking</em> code in Traveloka is providing a <em>Callback </em>as the last parameter to a function. The <em>Callback</em> itself is an <em>interface</em> serving as the <em>Continuation</em> function that will be invoked after the function being called(translate) has finished executing. The function being called has the option of continuing the process with either executing the <em>onComplete </em>function if it’s successful or the <em>onException </em>function if there is an error<em>.</em></p><p><strong>Aggregating the Continuation functions.</strong></p><p>Recall that the process of combining the translation results will continue only after the text has been translated to <em>all </em>languages. Therefore, the <em>Callback</em> function should <em>expect </em>to accept not a single, but <em>all</em> translation results. However, since the <em>translate</em> function only accepts a <em>single </em>result <em>callback</em>, how could we aggregate all translation results?</p><p>As expected from a medium-to-large company, Traveloka tackled this challenge by developing various libraries to compose <em>callbacks</em> that convert a single <em>callback </em>into an aggregated version using generic instance methods such as <em>List</em> or <em>Map .</em></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/14c2bb469ca20e4f1732e0086d8eab48/href">https://medium.com/media/14c2bb469ca20e4f1732e0086d8eab48/href</a></iframe><p><strong>Combining Together</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/41ccf9ee9d7e8ada6a6612474a49b0f9/href">https://medium.com/media/41ccf9ee9d7e8ada6a6612474a49b0f9/href</a></iframe><p>For simplification, several notable requirements such as <em>Timeout</em> and <em>Retry</em> have been omitted, left as an exercise for the reader :).</p><p>Nevertheless, the code has shown several notable characteristics that makes <em>asynchronous </em>and <em>non-blocking</em> code difficult to understand and error-prone, namely:</p><ol><li><em>Bottom-up </em>way of writing:<br>The <em>callback</em> function is created <em>before</em> the <em>translate</em> function is called and thus, the code is written backwards. In contrast, regular and <em>blocking</em> code is written in a sequentially forward-looking and step-by-step manner.</li><li>Error Propagation non-idiomatically through the <em>onException</em> function:<br>The issue with this technique is that any <em>uncaught </em>exception in the function being called (<em>translate) </em>will not invoke the <em>callback</em> (continuation function)<em> </em>causing unresolved or hanging callback. This will create an undefined behavior on the aggregated callback library. <br>Therefore, this technique requires meticulous attention in catching <em>all</em> possible exceptions in the function being called, to make sure that <em>any</em> exception will always be invoked and continue with <em>onException</em> instead of getting unresolved<em> callback</em>.</li><li>Inflexible <em>concurrency</em> composition due to libraries over-dependency:<br><em>MapCallbackComposition </em>library is inflexible since it only produces binary translation results; either <em>all</em><strong><em> </em></strong><em>successful</em> or <em>all exceptions</em>. There is no flexibility to obtain successful translation results in the case of a <em>partial</em> exception. Every single exception will result in <em>all Exceptions </em>being<em> </em>returned<em>.</em> <br>Different libraries are required for different behavior.</li><li>Callback hell:<br>Also referred to as the nested callback. It is one of the most prevalent problems when callbacks are executed sequentially.<br> In the actual <em>translation</em> task (<em>omitted in this problem</em>), there is a need to obtain the original review language (a <em>non-blocking</em> <em>callback function</em>) before translation. Because of the sequential flow, it will result in a nested callback. Adding a <em>retry </em>will also result in <em>callback hell</em> since <em>retry callback</em> is run sequentially after the first <em>onException </em>callback.</li></ol><h3>Tackling the Challenge and Solving the Pain Points</h3><p>There are various ways in expressing <em>non-blocking</em> functions and <em>concurrency </em>using programming language’s syntactic features such as <em>Future, Reactive, or async-await</em>. Nevertheless, based on my experience and experimentations, <em>coroutine </em>or <em>suspending</em> <em>function</em> is the one that solves the pain points elegantly due to its regular function signature.</p><p><strong>Translating Function</strong></p><p>Nowadays, I write the <em>translate </em>function using the <a href="https://medium.com/@elizarov/blocking-threads-suspending-coroutines-d33e11bf4761"><em>suspending</em></a> function that doesn’t<em> block threads,</em> but <em>suspends a coroutine</em> for performance reason. Similar to the original translate function, internally it uses a non-blocking <em>REST</em> client that might be written in a callback or the more <a href="https://ktor.io/clients/index.html#calls-requests-and-responses">idiomatic suspending function</a>.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9df61afce6d01898339fe1afc95502a1/href">https://medium.com/media/9df61afce6d01898339fe1afc95502a1/href</a></iframe><p>The elegance of this approach is the similar signature to a regular <em>blocking</em> function that simply returns a <em>String object</em> as opposed to supplying callback as the last parameter.</p><p>Furthermore, as opposed to Javascript’s <em>async </em>function, <em>suspending function</em> is free from concurrency as it is up for the caller to decide and compose.</p><p>As you will see, these characteristics make adding and composing concurrency not only intuitive, but also adaptable and less prone to error.</p><p><strong>Retry and Timeout</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2b68b7ecb17c314922d302f5aaece054/href">https://medium.com/media/2b68b7ecb17c314922d302f5aaece054/href</a></iframe><p>Creating a generic <em>retry</em> function that accepts a lambda variable (<em>block)</em> is really simple and easy to understand because idiomatic constructs such as <em>for-loop</em> and<em> try-catch (</em>similar to a regular code) can be used. For a deeper explanation, please refer to <a href="https://medium.com/@elizarov/kotlin-coroutines-a-deeper-look-180536305c3f">Kotlin Coroutines, a deeper look</a>.</p><h3><strong>Wrapping it up</strong></h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ecc67c2e7d34239a2d33de11b36b6985/href">https://medium.com/media/ecc67c2e7d34239a2d33de11b36b6985/href</a></iframe><p>Let’s go through the function assignment and try-catch function definition above:</p><ol><li>Easier code comprehension:<br>It is much easier now to comprehend the code’s overall sequential flow as opposed to the inverted flow of using callback.</li><li>More adaptive concurrency and less library dependency:<br>Because of the regular function signature, <em>concurrency</em> is written and composed with simple, explicit, and adaptable constructs (<em>delay, retry, timeout</em>, <em>async, for-each, try-catch, </em>or<em> </em><a href="https://vorpus.org/blog/notes-on-structured-concurrency-or-go-statement-considered-harmful"><em>coroutineScope</em></a>). 1Furthermore, the translate function results can now be written and transformed in a concise and functional way with generic instance methods such as <em>map, filter, or reduce.</em> <br>This approach is easier to adapt and customize than using callback aggregation libraries that are made for specific concurrency composition.<br>In the code sample 5 above, the try-catch encloses the whole translation tasks to catch any single translation exception immediately and suspend the overall translation tasks (similar to the <em>MapCallbackComposition </em>behavior<em>)</em>. If there is a need to obtain the partially successful translation tasks (not only as a simple <em>all success</em> or <em>exception</em>), modifying the try-catch<em> </em>scope is all it needs, as opposed to using a different callback composition library.</li><li>Error handling is safer by using idiomatic try-catch:<em><br></em>Try-catch<em> </em>is safer than calling <em>onException </em>callback since try-catch will guarantee that any exception within the block will get caught, whereas commonly forgetting to call <em>onException </em>will result in a <em>runtime undefined behavior </em>because of <em>unresolved callback</em>.</li></ol><p>In conclusion, writing <em>non-blocking asynchronous </em>code using <em>Callback </em>causes a lot of issues mentioned above and therefore, should be avoided. Nowadays, Coroutines is the preferred way of expressing <em>asynchronicity </em>since the resulting code is more concise, easier to grasp, adaptable, and safer. Hence, solving the pain points of using <em>Callbacks</em>.</p><p>Special thanks to the Backend Infra team, especially <a href="https://medium.com/@fajrin.azis">Fajrin Azis</a> and <a href="http://medium.com/@bobbypriambodo">Bobby Priambodo</a> of the Kotlin group for the fruitful discussions in making <em>asynchrony</em> more developer friendly.</p><p>I am really fortunate to undertake this fascinating and open-ended concurrency algorithm challenge with my Universal-Search team at Traveloka; one of the largest online travel companies in Southeast Asia. If you’re a software engineer interested in developing state-of-the-art solutions to help millions of users in finding their next adventures, have a search at the opportunities on<a href="https://www.traveloka.com/en/careers"> Traveloka’s careers</a> page!</p><h3>References</h3><ol><li><a href="https://en.wikipedia.org/wiki/Callback_(computer_programming)">https://en.wikipedia.org/wiki/Callback_(computer_programming)</a></li><li><a href="https://medium.com/@quyetvv/async-flow-from-callback-hell-to-promise-to-async-await-2da3ecfff997">https://medium.com/@quyetvv/async-flow-from-callback-hell-to-promise-to-async-await-2da3ecfff997</a></li><li><a href="https://medium.com/@elizarov/blocking-threads-suspending-coroutines-d33e11bf4761">https://medium.com/@elizarov/blocking-threads-suspending-coroutines-d33e11bf4761</a></li><li><a href="https://medium.com/@elizarov/kotlin-coroutines-a-deeper-look-180536305c3f">https://medium.com/@elizarov/kotlin-coroutines-a-deeper-look-180536305c3f</a></li><li><a href="https://vorpus.org/blog/notes-on-structured-concurrency-or-go-statement-considered-harmful/">https://vorpus.org/blog/notes-on-structured-concurrency-or-go-statement-considered-harmful/</a></li><li><a href="https://ktor.io/clients/index.html#calls-requests-and-responses">https://ktor.io/clients/index.html#calls-requests-and-responses</a></li><li><a href="https://blog.jetbrains.com/kotlin/2018/10/kotlin-1-3/">https://blog.jetbrains.com/kotlin/2018/10/kotlin-1-3/</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4c8d6109833" width="1" height="1" alt=""><hr><p><a href="https://medium.com/traveloka-engineering/bye-bye-callback-welcome-coroutines-4c8d6109833">Bye-bye Callback! Welcome Coroutines!</a> was originally published in <a href="https://medium.com/traveloka-engineering">Traveloka Engineering Blog</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Query Understanding Engine in Traveloka Universal Search]]></title>
            <link>https://medium.com/traveloka-engineering/query-understanding-engine-in-traveloka-universal-search-410ad3895db7?source=rss-f694ed3fc3a3------2</link>
            <guid isPermaLink="false">https://medium.com/p/410ad3895db7</guid>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[traveloka]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[search-engines]]></category>
            <category><![CDATA[search]]></category>
            <dc:creator><![CDATA[Ismail Afiff]]></dc:creator>
            <pubDate>Mon, 16 Mar 2020 03:46:24 GMT</pubDate>
            <atom:updated>2020-03-16T04:02:02.022Z</atom:updated>
            <content:encoded><![CDATA[<h4>Part 2: Goal and Implementation</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*PYNf-wOSAVTfF_0G" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*6whDfmBYLB4-9S6J" /><figcaption>Fig 1. Product, Subproduct, and Action Classifier, Named Entity Recognition, User’s Intent and Search results for query: “Apartment near Cp”</figcaption></figure><p><em>Editor’s note: This is the second in a series of three posts by Ismail Afiff, a Principal Software Engineer with the Universal Search team, on the Query Understanding Engine that powers Traveloka Universal Search, specifically on the feature goal and implementation. Read the first part: “</em><a href="https://medium.com/traveloka-engineering/query-understanding-engine-in-traveloka-universal-search-62313439cce4"><em>Introduction on why query understanding is a game changer for Traveloka Search Engine”</em></a><em>.</em></p><p><em>The Universal Search team is responsible for delivering solutions that allow users to fulfill their travel and lifetstyle needs through smart query understanding and recognition.</em></p><h3>Query Understanding Engine’s Goal</h3><p>Before going deeper, let’s discuss the expected outcome of the engine. As the name implies, the goal is to come up with the <strong>user’s intent </strong>based on user’s <em>query</em> and <em>context</em>. By understanding user’s intention, Traveloka will be able to provide meaningful search results and recommendations to the users.</p><p>Before heading to the implementation, we need to know the possible intents of Traveloka user’s search queries. Luckily, our product manager along with each Product’s representatives have compiled the list. User’s intent could come in a form of “<em>Searching</em> for <strong><em>Transportation Options</em></strong><em> from an </em><strong><em>Origin</em></strong><em> to a </em><strong><em>Destination</em></strong><em>”, </em>“<em>Searching</em> for <strong><em>Flights</em></strong><em> from an </em><strong><em>Origin</em></strong><em> to a </em><strong><em>Destination</em></strong><em>”, “Searching for </em><strong><em>Accommodations </em></strong><em>by </em><strong><em>Name</em></strong><em> with a certain </em><strong><em>AccommodationType</em></strong><em> in an </em><strong><em>Area</em></strong><em>”, “Searching for </em><strong><em>TravelokaEatsProduct</em></strong><em> by </em><strong><em>Name </em></strong><em>with a </em><strong><em>RestaurantType</em></strong><em> near a </em><strong><em>Place-of-Interest</em></strong><em>”, </em>“<em>searching for </em><strong><em>Everything </em></strong><em>near</em><strong><em> Me</em></strong><em>” or as simple as “</em><strong><em>An Area, a Place-of-Interest, or a Hotel</em></strong><em>” </em>and many more<em>.</em></p><p>You notice some words are boldfaced in the intents above. Actually, they each have a special meaning since they describe the properties of <strong><em>an intent</em></strong>. For example in “searching for <strong><em>Transportation</em></strong>” intent, it has properties such as <strong><em>Origin</em></strong> and<em> </em><strong><em>Destination</em>. </strong>Similarly with “Searching for <strong><em>Accommodations</em></strong>” intent, it has <strong><em>AccommodationName, AccommodationType</em></strong><em> and </em><strong><em>Area </em></strong>properties<em>.</em><strong> </strong>Intent properties are mostly unique to a specific intent. For example, <strong><em>AccommodationType</em></strong><em> </em>is not present in “searching for <strong><em>TravelokaEatsProduct”</em></strong><em>.</em></p><p>By understanding the user’s intent and its properties, Traveloka will comprehend the query better and thus be able to come up with better search and recommendation results over time.</p><h3>Query Understanding Engine Implementation</h3><p>For the MVP, we are taking two approaches to implement query understanding, the first one is via <em>Named Entity Recognition</em> lookup and the second is via Machine learned <em>Product, Subproduct, and Action Classifier (PAX), </em>each<em> </em>with their own strengths and weaknesses.<em> </em>The decision is taken since in the early phase of the project, the project is still a bit vague and the possibility for those algorithms to work is still uncertain.</p><p><strong>Named Entity Recognition (NER) Lookup.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Jajxi6IQGVqwhhL6" /><figcaption>Fig 2. Query to intent transformation for query: “Voucher Starbucks Kuncit”</figcaption></figure><p><em>Named Entity Recognition</em> is a service that recognizes entities present in a text (query). For example in the query “<em>Voucher Starbucks Kuncit</em>”, NER will recognize “<em>Starbucks</em>” as a <strong>Restaurant Name</strong> and “<em>Kuncit</em>” as a <strong>Landmark (Kuningan City Mall).</strong> Similarly for query “<em>Japanese Restaurant [in] Senopati”, </em>NER will recognize<em> “Japanese” </em>as a <strong>Cuisine Type</strong><em>,”Restaurant” as a </em><strong><em>RestaurantType</em></strong><em> </em>and <em>“Senopati” as an </em><strong><em>Area.</em></strong></p><p>Afterwards, the recognized entities are transformed into possible user intents. Recall that intent has properties — mostly unique to a specific intent. For example, <strong><em>CuisineType</em></strong><em> </em>is only present in a “Search for <strong><em>TravelokaEatsProduct</em></strong>” and is not present in “Search for <strong><em>Accommodation</em></strong>”. The uniqueness of intent properties makes property identification a powerful way to infer user’s intent.</p><p><strong>Machine-Learned Product, Subproduct, and Action Classifier (PAX)</strong></p><p>PAX is a service that tries to comprehend <em>Product, Subproduct, and Action </em>of a query. For example, query such as“<em>Cafe in central park</em>” is transformed into <em>Product</em>: Eats, <em>Subproduct</em>: “Eats Directory” and <em>Action</em>: “Search”. This is achieved via machine learning based on extensive manually annotated query samples.</p><p>Both <em>NER </em>and <em>PAX </em>have their own specific strengths and weaknesses, therefore, thorough comparison needs to be taken before deciding when to use which.</p><ol><li><strong>Ability to obtain properties of an intent.<br></strong>In the query “<strong><em>Starbucks</em></strong><em> [in]</em> <strong><em>kuncit</em></strong>”, it is not enough to classify only the <em>intent, the product, subproduct, or action </em>per se. For meaningful results and recommendations, the engine needs to comprehend that <em>Starbucks </em>is a <strong><em>RestaurantName</em></strong> and <em>Kuncit</em> is Kuningan City Mall (<strong><em>Place-of-Interest)</em></strong> to infer that the intent is <em>“Searching for </em><strong><em>TravelokaEatsProduct</em></strong><em> by a </em><strong><em>Name </em></strong><em>(Starbucks) near a </em><strong><em>Place-of-Interest </em></strong><em>(Kuningan City Mall)”. NER </em>is clearly the perfect tool for this job because of its ability to capture the intent properties.</li><li><strong>Ability to understand intent beyond Traveloka’s Products.<br></strong>As Traveloka goes beyond a simple <em>Online Travel Agent</em> and more into Enabling Discovery, user’s intent advances beyond a simple Traveloka Product. This could be in a form of “<em>Searching</em> for <strong><em>Transportation Options</em></strong><em> from an </em><strong><em>Origin</em></strong><em> to a </em><strong><em>Destination</em></strong><em>”, </em>“<em>searching for </em><strong><em>Everything </em></strong><em>near</em><strong><em> Me</em></strong><em>”, “City guide of an </em><strong><em>Area”,</em></strong><em> or as simple as “</em><strong><em>An Area </em></strong><em>or</em><strong><em> a Place-of-Interest”</em></strong><em>.</em><strong><em> </em></strong><br>It is much easier to comprehend these intents via <em>NER</em> because the detected <strong><em>EntityType</em></strong> can be used to infer the intent beyond Traveloka Product.</li><li><strong>Ability to understand dynamic products.<br></strong>Several products such as <strong><em>Movie</em></strong><em>,</em> come and go pretty quickly. <em>NER </em>lookup is superior in this regard since it will be immediately searchable after indexing.</li><li><strong>Ability to understand linguistic context.<br></strong>In this aspect, <em>PAX</em> tends to be superior from its <em>NER</em> lookup counterpart. <em>PAX</em> might be able to infer <em>Product, Subproduct and Action</em> from a less clear query context. <em>NER</em> lookup will simply throw away words that they don’t understand or in most cases refuse to propose an interpretation.</li><li><strong>Developer complexity.</strong><br>In this aspect, NER lookup is more complex to develop, since the burden of the algorithm is on the developer whereas machine-learned <em>PAX</em> relies on more annotated training data to enhance its inference.</li></ol><p>As you might know, the development of <em>NER</em> lookup relies on a carefully crafted algorithm. Currently, it is an extension of <em>single-entity-search</em> that has been a staple of Traveloka Search Engine. I will explore NER lookup implementation in great detail in part three of the series. Stay tuned.</p><p>I am really fortunate to undertake this fascinating, open-ended search algorithm challenge with my team at Traveloka; one of the largest online travel companies in Southeast Asia. If you’re a software engineer interested in developing state-of-the-art search system to help millions of users to find their next adventures, have a <em>search </em>at the opportunities on<a href="https://www.traveloka.com/en/careers"> Traveloka’s careers</a> page!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=410ad3895db7" width="1" height="1" alt=""><hr><p><a href="https://medium.com/traveloka-engineering/query-understanding-engine-in-traveloka-universal-search-410ad3895db7">Query Understanding Engine in Traveloka Universal Search</a> was originally published in <a href="https://medium.com/traveloka-engineering">Traveloka Engineering Blog</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Query Understanding Engine in Traveloka Universal Search]]></title>
            <link>https://medium.com/traveloka-engineering/query-understanding-engine-in-traveloka-universal-search-62313439cce4?source=rss-f694ed3fc3a3------2</link>
            <guid isPermaLink="false">https://medium.com/p/62313439cce4</guid>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[elasticsearch]]></category>
            <category><![CDATA[search-engines]]></category>
            <category><![CDATA[traveloka]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Ismail Afiff]]></dc:creator>
            <pubDate>Tue, 11 Feb 2020 02:16:31 GMT</pubDate>
            <atom:updated>2020-03-16T04:00:53.376Z</atom:updated>
            <content:encoded><![CDATA[<h4>Part 1: Introduction on why query understanding is a game changer for Traveloka Search Engine.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*BPOTfRcqjRLYzWoc" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*PI09Ty7QkpZK7G0l" /><figcaption>Fig 1. Search result in Accommodation Product (without query understanding engine — yet) vs in Universal Search (with query understanding engine)</figcaption></figure><p><em>Editor’s Note: This is the first in a series of three posts by Ismail Afiff, a Principal Software Engineer with the Universal Search team, on the Query Understanding Engine that powers Traveloka Universal Search, specifically on the urgencies and deployment benefits that would be advantageous for building complex queries within the Traveloka app. Read the second part:</em> “<a href="https://medium.com/traveloka-engineering/query-understanding-engine-in-traveloka-universal-search-410ad3895db7">Goal and Implementation</a>.”</p><p><em>The Universal Search team is responsible for delivering solutions that allow users to fulfill their travel and lifetstyle needs through smart query understanding and recognition.</em></p><p>Have you tried exploring and searching using the new universal search bar at the top of the Traveloka app? Did you notice something new with the search capability? If you think that it can now understand complex queries better, giving more relevant results and meaningful recommendations, you’re spot on. It is because we are introducing a new, unprecedented feature in Traveloka search, a <strong><em>Query Understanding Engine</em></strong>.</p><p>With the introduction of Query-Understanding-Engine, Traveloka Universal Search now can recognize and understand a lot of complex queries such as “<em>Flight Jakarta Singapore</em>”, “<em>Attractions in Sentosa</em>”, “<em>Hotel near Sydney Opera House</em>”, “<em>Voucher Seribu Rasa Cp</em>”, and many more. And as a result, turning those queries into more meaningful results and recommendations.</p><h3>Pre Query-Understanding-Engine Era</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*RBSmGc4HM2iHN7gy" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/873/0*VGhzISfFYu6PqKlr" /><figcaption>Fig 2.Search in Eats Product (without query understanding engine — yet) vs Universal Search. Showing the effect of query understanding engine.</figcaption></figure><p>Before the introduction of query understanding, Traveloka’s search engine is designed only for <em>single-entity</em> searching. What this means is, it is developed to infer only a single entity from a query. It performs well if the query is meant for only single entity such as queries: “<em>Universal Studios Singapore</em>”, “<em>Marina Bay Sands</em>”, “<em>Sydney</em>”, etc.</p><p>Consequently, the old search engine is not able to comprehend more complex queries. It fails to identify query “<em>Hotel Bali</em>” consists of a “<em>Hotel</em>” (accommodation) and a “<em>Bali</em>” (GeoLocation). It will simply find products that have “<em>Hotel Bali</em>” name on it, resulting in “<em>Whiz Prime </em><strong><em>Hotel Bali</em></strong><em>kpapan</em>” and “<em>Astara </em><strong><em>Hotel Bali</em></strong><em>kpapan</em>” as the top results.</p><p>The limited capability of the old search engine means understanding query’s intention such as <em>Flight from origin to destination</em>, <em>Attraction in an area</em>, <em>Hotel near a place-of-interest</em>, <em>Restaurant voucher near me</em>, etc is <strong>impossible</strong>.</p><p>We try to circumvent this huge limitation using various tricks by including the entity’s geo, its attributes and various factors into searchable entries. Nevertheless, the result is still far from ideal. It still can’t come up with satisfying results, even for a simple “<strong><em>Hotel Bali</em></strong>” query. The old search engine couldn’t understand that the user intention is searching for <strong><em>Accommodation</em></strong> that is located in <strong><em>Bali. </em></strong>It will only returns entities with “<strong><em>hotel bali</em></strong>” name on it.</p><p>If you want to know more regarding the old search engine implementation, I’ve written a great deal on it in these articles,<a href="https://medium.com/traveloka-engineering/high-quality-autocomplete-search-part-1-fcc1b0a4baa6"> part 1</a>,<a href="https://medium.com/traveloka-engineering/high-quality-autocomplete-search-part-2-d5b15bb0dadf"> part 2</a>.</p><h3>Benefits of Query Understanding</h3><p>The benefit of query understanding is immense.</p><p>The obvious one is the ability to give more accurate results for a more complex query, beyond a simple single entity search. This is because the query- understanding-engine is better in inferring user intention compared to the old search engine. Without the query understanding engine, query “<strong><em>cafe monas</em></strong>” will give erroneous results since it tries to find entities with “<strong><em>cafe monas</em></strong>” on it. It fails to understand that user intention is finding a <em>Restaurant</em> with type <strong><em>Cafe</em></strong> near or inside <strong><em>National Monument</em></strong> (Monas).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*7JXbTG1PMt5V0TON" /><figcaption>Fig 3. Example of Universal Search Result</figcaption></figure><p>Furthermore, the invaluable benefit of the new query understanding also comes in a more relevant recommendation. Take query “<strong><em>Tour Labuan Bajo</em></strong>” as an example, since the engine understands that the user intention is to find <strong><em>Attraction and Activities</em></strong> with type <strong><em>Tour</em></strong> in <strong><em>Labuan Bajo</em></strong><em>,</em> Traveloka is able to recommend user’s possible needs for that trip such as city guides, or accommodations located in <em>Labuan Bajo</em>. This will benefit not only the user itself but also Traveloka as a whole. Users will have a better preparation for the trip while Traveloka’s product exposure is increased.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*tGPU_1XmxK0TUhAn" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*eecI5Dwbzq-nLz4W" /><figcaption>Fig 4. Search results and recommendations for query “Tour labuan bajo” in universal search.</figcaption></figure><p>The recommendation system simply wouldn’t work without query understanding. Without the engine, it is difficult to understand that the user might have an intention to visit <em>Labuan Bajo</em>.</p><h3>Query-Understanding-Engine implementation in Traveloka</h3><p>There are several ways to implement query understanding engine. Some argue that Machine Learning method is superior to understand the query context, while others argue that for shorter and simpler query, lookup combined with rules might be a better choice. There is no silver bullet for it, each has its own strengths and weaknesses. That’s why sometimes the implementation is a combination of the two.</p><p>In choosing the appropriate algorithm for Traveloka Search we also need to consider Traveloka users’ searching behaviour. By analysing user’s behaviour, we can come up with an algorithm that is suitable for the task.</p><p>There are a lot more things to discuss on query understanding implementation in Traveloka Universal Search. It will be explored in great detail in part 2 of the series. Stay Tuned.</p><p>I am really fortunate to face this fascinating, open-ended search algorithm challenge with my team at Traveloka, one of the largest online travel companies in Southeast Asia. If you’re a software engineer interested in developing state-of-the-wart search system, helping millions users to find their next adventures, have a look at the opportunities on<a href="https://www.traveloka.com/en/careers"> Traveloka’s careers</a> page!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=62313439cce4" width="1" height="1" alt=""><hr><p><a href="https://medium.com/traveloka-engineering/query-understanding-engine-in-traveloka-universal-search-62313439cce4">Query Understanding Engine in Traveloka Universal Search</a> was originally published in <a href="https://medium.com/traveloka-engineering">Traveloka Engineering Blog</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[High Quality Autocomplete Search Part 2.]]></title>
            <link>https://medium.com/traveloka-engineering/high-quality-autocomplete-search-part-2-d5b15bb0dadf?source=rss-f694ed3fc3a3------2</link>
            <guid isPermaLink="false">https://medium.com/p/d5b15bb0dadf</guid>
            <category><![CDATA[traveloka]]></category>
            <category><![CDATA[elasticsearch]]></category>
            <category><![CDATA[search-engines]]></category>
            <category><![CDATA[technology]]></category>
            <category><![CDATA[engineering]]></category>
            <dc:creator><![CDATA[Ismail Afiff]]></dc:creator>
            <pubDate>Wed, 01 Aug 2018 07:38:17 GMT</pubDate>
            <atom:updated>2018-08-01T07:38:17.975Z</atom:updated>
            <content:encoded><![CDATA[<h4>Scaling autocomplete search service to millions of users.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/976/1*Wp25tNuSt5JIgROTj9BTrQ.jpeg" /><figcaption><a href="https://blog.algolia.com/distributed-search-network-latency-ruins-search-experience/">User experience as a function of search latency.</a></figcaption></figure><p>This is the second part of articles on how to create high quality autocomplete search. The <a href="https://medium.com/traveloka-engineering/high-quality-autocomplete-search-part-1-fcc1b0a4baa6">first part</a> is all about relevancy algorithm, how Traveloka overcome autocomplete search challenges in providing relevant results to users using the least amount of keystroke.</p><p>In this second part, We will have a look into another important metrics of autocomplete search — latency. No matter how good an autocomplete is, the user experience won’t be smooth if it takes too long to fetch results. In fact, <a href="https://www.nngroup.com/articles/powers-of-10-time-scales-in-ux/">100ms second is the response time limit if you want <strong>users to feel like their actions are directly causing something to happen on the screen</strong>.</a></p><p>Search-as-you-type in particular is challenging to scale since the amount of request is really massive because every character being typed means another query to the server.</p><p>Fortunately, there are several tips to improve performance of autocomplete search.</p><p><strong>1st, Moving the computation intensive part from query time to indexing time.</strong></p><p>It is essential for the query time to be fast and swift, whereas indexing time doesn’t have an impact to user since it happens behind the scene.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nNPZUGHAEAmpPo2QbwW4MA.jpeg" /><figcaption><a href="https://voormedia.com/blog/2016/06/cache-invalidation-using-elasticsearch-percolation">Indexing vs Query time.</a></figcaption></figure><p>Take <em>synonym </em>analyzer process for an example. In text search, we expand every tokens with their synonyms, such as <em>big</em> is expanded into <em>large</em>, <em>huge</em>, <em>humongous</em>, <em>extensive, etc, </em>so that it can also be searchable by its synonym.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*Vpt7cpTsE8yOtqvsMltDuw.jpeg" /><figcaption><a href="https://www.google.com/url?sa=i&amp;rct=j&amp;q=&amp;esrc=s&amp;source=images&amp;cd=&amp;cad=rja&amp;uact=8&amp;ved=2ahUKEwj84O2A3KvcAhVGMo8KHYplDyUQjRx6BAgBEAU&amp;url=http%3A%2F%2Fwww.primaryresourcecentre.com%2Fourshop%2Fprod_3808622-Alternative-word-synonym-poster-pack.html&amp;psig=AOvVaw3UVYrX22GOaMNqHZxbt7_K&amp;ust=1532108734537136">Synonym of Big</a></figcaption></figure><p>There are two options to implement synonym, during<em> indexing </em>or <em>query</em>.</p><p>If it is applied during indexing, tokens in the index will be supplemented with their synonyms. For example, a document “<em>Spacious Hotel in Jakarta</em>” becomes “<em>Huge, Large, humongous (..etc) hotel in Jakarta</em>” in the index. The apparent effect is the index size swells.</p><p>Whereas if synonym is implemented at query time, index size will still be the same, but the amount of query increases since we will also query the synonym afterwards. For example if the query is “<em>Spacious Hotel In Jakarta</em>”, we will also query “<em>Big Hotel in Jakarta</em>” “<em>Massive Hotel in Jakarta</em>”, etc. Hence, the noticable effect is an increase in search latency.</p><p>Unfortunately, choosing between implementing synonym at index time or query time is not that simple. Each of them have their own pros and cons.</p><p>Synonym during indexing</p><ul><li>(+) Heavy at indexing, light at querying. Less latency, users are happier 😉</li><li>(-) Index size swells. A lot more tokens (original plus it’s synonym) to store. Need more memory.</li><li>(-) Synonym modification requires <strong>reindexing of all documents</strong>, since modifying synonym means modifying the text-analyzer at index time.</li></ul><p>Synonym during query time</p><ul><li>(+) Index size is small. No additional token to store. Require less memory.</li><li>(+) Synonym modification can be done at any time, because it only modifies the query, keeping the index untouched.</li><li>(-) Light at indexing, heavy at querying. Users need to wait longer😭.</li></ul><p>In Traveloka, we believe user experience is crucial, therefore, heavy computation at query time should be avoided at all cost. Hence, We move various heavy token-expansion operations such as</p><ul><li><em>Synonym</em></li><li><em>Shingle</em> (space removal and token combination, remember “<em>Hong Kong”</em> vs <em>“HongKong”)</em></li><li><em>EdgeNgram</em> (<em>abc -&gt; a, ab, abc</em>)</li></ul><p>to indexing time, even at the expense of extra computational resource.</p><p>Furthermore, since the heavy-lifting token-expansion is being carried out at indexing time, we are able to use a simple <em>match</em> query. <em>Match </em>query works simply by checking whether a token exists in an index or not, making it blazingly fast. At best, this query requires only <em>O(1)</em> complexity, making query computation as light and as fast as possible.</p><p><strong>2nd, Modelling document for high performance.</strong></p><p>One of the easy way to improve performance is limiting the amount of searchable fields per document and combining equally treated fields.</p><p>Usually there are several fields in a document such as <em>name</em>, <em>additional info</em>, <em>alias</em>, etc. One of the purpose of this is to simply differentiate boosts between fields, e.g matching with <em>name</em> fields is more relevant than matching with <em>alias</em> fields.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/886/1*WHuhgfXQ7YXrJIos1uP34A.jpeg" /><figcaption>Name, additional info, alias and type fields in a document</figcaption></figure><p>However, if there is no boost difference applied (those fields are treated equally), it is much better to combine those into a single field. This is because the search complexity increases linearly with the amount of searchable fields, whereas the number of tokens in a field doesn’t really affect query performance that much (especially if a simple <em>match </em>query is used)</p><p>In fact, we learn this trick by accident. In the previous implementation of autocomplete document, there are 8 different fields for <em>name</em>, one for every <em>locales</em>. When the <em>name </em>fields are combined into single <em>name </em>field,<em> Voila</em> the query latency immediately improved by 7x.</p><p>What’s more, complex field relationship such nested parent-child and fields that require <em>joins </em>tends to slow down the query. By keeping the field relationship simple and avoiding <em>joins, </em>the query performance will be higher.</p><p><strong>3rd. Utilizing shards and replica</strong></p><p>If the number of query is huge, a single node might not be sufficient to handle all of the loads. One of the simple thing is to scale using sharding and replication.</p><p>Replication means duplicating data to another node, whereas sharding means partitioning the data into multiple node. By adding replica, the read throughput is increased since replicas also serve read requests, whereas sharding is useful when the index size is too big for a single node to handle. Furthermore by adding replica, the reliability is improved by providing <em>failover </em>mechanism<em>.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/1*SHrjzh2z8HPO2rRJhae2_Q.png" /><figcaption><a href="https://www.elastic.co/guide/en/elasticsearch/guide/current/replica-shards.html">Sharding and Replication in ElasticSearch</a></figcaption></figure><p>Just a quick note with sharding, on several search engines library such as <em>ElasticSearch</em> and <em>Solr</em>, by default, for performance reasons, some properties such as inverse document frequency <em>Idf </em>is calculated per shard, not across all documents in the index, causing issues when document is heavily skewed and not well distributed across shards. The issue can be mitigated by forcing to calculate global properties, which will add a round-trip latency. For further info on this topic please have a look at the reference for each library <a href="https://www.elastic.co/guide/en/elasticsearch/guide/current/relevance-is-broken.html">ElasticSearch</a> and <a href="https://lucene.apache.org/solr/guide/6_6/distributed-search-with-index-sharding.html#DistributedSearchwithIndexSharding-DistributingDocumentsacrossShards">Solr</a>.</p><p><strong>4th, Choosing hardware that ease performance bottlenecks.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*61QXPgiVfVlDeVWYd7-8cQ.jpeg" /><figcaption>AWS EC2 instance types.</figcaption></figure><p>Search algorithm tends to be <em>I/O bound</em>, therefore choosing hardware that has a better<em> I/O </em>performance will also improve search performance. The improvement can be in a form of higher memory performance (faster RAM) or faster disk (SSD vs spinning disk). Additionally, it is better to opt for local instead of external drive such as <a href="https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/EBSVolumeTypes.html"><em>AWS EBS</em></a><em> </em>since internal drive will provide less latency. Although beware the data in local drive data will be lost in case of instance stops, terminations, or hardware failure — making scaling a bit tricky.</p><p>Those are the four approaches to improve the performance of autocomplete search that I have thought of and implemented when building this feature for Traveloka. Each approach increases the engineering complexity and the resources required. Nevertheless, for a better User’s experience, the benefits are usually worth the extra effort and resources.</p><p>I am lucky to face this fascinating, open-ended search algorithm challenge with my team at Traveloka, one of the largest online travel companies in Southeast Asia. If you’re a software engineer interested in developing state of the art search system, helping millions users to find their next adventures, have a look at the opportunities on <a href="https://www.traveloka.com/en/careers">Traveloka’s careers</a> page!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d5b15bb0dadf" width="1" height="1" alt=""><hr><p><a href="https://medium.com/traveloka-engineering/high-quality-autocomplete-search-part-2-d5b15bb0dadf">High Quality Autocomplete Search Part 2.</a> was originally published in <a href="https://medium.com/traveloka-engineering">Traveloka Engineering Blog</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[High Quality Autocomplete Search Part 1.]]></title>
            <link>https://medium.com/traveloka-engineering/high-quality-autocomplete-search-part-1-fcc1b0a4baa6?source=rss-f694ed3fc3a3------2</link>
            <guid isPermaLink="false">https://medium.com/p/fcc1b0a4baa6</guid>
            <category><![CDATA[search-engines]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[technology]]></category>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[traveloka]]></category>
            <dc:creator><![CDATA[Ismail Afiff]]></dc:creator>
            <pubDate>Wed, 06 Jun 2018 10:32:36 GMT</pubDate>
            <atom:updated>2018-06-06T10:32:36.081Z</atom:updated>
            <content:encoded><![CDATA[<h4>Providing relevant results to millions of customers</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Y9H5HAH4omPs9ATp8njTtg.png" /><figcaption>Traveloka hotel autocomplete.</figcaption></figure><p>Have you searched for hotels in Traveloka?</p><p>I bet you’ve tried the autocomplete search. Indeed, Autocomplete search is the main gateway to explore myriads of Traveloka Hotels. By using hotel autocomplete search, users are given the most relevant hotel, region and landmark as-you-type. Autocomplete helps users saving time while typing and minimizes chances for spelling mistakes which result to a better customer experience overall, therefore it is essential for Traveloka to have a high quality autocomplete search.</p><p>However, there are several challenges that has to be tackled by hotel autocomplete.</p><p><strong>1st,</strong> hotel autocomplete is expected to give the most relevant results using the least amount of keystroke.</p><p><strong>2nd,</strong> since Traveloka is dealing with international users, autocomplete search must be able to handle various languages specific quirks such as in Thai language words are written without space separator e.g <em>เกาะสมุย </em>(ko samui).</p><p><strong>3rd</strong>, autocomplete should also be swift. No matter how good an autocomplete is, the user experience won’t be enjoyable if it takes too long to give results.</p><h3>Tackling the Challenges</h3><h3>1. Relevance Score formulation</h3><p>Users only want to see the most relevant results. Hence, the way relevance score algorithm works is one of the keys of autocomplete search.</p><h3>1.1 Classical Way of text relevance scoring</h3><p>The classical way of calculating relevance score is based on term frequency (<em>tf</em>), inverse document frequency (<em>idf</em>) and field-length norm.</p><p>Term frequency means the more frequent a term appears, the more significance it is, e.g text <em>“Bora bora island” </em>is more relevant than “<em>boracay island”</em> for query<em> “bora”.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/620/1*__eopBOW1YGK_HV929vm4g.jpeg" /><figcaption>Battle of term frequency, Bora-Bora vs Boracay. <a href="http://img.photobucket.com/albums/v218/corsarius_phil/ChoosePHL/boravs.jpg">[source</a>]</figcaption></figure><p>Inverse document frequency implies that a word’s relative weight is related to the inverse of its occurences in all documents, making more common words less significant than the unusual one. For example in text “<em>Eiffel tower</em>”, word <em>“Eiffel”</em> carries more weight than<em> “tower”</em> because <em>“tower”</em> is much more common and general than <em>“Eiffel”</em>.</p><p>Field-length norm describes that the longer the text, the less significant it is compared to the shorter ones. e.g text named “<em>Jakarta”</em> is more significant than <em>“West Jakarta” </em>because <em>“Jakarta”</em> is shorter than <em>“West Jakarta” </em>for query<em> </em>“<em>Jakarta”</em>.</p><p>Therefore the classical way of relevance score formula can be summarized by</p><p><em>Relevance Score = Tf * Idf * norm</em></p><h3>1.2 Improvement by BM25</h3><p>The classical way of relevance calculation is quite a huge step forward. However, for a short field — typical of traveloka entities — the relative significance of each factor (<em>tf, idf and norm</em>) shouldn’t be treated equal otherwise it will lead to erroneous results. In short texts it is much better to dampen the effect of <em>Tf </em>and <em>field</em> <em>norm</em> compared to Idf.</p><p>To tackle this problem we use BM25 as a basic way of calculating relevance score. BM25 itself is quite an extensive method of its own <a href="https://en.wikipedia.org/wiki/Okapi_BM25">(wikipedia)</a>, but by using BM25 the relative significance of each factor (T<em>f, Idf and field-length norm</em>) can be adjusted.</p><h3>1.3 Varying boost for every fields.</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/886/1*hCxBeBlUODmLrfjdqUYQBA.jpeg" /><figcaption>Sample of a landmark. Can you guess which one is name, alias and additional info?</figcaption></figure><p>A document entity consists of several fields such as<em> name, alias, additional infos. </em>Each field should carry different weights, e.g <em>name </em>field should be more important than <em>alias</em> and <em>additional info</em>. Therefore matching with <em>name</em> fields gives better score than matching with <em>additional infos</em> or <em>alias </em>field.</p><h3>1.4 Adding popularity and geoLocation based boosting</h3><p>To further improve the search result, we tune the calculated score with popularity data and geolocation.</p><p>Boosting by popularity means the more popular documents will have higher relevance scores compared to the less popular documents, other things being equal. The data can be inferred by various aspects, notably the amount of user search. Furthermore, popularity data should also be made per locale since popularity is location specific.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CS5EnzRaCxnBafbswcdB0g.jpeg" /><figcaption>Popularity is also taken into consideration. It is also locale specific.</figcaption></figure><p>We also boost the relevance score by user’s location. Results that are located in the same region as the user’s will be given an additional boost.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kMjnX3O6MQh2Xo1fV2effQ.jpeg" /><figcaption>Users tend to be interested in nearby results.</figcaption></figure><h3>1.5 Adding Exact boost.</h3><p>Although the above factors seems sufficient, we could instantly find a serious flaws in the algorithm. Since it emphasizes on popularity data, many unpopular entity will always ends in the bottom of the search result, no matter how exact the query is, making unpopular entity hardly searchable.</p><p>This problem is exacerbated in hotels since they usually have eccentric names. They might have names such as <em>“hotel j”</em>, <em>“hotel i”</em>,<em> “hotel m”</em>, etc. Based popularity alone, query <em>“hotel j”</em> will usually give <em>“hotel jxxx”</em> (the most popular one) on top of the lists, leaving <em>“hotel j”</em> close to the bottom because of its low popularity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LJEwxP6qbbEonhfjiJjD8w.jpeg" /><figcaption>Hotel J or Hotel Jxxx ?</figcaption></figure><p>To alleviate this problem, we add boost to the entities that exactly match the query itself. For example when the user queries <em>“hotel j”, </em>hotel with exact terms <em>“hotel j”</em> is given additional boost.</p><h3>2. Dealing with human languages</h3><p>Autocomplete search is related to the way human interacts with languages. Hence, a lot of things need to be implemented and taken care of compared to a non-text search.</p><h3>2.1 Analyzing Process</h3><p>The first step for a text search is analyzing the text. In this process, the text is transformed into simple searchable tokens. Analyzing consists of several steps such as tokenizing, stemming, synonym, and shingle processing.</p><p>a. Tokenizing</p><p>Tokenizing means separating the texts into smaller searchable tokens. The text separator should not only be whitespaces, but also numbers, symbols and other non-numeral characters since users usually treats those as a separator.</p><p>The following example is quite common in user search :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VB3Oh36dwAzkTw2zqsncNA.jpeg" /><figcaption>Sample Texts and their tokens.</figcaption></figure><p>b. Stemming</p><p>In stemming process, words are reduced into its basic form e.g <em>“eating”</em> into <em>“eat”</em>, <em>“buying”</em> into <em>“buy”</em>.</p><p>c. Synonym</p><p>In synonym process, the words are expanded into its synonym, making tokens also searchable by their synonyms.</p><p>d. Shingle</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/450/1*q-I1IblARskbPk1_BLzG-Q.jpeg" /><figcaption>With or without space?</figcaption></figure><p>Sometimes user also search the words without space in between. For example <em>“Hong Kong” </em>document should also be searchable by keyword <em>“Hongkong” </em>(without space). Therefore the problem is tackled by shingle process which combine adjacent tokens.</p><h3>2.2 Specific Language features</h3><p>As explained before, several languages have their own peculiar characteristics. In Thai language, words are written without space separator such as <em>เกาะสมุย (ko samui)</em>. This behavior will fail whitespace-based analyzer because of the lack of apparent token separator. The solution? use specific language analyzer to analyze text from various languages. By using Thai analyzer, text <em>เกาะสมุย </em>will be tokenized into เกาะ (koh) and สมุย (samui).</p><h3>2.3 Typo Handling</h3><p>It is quite common for users not to know the exact text they’re looking for, making them prone to typo. Therefore, autocomplete system should also be able to suggest them not only the documents that contain the exact tokens but also the ones that quite close to the query.</p><p>To tackle this problem we use fuzzy query which allows text that is within a certain <em>Levenshtein</em> edit distance (delete, insert and swap) to be considered match.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/842/1*vfsddwJ_FYehFhkluubKsQ.png" /><figcaption>ElasticSearch fuzzy query</figcaption></figure><p>For the last touch, we don’t want to give documents that were matched via typo to have a high relevance score, hence documents that are matched by fuzzy query were given lower boost.</p><h3>3. Creating a high performance autocomplete system</h3><p>A sophisticated autocomplete system would be meaningless if it takes too much time to produce results. Furthermore, a slow autocomplete system will also create an unpleasant user experience — something to avoid at all cost.</p><p>There are a lot of ways to improve latency performance of autocomplete, which itself is an interesting topic to cover in a separate blog. One of them is simply moving the computation intensive part from query time to indexing time. It is essential for the query time to be fast and swift, whereas indexing time doesn’t have an impact to user.</p><p>For the rest, stay tuned for the second part of this blog where I will discuss about the system architecture and solution for high-performance autocomplete service.</p><p>I am lucky to face this fascinating, open-ended search algorithm challenge with my team at Traveloka, one of the largest online travel companies in Southeast Asia. If you’re a software engineer interested in developing state of the art search system, helping millions users to find their next adventures, have a look at the opportunities on <a href="https://www.traveloka.com/en/careers">Traveloka’s careers</a> page!</p><p>Special thanks to Jogie for the discussion on the previous autocomplete implementation, Yosef Sidharta, for challenging the algorithm with tons of user cases, and Evan Yonathan for the invaluable guidance.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fcc1b0a4baa6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/traveloka-engineering/high-quality-autocomplete-search-part-1-fcc1b0a4baa6">High Quality Autocomplete Search Part 1.</a> was originally published in <a href="https://medium.com/traveloka-engineering">Traveloka Engineering Blog</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>