Spatial networks partitioning underpins diverse spatial applications such as dividing regions around task-allocation centers to optimize mobile crowdsourcing, adaptive partitioning of large datasets to improve load balancing in parallel spatial joins, segmenting geospatial knowledge graphs by spatial proximity to reduce cross-partition communication, and detecting geographically proximate communities. Traditional minimum k-way partitioning divides graphs into equal-sized partitions to minimize edge cuts, but this uniformity fails when regions require heterogeneous capacities (e.g., socioeconomic criteria like income or education levels). The Non-Uniform Graph Partitioning (NUGP) problem, in which partitions must obey application-specific size constraints, captures such non-uniformity. We introduce ReNUP; a tree-guided recursive algorithm that enforces non-uniform size constraints effectively and efficiently on large spatial networks. ReNUP is the first to empower users with a user-controllable violation threshold δ to balance size constraint adherence against edge-cut minimization. Experiments on ten real-world datasets demonstrate ReNUP's effectiveness and efficiency in enforcing non-uniform partitioning size constraints.

Quantum computing has shown significant potential to address complex optimization problems; however, its application remains confined to specific problems at limited scales. Spatial regionalization remains largely unexplored in quantum computing due to its complexity and large number of variables. In this paper, we introduce the first hybrid quantum-classical method to spatial regionalization by decomposing the problem into manageable sub-problems, leveraging the strengths of both classical and quantum computation. This study establishes a foundational framework for effectively integrating quantum computing methods into realistic and complex spatial optimization tasks. Our initial results show a promising quantum performance advantage for a broad range of spatial regionalization problems and their variants.

Spatial regionalization partitions a set of spatial polygons into contiguous, non-overlapping regions that optimize a specific objective function. This spatial operation serves diverse applications in environmental science, urban planning, public health, and economics. Due to the NP-hardness of this problem, most studies rely on heuristics and approximation techniques to balance solution quality with runtime efficiency. This tutorial reviews the main methods in the literature of spatial regionalization, organizing them into four categories: (i) linear and integer-programming formulations, (ii) top-down divisive strategies, (iii) bottom-up agglomerative strategies, and (iv) learning-based methods. For each category, we outline the core ideas and representative algorithms. We also discuss the open problems and future research directions.

Spatial regionalization seeks to partition a set of spatial polygons into contiguous, non-overlapping regions that optimize a specified objective function.This problem is fundamental in diverse applications across environmental science, urban planning, and public health, serving purposes such as resource allocation, policy formulation, and disease monitoring.Due to its computational complexity as an NP-hard problem, researchers typically rely on heuristics and approximation algorithms to achieve a practical balance between accuracy and runtime efficiency.This tutorial comprehensively reviews the main methodologies in the field, systematically categorizing them into three primary groups: (i) exact algorithms, (ii) top-down divisive strategies, and (iii) bottom-up agglomerative techniques.We detail each category by highlighting the core principles and representative algorithms.Furthermore, we identify and discuss open challenges in spatial regionalization.

Abstract The Doubly Connected Edge List (DCEL) is an edge-list structure widely used in spatial applications, primarily for planar topological and geometric computations. However, it is also applicable to various types of data, including 3D models and geographic data. An essential operation is the overlay operation, which combines the DCELs of two input polygon layers and can easily support spatial queries on polygons like the intersection, union, and difference between these layers. However, existing techniques for spatial overlay operations suffer from two main limitations. First, they fail to handle many large datasets practically used in real applications. Second, they cannot handle arbitrary spatial lines that practically form polygons, e.g., city blocks, but they are given as a set of scattered lines. This work proposes a distributed and scalable way to compute the overlay operation and its related supported queries. Our operations also support arbitrary spatial lines through a scalable polygonization process. We address the issues of efficiently distributing the lines and overlay operators and offer various optimizations that improve performance. Our experiments demonstrate that the proposed scalable solution can efficiently compute the overlay of large real datasets.

The rapid expansion of location-based services has generated an unprecedented volume of spatial data. Spatial grouping queries, which categorize sets of spatial objects based on their geographical properties and data characteristics, are fundamental in uncovering significant patterns from large-scale spatial data. This query type is applicable to both spatial points and spatial polygons. In the realm of spatial polygons, regionalization serves as a crucial grouping query by organizing spatial polygons into regions. For spatial points, hotspot detection over spatial networks identifies clusters that demonstrate areas of high concentration. However, existing algorithms often lack scalability, struggle with large datasets, and fail to offer the expressiveness needed to handle flexible, user-defined constraints. To address these limitations, this paper introduces novel algorithms tailored for enhanced spatial grouping queries, including both regionalization and hotspot detection.

This paper demonstrates Pyneapple-L, an open-source library designed to enhance scalable spatial analysis through learning-based techniques. Through collaboration with social scientists and domain experts, we identify scalability challenges inherent in conventional spatial analysis methods, particularly as the data size increases. Pyneapple-L addresses these challenges by leveraging learning-based models to offer scalable solutions. We demonstrate two modules: scalable learning of spatial hotspots along spatial networks and augmented geographically weighted regression. To showcase Pyneapple-L, we have developed a user-friendly frontend web application to interact with different datasets, algorithms, model configurations, and visualize outcomes on interactive maps that support both broad and analytical views.

This paper demonstrates Pyneapple-R, an open-source library for scalable and expressive regionalization. Re-gionalization algorithms, also known as the ‘spatially-constrained clustering algorithms', have been widely adopted in spatial analysis tasks and now evolving towards a more large-scale and fine-scale direction. Through collaborations with social scientists and domain experts, we have identified emerging challenges in existing regionalization techniques, particularly regarding scalability and expressiveness. As data volumes continue to grow and regionalization algorithms become increasingly crucial to decision-making across various fields, enhancing these aspects can significantly impact the quality and effectiveness of re-search and applications. To address these challenges, Pyneapple-R provides novel algorithms for regionalization queries including the expressive p-regions algorithm, the scalable max-p regions algorithm, and the expressive max-p regions problem. To show-case Pyneapple-R, we have developed frontend web applications that enable users to interact with the algorithms by selecting constraints or simply engaging in conversation with the system to issue queries with the help of popular AI models. Interactive notebooks, designed to demonstrate the superiority and simplicity of Pyneapple-R, provide varying levels of detail to help social scientists and developers explore its full potential.

This paper demonstrates Pynapple-G , an open-source library for scalable spatial grouping queries based on Apache Sedona (formerly known as GeoSpark). We demonstrate two modules, namely, SGPAC and DDCEL , that support grouping points, grouping lines, and polygon overlays. The SGPAC module 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. The DDCEL module 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 showcase Pyneapple-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 of Pyneapple-G to help social scientists and developers explore its full potential.

The process of regionalization involves clustering a set of spatial areas into spatially contiguous regions. Given the NP-hard nature of regionalization problems, all existing algorithms yield approximate solutions. To ascertain the quality of these approximations, it is crucial for domain experts to obtain statistically significant evidence on optimizing the objective function, in comparison to a random reference distribution derived from all potential sample solutions. In this paper, we propose a novel spatial regionalization problem, denoted as SISR (Statistical Inference for Spatial Regionalization), which generates random sample solutions with a predetermined region cardinality. The driving motivation behind SISR is to conduct statistical inference on any given regionalization scheme. To address SISR, we present a parallel technique named PRRP (P-Regionalization through Recursive Partitioning). PRRP operates over three phases: the region growing phase constructs initial regions with a predefined cardinality, while the region merging and region splitting phases ensure the spatial contiguity of unassigned areas, allowing for the growth of subsequent regions with predefined cardinalites. An extensive evaluation shows the effectiveness of PRRP using various real datasets.

The widespread of geotagged data combined with modern map services allows for the accurate attachment of data to spatial networks. Applying statistical analysis, such as hotspot detection, over spatial networks is very important for precise quantification and patterns analysis, which empowers effective decision-making in various important applications. Existing hotspot detection algorithms on spatial networks either lack statistical evidence on detected hotspots, such as clustering, or they provide statistical evidence at a prohibitive computational overhead. In this paper, we propose efficient algorithms for detecting hotspots based on the network local K-function for predefined and unknown hotspot radii. The network local K-function is a widely adopted statistical approach for network pattern analysis that enables the understanding of the density and distribution of activities and events in the spatial network. However, its practical application has been limited due to the inefficiency of existing algorithms, particularly for large-sized networks. Extensive experimental evaluation using real and synthetic datasets shows that our algorithms are up to 28 times faster than the state-of-the-art algorithms in computing hotspots with a predefined radius and up to more than four orders of magnitude faster in identifying hotspots without a predefined radius.

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 implementations 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 partitions 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.

