data.bythebay.io: Alexis Roos - Building a Graph of all US businesses using Spark technologies
thank you Michael so in this presentation I will talk about what we do I reduce intelligence and specifically discuss what we do for building a graph of all US businesses and I'll talk about you know or we do that you know using spark I'll skip that Michael introduced me already so in the agenda I have quickly introduced reduce intelligence and then I lay the foundation for the talk by introducing objectives and terminology and the bulk of the presentation we focus on our graph you know data pipeline so some of it will be a little bit technical but I would also presented at high levels so can give you a sense of where you can actually use a graph first an introduction so radius means offering is a predictive marketing software platform it is essentially designed for marketers to discover acquire new customers a measure success for those customers we essentially have a solution that empowers boss software end data so in our case were building a graph or folios businesses in necessary as typically our customer data isn't comprehensive our current enough and so our solution goes beyond just doing liquoring right with customer data as we provide our customers new data through our predictive segments so as such we first have to build a graph of our US businesses and this is what we talked about here just one more sign on the company when she had voted in a San Francisco we've already done quite a bit of money right and our core focus or differentiation is really focusing on it from the data science in the end design standpoint so our business graph is used by all our custom it has to be both comprehensive and accurate you know across all industries are typically our customer we use our software to create new campaigns like in a campaign phone campaign says campaign right so we first have to acquire a lot of data coming from dozens of sources like business seminar dress emails from the and pre information demographics financial data technology use you know these in the business news about the company you know intend that I and so forth and why building a graph right so the reason why we are doing that is to start answering compacted question complex questions right we just not simply want to find businesses right but we want to find businesses for instance by looking at injuring an executive at a given company focusing on big data security or looking for news related to a company's in a specific marketing segments so for instance look for company that I've recent funding announcements on mergers acquisitions show companies die interested in my product cry over a set of projects right based on the fact that they are by intent and they're kind of like browsing your specific notes things on the internet or look look forcing like show media organization of a company right what are the location what are the impression and so forth and in order to do that we have essentially to kind of do pipeline and that's what I'm gonna be talking about but first I'll introduce a little bit of terminology so here and i will use these symbols you know for the remaining of the presentation so we first have a concept of a business which represent a company organization structures in that example blue bottle and i'm representing that as the dark disk with a ball border we don't have a concept of a location the location represents the business at a particular address right such as you know the blue bottle at sansome street for instance and i'm representing that as a light disc with a light border then we have attributes essentially attribute represent information bits about a business so all the things that i was talking about before and that we get the rest such as like phone number an industry category financial information enter force here i'm representing them we were small geometrical shapes in addition we are also a number of other types of data in addition to possess a location such as you know employees intent news you know technology products and so forth that we want to have in the graph so at a very high level or data pipeline is broken down into four steps right to construe to grow essentially did acquisition preparation clustering and constriction and i will quickly go over the first three and then zoom in into some of the steps for the last one in the data acquisition we basically have to kuro license of the license there are from dozens of sources including billions of Records and tens of billions of data ports and we actually retain that information over time as we use you know some of that historical data for creating in on machine learning models in the output of that step we essentially have many different type of records which might represent the same information in different ways such as you know employees or revenues the next step of our pipeline you know is the run data preparation so in that step we standardize the data so that every data type is represented the same way for instance we have to stand out as the address and we have to do things like validation to get rid of it and craig data and lately lastly we have to normalize the data so it looks the same across recourse for instance we can see where records on the left cross sources and to the right we have data that it's been normalized for instance we have a single view for employees right we are to the left will get many different sources giving us you know i'm pretty information records are coming from a variety of sources right and so they look different and there is no concept of unique ID across so so so the next step we have is to group or cluster recalls together based on the fact that they represent the same business location so there we will use internal or field including in address name of the business in other dimensions such as website phone number and so on so to the left we can see normalize record users input and to the right the clusters of Records group buy a dress in business similarity they will use graphics in addition to sparkle skyline in-house libraries that we've developed such as men matching walking on sand tax and semantic level to be able to appropriately group your record you know together and the last step breaks into two sub steps first reconstruct the locations and second we construct you know the link between location and the business in for each cluster we will have to select the best value or values or cross all record in the cluster so for instance we have to select the best business name or rain call the phone number we have based on accuracy by creating a machine learning model that we use you know data across sources for instance how many you know source is proposed that phone number or how long was that phone number you know or record in a bed on historical data and we will have to include missing values as well so at this stage we use a variety of essentially a supervised machine learning models using a medley of such as a legit regression random forest or gbd and the output of that step is a set of locations as I defined previously that is a business at a given address and we can see here that each location is represented by lourdes can contain the attributes also that I defined properly and so the second sub step which is the one I actually am gonna dig into in in a minute is where we construct a business graph so now we have you know a set of you know essentially locations and we want to start your grouping in all those location together and there we will also need to add additional top of data such as newest employee and tenth and so forth in that simple example we can see to the right that we are presenting to business the red the dark blue disk across three locations the pink the green in the Buddhist that are sharing a new element which is a square wave and little inside and for the remaining of the presentation again I'm gonna I'm going to dive in and explain a little bit all we do that but before I do I'm gonna have one side to briefly introduce you know graphics as we're using that for a building a pipeline here so in the interest of time I will not go over its architecture and fentanyl except to mention that like a spa cottages a graphics is a property graph is immutable distributed in full tolerant right and I will illustrate briefly also what the graphics API provides and essentially the fact that is very approachable and easy to use so graphics models of property laughs which is attributed mulleted directed graph so multi directed essentially allows piling edges or relationship across the same source vertex and the same destination right an attributed mean that vertices also called nodes and edges and essentially have attributes here I'm showing a very simple grab there are three vertices a location a domain and a phone vertices and three edges or relationship linking those vertices you can see here that it's multi directed because we have two edges linking location and domain allowing us to show that to sources provide the same you know essentially website link now let's look at all graphics and model graph information the graph can be accessed as an object to the graph class as the table of vertices edges or triplets vertex represent a node and adoration ship and a triplet two connected nodes with the relationship a time it can be more efficient to use triplet over over looking up vertices and edges separately and then vertices and edges store our tributes and stir you know are essentially a attributed graph we've user-defined object that have the VD and ed types so i will quickly go there you know some of the operation that graphics you know provide right and this is a actually a pretty exhaustive list of everything that's available anywhere from high-level information about the graph such as the number of edges of vertices access to collections transformations aggregation and i will talk about a few in a minute and there's also a number of a graph algorithm and i will use connected component for the rest of the presentation so now I've Lee the foundation i'm going to zoom in into or we go from kind of the left side you know to the right side so the first step is for us to generate the location vertices basil the clusters so we have the group of record coming together and the next step is to start mapping each cluster to a vertex location limiting to do attributes which will need for linking locations right we have many many hundred of attributes you know for a given location we can only use a set of them start you know creating the graph enough pipeline features an optimization for non large businesses for this we have essentially a curated list including key attributes such as name website an additional information so here we essentially map every entry of that list to a business vertex and this allows us to improve the performance and accuracy of a graph in this step carrying on step one we want to link locations and non businesses if there's a relationship such as a domain we start with work we create into the previous step and use flat map operation to essentially project attributes inside out the locations are now kid by attribute as we can see in the city for example and we can see that we have a few eration ship between location and businesses specifically the pink players shares a pink attribute with the red business let's assume that this stuff of attribute would be a domain coming from a website or an email for instance and the green and blue locations share a yellow attribute with a dark blue business we then John based on kid attributes dc-3 keyvaluepair representing the relationship that we mentioned before which is the pink location is linked to drug business the green location is linked to the W business and the blue location is also linked to the W business we can then create edges between location and businesses basil attribute relationship and as an output we get a pink location linked to a reg business and a boss green and blue locations linked you know to the dark blue business so here we started basically creating relationship you know between your location and business in the next step we want to create a graph of location with attributes and show all these attributes actually share across location for the sake of illustration this example looks like the previous example but we can assume that will have different set of vocation at that stage at the intent of the previous step was to focus on non businesses while this step takes care of everything else all the other locations so we start with the location containing attributes you know represented to the left and then again we use flat map to get location kid by attributes we then do a group by which group locations in Opera tribute we can see here that the blue and the green location share common attributes and then we can create you know vertices for the attribute images based on location to our tribulation ships and end up with a graph to the right which not you you can see know the various location and the various attributes and you can see already you know which one are being basically shared so graph problem like page rank or connected component our frequently solved by our sending messages from vertices to the neighbors so aggregate messages provide the functional abstraction for aggregating neighbor information on the spa graph conceptually it's a lil bit similar to map and reduce for graph and consists of two steps defined by the user the same function accesses information about the edge triplet and passes that information to its source or destination node and the merge function is used to aggregate those messages at each node so here we can see an example on a simplify graph here we can see two location sharing a domain and we define a semi dysfunction that send the source ID NM to its neighbors and the merge function with simply aggregation of values running this on our graph yield the sequence of location for this domain so in that case the green and blue locations and we will use that function later it's essentially a way to play the graph in Mecca gregation our graph you already have so in the previous steps we have killing location over attributes in that step we want to link locations based on shared tributes to the left we have the location to attribute graph that we created previously and now we use aggregate message function explained before to reconstruct the key attribute location again in theory you could have used you know some of the perform some of the computations we did before but here the goal is to show that we can necessarily recompute that directly from the graph the next step is to do combination to the antenna for doing that is to start comparing each location with every other location in a graft will emit bad relationships because you can have location that share maybe something common but it can be like an arrow our times in this simple example we only have two locations and we only have to perform a single comparison but the number of comparison we'll go up as we have more locations right and we then apply a filtering function that will compare or similar the two places are so at a minimum you will apply some sophisticated in a matching but we uses or techniques as well any night example we can see that the green and blue places are similar so we create a relationship just to know Tom coalition to its sin square for the worse case scenario right so in case we have for instance where we have an auction where all locations share common domain this will create an expensive you know set of operations so an optimization for large groups is to fund the most common representative location and to compare essentially all those locations you know against you know that one and there that the price to pay is kind of like approximation compared to a quadratic right so we go from linear from karate to Lena complexity and that says a lot of compute timing on large clusters one last you know piece of code auger in we're using which is connected component it's actually computes to collected a company membership of each vertex and return a graph with the vertex value containing the lowest their tax ID in the group so in that particular example we call collect the components on the location graph and get two connected groups so in this step we call connected component on the link location and create businesses we start the location that we have the essentially location to location graph we had before we call connected component and get to connect a group and then for each group we can create the business and there we can see that we now have a business to businesses to group of two businesses so the idea will be if you have a number of starbucks location you want to link all those starbucks location together and you can want to create the parent company for Starbuck and indeed we have also kind of likely bit more you know additional you know optimizations right as I'm getting near my time I'll kind of quickly go over the remaining slides there's a number of performance implication being done right there's a lot of optimization graphics but some of the things you can do when you really work on our graph is to try to keep the information on memory like vertices and edges for instance so that you can actually keep the graph minimal and rejoin you know the information you need in addition to later checkpointing is also a way to improve performance because in spark connected component is a very iterative algorithm and it will keep the lineage in memory so if you actually a do checkpointing you your edges the lineage and improve performance now that we have graph of link location to business we can start doing a lot more step from the interest of tough time I will not detail them but they include for instance assigning the headquarter joining additional information that belong to the business via season given location like revenue information i'll come information headquarter and so forth and eventually we get a full graph by adding all those types of information available and there from there this business graph will be used by our SAS to automatically proposed relevant businesses you know or for customers the benefit of using a graph is we can easily visualize to understand the data and improve it the minute you start looking at the day I you know through graph lens you can find relationships and you can find a lot of ways and it will improve the data so in that simple example we have a small you know medium-sized in our Burger King to the left where we kid in all the location based on the graph in a connected component and we can see to the right essentially all the location map into the business location this is a larger example for retail chain with like tens of thousands of location and you can like consumed in an art and starts producing relationship the graph you know search and start really understanding what's going on in your system so in the interest of time I will just review your few lessons own which is essentially using a graph is a very intuitive natural way to moderation ship the wall is connected in loops a graph a new type of technology like graphics make it very easy to export the graph creating a graph our DD operation is very simple it's also very scalable in our case we use over 250 million vertices and 1 billion edges in the clustering step and educating is always a much of enough right and a science there's always constant in a way as and constant you know things we are doing to kind of improve yer estic as we create the graph and I collected component analysis celebration but if you actually take care of it you can complete you know pretty far on a large cluster I'm cannot really enough time already I'm not have time for a question of to know so come to me come to me afterwards if you have any questions thank you