Title

一個以RDF為基礎並支援萬用字元查詢的P2P系統

Translated Titles

A Novel RDF-based P2P System Supporting Wildcard Query

DOI

10.6845/NCHU.2012.00821

Authors

黃宣尹

Key Words

分散雜湊表 ; 點對點網路 ; 萬用字元 ; 資源描述框架 ; Distributed hash table ; DHT ; Peer-to-Peer network ; Wildcard ; RDF

PublicationName

中興大學資訊管理學系所學位論文

Volume or Term/Year and Month of Publication

2012年

Academic Degree Category

碩士

Advisor

呂瑞麟

Content Language

英文

Chinese Abstract

近年來,許多P2P方面的研究開始朝著語意式P2P系統的方向發展。語意式P2P系統使用中介資料(Metadata)描述資源,因此能夠提供複雜的查詢,如RDFPeers和RDF-Chord能支援範圍查詢。然而,現存的語意式系統中,沒有任何一個系統能夠支援萬用字元(Wildcard)查詢。 在本論文中,我們提出了一個以資源描述框架(RDF)為基礎並支援萬用字元查詢的P2P系統,稱為RDFChord-W。RDFChord-W能夠支援包括atomic查詢、conjunctive查詢、disjunctive查詢、範圍查詢以及萬用字元查詢等複雜的查詢。在RDFChord-W中,節點被分配到多個層上,每一層上的節點形成一個如Chord般的環狀結構;擁有資源的節點根據描述其資源的RDF檔案產生索引,並將產生的索引發佈至相對應的節點上。根據我們的文獻探討,RDFChord-W是第一個能夠支援萬用字元查詢的語意式P2P系統。雖然RDFChord-W支援了多種查詢的型態,其整體效能表現仍較支援類似查詢型態的系統(如RDFPeers和Squid)好。

English Abstract

In recent years, a new area of P2P research called semantic-based systems has emerged. The semantic-based P2P systems use metadata to describe resources so that complex queries can be implemented. Although systems such as RDFPeers and RDF-Chord support complex query including range query, none of these systems supports wildcard query. In this thesis, we propose a RDF-based P2P system, called RDFChord-W, which supports all atomic queries, conjunctive and disjunctive queries, range query, and wildcard query. In RDFChord-W, nodes are arranged into multiple layers where each layer is a Chord-like ring. Resources are described with RDF triples, and indices are generated by hashing the RDF triples and distributed to corresponding nodes. Based on our survey, RDFChord-W is the first RDF-based P2P system that supports wildcard queries. Although more query types are added, the performance of RDFChord-W is still superior to systems such as RDFPeers and Squid which support similar queries.

