Database Systems for Advanced Applications
16th International Conference, DASFAA 2011, Hong Kong, China, April 22-25, 2011, Proceedings, Part I
Published on 9. April 2011
XXII, 583 pages
978-3-642-20149-3 (ISBN)
Description
This two volume set LNCS 6587 and LNCS 6588 constitutes the refereed proceedings of the 16th International Conference on Database Systems for Advanced Applications, DASFAA 2011, held in Saarbrücken, Germany, in April 2010.
The 53 revised full papers and 12 revised short papers presented together with 2 invited keynote papers, 22 demonstration papers, 4 industrial papers, 8 demo papers, and the abstract of 1 panel discussion, were carefully reviewed and selected from a total of 225 submissions. The topics covered are social network, social network and privacy, data mining, probability and uncertainty, stream processing, graph, XML, XML and graph, similarity, searching and digital preservation, spatial queries, query processing, as well as indexing and high performance.
More details
Other editions
Additional editions
Jeffrey Xu Yu | Myoung Ho Kim | Rainer Unland
Database Systems for Advanced Applications
16th International Conference, DASFAA 2011, Hong Kong, China, April 22-25, 2011, Proceedings, Part I
Book
04/2011
1st Edition
Springer
€106.99
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents - Part I
- Keynote Talks
- Smarter Planet: Empower People with Information Insights
- Database Scalability, Elasticity, and Autonomy in the Cloud
- Introduc
- Database Scalability in the Cloud
- Scalability
- Data Fusion: Multi-key Atomicity in Key-Value Stores
- Data Fission: Database Partitioning Support in DBMS
- Database Elasticity in the Cloud
- Database Autonomy in the Cloud
- Concluding Remarks
- References
- Ten Year Award
- What Have We Learnt from Deductive Object-Oriented Database Research?
- References
- Social Network
- ECODE: Event-Based Community Detection from Social Networks
- Introduction
- Related Work
- The Proposed Technique
- Problem Definition
- Virtual Links between Events
- Similarity Measures
- ECODE Algorithm
- Assign People to Corresponding Communities
- Experimental Results
- Conclusions
- References
- A User Similarity Calculation Based on the Location for Social Network Services
- Introduction
- Related Work
- Preliminary
- Location Category
- Significant Score
- Similarity Score
- Significant Score Propagation
- User Similarity Calculation
- Overall Process
- Order of Match Nodes
- User Similarity Calculation
- Experiment
- Dataset
- Finding a Similar User
- Performance of Proposed Method
- Top-k Location
- Conclusion
- References
- Modeling User Expertise in Folksonomies by Fusing Multi-type Features
- Introduction
- Expertise Evidence in Folksonomy
- Feature Correlation
- Expertise Evidences
- CRF Based Expertise Model in Folksonomy
- Model Formulation
- Parameter Learning
- Empirical Study
- Experimental Setup
- Quantitative Result
- Related Work
- Conclusion
- References
- Identifying Topic Experts and Topic Communities in the Blogspace
- Introduction
- Related Work
- Experts on a Specific Topic
- Clusters of Keywords
- Approach of Identifying Experts
- Blog Communities on a Specific Topic
- Some Symbols and Definitions about Blog Graph
- Identifying Topic Blog Communities
- Experiments
- Identifying Experts on a Specific Topic
- Identifying Topic Blog Communities
- Conclusion
- References
- Social Network and Privacy
- Utility-Oriented K-Anonymization on Social Networks
- Introduction
- Preliminaries and Related Work
- Structural Re-identification Attack and K-Anonymity
- Related Work
- Graph Utility Measurement
- Hierarchical Random Graph
- Constructing HRG
- Hierarchical Community Entropy
- HRG Based K-Anonymization
- Basic Idea and Algorithm Framework
- Estimating Local Structure Information
- Generating Candidate Edge Operation Set
- Refining Target Local Structure Information
- Experimental Evaluation
- Utility Loss v.s. Graph Size
- Utility Loss v.s. k
- Conclusion
- References
- Distributed Privacy Preserving Data Collection
- Introduction
- Related Work
- Problem Formulation
- The System and the Adversaries
- Notion of Privacy
- Using Secret Sharing
- Towards the Solution
- A Sketch of the Solution
- Technical Details
- Analysis
- Information Leakage
- ?-Concealing Property
- Experimental Evaluation
- Evaluation of ?-Concealing Property
- Evaluation of Distance Preserving Mapping
- Evaluation of Utility Preservation
- Evaluation of System Time
- Conclusions
- References
- Privacy Preserving Query Processing on Secret Share Based Data Storage
- Introduction
- Preliminary
- Secret Share Scheme
- Data Division at DO
- Private Data Reconstruction at DR
- Storage Model and Privacy Preserving Index
- Storage Model
- Privacy Preserving Index
- Proposed Privacy Preserving Index
- Key Generation Function key_generation
- Index Creation Function index_creation
- Query Processing
- Experiments Evaluation
- Security Analysis
- Efficiency Evaluation
- Related Work
- Conclusions
- References
- Node Protection in Weighted Social Networks
- Introduction
- Problem Description
- Distance between Weight Sequences
- Absolute Distance
- Relative Distance
- Rate Distance
- Graph Construction Algorithm
- Algorithm Structure
- Assign New Weights
- Clustering
- Weight Adjustment
- Experiments
- DataSets
- Utilities
- Results
- Related Works
- Conclusion
- References
- Data Mining I
- An Unbiased Distance-Based Outlier Detection Approach for High-Dimensional Data
- Introduction
- Background and Literature Review
- Approach
- Outlier Score Function
- The HighDOD Method
- Theoretical Analysis
- Empirical Results and Analyses
- Conclusions
- References
- A Relational View of Pattern Discovery
- Introduction
- Basic Notions
- Relational Algebra
- Pattern Discovery
- Pattern-Oriented Relational Algebra
- Pattern-Oriented Attributes
- Cover, Semi-cover and Anti-cover Operators
- Domain Operator
- Scope of the Pattern-Oriented Relational Algebra
- Characterizing Pattern-Oriented Queries
- Downward Closed Query
- Local and Global Dependent Queries
- Rewriting Pattern-Oriented Queries
- Algebraic Laws Involving Cover-Like Operators
- Algebraic Reformulation of the Levelwise Algorithm
- Related Work
- Conclusion
- References
- Efficient Incremental Mining of Frequent Sequence Generators
- Introduction
- Problem Formulation
- Sequences and Generators
- Incremental Generator Mining
- GenTree: The Generating Tree
- The Concept of GenTree
- The Construction of GenTree
- The Node Type Switching of GenTree
- The IncGen Algorithm
- The IncGen-App Algorithm
- The IncGen-Ins and IncGen-Mix Algorithms
- Performance Study
- Test Environment and Datasets
- Performance Evaluation
- Related Works
- Conclusions
- References
- An Alternative Interestingness Measure for Mining Periodic-Frequent Patterns
- Introduction
- The Proposed Model and Pruning Techniques
- Proposed Model
- Pruning Techniques
- Proposed Algorithm
- ExPF-tree: Structure and Construction
- Mining ExPF-tree
- Experimental Results
- Conclusions
- References
- Data Mining II
- A Framework of Mining Semantic Regions from Trajectories
- Introduction
- Related Work
- A Framework of Mining Semantic Regions
- Overview
- Problem Formulation
- Discovering Semantic Regions
- Mining Frequent Semantic Regions
- Experiments
- Evaluation of Semantic Regions
- Accuracy of Frequent Semantic Regions
- Conclusion
- References
- STS: Complex Spatio-Temporal Sequence Mining in Flickr
- Introduction
- Preliminaries
- Problem Definition
- RelatedWork
- Approximation Algorithms
- Local Optimization Algorithms
- Global Optimization Algorithm
- Experimental Evaluation
- Conclusions and Future Work
- References
- Mining High Utility Mobile Sequential Patterns in Mobile Commerce Environments
- Introduction
- Related Work
- Problem Definition
- Proposed Methods
- Algorithm UMSP_DFG
- An Improved Tree-Based Method: An Improved Tree-Based Method: UMSP_DFG
- Experimental Results
- Conclusions
- References
- Reasoning about Dynamic Delegation in Role Based Access Control Systems
- Introduction
- An Overview of the Formal Framework
- Administrative Privilege Delegation Correctness
- Role and Access Right Assignment Correctness
- Degrees of Trust and Effective Trust
- Conflict Resolution
- Other Features
- Role Based Authorization Programs
- Syntax of RBAP
- Domain-Independent Rules
- Formal Semantics of RBAP
- Discussion and Related Work
- References
- Probability and Uncertainty
- Robust Ranking of Uncertain Data
- Introduction
- Probabilistic Data Model
- Related Work
- Robust Ranking Semantics
- U-Popk Algorithms
- Algorithm for Independent Tuples
- Algorithm for Tuples with Exclusion Rules
- Experiments
- Ranking Quality Comparison on IIP Iceberg Databases
- Scalability Evaluation
- Conclusion
- References
- Probabilistic Image Tagging with Tags Expanded By Text-Based Search
- Introduction
- Related Works
- Initial Tags
- Tags Expanding from Text-Based Search Result
- Initial Tags Denoising
- Tag Expansion
- Probability Flow
- Tag Refinement
- Correlation and Transition between Tags
- Tag Refinement
- Evaluations
- Dataset
- Image Tagging
- Image Retrieval
- Conclusions
- References
- Removing Uncertainties from Overlay Network
- Introduction
- Challenges and Our Contributions
- Probabilistic Lower Bounds of Query Delay of a Dynamic Overlay Network
- Topology Constructive and Data Placement Methods of Overlay Network
- Dynamic Multi-way Trie Tree Structure
- Mapping Overlay Network to Dynamic Trie Tree
- Data Placement Rule of Overlay Network
- Case Study
- Range Queries
- Performance Evaluation
- Conclusions
- References
- Probabilistic and Interactive Retrieval of Chinese Calligraphic Character Images Based on Multiple Features
- Introduction
- Background
- The PMF-Tree Index
- Preliminaries
- The Data Structure
- Building PMF-Tree
- Probabilistic $k$-NN Search Algorithm
- Experimental Results
- Effectiveness of the Retrieval Method
- Efficiency of PMF-Tree Index
- Conclusions
- References
- Stream Processing
- Real-Time Diameter Monitoring for Time-Evolving Graphs
- Introduction
- Contributions
- Problem Motivation
- Related Work
- Preliminary
- Monitoring the Diameter
- Ideas Behind G-Scale
- Reference Node Filtering
- Incremental Update
- Theoretical Analysis
- Accuracy
- Complexity
- Experimental Evaluation
- Efficiency and Scalability
- Effectiveness of Each Approach
- Exactness of the Monitoring Results
- Conclusions
- References
- Handling ER-topk Query on Uncertain Streams
- Introduction
- Our Contribution
- Data Models and Query Definition
- Our Solution
- domGraph
- probTree
- Handle a Request
- Experiments
- Related Work
- Conclusion
- References
- Seamless Event and Data Stream Processing: Reconciling Windows and Consumption Modes
- Introduction
- Integrated Event Stream Processing
- Event Consumption Modes
- Recent Consumption Mode
- Continuous Consumption Mode
- Chronicle Consumption Mode
- Cumulative Consumption Mode
- Consumption Modes in Other Systems
- Windows
- Tuple-based Window
- Time-based Window
- Summary
- Reconciliation of Windows and Consumption Modes
- Independent Approach
- Windows-Only Approach
- Hybrid Approach
- Analysis
- Conclusions and Future Work
- References
- Querying Moving Objects with Uncertainty in Spatio-Temporal Databases
- Introduction
- Related Work
- Modeling the Uncertainty of Moving Objects
- The Formalization of Uncertain Movements
- The Pendant Model as the Combination of Certain and Uncertain Movements
- Operations on the Pendant Model
- Spatio-Temporal Predicates with Uncertainty and Queries
- Definitions of Spatio-Temporal Uncertain Predicates
- Spatio-Temporal Uncertainty Queries
- Algorithms to Determine STUP
- Conclusions and Future Work
- References
- A Novel Hash-Based Streaming Scheme for Energy Efficient Full-Text Search in Wireless Data Broadcast
- Introduction
- Related Work
- Preliminary and System Model
- System Model
- Inverted List
- Hash Function and Collisions
- Data Structure of a Bucket
- Hash-Based Full-Text Search Methods
- Basic-Hash Data Streaming Scheme
- Merged-Hash Data Streaming Scheme
- Information Retrieval Protocol
- Performance Analysis
- Analysis for Basic-Hash
- Analysis for Merged-Hash
- Simulation and Performance Evaluation
- Comparison between Basic-Hash and Merged-Hash
- Comparison with Other Methods
- Conclusion
- References
- Graph
- Efficient Topological OLAP on Information Networks
- Introduction
- Problem Formulation
- Techniques and Framework
- T-Distributiveness
- T-Monotonicity
- T-OLAP Query Processing Framework
- Experimental Results
- Synthetic Data
- Real Data
- Related Work
- Conclusion
- References
- An Edge-Based Framework for Fast Subgraph Matching in a Large Graph
- Introduction
- Preliminaries
- Filtering and Verification Framework
- Representing Vertices and Edges
- Vertex and Edge Signatures
- Pre-processing
- Filtering
- Selecting a Spanning Tree
- Discovering Candidate Vertices
- Verification
- Heuristics for Fast Verification
- The FastMatch Algorithm
- The GetQualifiedCandidateVertices Function
- Improving the Connection-Aware Forward Checking Heuristic
- Discussion
- Evaluation
- Effect of the Size of the Query Graph
- Effect of the Average Degree of the Query Graph
- Related Work
- Conclusions
- References
- Context-Sensitive Query Expansion over the Bipartite Graph Model for Web Service Search
- Introduction
- Motivation
- Bipartite Graph Modeling to Service Context
- Topic Sensitive Bipartite Graph Constructing
- Bipartite Graph-Based Query Expansion
- Terms Filtering
- Semantics Bridging between Application (Query) Space and Service Space
- Query Expansion
- Experimental Results
- Experiment Data Set
- Data Status
- Evaluation Metrics
- Performance
- Related Work
- Conclusion and Future Work
- References
- BMC: An Efficient Method to Evaluate Probabilistic Reachability Queries
- Introduction
- Background
- Problem Definition
- Preliminaries
- Framework
- Upper Bound Index
- Dynamic Monte Carlo Simulation
- Experiment
- Real Dataset
- Synthetic Dataset
- Accuracy
- Related Work
- Conclusion
- References
- XML
- Improving XML Data Quality with Functional Dependencies
- Introduction
- Preliminaries
- Problem Formulation
- Fixing Initial Conflicts Based on Hypergraph
- Resolving Violations Thoroughly
- Implementation
- Experimental Study
- Experimental Setting
- Experimental Results
- Conclusions
- References
- Identifying Relevant Matches with NOT Semantics over XML Documents
- Introduction
- Basic Definitions
- SLCA Nodes with NOT Semantics
- Relevant Matches with NOT Semantics
- The RELMN Algorithm
- Definitions
- Algorithm
- Time Complexity
- Properties of Monotonicity and Consistency
- Experimental Evaluation
- Precision and Recall
- Processing Time and Scalability
- Related Works
- Conclusions
- References
- Evaluating Contained Rewritings for XPath Queries on Materialized Views
- Introduction
- Preliminaries
- XPath Tree Pattern
- Useful Embedding
- Basic Algorithm
- Optimizing Techniques
- Pruning Rules
- Heuristic Rules
- Optimized Algorithm
- Discussion
- Experiments
- Average Case Study
- Best and Worst Case Study
- Related Work
- Conclusions
- References
- XStreamCluster: An Efficient Algorithm for Streaming XML Data Clustering
- Introduction
- Related Work
- Streaming XML Clustering with XStreamCluster
- Preliminaries
- LSH-Based Candidate Clusters Detection
- Bottom-Level Strategy: Bloom Filter Based Distance Calculation
- Experimental Evaluation
- Efficiency
- Scalability
- Clustering Quality
- Conclusions
- References
- XML and Graph
- Efficient Evaluation of NOT-Twig Queries in Tree-Unaware Relational Databases
- Introduction
- Preliminaries
- Encoding Scheme
- SUCXENT++ Schema and Its Limitations
- AncestorValue Attribute
- AncestorDeweyGroup Attribute
- Ancestor Group-Based Approach
- Ancestor Group Identifier
- Computation of Common Ancestors
- Evaluation of NOT-Twig Queries
- SQL Translation Algorithm
- Performance Study
- Query Evaluation Times
- Conclusions and Future Work
- References
- A Hybrid Algorithm for Finding Top-k Twig Answers in Probabilistic XML
- Introduction
- Preliminaries
- Probabilistic XML Model
- Twig Query and Answers
- Encoding Scheme
- Improvement of the PEDewey Encoding
- HyTopKTwig: A Hybrid Algorithm
- Analysis of the Problem
- Data Structures and Notations
- Algorithm HyTopKTwig
- Analysis of Algorithm
- Experiments
- Experimental Setup
- Performance Study
- Conclusions
- References
- Optimizing Incremental Maintenance of Minimal Bisimulation of Cyclic Graphs
- Introduction
- Related Work
- Background
- Bisimulation of Cyclic Graphs
- Maintenance of Bisimulation
- Feature-Based Optimization
- Properties of Bisimulation of Cyclic Graphs
- Features of SCCs
- Offline versus Online Feature Construction
- Experimental Evaluation
- Conclusions
- References
- Social Based Layouts for the Increase of Locality in Graph Operations
- Introduction
- Related Work
- Community Based Data Layouts
- Community Layout - COM
- Truncated Community Layout - COM(x)
- Experimental Setup
- Social Network Generation
- Experiments
- Comparison of Layout Methods
- Scalability Analysis
- Community Size Discussion
- Profiling
- Conclusions and Future Work
- References
- Generating Random Graphic Sequences
- Introduction
- Background and Related Work
- Degree Sequences
- Graphic Sequences
- Random Walks on Markov Chains
- Generating Random Graphic Sequences
- Uniformly Random Graphic Sequence with Prescribed Length
- Uniformly Random Graphic Sequence with Prescribed Length and Sum
- Practical Optimization for D_u(n)
- Performance Evaluation
- Performance of D_u(n)
- Performance of D_u(n, s)
- Conclusion
- References
- Author Index
