You are previewing Temporal and Spatio-Temporal Data Mining.
O'Reilly logo
Temporal and Spatio-Temporal Data Mining

Book Description

"The recent surge of interest in spatio-temporal databases has resulted in numerous advances, such as: modeling, indexing, and querying of moving objects and spatio-temporal data. Aside from this, rule mining in spatial databases and temporal databases has been studied extensively in data mining research. Temporal and Spatio-Temporal Data Mining examines the problem of mining topological patterns in spatio-temporal databases by imposing the temporal constraints into the process of mining spatial collocation patterns.

Temporal and Spatio-Temporal Data Mining presents probable solutions when discovering the spatial sequence patterns by incorporating the spatial information into the sequence of patterns, and introduces two new classes of spatial sequence patterns: flow patterns and generalized spatio-temporal patterns. This innovative book addresses different scenarios when finding complex relationships in spatio-temporal data by modeling them as graphs, giving readers a comprehensive synopsis on two successful partition-based algorithms designed by the authors."

Table of Contents

  1. Copyright
  2. Preface
    1. To the Data Mining Researchers
    2. To the Graduate Students
    3. Organization of the Book
  3. Acknowledgments
  4. I. Introduction
    1. Temporal Data Mining
      1. Temporal Association Rules
      2. Sequence Patterns
      3. Periodic Patterns
    2. Spatio-Temporal Data Mining
      1. Spatial Association Rules
      2. Spatial Collocation Patterns
    3. Organization of the Book
    4. References
  5. II. Time Series Mining: Background and Related Work
    1. Issues in Time Series Mining
      1. Similarity Measures
        1. Euclidean Distance
        2. Dynamic Time Warping
      2. Dimension Reduction
      3. Data Discretization
    2. Time Series Mining Techniques
      1. Periodic Pattern Mining
        1. Partial Periodic Patterns
        2. Asynchronous Periodic Patterns
        3. Unknown Period Patterns
        4. Periodic Patterns with Gap Requirement
      2. Sequential Pattern Mining
        1. General Sequence Mining
        2. PrefixSpan
        3. SPADE
        4. Incremental Sequence Mining
        5. Closed Sequence Mining
        6. Constrained Sequence Mining
    3. Summary
    4. References
  6. III. Mining Dense Periodic Patterns in Time Series Databases
    1. Notations and Definitions
    2. Dense Periodicity
      1. Density in Time Series
      2. Lower Bound Period in Fragments
      3. Density-Based Pruning
    3. DPMiner
        1. Analysis
    4. Experiment Evaluation
        1. Synthetic Datasets
        2. Real-Life Dataset
      1. Sensitivity Experiments
      2. Efficiency
      3. Effectiveness
      4. Scalability
    5. Summary
    6. References
  7. IV. Mining Sequence Patterns in Evolving Databases
    1. Problem Definition
    2. Algorithm MFS
    3. Incremental Update Algorithms
      1. Algorithm GSP+
      2. Algorithm MFS+
    4. Performance Study
      1. Experimental Dataset
      2. Coverages and I/O Savings
      3. Sampling
      4. CPU Cost
      5. MFS vs. SPADE
      6. Incremental Update
      7. Varying |Δ+| and |Δ-|
    5. Summary
    6. References
  8. V. Mining Progressive Confident Rules in Sequence Databases
    1. Problem Definition
    2. Mining Concise Set of PCR
      1. Algorithm FMP
    3. Experiments
      1. Synthetic Data Generation
      2. Effect of Varying Support Threshold
      3. Effect of Varying Confidence Thresholds
      4. Effect of Parameters O, T, S, and I
      5. Scalability
    4. Application of PCR in Classification
    5. Summary
    6. References
  9. VI. Early Works in Spatio-Temporal Mining
    1. Spatio-Temporal Patterns
      1. Evolution Patterns
      2. Frequent Movements of Objects
      3. Space-Time Clusters
    2. Review of Association Rule Mining
      1. Mining Association Rules in Transactional Data
      2. Apriori Algorithm
      3. Mining Association Rules in Temporal Data
    3. Spatial Association Pattern Mining
      1. Spatial Association Rules
      2. Spatial Collocation Patterns
    4. Summary
    5. References
  10. VII. Mining Topological Patterns in Spatio-Temporal Databases
    1. Problem Statement
      1. Topological Patterns
      2. Geographical Features
    2. Mining Topological Patterns
      1. Summary Structure
      2. Projected Database
      3. Mining Projected Databases
        1. Mining Star-Like Patterns
        2. Mining Clique Patterns
        3. Mining Star-Clique Patterns
    3. Algorithm TopologyMiner
    4. Experimental Study
      1. Synthetic Data Generation
      2. Effect of Prevalence Threshold
      3. Effect of Database Size
      4. Effect of Distance Thresholds
      5. Effect of the Number of Features
    5. Summary
    6. References
  11. VIII. Mining Flow Patterns in Spatio-Temporal Data
    1. Notations and Terminologies
    2. Flow Patterns
    3. Mining Flow Patterns
      1. Candidates Generation
      2. Summary Tree
      3. Methodology
        1. Step 1. Determine Relevant Temporal Constraints
        2. Step 2. Find Feasible Insert Positions Based on Temporal Constraints
        3. Step 3. Reduce Feasible Insert Positions Based on Spatial Constraints
        4. Step 4. Generate New Flow Patterns
      4. Support Counting
      5. Pruning Techniques
        1. Prune Infrequent Candidates
        2. Eliminate Hashing Non-Promising Events
        3. Delay Database Scans
    4. Algorithm FlowMiner
    5. Performance Study
        1. Synthetic Dataset
        2. Real-Life Datasets
      1. Experiments on Synthetic Datasets
      2. Experiments on Real-life Datasets
      3. Evaluation of Optimization Techniques
      4. Comparative Study
    6. Summary
    7. References
  12. IX. Mining Generalized Flow Patterns
    1. Notations and Terminologies
    2. Generalized ST Patterns
      1. Choice of Reference Location
      2. k-Generalized Spatio-Temporal Patterns
    3. Algorithm GenSTMiner
      1. Conditional Projected Database
      2. Pseudo Projection
    4. Performance Evaluation
      1. Experiments on Synthetic Dataset
      2. Comparative Study
    5. Summary
    6. References
  13. X. Mining Spatio-Temporal Trees
    1. Preliminaries
      1. Sub-Tree Categorization
      2. DFS String Encoding
      3. Canonical Form for Unordered Trees
    2. Related Work
    3. Frequent Weak Sub-Tree Mining
      1. ATMiner
        1. Candidate Generation
        2. Pattern Matching
        3. Candidate Pruning by Apriori
    4. Experimental Evaluation
      1. Response Time
      2. Scalability
      3. Space Requirement
    5. Summary
    6. References
  14. XI. Mining Spatio-Temporal Graph Patterns
    1. Related Work
    2. Preliminary Concepts
    3. Partition-Based Graph Mining
      1. Divide Graph Database into Units
      2. Mine Frequent Sub-Graphs in Units
      3. Combine Frequent Sub-Graphs
      4. Proof of Completeness
    4. Algorithm PartMiner
    5. Incremental Mining Using PartMiner
    6. Experimental Study
      1. Experiments on Static Datasets
      2. Effect of Partitioning Criteria
      3. Varying Minimum Support
      4. Effect of Number of Units k
      5. Scalability
      6. Experiments on Dynamic Datasets
      7. Effect of Partitioning Criteria
      8. Varying Minimum Support
      9. Effect of Number of Units k
      10. Effect of Various Types of Updates
    7. Summary
    8. References
  15. XII. Conclusions and Future Work
    1. Future Research Directions
      1. Data Integration and Data Classification
      2. Representation and Computation of Spatial Relationships
      3. Representation of Spatio-Temporal Data
      4. Indexing Schemes for Spatio-Temporal Data
      5. Efficient Trend Detection Algorithms
      6. Discovering Changes in Data Distribution
      7. Flow/Interaction Patterns Over Time
  16. About the Authors