Search for: All records

Abstract American Community Survey (ACS) data have become the workhorse for the empirical analysis of segregation in the U.S.A. during the past decade. The increased frequency the ACS offers over the 10-year Census, which is the main reason for its popularity, comes with an increased level of uncertainty in the published estimates due to the reduced sampling ratio of ACS (1:40 households) relative to the Census (1:6 households). This paper introduces a new approach to integrate ACS data uncertainty into the analysis of segregation. Our method relies on variance replicate estimates for the 5-year ACS and advances over existing approaches by explicitly taking into account the covariance between ACS estimates when developing sampling distributions for segregation indices. We illustrate our approach with a study of comparative segregation dynamics for 29 metropolitan statistical areas in California, using the 2010–2014 and 2015–2019. Our methods yield different results than the simulation technique described by Napierala and Denton (Demography 54(1):285–309, 2017). Taking the ACS estimate covariance into account yields larger error margins than those generated with the simulated approach when the number of census tracts is large and minority percentage is low, and the converse is true when the number of census tracts is small and minority percentage is high. 

This paper studies the spatial group-by query over complex polygons. Given a set of spatial points and a set of polygons, the spatial group-by query returns the number of points that lie within the boundaries of each polygon. Groups are selected from a set of non-overlapping complex polygons, typically in the order of thousands, while the input is a large-scale dataset that contains hundreds of millions or even billions of spatial points. This problem is challenging because real polygons (like counties, cities, postal codes, voting regions, etc.) are described by very complex boundaries. We propose a highly-parallelized query processing framework to efficiently compute the spatial group-by query on highly skewed spatial data. We also propose an effective query optimizer that adaptively assigns the appropriate processing scheme based on the query polygons. Our experimental evaluation with real data and queries has shown significant superiority over all existing techniques. 

ABSTRACT The Doubly Connected Edge List (DCEL) is an edge-list structure that has been widely utilized in spatial applications for planar topological computations. An important operation is the overlay which combines the DCELs of two input layers and can easily support spatial queries like the intersection, union and difference between these layers. However, existing sequential implementations for computing the overlay do not scale and fail to complete for large datasets (for example the US census tracks). In this paper we propose a distributed and scalable way to compute the overlay operation and its related supported queries. We address the issues involved in efficiently distributing the overlay operator and over various optimizations that improve performance. Our scalable solution can compute the overlay of very large real datasets (32M edges) in few minutes. 

Abstract—The Doubly Connected Edge List (DCEL) is a popular data structure for representing planar subdivisions and is used to accelerate spatial applications like map overlay, graph simplification, and subdivision traversal. Current DCEL imple- mentations assume a standalone machine environment, which does not scale when processing the large dataset sizes that abound in today’s spatial applications. This paper proposes a Distributed Doubly Connected Edge List (DDCEL) data structure extending the DCEL to a distributed environment. The DDCEL constructor undergoes a two-phase paradigm to generate the subdivision’s vertices, half-edges, and faces. After spatially partitioning the input data, the first phase runs the sequential DCEL construction algorithm on each data partition in parallel. The second phase then iteratively merges information from multiple data parti- tions to generate the shared data structure. Our experimental evaluation with real data of road networks of up to 563 million line segments shows significant performance advantages of the proposed approach over the existing techniques.