Abstract
The scalability and flexibility of the Resource Description Framework (RDF) model make it ideally suited for representing online social networks (OSN). One basic operation in OSN is to find chains of relations, such as k-Hop friends. Property path query in SPARQL can express this type of operation, but its implementation suffers from performance problems considering the ever-growing data size and complexity of OSN. In this paper, we present a main memory/disk-based hybrid RDF data management framework for efficient property path query. In this hybrid framework, we realize an efficient in-memory algebra operator for property path query using graph traversal and estimate the cost of this operator to cooperate with existing cost-based optimization. Experiments on benchmark and real datasets demonstrated that our approach can achieve a good tradeoff between data load expense and online query performance.
The Challenge of Social Network Path Queries
Online Social Networks (OSNs) are naturally modeled by RDF, yet querying them remains a significant performance hurdle. Specifically, "Property Path" queries—which identify chains of relationships like "friends-of-friends"—are notoriously slow in traditional RDF stores such as Jena or Sesame.
Traditional stores typically treat path queries as a series of expensive relational "join" operations. While specialized in-memory graph databases offer a solution, social network data is often too massive to fit entirely in RAM. Loading every user attribute (bios, birthdates, profile text) into memory is impractical and expensive. There is a clear need for a system that combines the speed of in-memory graph traversal for relationships with the storage efficiency of disks for metadata.
A Hybrid Architecture for RDF Management
The proposed framework is designed as a plugin for the Jena TDB triple store, utilizing a hybrid architecture to balance performance and resource usage.
The system employs three key strategies:
- Rule-Based Data Partitioning: During data loading, triples are automatically separated. Attributes (e.g., "User hasName 'John'") are stored on disk, while relationship triples (e.g., "User1 knows User2") are duplicated into a specialized in-memory index.
- In-Memory Graph Traversal: The system introduces a new algebra operator,
OpPath, which performs Breadth-First Search (BFS) on the in-memory topology. This traversal-based approach is significantly more efficient than relational joins, reducing computational complexity. - Cost Estimation Model: To assist the SPARQL query optimizer, the authors developed a mathematical heuristic to estimate the result cardinality of path queries. This allows the system to intelligently order operations, such as applying filters before or after path searches.
Evaluation and Results
The framework was evaluated using the Social Network Intelligence Benchmark (SNIB) and the DBLP bibliographic dataset.
Key Insights
- The 80/20 Rule of Social Data: The authors observed that the vast majority of OSN triples are attributes rather than links. By keeping only the "topology" (the links) in memory, they achieve massive speedups with a fraction of the RAM required by full in-memory databases.
- Efficiency and Accuracy: The hybrid approach outperformed standard Jena and Sesame on the SNIB benchmark. Furthermore, the cost-estimation heuristic achieved a relative error of only 27-32%, providing a reliable basis for query optimization.
Conclusion
This hybrid RDF management framework demonstrates that partitioning graph topology from node attributes allows for high-performance path queries without the prohibitive memory costs of pure in-memory systems. Future work will focus on more sophisticated rule-based filtering for complex ontologies and exploring distributed architectures for extremely large-scale graphs.
Summary updated