Browsing by Author "Zhou, Xun"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Crime pattern analysis: A spatial frequent pattern mining approach
    (2012-05-10) Shekhar, Shashi; Mohan, Pradeep; Oliver, Dev; Zhou, Xun
    Crime pattern analysis (CPA) is the process of analytical reasoning facilitated by an understanding about the nature of an underlying spatial framework that generates crime. For example, law enforcement agencies may seek to identify regions of sudden increase in crime activity, namely, crime outbreaks. Many analytical tools facilitate this reasoning process by providing support for techniques such as hotspot analysis. However, in practice, police departments are desirous of scalable tools for existing techniques and new insights including, interaction between different crime types. Identifying new insights using scalable tools may help reduce the human effort that may be required in CPA. Formally, given a spatial crime dataset and other information familiar to law enforcement agencies, the CPA process identifies interesting, potentially useful and previously unknown crime patterns. For example, analysis of an urban crime dataset might reveal that downtown bars frequently lead to assaults just after bar closing. However, CPA is challenging due to: (a) the large size of crime datasets, and (b) a potentially large collection of interesting crime patterns. This chapter explores, spatial frequent pattern mining (SFPM), which is a spatial data driven approach for CPA and describes SFPM in the context of one type of CPA, outbreak detection. We present a case study to discover interesting, useful and non-trivial crime outbreaks in a dataset from Lincoln, NE. A review of emerging trends and new research needs in CPA methods for study to discover interesting, useful and non-trivial crime outbreaks in a dataset from outbreak detection is also presented.
  • Thumbnail Image
    Item
    Motion induced robot-to-robot extrinsic calibration.
    (2012-05) Zhou, Xun
    Multi-robot systems, or mobile sensor networks, which have become increasingly popular due to recent advances in electronics and communications, can be used in a wide range of applications, such as space exploration, search and rescue, target tracking, and cooperative localization and mapping. In contrast to single robots, multi-robot teams are more robust against single-point failures, accomplish coverage tasks more efficiently by dispersing multiple robots into large areas, and achieve higher estimation accuracy by directly communicating and fusing their sensor measurements. Realizing these advantages of multi-robot systems, however, requires addressing certain challenges. Specifically, in order for teams of robots to cooperate, or fuse measurements from geographically dispersed sensors, they need to know their poses with respect to a common frame of reference. Initializing the robots' poses in a common frame is relatively easy when using GPS, but very challenging in the absence of external aids. Moreover, planning the motion of multiple robots to achieve optimal estimation accuracy is quite challenging. Specifically, since the estimation accuracy depends on the locations where the robots record their sensor measurements, it may take an extensive amount of time to reach a required level of accuracy, if the robots' motions are not properly designed. This thesis offers novel solutions to the aforementioned challenges. The first part of the thesis investigates the problem of relative robot pose initialization, using robot-to-robot distance and/or bearing measurements collected over multiple time steps. In particular, it focuses on solving minimal problems and proves that in 3D there exist only 14 such problems that need to be solved. Furthermore, it provides efficient algorithms for computing the robot-to-robot transformation, which exploit recent advances in algebraic geometry. The second part of the thesis investigates the problem of optimal motion strategies for localization in leader-follower formations using distance or bearing measurements. Interestingly, the robot-to-robot pose is unobservable if the robots move on a straight line and maintain their formations, hence, the uncertainty of the robots' poses increases over time. If the robots, however, deviate from the desired formation, their measurements provide additional information which makes the relative pose observable. This thesis addresses the trade-off between maintaining the formation and estimation accuracy, and provides algorithms for computing the optimal positions where the robots should move to in order to collect the most informative measurements at the next time step. By providing solutions to two important problems for multi-robot systems: motion-induced extrinsic calibration, and optimal motion strategies for relative localization, the work presented in this thesis is expected to promote the use of multi-robot teams in real-world applications.
  • Thumbnail Image
    Item
    Spatiotemporal Big Data Analytics: Change Footprint Pattern Discovery
    (2014-05) Zhou, Xun
    Recent years have seen the emergence of many new and valuable datasets such as global climate projection, GPS traces, and tweets. However, these Spatiotemporal Big Data (STBD) poses significant challenges for data analytics due to high data variety and candidate-pattern cardinality. One specific STBD analytics tasks is change footprint pattern discovery. Given a definition of change and a dataset about a spatiotemporal(ST) phenomenon, ST change footprint pattern discovery is the process of identifying the location and/or time of such changes in the data. This problem is of fundamental significance to a variety of applications such as understanding climate change, public safety, environmental monitoring, etc. This thesis formally defines the spatiotemporal change footprint as a new pattern family in STBD analytics, and examined footprint patterns and related discovery techniques across disciplines via a novel taxonomy. Methods for detecting change footprints have emerged from a diverse set of research areas, ranging from time series analysis and remote sensing to spatial statistics. Existing reviews focus on discovery methods for only one or a few types of change footprints. To facilitate sharing of insights across disciplines, we conduct a multi-disciplinary review of ST change patterns and their respective discovery methods. We develop a taxonomy of possible ST change footprints and classified our review findings accordingly. This exercise allows us to identify gaps in the research that we consider ripe for exploration, most notably change pattern discovery in vector ST datasets. To address the research gaps identified in the above analysis, this thesis further explores the computational solutions to the discovery of two specific change footprint patterns, namely, interesting sub-paths (e.g., change intervals) and persistent change windows. Given a spatiotemporal (ST) dataset and a path in its embedding spatiotemporal framework, the goal of the interesting sub-path discovery problem is to identify all interesting sub-paths defined by an interest measure. An important application domain of sub-path discovery is understanding climate change. This thesis formally defines the computational structure of interesting sub-path discovery as a Grid-based Directed Acyclic Graph (G-DAG). We propose a new algorithm, namely, the Row-wise Traversal (after leaf-evaluation) with Column Pruning (RTCP) which brings dramatically down the memory cost for G-DAG traversal in our earlier approaches while also reducing CPU cost. We also provide theoretical analyses of correctness, completeness and computational complexity of the RTCP algorithm. Experimental evaluation on both synthetic and real datasets show that the RTCP algorithm is always the fastest in computational time among all the proposed algorithms. The thesis finally explores a more complicated change footprint pattern, namely, the persistent change window. Given a region comprised of locations that each have a time series, the Persistent Change Windows (PCW) discovery problem aims to find all spatial window and temporal interval pairs that exhibit persistent change of attribute values over time. PCW discovery is important for critical societal applications such as detecting desertification, deforestation, and monitoring urban sprawl. The PCW discovery problem is challenging due to the large number of candidate patterns, the lack of monotonicity, and large datasets of detailed resolution and high volume. Previous approaches in ST change footprint discovery have focused on local spatial footprints for persistent change discovery and may not guarantee completeness. In contrast, we propose a space-time window enumeration and pruning (SWEP) approach that considers zonal spatial footprints when finding persistent change patterns. We provide theoretical analysis of SWEP's correctness, completeness, and space-time complexity. We also present a case study on vegetation data that demonstrates the usefulness of the proposed approach. Experimental evaluation on synthetic data show that the SWEP approach is orders of magnitude faster than the naive approach. The work in this thesis is the first step towards understanding the spatiotemporal change footprint discovery problem, including its formulation, computational challenges and solutions, and applications. In this thesis, we have explored automatic and efficient approaches to discovery raster-based ST change footprints, and applied our techniques on climate data in the context of understanding climate change. We conclude this thesis by exploring potential ST change patterns with new footprints (e.g., geographic feature based footprints), alternative computational paradigms (e.g., parallel and distributed STBD analytics), their challenges and solutions, and other future research directions.
  • Thumbnail Image
    Item
    Spatiotemporal Change Footprint Pattern Discovery: An Interdisciplinary Survey
    (2014-10-01) Zhou, Xun; Shekhar, Shashi; Ali, Reem Y.
    Given a definition of change and a dataset about spatiotemporal (ST) phenomena, ST change footprint discovery is the process of identifying the location and/or time of such changes from the dataset. Change footprint discovery is fundamentally important for the study of climate change, the tracking of disease, and many other applications. Methods for detecting change footprints have emerged from a diverse set of research areas, ranging from time series analysis and remote sensing to spatial statistics. Researchers have much to learn from one another, but are stymied by inconsistent use of terminology and varied definitions of change across disciplines. Existing reviews focus on discovery methods for only one or a few types of change footprints (e.g., point change in a time series). To facilitate sharing of insights across disciplines, we conducted a multi-disciplinary review of ST change patterns and their respective discovery methods. We developed a taxonomy of possible ST change footprints and classified our review findings accordingly. This exercise allowed us to identify gaps in the research that we consider ripe for exploration, most notably change pattern discovery in vector ST datasets. In addition, we illustrate how such pattern discovery might proceed using two case studies from historical GIS.