Preference-based Spatial Co-location Pattern Mining (Big Data Management)

Foreword
Preface
Contents
Chapter 1: Introduction
	1.1 The Background and Applications
	1.2 The Evolution and Development
	1.3 The Challenges and Issues
	1.4 Content and Organization of the Book
Chapter 2: Maximal Prevalent Co-location Patterns
	2.1 Introduction
	2.2 Why the MCHT Method Is Proposed for Mining MPCPs
	2.3 Formal Problem Statement and Appropriate Mining Framework
		2.3.1 Co-Location Patterns
		2.3.2 Related Work
		2.3.3 Contributions and Novelties
	2.4 The Novel Mining Solution
		2.4.1 The Overall Mining Framework
		2.4.2 Bit-String-Based Maximal Clique Enumeration
		2.4.3 Constructing the Participating Instance Hash Table
		2.4.4 Calculating Participation Indexes and Filtering MPCPs
		2.4.5 The Analysis of Time and Space Complexities
	2.5 Experiments
		2.5.1 Data Sets
			2.5.1.1 Synthetic Data Sets
			2.5.1.2 Real Data Sets
		2.5.2 Experimental Objectives
		2.5.3 Experimental Results and Analysis
			2.5.3.1 The Effect of Bit Strings on Enumerating Maximal Cliques
			2.5.3.2 The Comparative Performance of the MCHT Algorithm
			2.5.3.3 The Scalability of the MCHT Algorithm
			2.5.3.4 Memory Consumption
			2.5.3.5 The Evaluation of Response to Changing User Requests
			2.5.3.6 Analysis of Mining Results on the Real Data Sets
	2.6 Chapter Summary
Chapter 3: Maximal Sub-prevalent Co-location Patterns
	3.1 Introduction
	3.2 Basic Concepts and Properties
	3.3 A Prefix-Tree-Based Algorithm (PTBA)
		3.3.1 Basic Idea
		3.3.2 Algorithm
		3.3.3 Analysis and Pruning
	3.4 A Partition-Based Algorithm (PBA)
		3.4.1 Basic Idea
		3.4.2 Algorithm
		3.4.3 Analysis of Computational Complexity
	3.5 Comparison of PBA and PTBA
	3.6 Experimental Evaluation
		3.6.1 Synthetic Data Generation
		3.6.2 Comparison of Computational Complexity Factors
		3.6.3 Comparison of Expected Costs Involved in Identifying Candidates
		3.6.4 Comparison of Candidate Pruning Ratio
		3.6.5 Effects of the Parameter Clumpy
		3.6.6 Scalability Tests
		3.6.7 Evaluation with Real Data Sets
	3.7 Related Work
	3.8 Chapter Summary
Chapter 4: SPI-Closed Prevalent Co-location Patterns
	4.1 Introduction
	4.2 Why SPI-Closed Prevalent Co-locations Improve Mining
	4.3 The Concept of SPI-Closed and Its Properties
		4.3.1 Classic Co-location Pattern Mining
		4.3.2 The Concept of SPI-Closed
		4.3.3 The Properties of SPI-Closed
	4.4 SPI-Closed Miner
		4.4.1 Preprocessing and Candidate Generation
		4.4.2 Computing Co-location Instances and Their PI Values
		4.4.3 The SPI-Closed Miner
	4.5 Qualitative Analysis of the SPI-Closed Miner
		4.5.1 Discovering the Correct SPI-Closed Co-location Set Omega
		4.5.2 The Running Time of SPI-Closed Miner
	4.6 Experimental Evaluation
		4.6.1 Experiments on Real-life Data Sets
			4.6.1.1 The Effectiveness of SPI-Closed Miner
			4.6.1.2 The Efficiency of SPI-Closed Miner
		4.6.2 Experiments with Synthetic Data Sets
	4.7 Related Work
	4.8 Chapter Summary
Chapter 5: Top-k Probabilistically Prevalent Co-location Patterns
	5.1 Introduction
	5.2 Why Mining Top-k Probabilistically Prevalent Co-location Patterns (Top-k PPCPs)
	5.3 Definitions
		5.3.1 Spatially Uncertain Data
		5.3.2 Prevalent Co-locations
		5.3.3 Prevalence Probability
		5.3.4 Min_PI-Prevalence Probabilities
		5.3.5 Top-k PPCPs
	5.4 A Framework of Mining Top-k PPCPs
		5.4.1 Basic Algorithm
		5.4.2 Analysis and Pruning of Algorithm 5.1
	5.5 Improved Computation of P(c, min_PI)
		5.5.1 0-1-Optimization
		5.5.2 The Matrix Method
		5.5.3 Polynomial Matrices
	5.6 Approximate Computation of P(c, min_PI)
	5.7 Experimental Evaluations
		5.7.1 Evaluation on Synthetic Data Sets
			5.7.1.1 Main Memory Cost of Algorithms
			5.7.1.2 Running Time of Algorithms
			5.7.1.3 Accuracy of the Approximation Algorithm
			5.7.1.4 Effect of ε and δ
		5.7.2 Evaluation on Real Data Sets
			5.7.2.1 Running Time of Algorithms
	5.8 Chapter Summary
