Advances in Spatial and Temporal Databases

Name: Advances in Spatial and Temporal Databases | 12th International Symposium, SSTD 2011, Minneapolis, MN, USA, August 24-26, 2011. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

12th International Symposium, SSTD 2011, Minneapolis, MN, USA, August 24-26, 2011. Proceedings

Dieter Pfoser Yufei Tao Kyriakos Mouratidis Mario A. Nascimento Mohamed Mokbel Shashi Shekhar Yan Huang(Herausgeber*in)

Springer (Verlag)

Erschienen am 28. Juli 2011

XIV, 518 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-22922-0 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title
Preface
Organization
Table of Contents
Keynote
Keynote Speech: Underexplored Research Topics from the Commercial World
Research Sessions
Session 1: Knowledge Discovery
SSCP: Mining Statistically Significant Co-location Patterns
Introduction
Related Work
Problem Definition
Motivating Examples
Basic Idea for Finding Significant Co-location Patterns
Null Model Design
Definition of Co-location
Algorithm
Experimental Evaluation
Synthetic Data
Real Data Set
Conclusions
References
An Ontology-Based Traffic Accident Risk Mapping Framework
Introduction
Related Works
Accident Concentration Detection
Spatial Clustering
Ontology in Traffic Accidents
Methodology
An Ontology-Based Traffic Accident Risk Mapping Framework
Density-Based Clustering for Traffic Accident Risk (DBCTAR)
Implementation and Case Study
Conclusions and Future Work
References
Comparing Predictive Power in Climate Data: Clustering Matters
Introduction
Climate Data
Dataset Description
Seasonality and Autocorrelation
Data Representation
Climate Networks
Estimating Link Strength
Threshold Selection and Pruning
Clustering Methods
Network Communities
K-Means Clustering
K-Medoids Clustering
Spectral Clustering
Expectation Maximization
Experimental Setup
Extracting Candidate Indices
Evaluating Predictive Power
Experimental Results
Comparing Clustering Algorithms
Validating Predictive Skill
Prediction Algorithms
Domain Interpretation
Discussion and Future Work
References
Region of Interest Queries in CT Scans
Introduction
Related Work
Example-Based ROI Queries
Efficient Instance-Based Regression
Answering ROI Queries
Interpolation Using Matching Points
Retrieval Algorithm
Experimental Validation
Prediction via Regression
Precision of ROI Queries
Runtime of ROI Queries
Conclusion
References
Session 2: Spatial Networks
A Critical-Time-Point Approach to All-Start-Time Lagrangian Shortest Paths: A Summary of Results
Introduction
Basic Concepts and Problem Definition
Computational Structure of the ALSP Problem
Critical Time-Point Based ALSP Solver (CTAS)
CTAS Algorithm
Analysis of the CTAS Algorithm
Experimental Evaluation
Conclusions and Future Work
References
Online Computation of Fastest Path in Time-Dependent Spatial Networks
Introduction
Towards Time-Dependent Path Planning
Related Work
Problem Definition
Time-Dependent Fastest Path Computation
Precomputation Phase
Online B-TDFP Computation
Experimental Evaluation
Experimental Setup
Results
Conclusion and Future Work
References
Dynamic Pickup and Delivery with Transfers
Introduction
Related Work
Problem Formulation
Definitions
Actions
Solving Dynamic Pickup and Delivery with Transfers
The Dynamic Plan Graph
The SP Algorithm
Experimental Evaluation
The HT Method
Experiments
Conclusions
References
Finding Top-k Shortest Path Distance Changes in an Evolutionary Network
Introduction
Related Work
Shortest Path Evolution: Model and Algorithms
Edge Importance Estimation Algorithm
The Incidence Algorithm
Selective Expansion of Active Node Set V'
Node Ranking for Improved Efficiency
Edge Weight Based Ranking (EWBR)
Edge Weight Change Based Ranking (EWCBR)
Importance Number Based Ranking (INBR)
Importance Number Change Based Ranking (INCBR)
Ranking Using Edge Weight and Importance Numbers (RUEWIN)
Clustering Based Ranking (CBR)
Experimental Results
Datasets
Evaluation Methodology
Typical Distribution of Maximum Distance Change Values
Contributions by Individual Nodes
Accuracy Using the Incidence Algorithm and Selective Expansion
Accuracy of Edge Importance Numbers
Accuracy Comparison of Ranking Algorithms
Time Comparison of Ranking Algorithms
Case Studies
Conclusions and Future Work
References
Session 3: Access Methods
FAST: A Generic Framework for Flash-Aware Spatial Trees
Introduction
Fast System Overview
FAST Modules
FAST Design Goals
FAST Data Structure
Running Example
Tree Updates in FAST
Searching in FAST
Memory Flushing in FAST
Flushing Unit
Flushing Policy
Flushing Algorithm
Crash Recovery and Log Compaction in FAST
Recovery
Log Compaction
Experimental Evaluation
Effect of Memory Size
Effect of Log File Size
Effect of Index Size
Effect of Number of Updates
Log Compaction
Recovery Performance
Conclusion
References
MIDAS: Multi-attribute Indexing for Distributed Architecture Systems
Introduction
Related Work
MIDAS Architecture
Index Structure
MIDAS Peers
Peer Joins
Peer Departures
Peer Failures
Load Balancing and Fault Tolerance
Query Processing on MIDAS
Point Queries
Range Queries
Experimental Evaluation
Setting
Results
Conclusion
References
Thread-Level Parallel Indexing of Update Intensive Moving-Object Workloads
Introduction
Preliminaries
Problem Setting
Related Work
Multi-threaded Processing
Parallel Workload Processing
Single-Threaded Processing
TwinGrid
Multi-threaded Processing
Comparison with MOVIES
Experimental Study
Setting
Optimal Index Parameters
TwinGrid Scalability
TwinGrid vs. MOVIES
Conclusions
References
Efficient Processing of Top-k Spatial Keyword Queries
Introduction
Related Work
Problem Statement
Spatial Inverted Index
Single-Keyword Queries
Multiple-Keyword Queries
Partial-Score on Keyword
Multiple Keyword Algorithm
Experimental Evaluation
Query Processing Performance
Maintenance and Space Requirements
Conclusions
References
Session 4: Moving Objects and Sensor Networks
Retrieving k-Nearest Neighboring Trajectories by a Set of Point Locations
Introduction
Problem Formulation
Query Processing
Candidate Generation
Candidate Verification
Qualifier Expectation
Performance Evaluation
Experiment Settings
Evaluations on Algorithm's Performance
Discussions
Related Work
Conclusions and Future Work
References
Towards Reducing Taxicab Cruising Time Using Spatio-Temporal Profitability Maps
Introduction
Related Work
Methodology
Case Study - Shanghai Taxi Service
Validation
Future Work
Conclusion
References
Computing the Cardinal Direction Development between Moving Points in Spatio-temporal Databases
Introduction
Related Work
A Review of the Modeling Strategy for Cardinal Direction Developments between Moving Points
Computing Developments between Moving Points
The Slice Representation for Moving Points
The Time-Synchronized Interval Refinement Phase
The Slice Unit Direction Evaluation Phase
The Direction Composition Phase
Defining Spatial-temporal Direction Predicates within Databases
Case Study: Cardinal Direction Development in Hurricane Research
Conclusions and Future Work
References
Continuous Probabilistic Count Queries in Wireless Sensor Networks
Introduction
Related Work
Background
Probabilistic Data Model
Probabilistic Count Query
Poisson Binomial Recurrence
Allowing Certainty
Probabilistic Count Queries in Wireless Sensor Networks
A Centralized Algorithm
A Centralized Incremental Algorithm
An In-Network Algorithm
An Incremental In-Network Algorithm
Performance Evaluation
Experiments and Results
Conclusions
References
Session 5: Multidimentional Query Processing
Geodetic Point-In-Polygon Query Processing in Oracle Spatial
Introduction
Prior Art
Geodetic PIP Query Processing
New R-Tree Index Query Processing
Determining Topological Relationship between R-Tree Index Entry and Query Polygon
Geodetic Point-In-Polygon Methods
Memory Usage
Experiments
Compare Geodetic PIP with Different Configurations
Different Limits of Entries in In-Memory R-Tree Structure
Compare NN-Based PIP and Ray-Based PIP
Conclusions
References
MSSQ: Manhattan Spatial Skyline Queries
Introduction
Related Work
Skyline Computation
Spatial Query Processing
Problem Definition
Observation
Algorithm
Data Structure
Computing the Common Intersection R(p)
For Data Points on the Boundary of R(p)
Computing all the Skyline Points
Implementation
PSQ
BBS
Experimental Evaluation
Experimental Settings
Efficiency
Conclusion
References
Inverse Queries for Multidimensional Spaces
Introduction
Related Work
Inverse Query (IQ) Framework
Inverse -Range Query
Framework Implementation
Algorithm
Inverse k-NN Query
Framework Implementation
Algorithm
Inverse Dynamic Skyline Query
IQ Framework Implementation
Algorithm
Experiments
Inverse -Range Queries
Inverse k-NN Queries
Inverse Dynamic Skyline Queries
Conclusions
References
Efficient Evaluation of k-NN Queries Using Spatial Mashups
Introduction
System Model
Processing k-NN Queries Using Spatial Mashups
Basic Algorithm
Our Efficient k-NN Query Processing Algorithm
Extensions
One-Way Road Segments
Grouping Users for Shared Execution
Performance Analysis
Performance Evaluation
Simulation Results
Experiment Results
Related Work
Conclusion
References
Session 6: Temporal and Streaming Data
SeTraStream: Semantic-Aware Trajectory Construction over Streaming Movement Data
Introduction
Related Work
Preliminaries
Data and Semantic Trajectory Models
Window Specifications
SeTraStream Overview
Online Data Preparation
Online Cleaning
Online Compression
Semantic Trajectory Construction
Online Episode Determination - Trajectory Segmentation
Time and Space Complexity
Episode Tagging
Experiments
Conclusions and Future Work
References
Mining Significant Time Intervals for Relationship Detection
Introduction
Problem Analysis
Finding T-Motifs
Significance of Time Intervals
Overview of Basic Algorithm
Speed Up the Searh for T-Motifs
Time-Indexed Meeting Pairs
Finding the Best Split Point
Experiment
Dataset Description
Discovery of T-Motifs
Efficiency Study
Relationship Detection Using T-Motifs
Related Work
Conclusion
References
A Uniform Framework for Temporal Functional Dependencies with Multiple Granularities
Introduction
A Motivating Scenario from Clinical Medicine
Temporal Data Model and Temporal Views
A Uniform Framework for TFDs
TFD Checking
Related Work
Conclusions
References
Quality of Similarity Rankings in Time Series
Introduction
Shared Nearest Neighbor Similarity
Experimental Setup
Distance Measures
Evaluation Criteria
Data Sets
Dimensional Scaling
Performance of Secondary Measures on Time Series
Discriminability of Classes
Impact of the Choice of s on SNN Distances
Results on Dimensionally Scaled Data Sets
Discussion and Conclusions
References
Vision and Challenge Papers
Managing and Mining Multiplayer Online Games
Introduction
Spatial Temporal Data Management
Monitoring Player Behavior
Conclusion
References
Citizens as Database: Conscious Ubiquity in Data Collection
Users as Data Providers
The Volunteered Image of the City
Conscious Ubiquity in Data Collection
References
Spatial Data Management over Flash Memory
Introduction
Data Structure Organization
Buffer Management
Conclusions and Outlook
References
Tipping Points, Butterflies, and Black Swans: A Vision for Spatio-temporal Data Mining Analysis
Vision
Challenges
Summary
References
On User-Generated Geocontent
Problem Description
Research Directions
Summary
References
Localizing the Internet: Implications of and Challenges in Geo-locating Everything Digital
Vision
Challenges
Conclusion
References
From Geography to Medicine: Exploring Innerspace via Spatial and Temporal Databases
References
Smarter Water Management: A Challenge for Spatio-Temporal Network Databases
References
Demonstratioions
FlexTrack: A System for Querying Flexible Patterns in Trajectory Databases
Introduction
The Flexible Pattern Query Language
Pattern Query Evaluation
Demonstration
Conclusion
References
A System for Discovering Regions of Interest from Trajectory Data
Introduction
Defining Regions of Interest
Indexing Trajectory Segments by Speed
Finding Regions of Interest
Step 2: Verifying the Duration Condition
Step 3: Finding Dense Regions
Demonstration
References
MARiO: Multi-Attribute Routing in Open Street Map
Introduction
System Overview and Functionalities
Implemented Algorithms
Demonstration
Conclusion
References
TiP: Analyzing Periodic Time Series Patterns
Introduction
Theoretical Background
Architecture
Demo Tour
References
An Extensibility Approach for Spatio-temporal Stream Processing Using Microsoft StreamInsight
Introduction
Motivation
The Case for Extensibility in a DSMS
Applying StreamInsight to the Spatial Domain
StreamInsight Overview
Capabilities of StreamInsight
Developing a Streaming Solution with StreamInsight
Demo Scenario
References
Efficient Spatio-temporal Sensor Data Loading for a Sensor Web Browser
Introduction
LOST-Tree
Demonstration
References
A Visual Evaluation Framework for Spatial Pruning Methods
Introduction
Domination Criteria
MinMax Domination
Trigonometric Pruning
Optimal DDC
Visual Evaluation of Pruning Criteria
Individual Object View
Data Set View
Conclusions
References
Spatial Outlier Detection: Data, Algorithms, Visualizations
Introduction
Workbench: System, Functionality, Work-Flow
Data - Typical Formats and Conversions
Spatial Outlier Detection Algorithms
Visualizations
Conclusion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken