Advances in Spatial and Temporal Databases
12th International Symposium, SSTD 2011, Minneapolis, MN, USA, August 24-26, 2011. Proceedings
Published on 28. July 2011
XIV, 518 pages
978-3-642-22922-0 (ISBN)
Description
This volume constitutes the refereed proceedings of the 12th International Symposium on Spatial and Temporal Databases, SSTD 2011, held in Minneapolis, USA, in August 2011. The 24 revised full papers presented together with one keynote, 8 short papers, and 8 demonstration papers, were thoroughly reviewed and selected from a total of 63 research submissions, 21 vision and challenges submissions and 16 demonstration submissions. The papers are organized in topical sections on knowledge discovery; spatial networks; access methods; moving objects and sensor networks; multidimensional query processing; and temporal and streaming data.
More details
Other editions
Additional editions
Dieter Pfoser | Yufei Tao | Kyriakos Mouratidis
Advances in Spatial and Temporal Databases
12th International Symposium, SSTD 2011, Minneapolis, MN, USA, August 24-26, 2011. Proceedings
Book
07/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- 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
