CS 348 Project: Where are the People?

The file CenPop2010.txt (distributed with the project files) contains real data published by the U.S. Census Bureau. The data divides the U.S. into 220,333 geographic areas called "census-block-groups" and reports for each such group the population in 2010 and the latitude/longitude of the group. It actually reports the average latitude/longitude of the people in the group, but that will not concern us: just assume everyone in the group lived on top of each other at this single point.

Given this data, we can imagine the entire U.S. as a giant rectangle bounded by the minimum and maximum latitude/longitude of all the census-block-groups. Most of this rectangle will not have any population:

• The rectangle includes all of Alaska, Hawaii, and Puerto Rico and therefore, since it is a rectangle, a lot of ocean and Canada that have no U.S. popluation.
• The continental U.S. is not a rectangle. For example, Maine is well East of Florida, adding more ocean.

Note that the provided code reads in the input data and changes the latitude for each census group. That is because the Earth is spherical but our grid is rectangular. Our code uses the Mercator Projection to map a portion of a sphere onto a rectangle. It stretches latitudes more as you move North. You do not have to understand this except to know that the latitudes you will compute with are not the latitudes in the input file. If you find it helpful to do so, you can change the code to disable this projection during your testing.

We can next imagine answering queries related to areas inside the U.S.:

1. For some rectangle inside the U.S. rectangle, what is the 2010 census population total?
2. For some rectangle inside the U.S. rectangle, what percentage of the total 2010 census U.S. population is in it?

Such questions can reveal that population density varies dramatically in different regions, which explains, for example, how a presidential candidate can win despite losing the states that account for most of the country's geographic area. By supporting only rectangles as queries, we can answer queries more quickly.

Your program will first process the data to find the four corners of the rectangle containing the United States. Some versions of the program will then further preprocess the data to build a data structure that can efficiently answer the queries described above. The program will then prompt the user for such queries and answer them until the user chooses to quit. For testing and timing purposes, you may also wish to provide an alternative where queries are read from a second file. We also provide you a graphical interface that makes asking queries more fun.

The provided code will take care of parsing the input file (sequentially), performing the Mercator Projection, and putting the data you need in a large array. The provided code uses float instead of double since the former is precise enough for the purpose of representing latitude/longitude and takes only half the space.

The provided code includes a main function in the PopulationQuery class that takes four command-line arguments:

1. The file containing the input data.
2. x, the number of columns in the grid for queries.
3. y, the number of rows in the grid for queries.
4. One of -v1, -v2, -v3, -v4, -v5 corresponding to which version of your implementation to use.

Suppose the values for x and y are 100 and 50. That would mean we want to think of the rectangle containing the entire U.S. as being a grid with 100 columns (the x-axis) numbered 1 through 100 from West to East and 50 rows (the y-axis) numbered 1 through 50 from South to North. (Note we choose to be "user friendly" by not using zero-based indexing.) So the grid would have 5000 little rectangles in it. Larger x and y will let us answer queries more precisely but will require more time and/or space.

The program answers queries about the census data. A query describes a rectangle within the U.S. using the grid. It is simply four numbers:

• The westernmost column that is part of the rectangle; error if this is less than 1 or greater than x.
• The southernmost row that is part of the rectangle; error if this is less than 1 or greater than y.
• The easternmost column that is part of the rectangle; error if this is less than the westernmost column (equal is okay) or greater than x.
• The northernmost row that is part of the rectangle; error if this is less than the southernmost column (equal is okay) or greater than y.

main then repreatedly prints a single one-line prompt asking for these four numbers, reads them in, and outputs two numbers:

• The total population in the queried rectangle.
• The percentage of the total U.S. population in the queried rectangle.

Here is an example of running main, querying the population of Alaska, the entire US, and Puerto Rico, in that order.

$ java PopulationQuery CenPop2010.txt 108 149 -v1
Query? (west south east north | quit) 1 81 44 149
Query population:     710231
Percent of total:       0.23%
Query? (west south east north | quit) 1 1 108 149
Query population:  312471327
Percent of total:     100.00%
Query? (west south east north | quit) 1 1 108 2
Query population:    3725789
Percent of total:       1.19%
Query? (west south east north | quit) quit

The provided main function works by calling two functions that you need to implement:

public void preprocess(int x, int y, int versionNum);
public Pair<Integer, Float> singleInteraction(int w, int s, int e, int n);

The preprocess method assumes that the input file has already been parsed into an array. This method performs any necessary preprocessing for the given version of your implementation. We'll go into much more detail on each version in a moment, but, for example, for versions 1 and 2 you will need to find the minimum and maximum latitude and longitude. The arguments to the preprocess method are x and y, the number of columns and rows in the map grid, respectively, and versionNum, an integer from 1 to 5 representing the version of the implementation you should be using. The preprocess method may be called more than once; each time you should restart processing from the parsed data array.

The singleInteraction method performs a single query using the implementation version most recently passed to preprocess. The arguments to the singleInteraction method are the four numbers described earlier: the west-, south-, east-, and northern most blocks in the query rectangle. This method should determine the population size and the population percentage of the U.S. given the parameters and return those two pieces of information as a Pair.

You will implement 5 versions of your program. There are significant opportunities to share code among the different versions, so do so if you can!

The write-up requires you to measure the performance (running time) of various implementations with different parameter settings. To report interesting results properly, you should use a machine with at least four processors and report relevant machine characteristics. The lab machines should work, although you should make sure no one else is using the machine for experiments at the same time as you. Open a terminal and enter w; that will show you if anyone is logged in remotely.

You will also need to report interesting numbers more relevant to long-running programs. In particular you need to:

• Not measure time parsing the data out of the input file.
• Allow the Java Virtual Machine and the ForkJoin Framework to "warm up" before taking measurements. The easiest way to do this is to put the initial processing in a loop and not count the first few loop iterations which are probably slower. While this is wasted work for your program, (a) you should do this only for timing experiements and (b) this may give a better sense of how your program would behave if run many times, run for a long time, or run on more data.
• Try to avoid having your experiments be interrupted by Java's garbage collector. You can do this by running System.gc() just before starting your experiment.
• Write extra code to perform the experiments, but this code should not interfere with your working program. You do not want to sit entering queries manually in order to collect timing data.

I also got much more worthwhile timing numbers by concatenating the cenus data file to itself a bunch of times. This effectively made it larger, which increased the benefit of parallel computation. You shouldn't do this for the final submission that requires correct answers, but you could do so for timing measurements.

For guidelines on what experiments to run, see the Write-Up Questions. Note you may not have the time or resources to experiment with every combination of every parameter; you will need to choose wisely to reach appropriate conclusions in an effective way.