Spatial regionalization is the process of combining a collection of spatial polygons into contiguous regions that satisfy user-defined criteria and objectives. Numerous techniques for spatial regionalization have been proposed in the literature, which employ varying methods for region growing, seeding, optimization and enforce different user-defined constraints and objectives. This paper introduces a scalable unified system for addressing seeding spatial regionalization queries efficiently. The proposed system provides a usable and scalable framework that employs a wide-range of existing spatial regionalization techniques and allows users to submit novel combinations of queries that have not been previously explored. This represents a significant step forward in the field of spatial regionalization as it provides a robust platform for addressing different regionalization queries. The system is mainly composed of three components: query parser, query planner, and query executor. Preliminary evaluations of the system demonstrate its efficacy in efficiently addressing various regionalization queries.

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 offer various optimizations that improve performance. Our scalable solution can compute the overlay of very large real datasets (32M edges) in few minutes.

Abstract 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.

MP-regions is an NP-hard problem that groups spatial areas to produce a maximum number of regions by enforcing a user-defined constraint at the regional level. Existing approximate algorithms for MP-regions do not scale for large datasets due to their high computational cost. This paper introduces SMP; a scalable technique to support MP-regions on large datasets. SMP works on two stages. The first stage finds an initial solution through randomized search, and the second stage improves this solution through efficient heuristic search. SMP optimizes the region building efficiency and quality by tuning the randomized area selection to trade-off runtime with region homogeneity. The experimental evaluation shows the superiority of our technique to support an order of magnitude larger datasets efficiently compared to the state-of-the-art techniques while producing high-quality solutions.

Spatial keyword queries have been popular in the research community for over a decade due to the explosive growth in user-generated data and its prime applications in different domains. kNN queries make a major category of spatial keyword queries that is heavily studied. However, the expressiveness of existing kNN queries is limited in supporting negative keyword predicates, e.g., find tweets with keywords "Chipotle" but NOT "Chipotle sauce", which have prime applications. In addition, existing architectures suffer from a lack of generality for different types of kNN queries. This paper proposes U-ASK; a Unified Architecture for Spatial-Keyword query supporting negative keyword predicates. U-ASK includes an indexing framework named TEQ (Textual-Enhanced Quadtree) and a query processor POWER (Parallel bOttom-up search With incrEmental pRuning) that handle various forms of kNN spatial keyword queries with negative keyword predicates. The experimental evaluation on real tweet datasets demonstrates up to 30× faster runtime compared to the state-of-the-art algorithms.

Spatial regionalization is the process of grouping a set of spatial areas into spatially contiguous and homogeneous regions. This paper introduces an enriched max-p-regions (EMP) problem; a regionalization process that allows enriched user-defined constraints based on SQL aggregate functions. In addition to enabling richer constraints, it enables users to employ multiple constraints simultaneously to significantly push the expressiveness and effectiveness of the existing regionalization literature. The EMP problem is NP-hard and significantly enriches the existing regionalization problems. Such a major enrichment introduces several challenges in both feasibility and scalability. To address these challenges, we propose the FaCT algorithm, a three-phase greedy approach that finds a feasible set of spatial regions that satisfy EMP constraints while supporting large datasets compared to the existing literature. Our extensive experimental evaluation has demonstrated the effectiveness and scalability of our techniques on several real datasets.

The excessive amount of data that online users produce through social media platforms provides valuable insights about users and communities at scale. Existing techniques have not fully exploited such data to help practitioners perform a deep analysis of large online communities. Lack of scalability hinders analyzing communities of large sizes and requires tremendous system resources and unacceptable runtime. This paper introduces a new analytical query that reveals the top-k posts of interest of a given user community over a period of time and in a certain location. We propose a novel indexing framework that captures the interactions of community users to provide a low query latency. Moreover, we propose efficient query algorithms that utilize the index content to prune the search space. The extensive experimental evaluation on real data has shown the superiority of our techniques and their scalability to support large online communities.

