1 of 10

Devika Kakkar

Harvard University, CGA

kakkar@fas.harvard.edu

Measurement of Partisan Segregation of 180 million U.S. voters using advanced GIS Data Science

2 of 10

Project Overview

Objective: Measure partisan segregation at individual level for 180 Million U.S. voters

This work is partially sponsored by NSF Awards #1841403 and OmniSci

3 of 10

Challenges: Big geospatial data processing

	Traditional method	Challenges
K-Nearest Neighbor search	Creating pairwise distance matrix and sorting on distance Buffer method	Dataset of 180 Million records implies trillion calculations Traditional method are slow and inefficient
Partisan exposure calculations	Execute using scripting language e.g., Python, R	Partisan weight calculations from 180 Billion distances Scripting methods are slow and resource intense I/O speed is very slow

[Images: Nature Human Behaviour]

In this problem, we have residential addresses for 180 M voters. To calculate partisan exposure, first we need to find nearest neighbors of each voter and then, we need to compute a spatially weighted metric that would represent the exposure index. Now let me tell you why traditional methods fail in the case of this dataset.

The nearest neighbor calculation is easy when you have a smaller number but when we talk about searching through 180 million individuals that implies more than a trillion calculations when using traditional methods of sorting by distance or buffering.

Similarly, computing spatially weighted metrics by processing 180 B would be way too slow in python and R for big geospatial data such as this one. That's why we have to apply GIS data science to solve this complex problem.

4 of 10

Solution: Available Computing Resources

+

5 of 10

Solution: Two-Layered Approach for KNN Calculations

1. Geohash based Spatial Clustering

2. R-tree based Index Search

Coordinates expressed as alphanumeric string
Longer the shared prefix, closer the points
Closer points clustered together on disk
Provides fast and efficient access to data

Pure spatial Index based search
Faster, cheaper and more efficient
Searches up and down the Bounding boxes

6 of 10

Solution: Accelerated GPU based processing of partisan exposure

180 Billion relations

180 million�voters

1000 neighbors

Now we have all the distances 180 B computed. We need to use that to give every voter a partisan index. We use the IDW method using the distance and neighbours partisan affiliation to come up with the exposure and isolation index for every voter. Again, the tradition methods such as Python/ R are slow and I/O is inefficient for such large data. Now Omnisci, the GPU accelerated platform comes into picture and we use that to calculate the index. Omni Sci allows what we call the “hot data” to be in GPU memory so the access becomes very fast. So what we need to do is divided the country into chunks and every chunk is fed to the hot memory of the GPU to provides a super fast access and then in the end we combine the results of every chunk. This helps us to calculation partisan weight at speed of 800 million records per sec.

7 of 10

Solution: Novelty of our approach

KNN calculations @ 200,000 distances/sec

Partisan weights @ 800M distances/sec

Accelerated GPU processing

Big geospatial data using Data Science

Extremely fast I/O on big data

Cost and Time Effective

8 of 10

Results: Partisan exposure of individual US voters

[Images: Nature Human Behaviour]

9 of 10

Results: Publications and news coverage

10 of 10

References

[1] Brown J. & Enos R., The measurement of partisan sorting for 180 million voters, Nature Human Behavior, 2021 https://www.nature.com/articles/s41562-021-01066-z.epdf

[2] Badger B., Quealy K. & Katz. J, A Close-Up Picture of Partisan Segregation, Among 180 Million Voters, The New York Times, 2021 https://www.nytimes.com/interactive/2021/03/17/upshot/partisan-segregation-maps.html

[3] Kakkar D., Lewis B., Singh R., OmniSci Virtual Summit, 2020 https://www.youtube.com/watch?v=3DlOeWqDMSs

[4] Kakkar D., Lewis B., Scaling geospatial processes on Harvard’s high-performance cluster, Harvard DataFest, 2020 https://drive.google.com/file/d/1FEnh-okCNLuthtyQtoBldyid7D6Sb-F_/view?usp=sharing

[5] Introduction to Cluster Computing on FASRC: https://www.rc.fas.harvard.edu/wp-content/uploads/2019/12/Intro-to-Cannon.pdf

[6] About Postgis: https://postgis.net/

[7] OmniSci Overview: https://docs.omnisci.com/latest/4_distributed.html