Design Considerations of Yelp

Introduction

The previous lesson covered the system architecture, core components, and overall workflow, which raised several open design questions. For example, how should the system retrieve nearby places, and how should it rank them by popularity? This lesson addresses these design concerns. The following table summarizes the objectives of this lesson.

Searching

Using Google Maps, we were able to connect segments and overcome the scalability challenge to efficiently process a large graph. The graph of the world had numerous nodes and vertices, and traversing them was time-consuming. Therefore, we divided the whole world into smaller segments/subgraphs to process and query them simultaneously. The segmentation helps improve the system’s scalability.

Each segment will be of the size $5 \times 5 \ \text{miles}$ and will contain a list of places that exist within it. We only search a few segments to find nearby destinations. We can use a given location and a defined radius to find all nearby segments and identify nearby sites.

We can store all the places in a table and uniquely identify a segment by having a segment_ID. We can index each segment in the database. Now, we have limited the number of segments we need to search, so the query will be optimized and return results quickly.

Improve data fetching

We use a key-value store for quick access to places in the segments. The key is the segment_ID, while the value contains the list of places in that segment. Let’s estimate how much space we need to store the indexes.

The total area of the Earth is around 200 million square miles, and the land surface area is about 60 million square miles. If we assume our radius is 10 miles, we’ll have 6 million segments. An 8-byte identifier will identify each segment.

Let’s calculate how much memory we need.

Search using segments

A user may select a radius to search for places that aren’t in a single segment. So, we need to combine multiple segments by connecting the segments to find locations within the specified radius—say, 5 miles.

First, we constrain the number of segments. This reduces the graph size and enables the search process to be optimized. Then, we identify all relevant locations, compute the distance to the search point, and display it to the user.

Dynamic segments

We solve the problem of uneven distribution of places in a segment by dynamically sizing the segments. We do this by focusing on the number of places. We split a segment into four more segments if the number of places reaches a certain limit. We assume 500 places as our limit. While using this approach, we need to decide on the following questions:

1. How will we map the segments?

2. How will we connect to other segments?

We use a QuadTreeA QuadTree is a tree data structure in which each internal node has exactly four children. QuadTrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a “unit of interesting spatial information”. Source: Wikipedia to manage our segments. Each node contains the information of a segment. If the number of places exceeds 500, we split the segment into four additional child nodes and divide the places among them. In this way, the leaf nodes will be those segments that can’t be broken down any further. Each leaf node will have a list of places in it, too.

Search using a QuadTree

We start at the root node and continue visiting nodes to find the desired segment. We check every node to see if it has more child nodes. If a node has no more children, then we stop our search because that node is the required one. We also connect each child node to its neighbors using a doubly linked list. All child nodes of all parent nodes are connected via a doubly linked list. This list allows us to find the neighboring segments when we need to move forward or backward, as per our requirements. After identifying the segments, we have the required PlaceID values of the places, and we can search our ...