More Like this

1. Pyneapple-G: Scalable Spatial Grouping Queries

   https://doi.org/10.14778/3685800.3685902  

   Abdelhafeez, Laila; Calderon-Romero, Andres; Magdy, Amr; Tsotras, Vassilis J (August 2024, Proceedings of the VLDB Endowment)

   This paper demonstratesPynapple-G, an open-source library for scalable spatial grouping queries based on Apache Sedona (formerly known as GeoSpark). We demonstrate two modules, namely,SGPACandDDCEL, that support grouping points, grouping lines, and polygon overlays. TheSGPACmodule provides a large-scale grouping of spatial points by highly complex polygon boundaries. The grouping results aggregate the number of spatial points within the boundaries of each polygon. TheDDCELmodule provides the first parallelized algorithm to group spatial lines into a DCEL data structure and discovers planar polygons from scattered line segments. Exploiting the scalable DCEL, we support scalable overlay operations over multiple polygon layers to compute the layers' intersection, union, or difference. To showcasePyneapple-G, we have developed a frontend web application that enables users to interact with these modules, select their data layers or data points, and view results on an interactive map. We also provide interactive notebooks demonstrating the superiority and simplicity ofPyneapple-Gto help social scientists and developers explore its full potential. 

   more » « less
2. Mapper Interactive: A Scalable, Extendable, and Interactive Toolbox for the Visual Exploration of High-Dimensional Data

   https://doi.org/10.1109/PacificVis52677.2021.00021  

   Zhou, Youjia; Chalapathi, Nithin; Rathore, Archit; Zhao, Yaodong; Wang, Bei (April 2021, IEEE 14th Pacific Visualization Symposium (PacificVis))

   The mapper algorithm is a popular tool from topological data analysis for extracting topological summaries of high-dimensional datasets. In this paper, we present Mapper Interactive, a web-based framework for the interactive analysis and visualization of high-dimensional point cloud data. It implements the mapper algorithm in an interactive, scalable, and easily extendable way, thus supporting practical data analysis. In particular, its command-line API can compute mapper graphs for 1 million points of 256 dimensions in about 3 minutes (4 times faster than the vanilla implementation). Its visual interface allows on-the-fly computation and manipulation of the mapper graph based on user-specified parameters and supports the addition of new analysis modules with a few lines of code. Mapper Interactive makes the mapper algorithm accessible to nonspecialists and accelerates topological analytics workflows. 

   more » « less
3. SGPAC: Generalized Scalable Spatial GroupBy Aggregations over Complex Polygons

   https://doi.org/10.1007/s10707-023-00491-8  

   Abdelhafeez, Laila; Magdy, Amr; Tsotras, Vassilis J. (October 2023, GeoInformatica)

   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. 

   more » « less
4. Preparing, Visualizing, and Using Real-world Data in Introductory Courses

   https://doi.org/10.1145/3159450.3159616  

   Bart, Austin Cory; Subramanian, Kalpathi; Anderson, Ruth E.; Hamid, Nadeem Abdul (January 2018, ACM Special Interest Group on Computer Science Education 2018)

   In recent years, interactive textbooks have gained prominence in an effort to overcome student reluctance to routinely read textbooks, complete assigned homeworks, and to better engage students to keep up with lecture content. Interactive textbooks are more structured, contain smaller amounts of textual material, and integrate media and assessment content. While these are an arguable improvement over traditional methods of teaching, issues of academic integrity and engagement remain. In this work we demonstrate preliminary work on building interactive teaching modules for data structures and algorithms courses with the following characteristics, (1) the modules are highly visual and interactive, (2) training and assessment are tightly integrated within the same module, with sufficient variability in the exercises to make it next to impossible to violate academic integrity, (3) a data logging and analytic system that provides instantaneous student feedback and assessment, and (4) an interactive visual analytic system for the instructor to see students’ performance at the individual, sub-group or class level, allowing timely intervention and support for selected students. Our modules are designed to work within the infrastructure of the OpenDSA system, which will promote rapid dissemination to an existing user base of CS educators. We demonstrate a prototype system using an example dataset. 

   more » « less
5. Hierarchical Filter and Refinement System Over Large Polygonal Datasets on CPU-GPU

   https://doi.org/10.1109/HiPC.2019.00027  

   Liu, Yiming; Yang, Jie; Puri, Satish (December 2019, 2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC))

   In this paper, we introduce our hierarchical filter and refinement technique that we have developed for parallel geometric intersection operations involving large polygons and polylines. The inputs are two layers of large polygonal datasets and the computations are spatial intersection on a pair of cross-layer polygons. These intersections are the compute-intensive spatial data analytic kernels in spatial join and map overlay computations. We have extended the classical filter and refine algorithms using PolySketch Filter to improve the performance of geospatial computations. In addition to filtering polygons by their Minimum Bounding Rectangle (MBR), our hierarchical approach explores further filtering using tiles (smaller MBRs) to increase the effectiveness of filtering and decrease the computational workload in the refinement phase. We have implemented this filter and refine system on CPU and GPU by using OpenMP and OpenACC. After using R-tree, on average, our filter technique can still discard 69% of polygon pairs which do not have segment intersection points. PolySketch filter reduces on average 99.77% of the workload of finding line segment intersections. PNP based task reduction and Striping algorithms filter out on average 95.84% of the workload of Point-in-Polygon tests. Our CPU-GPU system performs spatial join on two shapefiles, namely USA Water Bodies and USA Block Group Boundaries with 683K polygons in about 10 seconds using NVidia Titan V and Titan Xp GPU. 

   more » « less