Geographically Weighted Regression (GWR) is a seminal technique with rich applications in geospatial data analysis. However, it has critical drawbacks in the age of big data in terms of expressiveness, i.e., predictive power, and scalability. This work proposes Augmented GWR (A-GWR) that alleviates these drawbacks. A-GWR adapts a novel technique, Stateless-MGWR or S-MGWR, that enriches the predictive power by allowing different training data features to influence at different spatial scales. S-MGWR uses a customized black-box optimization approach for discovering optimal parameters in a fast and efficient way. In addition, A-GWR modularly combines S-MGWR with versatile models such as random forest models. Moreover, A-GWR enables scalability by operating on partitioned data to adapt to tight computational budgets. Our extensive experiments on various real and synthetic datasets demonstrate the scalability and accuracy benefits of the proposed techniques over state-of-the-art competitors.

Selectivity and cardinality estimation are main driving factors for developing cheap query plans and ultimately faster query processing. Traditionally, database systems use estimation data structures, e.g., histograms, to maintain data summaries. Machine learning models have recently been employed, acting as black boxes, in several database tasks, including cardinality estimation. In the dynamic streaming environments, both estimation data structures and machine learning models struggle with adaptation for dynamic changes in data and query workloads. This paper proposes LATEST; a system module that uses machine learning to enable dynamic adaptation of estimation data structures. For spatial-keyword queries in a streaming environment, it shows on par or better performance than the state-of-the-art estimators. LATEST builds an incremental supervised learning model over a moving time window that helps the underlying system to switch among several estimation structures to keep estimation accuracy high at all times. As an incremental learner, LATEST effectively adapts to dynamic changes of both data and queries in streaming environments. Our extensive experiments on three real datasets and various query workloads verify the effectiveness of LATEST with higher accuracy and lower response times over the state-of-the-art estimators.

This paper introduces a generalized spatial regionalization problem, namely, PRUC ( P -Regions with User-defined Constraint) that partitions spatial areas into homogeneous regions. PRUC accounts for user-defined constraints imposed over aggregate region properties. We show that PRUC is an NP-Hard problem. To solve PRUC, we introduce GSLO (Global Search with Local Optimization), a parallel stochastic regionalization algorithm. GSLO is composed of two phases: (1) Global Search that initially partitions areas into regions that satisfy a user-defined constraint, and (2) Local Optimization that further improves the quality of the partitioning with respect to intra-region similarity. We conduct an extensive experimental study using real datasets to evaluate the performance of GSLO. Experimental results show that GSLO is up to 100× faster than the state-of-the-art algorithms. GSLO provides partitioning that is up to 6× better with respect to intra-region similarity. Furthermore, GSLO is able to handle 4× larger datasets than the state-of-the-art algorithms.

This paper studies a spatial group-by query over complex polygons. 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. Given a set of spatial points and a set of polygons, the spatial group-by query returns the number of points that lie within boundaries of each polygon. 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. Our experimental evaluation with real data and queries has shown significant superiority over all existing techniques.

This paper demonstrates DLEEL; a research system that supports scalable spatial queries with multiple predicates on user-generated data streams, such as social media streams. Supported queries include spatial-social queries and spatial-keyword queries, which are popular in different applications but have never been addressed in the challenging environment of streaming data, where data arrives with excessively high rates. DLEEL distinguishes itself with three novel contributions: (1) Indexing spatial-social data in for personalized real-time search: DLEEL is the first to address personalized queries on streaming spatial- social data through novel low-overhead indexing that scales for large amounts of data and users. The novel indexing has a hybrid storage architecture that trades off indexing overhead, memory consumption, and query latency. (2) Indexing spatial-keyword data for real-time search: DLEEL is the first to enrich existing spatial-keyword indexes with novel streaming data components. The new components reveal performance losses and gains from a system perspective, trading off the system overhead with flexibility to support a variety of queries. (3) Scalable query processing: DLEEL exploits the indexes content to smartly prune the search space on multiple dimensions and support efficient query latency for its different queries on excessive number of data records. DLEEL is demonstrated using a stream of 5 billions real tweets collected from Twitter APIs and real query locations obtained from a popular web search engine. DLEEL has shown superior performance with serving incoming queries with an average latency of few milliseconds while digesting hundreds of thousands of data records every second.