Topic Category 管理學院 > 資訊管理學系所
社會科學 > 管理學
Reference
  1. [1] A. Rowstron, and P. Druschel, "Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems," Proceedings of IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, pp. 329-350, 2001.
    連結:
  2. [2] B. H. Bloom, "Space/time trade-offs in hash coding with allowable errors," Communications of ACM, vol. 13, no. 7, pp. 422–426, 1970.
    連結:
  3. [3] B.Y. Zhao, L. Huang, J. Stribling, S. Rhea, A. Joseph, and J. Kubiatowicz, "Tapestry: A Resilient Global-Scale Overlay for Service Deployment," IEEE Journal on Selected Areas in Communications, vol. 22, pp. 41-53, 2004.
    連結:
  4. [4] C. Schmidt and M. Parashar, "Squid: Enabling Search in DHT-based Systems," Journal of Parallel and Distributed Computing, vol. 68, no. 7, pp. 962-975, 2008.
    連結:
  5. [5] C.L. Yeh, C.F. Chang, and K.C. Lin, "Two-Level Chord-Ring for Ontology-based Distributed RDF Store," Proceedings of International Conference on Complex, Intelligent and Software Intensive Systems (CISIS 2010), Krakow, pp. 283-290, 2010.
    連結:
  6. [7] E.J.L. Lu, Y.F. Huang, and S.C. Lu, "ML-Chord: A Multi-Layered P2P Resource Sharing Model," Journal of Network and Computer Applications, vol. 32, no. 3, pp. 578-588, 2009.
    連結:
  7. [8] E.J.L. Lu, Y.H. Chen, S.Y. Huang, and Y.T. Chang, "RDF-Chord: A Semantic-based P2P System for RDF Queries," Proceedings of International Conference on Communications, Mobility, and Computing (CMC 2012), Guilin, pp. 162-166, 2012.
    連結:
  8. [9] H. Sagan, Space-Filling Curves, Springer-Verlag, 1994.
    連結:
  9. [10] H. Zhuge, J. Liu, and L. Feng, Xiaoping Sun, and Chao He, "Query Routing in a Peer-to-Peer Semantic Link Network," Computational Intelligence, vol. 21, no. 2, pp. 197-216, 2005.
    連結:
  10. [12] J. Liu and H. Zhuge, "A Semantic-based P2P Resource Organization Model R-Chord," Journal of Systems and Software, vol. 79, no. 11, pp. 1619-1631, 2006.
    連結:
  11. [13] M. Cai, M. Frank, B. Yan, and R. MacGregor, "A Subscribable Peer-to-Peer RDF Repository for Distributed Metadata Management," Journal of Web Semantics: Science, Services and Agents on the World Wide Web, vol. 2, no.2, pp. 109-130, 2004.
    連結:
  12. [14] M. Cai, M. Frank, J. Chen, and P. Szekely, "MAAN: A Multi-Attribute Addressable Network for Grid Information Services," Journal of Grid Computing, vol.2, no.1, pp. 3-14, 2004.
    連結:
  13. [15] P. Cudre-Mauroux, S. Agarwal, K. Aberer, "GridVine: An Infrastructure for Peer Information Management," IEEE Transactions on Internet Computing, vol. 11, no. 5, pp. 36-44, 2007.
    連結:
  14. [16] PeerSim, 2006. Available from: < http://peersim.sourceforge.net/>.
    連結:
  15. [17] R. Ahmed and R. Boutaba, "Distributed Pattern Matching: A Key to Flexible and Efficient P2P Search," IEEE Journal on Selected Areas in Communications, vol. 25, no.1. pp. 73-83, 2007.
    連結:
  16. [18] R. Ahmed and R. Boutaba, "Plexus: A Scalable Peer-to-Peer Protocol Enabling Efficient Subset Search," IEEE/ACM Transactions on Networking, vol. 17, no. 1, pp. 130-143, 2009.
    連結:
  17. [19] Resource Description Framework, Available from:
    連結:
  18. [6] D. Li, J. Cao, X. Lu, and K. Chen, "Efficient Range Query Processing in Peer-to-Peer Systems," IEEE Transactions on Knowledge and Data Engineering, vol.21, no.1, pp.78-91, 2009.
  19. [11] I. Stoica, R. Morris, D. Liben-Nowell, D.R. Karger, M.F. Kaashoek, F. Dabek, and H. Balakrishnan, "Chord: a scalable peer-to-peer lookup protocol for Internet applications," IEEE/ACM Transactions on Networking, vol.11, no.1, pp. 17- 32, 2003.
  20. [20] Y.J. Joung and L.W. Yang, "Wildcard Search in Structured Peer-to-Peer Networks," IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 11, pp. 1524-1540, 2009.
  21. [21] Z. Kaoudi, M. Koubarakis, K. Kyzirakos, I. Miliaraki, M. Magiridou, and A. Papadakis-Pesaresi, "Atlas: Storing, Updating and Querying RDF(S) Data on Top of DHTs," Journal of Web Semantics: Science, Services and Agents on the World Wide Web, vol. 8, no. 4, pp. 271–277, 2010.