Towards Efficient Path Query on Social Network with Hybrid RDF Management

详细信息    查看全文

• 作者：Lei Gai (19)
  Wei Chen (19)
  Zhichao Xu (19)
  Changhe Qiu (19)
  Tengjiao Wang (19)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8709
• 期：1
• 页码：525-532
• 全文大小：600 KB
• 参考文献：1. Fan, W., Li, J., Ma, S., Tang, N., Wu, Y.: Adding Regular Expressions to Graph Reachability and Pattern Queries. In: 2011 IEEE 27th International Conference on Data Engineering (ICDE), pp. 39鈥?0. IEEE (2011)
  2. Gubichev, A., Bedathur, S.J., Seufert, S.: Sparqling Kleene: Fast Property Paths in RDF-3X. In: First International Workshop on Graph Data Management Experiences and Systems, p. 14. ACM (2013)
  3. Janik, M., Kochut, K.: BRAHMS: A WorkBench RDF Store and High Performance Memory System for Semantic Association Discovery. In: Gil, Y., Motta, E., Benjamins, V.R., Musen, M.A. (eds.) ISWC 2005. LNCS, vol.聽3729, pp. 431鈥?45. Springer, Heidelberg (2005) CrossRef
  4. Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph Evolution: Densification and Shrinking Diameters. ACM Transactions on Knowledge Discovery from Data (TKDD)聽1(1) (2007)
  5. Neumann, T., Weikum, G.: RDF-3X: A RISC-style Engine for RDF. Proceedings of the VLDB Endowment聽1(1), 647鈥?59 (2008) CrossRef
  6. Pham, M.-D., Boncz, P., Erling, O.: S3G2: A Scalable Structure-Correlated Social Graph Generator. In: Nambiar, R., Poess, M. (eds.) TPCTC 2012. LNCS, vol.聽7755, pp. 156鈥?72. Springer, Heidelberg (2013) CrossRef
  7. Sakr, S., Elnikety, S., He, Y.: G-SPARQL: A Hybrid Engine for Querying Large Attributed Graphs. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp. 335鈥?44. ACM (2012)
  8. Stocker, M., Seaborne, A., Bernstein, A., Kiefer, C., Reynolds, D.: SPARQL Basic Graph Pattern Optimization Using Selectivity Estimation. In: Proceedings of the 17th International Conference on World Wide Web, pp. 595鈥?04. ACM (2008)
  9. Zeng, K., Yang, J., Wang, H., Shao, B., Wang, Z.: A Distributed Graph Engine for Web Scale RDF Data. In: Proceedings of the 39th International Conference on Very Large Data Bases, pp. 265鈥?76. VLDB Endowment (2013)
  10. Zou, L., Xu, K., Yu, J.X., Chen, L., Xiao, Y., Zhao, D.: Efficient Processing of Label-constraint Reachability Queries in Large Graphs. Information Systems聽40, 47鈥?6 (2014) CrossRef
  
• 作者单位：Lei Gai (19)
  Wei Chen (19)
  Zhichao Xu (19)
  Changhe Qiu (19)
  Tengjiao Wang (19)
  
  19. School of Electronic Engineering and Computer Science, Peking University, Beijing, China
  
• ISSN：1611-3349

文摘

The scalability and flexibility of 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 problem 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. This hybrid framework realizes an efficient in-memory algebra operator for property path query using graph traversal, and estimates the cost of this operator to cooperate with existing cost-based optimization. Experiments on benchmark and real dataset demonstrated that our approach achieves a good tradeoff between data load expense and online query performance.