The unprecedented rise of social media platforms, combined with location-aware technologies, has led to continuously producing a significant amount of geo-social data that flows as a user-generated data stream. This data has been exploited in several important use cases in various application domains. This paper supports geo-social personalized queries in streaming data environments that have not been addressed in the existing literature. We define two temporal geo-social queries that provide users with real-time personalized answers based on their social graph. Then, we propose an indexing framework that provides lightweight and effective real-time indexing to digest geo-social data in real time. The framework distinguishes highly-dynamic data from relatively-stable data and uses appropriate data structures and storage tier for each. Based on this framework, we propose a novel geo-social index and adopt two baseline indexes to support the addressed queries. The query processor then employs different types of pruning to efficiently access the index content and provide real-time query response. The extensive experimental evaluation based on real datasets has shown the superiority of our proposed techniques to index real-time data and provide low-latency queries compared to existing competitors.

This paper demonstrates CleanUpOurWorld; a research spatial database that is designed and deployed to collect, process, query, and visualize anthropogenic litter data. Such data has a significant importance in the field of environmental sciences due to its important use cases. We make a major on-going effort to collect and maintain such data worldwide from different sources through a community of environmental scientists and partner organizations. With the increasing volume of data, existing software packages, such as GIS software, do not scale to process, query, and visualize such data. To overcome this, CleanUpOurWorld digests datasets from diferent sources, with different formats, in a scalable backend that cleans, integrates, and unifies them in a structured form in a relational spatial database. Frontend applications are built to visualize litter data at multiple spatial resolutions.

Event detection applications have gained significant attention with the rise of user-generated spatio-temporal data over the past decade. However, building event detection applications still encounter high cost and effort due to lack of support in existing data management systems. This paper envisions a holistic system approach to support an efficient and easy-to-use system infrastructure for building event detection applications. We outline our vision for representing event detection applications as a set of layered abstractions and discuss potential pathways to realize these abstractions at the system level.

This paper provides an extensive experimental evaluation for different spatial-keyword index structures on streaming data. We extend existing snapshot spatial-keyword queries with the temporal dimension to effectively serve streaming data applications. Then, the major index structures are equipped with efficient query processing techniques and evaluated to process the extended queries. The evaluation is oriented towards a system building perspective to provide system builders with insights on supporting scalable spatial-keyword queries on fast data streams, e.g., social media streams and news streams. In particular, we have taken existing spatial-keyword index structures apart into four major building blocks that are commonly supported at a system-level. Ten different index structures are then composed as combinations of these four building blocks. The ten indexes are wholly residents in main-memory, and they are evaluated on real datasets and query locations. The index performance is measured in terms of data digestion rate in real time, main-memory footprint, and query latency. The results show the relative performance gains of both basic and hybrid index structures with abundant insights from a system point of view.

Motivated by its wide availability and richness, there have been a plethora of recent work in querying, analyzing, and visualizing microblogs (see [3] for a brief survey). Examples of microblogs include tweets, online reviews, and comments on news websites. Unfortunately, existing work in microblog lacks data management tools that provide the necessary infrastructure to support efficient storage, indexing, and retrieval of microblogs. Hence, researchers, developers, and practitioners who need to process microblogs for their own purposes would need to either build their own ad-hoc techniques [5] or use any of existing general purpose big data engines, e.g., Spark, as their backbone [4]. Relying on ad-hoc techniques does not scale for large data sizes. Meanwhile, existing general purpose big data engines are built in a generic way to support various query workloads. Thus, they are not equipped to support the characteristics of microblogs [2], and so they are missing necessary infrastructure like supporting the real-time indexing and promoting temporal, spatial, and ranking queries. This results in sub par performance when supporting microblogs. Video: http://kite.cs.umn.edu/video.html

This paper presents GeoTrend; a system for scalable support of spatial trend discovery on recent microblogs, e.g., tweets and online reviews, that come in real time. GeoTrend is distinguished from existing techniques in three aspects: (1) It discovers trends in arbitrary spatial regions, e.g., city blocks. (2) It supports trending measures that effectively capture trending items under a variety of definitions that suit different applications. (3) It promotes recent microblogs as first-class citizens and optimizes its system components to digest a continuous flow of fast data in main-memory while removing old data efficiently. GeoTrend queries are top-k queries that discover the most trending k keywords that are posted within an arbitrary spatial region and during the last T time units. To support its queries efficiently, GeoTrend employs an in-memory spatial index that is able to efficiently digest incoming data and expire data that is beyond the last T time units. The index also materializes top-k keywords in different spatial regions so that incoming queries can be processed with low latency. In case of peak times, a main-memory optimization technique is employed to shed less important data, so that the system still sustains high query accuracy with limited memory resources. Experimental results based on real Twitter feed and Bing Mobile spatial search queries show the scalability of GeoTrend to support arrival rates of up to 50,000 microblog/second, average query latency of 3 milli-seconds, and at least 90+% query accuracy even under limited memory resources.

