<commit_before># Traveling in the Big Apple

The Association for Computer Machinery holds annually the International Conference on Distributed Event-Based Systems (ACM DEBS).
This conference includes a Grand Challenge which aims at providing a common ground and evaluation criteria for both research and industrial event-based systems.
This practical is freely inspired from the [ACM DEBS 2015 Grand Challenge](http://www.debs2015.org/call-grand-challenge.html).

In this practical, we focus on the processing of a data stream originating from the New York City (NYC) Taxi and Limousine Commission.
This data is made available under the Freedom of Information Law and provides information regarding the pickups, drops-off, and payments made in the NYC medallion taxis.
The goal is to process this spatio-temporal data stream in order to find the most frequent routes.
We shall use [Apache Spark](http://spark.apache.org).

## 1. Data

We consider the first 20 days of year 2013.
This data set is available locally at `b313-13.int-evry.fr:/tmp/challenge/data.csv`.
It weights approximately 350MB.
You can copy it using SSH (`scp` command).

This data set reports the NYC taxi trips.
It includes the starting and drop-off points, their corresponding timestamps, as well as some information related to the payment.
Data are reported at the end of the trip, that this in the order of their drop-off timestamps.
With more details, the attributes of each tuple in the stream are as follows:

* **medallion**	an md5sum of the identifier of the taxi - vehicle bound
* **hack_license**	an md5sum of the identifier for the taxi license
* **pickup_datetime**	time when the passenger(s) were picked up
* **dropoff_datetime**	time when the passenger(s) were dropped off
* **trip_time_in_secs**	duration of the trip
* **trip_distance	trip** distance in miles
* **pickup_longitude**	longitude coordinate of the pickup location
* **pickup_latitude**	latitude coordinate of the pickup location
* **dropoff_longitude**	longitude coordinate of the drop-off location
* **dropoff_latitude**	latitude coordinate of the drop-off location
* **payment_type**	the payment method - credit card or cash
* **fare_amount**	fare amount in dollars
* **surcharge**	surcharge in dollars
* **mta_tax**	tax in dollars
* **tip_amount**	tip in dollars
* **tolls_amount**	bridge and tunnel tolls in dollars
* **total_amount**	total paid amount in dollars

Next, you will find the first ten line of the data file:

	07290D3599E7A0D62097A346EFCC1FB5,E7750A37CAB07D0DFF0AF7E3573AC141,2013-01-01 00:00:00,2013-01-01 00:02:00,120,0.44,-73.956528,40.716976,-73.962440,40.715008,CSH,3.50,0.50,0.50,0.00,0.00,4.50
	22D70BF00EEB0ADC83BA8177BB861991,3FF2709163DE7036FCAA4E5A3324E4BF,2013-01-01 00:02:00,2013-01-01 00:02:00,0,0.00,0.000000,0.000000,0.000000,0.000000,CSH,27.00,0.00,0.50,0.00,0.00,27.50
	0EC22AAF491A8BD91F279350C2B010FD,778C92B26AE78A9EBDF96B49C67E4007,2013-01-01 00:01:00,2013-01-01 00:03:00,120,0.71,-73.973145,40.752827,-73.965897,40.760445,CSH,4.00,0.50,0.50,0.00,0.00,5.00
	1390FB380189DF6BBFDA4DC847CAD14F,BE317B986700F63C43438482792C8654,2013-01-01 00:01:00,2013-01-01 00:03:00,120,0.48,-74.004173,40.720947,-74.003838,40.726189,CSH,4.00,0.50,0.50,0.00,0.00,5.00
	3B4129883A1D05BE89F2C929DE136281,7077F9FD5AD649AEACA4746B2537E3FA,2013-01-01 00:01:00,2013-01-01 00:03:00,120,0.61,-73.987373,40.724861,-73.983772,40.730995,CRD,4.00,0.50,0.50,0.00,0.00,5.00
	5FAA7F69213D26A42FA435CA9511A4FF,00B7691D86D96AEBD21DD9E138F90840,2013-01-01 00:02:00,2013-01-01 00:03:00,60,0.00,0.000000,0.000000,0.000000,0.000000,CRD,2.50,0.50,0.50,0.25,0.00,3.75
	DFBFA82ECA8F7059B89C3E8B93DAA377,CF8604E72D83840FBA1978C2D2FC9CDB,2013-01-01 00:02:00,2013-01-01 00:03:00,60,0.39,-73.981544,40.781475,-73.979439,40.784386,CRD,3.00,0.50,0.50,0.70,0.00,4.70
	1E5F4C1CAE7AB3D06ABBDDD4D9DE7FA6,E0B2F618053518F24790C7FD0264E302,2013-01-01 00:03:00,2013-01-01 00:04:00,60,0.00,-73.993973,40.751266,0.000000,0.000000,CSH,2.50,0.50,0.50,0.00,0.00,3.50
	468244D1361B8A3EB8D206CC394BC9E9,BB899DFEA9CC964B50C540A1D685CCFB,2013-01-01 00:00:00,2013-01-01 00:04:00,240,1.71,-73.955383,40.779728,-73.967758,40.760326,CSH,6.50,0.50,0.50,0.00,0.00,7.50
	5F78CC6D4ECD0541B765FECE17075B6F,B7567F5BFD558C665D23B18451FE1FD1,2013-01-01 00:00:00,2013-01-01 00:04:00,240,1.21,-73.973000,40.793140,-73.981453,40.778465,CRD,6.00,0.50,0.50,1.30,0.00,8.30

The data file is sorted chronologically according to the *dropoff_datetime*.
Events with the same dropoff_datetime are in random order.
Please note that the quality of the data is not perfect.
Some events might miss information such as drop off and pickup coordinates or fare information.
Moreover, some information, such as, e.g., the fare price might have been entered incorrectly by the taxi drivers thus introducing additional skew.
Handling of data quality issues is outside of the scope of this practical.

## 2. The Challenge

The challenge of this practical is to find the top 10 most frequent cab routes.
A route is represented by a starting grid cell and an ending grid cell.

The cells for this query are squares of 500 m X 500 m.
The cell grid starts with cell 1.1, located at 41.474937, -74.913585 (in Barryville).
The coordinate 41.474937, -74.913585 marks the center of the first cell.
Cell numbers increase towards the east and south, with the shift to east being the first and the shift to south the second component of the cell, i.e., cell 3.7 is 2 cells east and 6 cells south of cell 1.1.

The overall grid expands 150km south and 150km east from cell 1.1 with the cell 300.300 being the last cell in the grid.
All trips starting or ending outside this area are treated as *outliers* and must not be considered in the result computation.

## 2.1 Tentative plan

Below, we propose you a tentative plan to implement the query in three phases.
In a nutshell, our idea is first to solve the problem statically, when considering a chunk of the data.
In this task, we do not consider the grid of cells, but solely each route.
Then, we refine our solution and solve the online problem, leveraging the streaming capabilities of Spark.
In the last phase, we process the data this time taking into account the grid.

All our code snippet below are in Python -- but one may adapt them it to Scala (or Java).
In addition, we use the command *spark-submit* to submit the job locally (using *--master local script.py*).

### 2.1.1 Phase 1

1. Split the data into chunks of 1MB using the *split* command.
Hereafter, we shall use the first chunk, that is the file "aa".
2. Create a *SparkContex* object and use it to create an rdd from the file *frdd=sc.textFile("data/all")*.<commit_msg>spark<commit_after># Traveling in the Big Apple

The Association for Computer Machinery holds annually the International Conference on Distributed Event-Based Systems (ACM DEBS).
This conference includes a Grand Challenge which aims at providing a common ground and evaluation criteria for both research and industrial event-based systems.
This practical is freely inspired from the [ACM DEBS 2015 Grand Challenge](http://www.debs2015.org/call-grand-challenge.html).

In this practical, we focus on the processing of a data stream originating from the New York City (NYC) Taxi and Limousine Commission.
This data is made available under the Freedom of Information Law and provides information regarding the pickups, drops-off, and payments made in the NYC medallion taxis.
The goal is to process this spatio-temporal data stream in order to find the most frequent routes.
We shall use [Apache Spark](http://spark.apache.org).

## 1. Data

We consider the first 20 days of year 2013.
This data set is available locally at `b313-13.int-evry.fr:/tmp/challenge/data.csv`.
It weights approximately 350MB.
You can copy it using SSH (`scp` command).

This data set reports the NYC taxi trips.
It includes the starting and drop-off points, their corresponding timestamps, as well as some information related to the payment.
Data are reported at the end of the trip, that this in the order of their drop-off timestamps.
With more details, the attributes of each tuple in the stream are as follows:

* **medallion**	an md5sum of the identifier of the taxi - vehicle bound
* **hack_license**	an md5sum of the identifier for the taxi license
* **pickup_datetime**	time when the passenger(s) were picked up
* **dropoff_datetime**	time when the passenger(s) were dropped off
* **trip_time_in_secs**	duration of the trip
* **trip_distance	trip** distance in miles
* **pickup_longitude**	longitude coordinate of the pickup location
* **pickup_latitude**	latitude coordinate of the pickup location
* **dropoff_longitude**	longitude coordinate of the drop-off location
* **dropoff_latitude**	latitude coordinate of the drop-off location
* **payment_type**	the payment method - credit card or cash
* **fare_amount**	fare amount in dollars
* **surcharge**	surcharge in dollars
* **mta_tax**	tax in dollars
* **tip_amount**	tip in dollars
* **tolls_amount**	bridge and tunnel tolls in dollars
* **total_amount**	total paid amount in dollars

Next, you will find the first ten line of the data file:

	07290D3599E7A0D62097A346EFCC1FB5,E7750A37CAB07D0DFF0AF7E3573AC141,2013-01-01 00:00:00,2013-01-01 00:02:00,120,0.44,-73.956528,40.716976,-73.962440,40.715008,CSH,3.50,0.50,0.50,0.00,0.00,4.50
	22D70BF00EEB0ADC83BA8177BB861991,3FF2709163DE7036FCAA4E5A3324E4BF,2013-01-01 00:02:00,2013-01-01 00:02:00,0,0.00,0.000000,0.000000,0.000000,0.000000,CSH,27.00,0.00,0.50,0.00,0.00,27.50
	0EC22AAF491A8BD91F279350C2B010FD,778C92B26AE78A9EBDF96B49C67E4007,2013-01-01 00:01:00,2013-01-01 00:03:00,120,0.71,-73.973145,40.752827,-73.965897,40.760445,CSH,4.00,0.50,0.50,0.00,0.00,5.00
	1390FB380189DF6BBFDA4DC847CAD14F,BE317B986700F63C43438482792C8654,2013-01-01 00:01:00,2013-01-01 00:03:00,120,0.48,-74.004173,40.720947,-74.003838,40.726189,CSH,4.00,0.50,0.50,0.00,0.00,5.00
	3B4129883A1D05BE89F2C929DE136281,7077F9FD5AD649AEACA4746B2537E3FA,2013-01-01 00:01:00,2013-01-01 00:03:00,120,0.61,-73.987373,40.724861,-73.983772,40.730995,CRD,4.00,0.50,0.50,0.00,0.00,5.00
	5FAA7F69213D26A42FA435CA9511A4FF,00B7691D86D96AEBD21DD9E138F90840,2013-01-01 00:02:00,2013-01-01 00:03:00,60,0.00,0.000000,0.000000,0.000000,0.000000,CRD,2.50,0.50,0.50,0.25,0.00,3.75
	DFBFA82ECA8F7059B89C3E8B93DAA377,CF8604E72D83840FBA1978C2D2FC9CDB,2013-01-01 00:02:00,2013-01-01 00:03:00,60,0.39,-73.981544,40.781475,-73.979439,40.784386,CRD,3.00,0.50,0.50,0.70,0.00,4.70
	1E5F4C1CAE7AB3D06ABBDDD4D9DE7FA6,E0B2F618053518F24790C7FD0264E302,2013-01-01 00:03:00,2013-01-01 00:04:00,60,0.00,-73.993973,40.751266,0.000000,0.000000,CSH,2.50,0.50,0.50,0.00,0.00,3.50
	468244D1361B8A3EB8D206CC394BC9E9,BB899DFEA9CC964B50C540A1D685CCFB,2013-01-01 00:00:00,2013-01-01 00:04:00,240,1.71,-73.955383,40.779728,-73.967758,40.760326,CSH,6.50,0.50,0.50,0.00,0.00,7.50
	5F78CC6D4ECD0541B765FECE17075B6F,B7567F5BFD558C665D23B18451FE1FD1,2013-01-01 00:00:00,2013-01-01 00:04:00,240,1.21,-73.973000,40.793140,-73.981453,40.778465,CRD,6.00,0.50,0.50,1.30,0.00,8.30

The data file is sorted chronologically according to the *dropoff_datetime*.
Events with the same dropoff_datetime are in random order.
Please note that the quality of the data is not perfect.
Some events might miss information such as drop off and pickup coordinates or fare information.
Moreover, some information, such as, e.g., the fare price might have been entered incorrectly by the taxi drivers thus introducing additional skew.
Handling of data quality issues is outside of the scope of this practical.

## 2. The Challenge

The challenge of this practical is to find the top 10 most frequent cab routes.
A route is represented by a starting grid cell and an ending grid cell.

The cells for this query are squares of 500 m X 500 m.
The cell grid starts with cell 1.1, located at 41.474937, -74.913585 (in Barryville).
The coordinate 41.474937, -74.913585 marks the center of the first cell.
Cell numbers increase towards the east and south, with the shift to east being the first and the shift to south the second component of the cell, i.e., cell 3.7 is 2 cells east and 6 cells south of cell 1.1.

The overall grid expands 150km south and 150km east from cell 1.1 with the cell 300.300 being the last cell in the grid.
All trips starting or ending outside this area are treated as *outliers* and must not be considered in the result computation.

## 2.1 Tentative plan

Below, we propose you a tentative plan to implement the query in three phases.
In a nutshell, our idea is first to solve the problem statically, when considering a chunk of the data.
In this task, we do not consider the grid of cells, but solely each route.
Then, we refine our solution and solve the online problem, leveraging the streaming capabilities of Spark.
In the last phase, we process the data this time taking into account the grid.

All our code snippet below are in Python -- but one may adapt them it to Scala (or Java).
In addition, we use the command *spark-submit* to submit the job locally (using *--master local script.py*).

### 2.1.1 Phase 1

1. Split the data into chunks of 1MB using the Bash *split* command.
Hereafter, we shall use the first chunk, that is the file "aa".
2. Create a *SparkContex* object and use it to create an rdd from the file *frdd=sc.textFile("data/all")*.
{'fraction_non_alphanumeric': 0.09657344230336658, 'fraction_numerical': 0.1962960185948864, 'mean_word_length': 5.169287696577244, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '179707', 'n_tokens_mistral': 6258, 'n_tokens_neox': 4793, 'n_words': 1532}