Large Scale Data Processing: Project 2

Getting started

Head to Project 1 if you're looking for information on Git, template repositories, or setting up your local/remote environments.

Resilient distributed datasets in Spark

This project will familiarize you with RDD manipulations by implementing some of the sketching algorithms the course has covered thus far.

You have been provided with the program's skeleton, which consists of 5 functions for computing either F0 or F2: the BJKST, tidemark, tug-of-war, exact F0, and exact F2 algorithms. The tidemark and exact F0 functions are given for your reference.

Relevant data

You can find the TAR file containing 2014to2017.csv here. Download and expand the TAR file for local processing. For processing in the cloud, refer to the steps for creating a storage bucket in Project 1 and upload 2014to2017.csv.

2014to2017.csv contains the records of parking tickets issued in New York City from 2014 to 2017. You'll see that the data has been cleaned so that only the license plate information remains. Keep in mind that a single car can receive multiple tickets within that period and therefore appear in multiple records.

Hint: while implementing the functions, it may be helpful to copy 100 records or so to a new file and use that file for faster testing.

Calculating and reporting your findings

You'll be submitting a report along with your code that provides commentary on the tasks below.

1. (3 points) Implement the exact_F2 function. The function accepts an RDD of strings as an input. The output should be exactly F2 = sum(Fs^2), where Fs is the number of occurrences of plate s and the sum is taken over all plates. This can be achieved in one line using the map and reduceByKey methods of the RDD class. Run exact_F2 locally and on GCP with 1 driver and 4 machines having 2 x N1 cores. Copy the results to your report. Terminate the program if it runs for longer than 30 minutes.
2. (3 points) Implement the Tug_of_War function. The function accepts an RDD of strings, a parameter width, and a parameter depth as inputs. It should run width * depth Tug-of-War sketches, group the outcomes into groups of size width, compute the means of each group, and then return the median of the depth means in approximating F2. A 4-universal hash function class four_universal_Radamacher_hash_function, which generates a hash function from a 4-universal family, has been provided for you. The generated function hash(s: String) will hash a string to 1 or -1, each with a probability of 50%. Once you've implemented the function, set width to 10 and depth to 3. Run Tug_of_War locally and on GCP with 1 driver and 4 machines having 2 x N1 cores. Copy the results to your report. Terminate the program if it runs for longer than 30 minutes. Please note that the algorithm won't be significantly faster than exact_F2 since the number of different cars is not large enough for the memory to become a bottleneck. Additionally, computing width * depth hash values of the license plate strings requires considerable overhead. That being said, executing with width = 1 and depth = 1 should generally still be faster.
3. (3 points) Implement the BJKST function. The function accepts an RDD of strings, a parameter width, and a parameter trials as inputs. width denotes the maximum bucket size of each sketch. The function should run trials sketches and return the median of the estimates of the sketches. A template of the BJKSTSketch class is also included in the sample code. You are welcome to finish its methods and apply that class or write your own class from scratch. A 2-universal hash function class hash_function(numBuckets_in: Long) has also been provided and will hash a string to an integer in the range [0, numBuckets_in - 1]. Once you've implemented the function, determine the smallest width required in order to achieve an error of +/- 20% on your estimate. Keeping width at that value, set depth to 5. Run BJKST locally and on GCP with 1 driver and 4 machines having 2 x N1 cores. Copy the results to your report. Terminate the program if it runs for longer than 30 minutes.
4. (1 point) Compare the BJKST algorithm to the exact F0 algorithm and the tug-of-war algorithm to the exact F2 algorithm. Summarize your findings.

Submission via GitHub

Delete your project's current README.md file (the one you're reading right now) and include your report as a new README.md file in the project root directory. Have no fear—the README with the project description is always available for reading in the template repository you created your repository from. For more information on READMEs, feel free to visit this page in the GitHub Docs. You'll be writing in GitHub Flavored Markdown. Be sure that your repository is up to date and you have pushed all changes you've made to the project's code. When you're ready to submit, simply provide the link to your repository in the Canvas assignment's submission.

You must do the following to receive full credit:

1. Create your report in the README.md and push it to your repo.
2. In the report, you must include your (and your group members') full name in addition to any collaborators.
3. Submit a link to your repo in the Canvas assignment.

Late submission penalties

Please refer to the course policy.

Write-up

Group members:

• Caden Parajuli
• Tian-hao Zhang

1. Computing $F_2$ exactly on a local machine produced the value 8567966130 in 26 seconds. The specifications of this local machine are:
   • Lenovo Thinkpad X13
     • AMD Ryzen 7 PRO 4750U
       • 8 cores, 16 threads
       • 1.7 GHz base, 4.2 GHz max
     • 16 GiB RAM

This was also run on a GCP cluster with 4 workers having 2 N1 cores each, which confirmed the result of 8567966130 in 57s.

2. A run of the Tug of War sketch with width 10 and depth 3 on the local machine (the same one as for exactF2) produced an estimate of 6392961048 for $F_2$ in 25 seconds.
   
   This was also run on a GCP cluster with 4 workers having 2 N1 cores each, which produced an estimate of 7174856114 in 108s

3. After doing much trial and error, the minimum width required to consistently achieve an error within 20% is about 5500. For example, one of the local runs gave this:

This was also run on a GCP cluster with 4 workers having 2 N1 cores each, which produced an estimate of 8435712 in 38s

4. Compared to the exact F0 algorithm, the BJKST ran almost three times as fast and was more memory-efficient than F0. The only thing that wasn't as good was the accuracy. While BJKST wasn't perfect like F0, it still gave an answer that was quite close.
   
   Computing $F_2$ exactly produced the value 8567966130 in 26 seconds on the local machine, compared to the 25 seconds the Tug of War sketch took produce an estimate of 6392961048 (both performed on the same local machine). Thus we see that the Tug of War takes approximately the same amount of time as the exact computation for this data, while being accurate to within about 25%. However, this accuracy varied, and performing additional runs produced the table below, which indicates that we can only assume about a 50% error.

Estimate	Time
6392961048	25s
4228856047	25s
7943122858	26s
4252007852	24s
6096010550	25s
10293972648	25s

Thus on this dataset, the exact F2 computation is preferably since it takes the same amount of time (or significantly less on the GCP cluster), and the Tug of War is significantly less accurate.