Searching microblogs, e.g., tweets and comments, is practically supported through main-memory indexing for scalable data digestion and efficient query evaluation. With continuity and excessive numbers of microblogs, it is infeasible to keep data in main-memory for long periods. Thus, once allocated memory budget is filled, a portion of data is flushed from memory to disk to continuously accommodate newly incoming data. Existing techniques come with either low memory hit ratio due to flushing items regardless of their relevance to incoming queries or significant overhead of tracking individual data items, which limit scalability of microblogs systems in either cases. In this paper, we propose kFlushing policy that exploits popularity of top-k queries in microblogs to smartly select a subset of microblogs to flush. kFlushing is mainly designed to increase memory hit ratio. To this end, it identifies and flushes in-memory data that does not contribute to incoming queries. The freed memory space is utilized to accumulate more useful data that is used to answer more queries from memory contents. When all memory is utilized for useful data, kFlushing flushes data that is less likely to degrade memory hit ratio. In addition, kFlushing comes with a little overhead that keeps high system scalability in terms of high digestion rates of incoming fast data. Extensive experimental evaluation shows the effectiveness and scalability of kFlushing to improve main-memory hit by 26–330% while coping up with fast microblog streams of up to 100K microblog/second.

Microblogs data, e.g., tweets, reviews, news comments, and social media comments, has gained considerable attention in recent years due to its popularity and rich contents. Nowadays, microblogs applications span a wide spectrum of interests, including detecting and analyzing events, user analysis for geo-targeted ads and political elections, and critical applications like discovering health issues and rescue services. Consequently, major research efforts are spent to analyze and manage microblogs data to support different applications. In this tutorial, we give a 1.5 hours overview about microblogs data analysis, management, and systems. The tutorial gives a comprehensive review for research efforts that are trying to analyze microblogs contents to build on them new functionality and use cases. In addition, the tutorial reviews existing research that propose core data management components to support microblogs queries at scale. Finally, the tutorial reviews system-level issues and on-going work on supporting microblogs data through the rising big data systems. Through its different parts, the tutorial highlights the challenges and opportunities in microblogs data research.

The recent wide popularity of microblogs (e.g., tweets, online comments) has empowered various important applications, including, news delivery, event detection, market analysis, and target advertising. A core module in all these applications is a frequent/trending query processor that aims to find out those topics that are highly frequent or trending in the social media through posted microblogs. Unfortunately current attempts for such core module suffer from several drawbacks. Most importantly, their narrow scope, as they focus only on solving trending queries for a very special case of localized and very recent microblogs. This paper presents GARNET; a holistic system equipped with one-stop efficient and scalable solution for supporting a generic form of context-aware frequent and trending queries on microblogs. GARNET supports both frequent and trending queries, any arbitrary time interval either current, recent, or past, of fixed granularity, and having a set of arbitrary filters over contextual attributes. From a system point of view, GARNET is very appealing and industry-friendly, as one needs to realize it once in the system. Then, a myriad of various forms of trending and frequent queries are immediately supported. Experimental evidence based on a real system prototype of GARNET and billions of real Twitter data show the scalability and efficiency of GARNET for various query types.

Microblogs data, e.g., tweets, reviews, news comments, and social media comments, has gained considerable attention in recent years due to its popularity and rich contents. Nowadays, microblogs applications span a wide spectrum of interests, including analyzing events and users activities and critical applications like discovering health issues and rescue services. Consequently, major research efforts are spent to manage, analyze, and visualize microblogs data to support different applications. In this tutorial, we give a 1.5 hours overview about microblogs data management, analysis, visualization, and systems. The tutorial gives a comprehensive review for research on core data management components to support microblogs queries at scale. This includes system-level issues and on-going work on supporting microblogs data through the rising wave of big data systems. In addition, the tutorial reviews research on microblogs data analysis and visualization. Through its different parts, the tutorial highlights the challenges and opportunities in microblogs data research.