Chapter 6: Non-redundant Prevalent Co-location Patterns
	6.1 Introduction
	6.2 Why We Need to Explore Non-redundant Prevalent Co-locations
	6.3 Problem Definition
		6.3.1 Semantic Distance
		6.3.2 δ-Covered
		6.3.3 The Problem Definition and Analysis
	6.4 The RRclosed Method
	6.5 The RRnull Method
		6.5.1 The Method
		6.5.2 The Algorithm
		6.5.3 The Correctness Analysis
		6.5.4 The Time Complexity Analysis
		6.5.5 Comparative Analysis
	6.6 Experimental Results
		6.6.1 On the Three Real Data Sets
		6.6.2 On the Synthetic Data Sets
	6.7 Related Work
	6.8 Chapter Summary
Chapter 7: Dominant Spatial Co-location Patterns
	7.1 Introduction
	7.2 Why Dominant SCPs Are Useful to Mine
	7.3 Related Work
	7.4 Preliminaries and Problem Formulation
		7.4.1 Preliminaries
		7.4.2 Definitions
		7.4.3 Formal Problem Formulation
		7.4.4 Discussion of Progress
	7.5 Proposed Algorithm for Mining Dominant SCPs
		7.5.1 Basic Algorithm for Mining Dominant SCPs
		7.5.2 Pruning Strategies
		7.5.3 An Improved Algorithm
		7.5.4 Comparison of Complexity
	7.6 Experimental Study
		7.6.1 Data Sets
		7.6.2 Efficiency
		7.6.3 Effectiveness
		7.6.4 Real Applications
	7.7 Chapter Summary
Chapter 8: High Utility Co-location Patterns
	8.1 Introduction
	8.2 Why We Need High Utility Co-location Pattern Mining
	8.3 Related Work
		8.3.1 Spatial Co-location Pattern Mining
		8.3.2 Utility Itemset Mining
	8.4 Problem Definition
	8.5 A Basic Mining Approach
	8.6 Extended Pruning Approach
		8.6.1 Related Definitions
		8.6.2 Extended Pruning Algorithm (EPA)
	8.7 Partial Pruning Approach
		8.7.1 Related Definitions
		8.7.2 Partial Pruning Algorithm (PPA)
	8.8 Experiments
		8.8.1 Differences Between Mining Prevalent SCPs and High Utility SCPs
		8.8.2 Effect of the Number of Total Instances n
		8.8.3 Effect of the Distance Threshold d
		8.8.4 Effect of the Pattern Utility Ratio Threshold xi
		8.8.5 Effect of s in vss
		8.8.6 Comparing PPA and EPA with a Different Utility Ratio Threshold xi
	8.9 Chapter Summary
Chapter 9: High Utility Co-location Patterns with Instance Utility
	9.1 Introduction
	9.2 Why We Need Instance Utility with Spatial Data
	9.3 Related Work
	9.4 Related Concepts
	9.5 A Basic Algorithm
	9.6 Pruning Strategies
	9.7 Experimental Analysis
		9.7.1 Data Sets
		9.7.2 The Quality of Mining Results
		9.7.3 Evaluation of Pruning Strategies
	9.8 Chapter Summary
Chapter 10: Interactively Post-mining User-Preferred Co-location Patterns with a Probabilistic Model
	10.1 Introduction
	10.2 Why We Need Interactive Probabilistic Post-mining
	10.3 Related Work
	10.4 Problem Statement
		10.4.1 Basic Concept
		10.4.2 Subjective Preference Measure
		10.4.3 Formal Problem Statement
	10.5 Probabilistic Model
		10.5.1 Basic Assumptions
		10.5.2 Probabilistic Model
		10.5.3 Discussion
	10.6 The Complete Algorithm
		10.6.1 The Algorithm
		10.6.2 Two Optimization Strategies
		10.6.3 The Time Complexity Analysis
	10.7 Experimental Results
		10.7.1 Experimental Setting
		10.7.2 The Simulator
		10.7.3 Accuracy Evaluation on Real Data Sets
		10.7.4 Accuracy Evaluation on Synthetic Data Sets
		10.7.5 Sample Co-location Selection
	10.8 Chapter Summary
Chapter 11: Vector-Degree: A General Similarity Measure for Co-location Patterns
	11.1 Introduction
	11.2 Why We Measure the Similarity Between SCPs
	11.3 Preliminaries
		11.3.1 Spatial Co-location Pattern (SCP)
		11.3.2 A Toy Example
		11.3.3 Problem Statement
	11.4 The Method
		11.4.1 Maximal Cliques Enumeration Algorithm
		11.4.2 A Representation Model of SCPs
		11.4.3 Vector-Degree: the Similarity Measure of SCPs
		11.4.4 Grouping SCPs Based on Vector-Degree
	11.5 Experimental Evaluations
		11.5.1 Data Sets
		11.5.2 Results
	11.6 Chapter Summary
References