This book details recent developments in the emerging area of plug-and-play (PnP) visual subgraph query interfaces (VQI). These PnP interfaces are grounded in the principles of human-computer interaction (HCI) and cognitive psychology to address long-standing limitations to bottom-up search capabilities in graph databases using traditional graph query languages, which often require domain experts and specialist programmers. This book explains how PnP interfaces go against the traditional mantra of VQI construction by taking a data-drivenapproach and giving end users the freedom to easily and quickly construct and maintain a VQI for any data sources without resorting to coding. The book walks readers through the intuitive PnP interface that uses templates where the underlying graph repository represents the socket and user-specified requirements represent the plug. Hence, a PnP interface enables an end user to change the socket (i.e., graph repository) or the plug (i.e., requirements) as necessary to automatically and effortlessly generate VQIs. The book argues that such a data-driven paradigm creates several benefits, including superior support for visual subgraph query construction, significant reduction in the manual cost of constructing and maintaining a VQI for any graph data source, and portability of the interface across diverse sources and querying applications. This book provides a comprehensive introduction to the notion of PnP interfaces, compares it to its classical manual counterpart, and reviews techniques for automatic construction and maintenance of these new interfaces. In synthesizing current research on plug-and-play visual subgraph query interface management, this book gives readers a snapshot of the state of the art in this topic as well as future research directions.
Author(s): Sourav S. Bhowmick, Byron Choi
Series: Synthesis Lectures on Data Management
Publisher: Springer
Year: 2023
Language: English
Pages: 181
City: Cham
Foreword by the Series Editor
Preface
Contents
About the Authors
1 The Future is Democratized Graphs
[DELETE]
1.1 Querying Graphs
1.2 Subgraph Query Formulation Process
1.3 Graph Query Languages
1.4 Toward Graph Databases for All!
1.5 Visual Subgraph Query Interfaces (VQIs)
1.6 Limitations of Existing VQI
1.7 Plug-and-Play (PnP) Interfaces—Democratizing Subraph Querying
1.8 Overview of This Book
1.9 Scope
2 Background
[DELETE]
2.1 Graph Terminology
2.1.1 Subgraph Isomorphism-Related Terminology
2.1.2 Maximum (Connected) Common Subgraph
2.1.3 k-Truss
2.1.4 Types of Graph Collection
2.2 Cognitive Load
2.3 Usability
2.4 Conclusions
3 The World of Visual Graph Query Interfaces—An Overview
[DELETE]
3.1 Visual Subgraph Query Formulation (VQF) Approaches
3.2 Visual Subgraph Query Interfaces (VQI)
3.2.1 First Generation VQI
3.2.2 Second Generation VQI
3.2.3 Third Generation VQI
3.3 Comparative Analysis
3.4 Conclusions
4 Plug-and-Play Visual Subgraph Query Interfaces
[DELETE]
4.1 Assumptions Made by Existing VQI
4.2 Limitations of Existing VQI
4.3 Design Principles of Plug-and-Play VQI
4.4 Plug-and-Play (PnP) Interface
4.4.1 PnP Template
4.4.2 Plug
4.4.3 PnP Engine
4.4.4 Play Mode
4.5 Benefits of PnP Interfaces
4.6 Conclusions
5 The Building Block of PnP Interfaces: Canned Patterns
[DELETE]
5.1 Characteristics of Canned Patterns
5.2 Quantifying Coverage
5.3 Quantifying Diversity
5.4 Quantifying Cognitive Load
5.5 Conclusions
6 Pattern Selection for Graph Databases
[DELETE]
6.1 Closure Graph
6.2 Canned Pattern Selection Problem
6.3 The CATAPULT Framework
6.4 Cluster Summary Graph (CSG) Generation
6.4.1 Small Graph Clustering
6.4.2 Generation of CSGs
6.4.3 Handling Larger Graph Databases
6.5 Selection of Canned Patterns
6.6 Selection of Basic Patterns
6.7 Performance Study
6.7.1 Experimental Setup
6.7.2 Experimental Results
6.8 AURORA—A PnP Interface for Graph Databases
6.8.1 VQI Structure
6.8.2 Pattern-at-a-time Query Formulation
6.8.3 User Experience and Feedback
6.9 Conclusions
7 Pattern Selection for Large Networks
[DELETE]
7.1 The CPS Problem
7.2 Categories of Canned Patterns
7.2.1 Topologies of Real-World Queries
7.2.2 Topologies of Canned Patterns
7.3 Candidate Pattern Generation
7.3.1 Truss-Based Graph Decomposition
7.3.2 Patterns from a TIR Graph
7.3.3 Patterns from a TOR Graph
7.4 Selection of Canned Patterns
7.4.1 Theoretical Analysis
7.4.2 Quantifying Coverage and Similarity
7.4.3 CPS-Randomized Greedy Algorithm
7.5 Performance Study
7.5.1 Experimental Setup
7.5.2 User Study
7.5.3 Automated Performance Study
7.6 PLAYPEN—A PnP Interface for Large Networks
7.6.1 Pattern-at-a-Time Query Formulation
7.6.2 User Experience and Feedback
7.7 Conclusions
8 Maintenance of Patterns
[DELETE]
8.1 The CPM Problem
8.1.1 Problem Definition
8.1.2 Design Challenges
8.1.3 Scaffolding Strategy
8.1.4 Selective Maintenance Strategy
8.2 The MIDAS Framework
8.3 Maintenance of Clusters and CSGs
8.3.1 Closure Property of FCT
8.3.2 Maintenance of FCT
8.3.3 Maintenance of Graph Clusters
8.3.4 Maintenance of CSG Set
8.4 Candidate Pattern Generation
8.4.1 FCT-Index and IFE-Index
8.4.2 Pruning-Based Candidate Generation
8.5 Canned Pattern Maintenance
8.5.1 Pattern Score
8.5.2 Swap-based Pattern Maintenance
8.6 Maintenance of Basic Patterns
8.7 Performance Study
8.7.1 Experimental Setup
8.7.2 User Study
8.7.3 Experimental Results
8.8 MIDAS in AURORA
8.9 Conclusions
9 The Road Ahead
[DELETE]
9.1 Summary
9.1.1 Plug-and-Play (PnP) Interfaces
9.1.2 Canned Patterns—The Building Block of PnP Interfaces
9.1.3 Pattern Selection for Graph Databases
9.1.4 Pattern Selection for Large Networks
9.1.5 Pattern Maintenance
9.1.6 Usability Results
9.2 Future Directions
References
Index