Microblogging services have become among the most popular services on the web in the last few years. This led to significant increase in data size, speed, and applications. This paper presentsVenus; a system that supports real-time spatial queries on microblogs.Venussupports its queries on a spatial boundary$R$and a temporal boundary$T$, from which only the top-$k$microblogs are returned in the query answer based on a spatio-temporal ranking function. Supporting such queries requiresVenusto digest hundreds of millions of real-time microblogs in main-memory with high rates, yet, it provides low query responses and efficient memory utilization. To this end,Venusemploys: (1) an efficient in-memory spatio-temporal index that digests high rates of incoming microblogs in real time, (2) a scalable query processor that prune the search space,$R$and$T$, effectively to provide low query latency on millions of items in real time, and (3) a group of memory optimization techniques that provide system administrators with different options to save significant memory resources while keeping the query accuracy almost perfect.Venusmemory optimization techniques make use of the local arrival rates of microblogs to smartly shed microblogs that are old enough not to contribute to any query answer. In addition,Venuscan adaptively, in real time, adjust its load shedding based on both the spatial distribution and the parameters of incoming query loads. AllVenuscomponents can accommodate different spatial and temporal ranking functions that are able to capture the importance of each dimension differently depending on the applications requirements. Extensive experimental results based on real Twitter data and actual locations of Bing search queries show thatVenussupports high arrival rates of up to 64 K microblogs/second and average query latency of 4 msec.

This paper demonstrates Taghreed; a full-fledged system for efficient and scalable querying, analyzing, and visualizing geotagged microblogs, such as tweets. Taghreed supports a wide variety of queries on all microblogs attributes. In addition, it is able to manage a large number (billions) of microblogs for relatively long periods, e.g., months. Taghreed consists of four main components: (1) indexer, (2) query engine, (3) recovery manager, and (4) visualizer. Taghreed indexer efficiently digests incoming microblogs with high arrival rates in light main-memory indexes. When the memory becomes full, the memory contents are flushed to disk indexes which are managing billions of microblogs efficiently. On memory failure, the recovery manager restores the memory contents from backup copies. Taghreed query engine consists of two modules: a query optimizer and a query processor. The query optimizer generates an optimized query plan to be executed by the query processor to provide low query responses. Taghreed visualizer features to its users a wide variety of spatiotemporal queries and presents the answers on a map-based user interface that allows an interactive exploration. Taghreed is the first system that addresses all these challenges collectively for geotagged microblogs data. The system is demonstrated based on real system implementation through different scenarios that show system functionality and internals.

This paper advocates for the need to build a Microblogs Data Management System (MDMS) as an end-to-end data management system to support indexing, querying, and analyzing microblogs, e.g., Tweets, comments, or check-in's. We identify a set of characteristics for microblogging environments that are distinguishing from any other data management environment. Then, we propose a system architecture for the first Microblogs Data Management System, which includes indexing, querying, and recovery components. The indexing component is responsible for indexing recent data in memory, indexing older data in disk, and synchronizing the flow of data from memory to disk without affecting the query response time. The querying component is responsible for retrieving the query answer from both memory and disk storage as well as employing online selectivity estimation techniques tuned to the behavior of microblogs data. The recovery module allows for efficiently storing and processing incoming microblogs in memory without worrying about data loss.

This paper presents Taghreed; a full-fledged system for efficient and scalable querying, analyzing, and visualizing geotagged microblogs, e.g., tweets. Taghreed supports arbitrary queries on a large number (Billions) of microblogs that go up to several months in the past. Taghreed consists of four main components: (f) Indexer, (2) query engine, (3) recovery manager, and (4) visualizer. Taghreed indexer efficiently digests incoming microblogs with high arrival rates in light memory-resident indexes. When the memory becomes full, a flushing policy manager transfers the memory contents to disk indexes which are managing Billions of microblogs for several months. On memory failure, the recovery manager restores the system status from replicated copies for the main-memory content. Taghreed query engine consists of two modules: a query optimizer and a query processor. The query optimizer generates an optimal query plan to be executed by the query processor through efficient retrieval techniques to provide low query response, i.e., order of milli-seconds. Taghreed visualizer allows end users to issue a wide variety of spatio-temporal queries. Then, it graphically presents the answers and allows interactive exploration through them. Taghreed is the first system that addresses all these challenges collectively for microblogs data. In the paper, each system component is described in detail.

In the last few years, Twitter data has become so popular that it is used in a rich set of new applications, e.g., real-time event detection, demographic analysis, and news extraction. As user-generated data, the plethora of Twitter data motivates several analysis tasks that make use of activeness of 271+ Million Twitter users. This demonstration presents VisCAT; a tool for aggregating and visualizing categorical attributes in Twitter data. VisCAT outputs visual reports that provide spatial analysis through interactive map-based visualization for categorical attributes---such as tweet language or source operating system---at different zoom levels. The visual reports are built based on user-selected data in arbitrary spatial and temporal ranges. For this data, VisCAT employs a hierarchical spatial data structure to materialize the count of each category at multiple spatial levels. We demonstrate VisCAT, using real Twitter dataset. The demonstration includes use cases on tweet language and tweet source attributes in the region of Gulf Arab states, which can be used for deducing thoughtful conclusions on demographics and living levels in local societies.

Mars demonstration exploits the microblogs location information to support a wide variety of important spatio-temporal queries on microblogs. Supported queries include range, nearest-neighbor, and aggregate queries. Mars works under a challenging environment where streams of microblogs are arriving with high arrival rates. Mars distinguishes itself with three novel contributions: (1) Efficient in-memory digestion/expiration techniques that can handle microblogs of high arrival rates up to 64,000 microblog/sec. This also includes highly accurate and efficient hopping-window based aggregation for incoming microblogs keywords. (2) Smart memory optimization and load shedding techniques that adjust in-memory contents based on the expected query load to trade off a significant storage savings with a slight and bounded accuracy loss. (3) Scalable real-time query processing, exploiting Zipf distributed microblogs data for efficient top-k aggregate query processing. In addition, Mars employs a scalable real-time nearest neighbor and range query processing module that employs various pruning techniques so that it serves heavy query workloads in real time. Mars is demonstrated using a stream of real tweets obtained from Twitter firehose with a production query workload obtained from Bing web search. We show that Mars serves incoming queries with an average latency of less than 4 msec and with 99% answer accuracy while saving up to 70% of storage overhead for different query loads.

This paper presents Mercury; a system for real-time support of top-k spatio-temporal queries on microblogs, where users are able to browse recent microblogs near their locations. With high arrival rates of microblogs, Mercury ensures real-time query response within a tight memory-constrained environment. Mercury bounds its search space to include only those microblogs that have arrived within certain spatial and temporal boundaries, in which only the top-k microblogs, according to a spatio-temporal ranking function, are returned in the search results. Mercury employs: (a) a scalable dynamic in-memory index structure that is capable of digesting all incoming microblogs, (b) an efficient query processor that exploits the in-memory index through spatio-temporal pruning techniques that reduce the number of visited microblogs to return the final answer, (c) an index size tuning module that dynamically finds and adjusts the minimum index size to ensure that incoming queries will be answered accurately, and (d) a load shedding technique that trades slight decrease in query accuracy for significant storage savings. Extensive experimental results based on a real-time Twitter Firehose feed and actual locations of Bing search queries show that Mercury supports high arrival rates of up to 64K microblogs/second and average query latency of 4 msec.

This demo presents Minnesota Traffic Generator (MNTG); an extensible web-based road network traffic generator. MNTG enables its users to generate traffic data at any arbitrary road networks with different traffic generators. Unlike existing traffic generators that require a lot of time/effort to install, configure, and run, MNTG is a web service with a user-friendly interface where users can specify an arbitrary spatial region, select a traffic generator, and submit their traffic generation request. Once the traffic data is generated by MNTG, users can then download and/or visualize the generated data. MNTG can be extended to support: (1) various traffic generators. It is already shipped with the two most common traffic generators, Brinkhoff and BerlinMOD, but other generators can be easily added. (2) various road network sources. It is shipped with U.S. Tiger files and OpenStreetMap, but other sources can be also added. A beta version of MNTG is launched at: http://mntg.cs.umn.edu.

This demo presents Sindbad; a location-based social networking system. Sindbad supports three new services beyond traditional social networking services, namely, location-aware news feed, location-aware recommender, and location-aware ranking. These new services not only consider social relevance for its users, but they also consider spatial relevance. Since location-aware social networking systems have to deal with large number of users, large number of messages, and user mobility, efficiency and scalability are important issues. To this end, Sindbad encapsulates its three main services inside the query processing engine of PostgreSQL. Usage and internal functionality of Sindbad, implemented with PostgreSQL and Google Maps API, are demonstrated through user (i.e., web/phone) and system analyzer GUI interfaces, respectively.