›› 2010, Vol. 25 ›› Issue (2): 313-329.

• Distributed Computing and Systems • Previous Articles     Next Articles

Tree-Based Index Overlay in Hybrid Peer-to-Peer Systems

InSung Kang1, SungJin Choi2, Member, IEEE, SoonYoung Jung3, and SangKeun Lee1, *   

  1. 1Computer Science and Engineering Department, Korea University, Seoul, 136-713, Korea
    2Corporate Center, KT (Korea Telecom), Seoul, 137-792, Korea
    3Computer Science Education Department, Korea University, Seoul, 136-701, Korea
  • Received:2009-02-02 Revised:2010-01-20 Online:2010-03-05 Published:2010-03-05
  • About author:
    InSung Kang is a Ph.D. candidate in the College of Information and Communication, Korea University since 1999. He had been working on the electronic data processing job in the Bank. His current research interests include P2P computing, grids, fault tolerance and distributed systems. He received the M.S. degree in computer science from Yonsei University in 1988. Contact him at iskang@korea.ac.kr.
    SungJin Choi is a manager in corporate center KT (Korea Telecom), Seoul, Korea. His current research interests include P2P computing, desktop grids, volunteer computing, cloud computing, ubiquitous computing, mobile agents, and distributed systems. He is a member of the IEEE Computer Society. Dr. Choi received the M.S. and the Ph.D. degrees in computer science from Korea University in 2003 and 2007, respectively. Contact him at lotieye@gmail.com.
    SoonYoung Jung is a professor in the Department of Computer Science Education at Korea University. His research interests include grid computing, web-based education systems, database systems, knowledge management systems, and mobile computing. Dr. Jung received his Ph.D. degree in computer science from Korea University. Contact him at jsy@comedu.korea.ac.kr.
    SangKeun Lee received the B.S., M.S., and Ph.D. degrees in computer science and engineering from Korea University in 1994, 1996, and 1999, respectively. He was a recipient of the Japan Society for the Promotion of Science (JSPS) Postdoctoral Fellowship in 2000. Since 2003, he has been an assistant/associate professor in the College of Information and Communication, Korea University. His research interests include data management in mobile/pervasive computing systems, location-based information systems, XML databases, and data management in mobile ad hoc networks. Contact him at yalphy@korea.ac.kr.
  • Supported by:

    This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) under Grant No. KRF-2007-314-D00223.

PDF

1890

Hybrid Peer-to-Peer (P2P) systems that construct overlay networks structured among superpeers have great potential in that they can give the benefits such as scalability, search speed and network traffic, taking advantages of superpeer-based and the structured P2P systems. In this article, we enhance keyword search in hybrid P2P systems by constructing a tree-based index overlay among directory nodes that maintain indices, according to the load and popularity of a keyword. The mathematical analysis shows that the keyword search based on semi-structured P2P overlay can improve the search performance, reducing the message traffic and maintenance costs.

[1] Milojicic D S, Kalogeraki V, Lukose R, Nagaraha K, Pruyne J, Rollins S, Xu Z. Peer-to-peer computing. Technical Report, HP Laboratories Palo Alto, Mar. 2002.
[2] Li D, Xiao N, Lu X. Topology and resource discovery in peerto- peer overlay networks. In Grid and Cooperative Computing Workshops (GCC 2004), Wuhan, China, Oct. 20-24, 2004, pp.221-228.
[3] Androutsellis-Theotokis S, Spinellis D. A survey of peer-topeer content distribution technologies. ACM Comput. Surv., Dec. 2004, 36(4): 335-371.
[4] Choi S, Baik M, Gil J, Jung S, Hwang C. Adaptive group scheduling mechanism using mobile agents in peer-to-peer grid computing environment. Applied Intelligence, Oct. 2006, 25(2): 199-221.
[5] Napster. http://free.napster.com/.
[6] Ratnasamy S, Francis P, Handley M, Karp R, Shenker S. A scalable content addressable network. In Proc. the 2001 ACM SIGCOMM Conf., San Diego, CA, Aug. 27-31, 2001, pp.161- 172.
[7] Stoica I, Morris R, Karger D, Kaashoek F, Balakrishnan H. Chord: A scalable peer-to-peer lookup service for Internet applications. In Proc. the 2001 ACM SIGCOMM Conf., San Diego, CA, Aug. 27-31, 2001, pp.149-160.
[8] Rowstron A, Druschel P. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Proc. Middleware 2001, Heidelberg, Germany, Nov. 12-16, 2001, pp.329-350.
[9] Zhao B Y, Kubiatowicz J D, Joseph A D. Tapestry: An infrastructure for fault-tolerant widearea location and routing. Technical Report UCB/CSD-01-1141, UC Berkeley, Apr. 2001.
[10] Yang B, Garcia-Molina H. Improving search in peer-to-peer networks. In Proc. the 22nd Int. Conf. Distributed Computing Systems (ICDCS 2002), Vienna, Austria, Jul. 2-5, 2002, pp.5-14.
[11] Lv Q, Cao P, Cohen E, Li K, Shenker S. Search and replication in unstructured peer-to-peer networks. In Proc. the 16th Int. Conf. Supercomputing (ICS 2002), New York, USA, Jun. 22- 26, 2002, pp.84-95.
[12] Kalogeraki V, Gunopulos D, Zeinalipour-Yazti D. A local search mechanism for peer-to-peer networks. In Proc. the Eleventh Int. Conf. Information and Knowledge Management (CIKM2002), McLean, USA, Nov. 4-9, 2002, pp.300- 307.
[13] Chawathe Y, Ratnasamy S, Breslau L, Lanham N, Shenker S. Making Gnutella-like P2P systems scalable. In Proc. SIGCOMM, Karlsruhe, Germany, Aug. 25-29, 2003, pp.407-418.
[14] Tsoumakos D, Roussopoulos N. Adaptive probabilistic search for peer-to-peer networks. In Proc. the 3rd IEEE Int. Conf. P2P Computing, Linkoping, Sweden, Sep. 1-3, 2003, pp.102- 109.
[15] Menasce D, Kanchanapalli L. Probabilistic scalable P2P resource location services. SIGMETRICS Perform. Eval. Rev., Sep. 2002, 30(2): 48-58.
[16] Crespo A, Garcia-Molina H. Routing indices for peer-to-peer systems. In Proc. the 22nd Int. Conf. Distributed Computing Systems (ICDCS 2002), Vienna, Austria, Jul. 2-5, 2002, pp.23-32.
[17] Joseph S. NeuroGrid: Semantically routing queries in peerto- peer networks. In Proc. Networking 2002 Workshops Web Engineering and Peer-to-Peer Computing, Pisa, Italy, May 19-24, 2002, pp.202-214.
[18] Sripanidkulchai K, Maggs B, Zhang H. Efficient content location using interest-based locality in peer-to-peer systems. In Proc. IEEE INFOCOM 2003, San Francisco, USA, Mar. 30- Apr. 3, 2003, pp.2166-2176.
[19] Nakauchi K, Ishikawa Y, Morikawa H, Aoyama T. Peer-topeer keyword search using keyword relationship. In Proc. the Third Int. Workshop on Global and P2P Computing (GP2PC 2003), Tokyo, Japan, May 12-15, 2003, pp.359-366.
[20] Cai H, Wang J. Foreseer: A novel, locality-aware peer-topeer system architecture for keyword searches. In Proc. the 5th ACM/IFIP/USENIX Int. Conf. Middleware, Toronto, Canada, Oct. 18-22, 2004, pp.38-58.
[21] Cheng A H, Joung Y J. Probabilistic file indexing and searching in unstructured peer-to-peer networks. Computer Networks, 2006, 5(1): 106-127.
[22] Reynolds P, Vahdat A. Efficient peer-to-peer keyword searching. In Proc. Middleware 2003, Rio de Janeiro, Brazil, Jun. 16-20, 2003, pp.21-40.
[23] Harren M, Hellerstein J M, Huebsch R, Loo B T, Shenker S, Stoica I. Complex queries in DHT-based peer-to-peer networks. In Proc. Int. Workshop on Peer-to-Peer Systems (IPTPS 2002), Cambridge, MA, Mar. 7-8, 2002, pp.242-259.
[24] Garces-Erice L, Felber P A, Biersack E W, Urvoy-Keller G, Ross K W. Data indexing in peer-to-peer DHT networks. In Proc. the 24th Int. Distributed Computing Systems Conf. (ICDCS 2004), Tokyo, Japan, Mar. 23-26, 2004, pp.200-208.
[25] Joung Y, Yang L, Fang C. Keyword search in DHT-based peer-to-peer networks. IEEE Journal on Selected Areas in Communications, Jan. 2007, 25(1): 46-61.
[26] Zhuge H, Feng L. Distributed suffix tree overlay for peer-topeer search. IEEE Transactions on Knowledge and Data Engineering, Feb. 2008, 20(2): 276-285.
[27] Nejdl W, Siberski W, Sintek M. Design issues and challenges for RDF- and schema-based peer-to-peer systems. SIGMOD Rec., Sep. 2003, 32(3): 41-46.
[28] Mizrak A T, Cheng Y, Kumar V, Savage S. Structured superpeers: Leveraging heterogeneity to provide constant-time lookup. In Proc. the Third IEEE Workshop on Internet Applications (WIAPP 2003), San Jose, CA, Jun. 23-24, 2003, pp.104-111.
[29] KaZaA. http://www.kazaa.com/us/index.htm.
[30] Daswani S, Fisk A. Gnutella UDP extension for scalable searches (GUESS) v0.1. http://www.linewire.org/fisheye/browse/∼ raw, r=1.2/linescvs/core/quess 01.html, Aug. 2002.
[31] Singla A, Rohrs C. Ultrapeers: Another step towards Gnutella scalability version 1.0. http://www.linewire.com/en/download/? 404, Nov. 2002.
[32] Yang B, Garcia-Molina H. Designing a Super-Peer network. In Proc. the 19th Int. Conf. Data Engineering (ICDE 2003), Bangalore, India, Mar. 5-8, 2003, pp.49-60.
[33] Garbacki P, Epema D H, Steen M. V. Optimizing peer relationships in a SuperPeer network. In Proc. the 27th Int. Conf. Distributed Computing Systems (ICDCS 2007), Toronto, Canada, Jun. 25-29, 2007, pp.31-40.
[34] Blanco R, Ahmed N, Hadaller D, Sung L G A, Li H, Soliman M A. A survey of data management in peer-to-peer systems. Technical Report CS-2006-18, University of Waterloo, Jun. 2006.
[35] Lua E K, Crowcroft J, Pias M, Sharma R, Lim S. A survey and comparison of peer-to-peer overlay network schemes. IEEE Communications Surveys & Tutorials, 2005, 7(2): 72- 93.
[36] Dimitrios T, Nick R. Analysis and comparison of P2P search methods. In Proc. the 1st Int. Conf. Scalable Information Systems (InfoScale 2006), Hong Kong, China, May 29-Jun. 1, 2006, 152: 25.
[37] Freenet. http://freenetproject.org/.
[38] Risson J, Moors T. Survey of research towards robust peer-topeer networks: Search methods. Comput. Netw., Dec. 2006, 50(17): 3485-3521.
[39] Dynamic Querying. LimeWire, http://wiki.limewire.org/index. php?title=Dynamic-Querying.
[40] Tang C, Dwarkadas S. Hybrid global-local indexing for efficient peer-to-peer information retrieval. In Proc. the 1st Conf. Symposium on Networked Systems Design and Implementation (NSDI 2004), San Francisco, USA, Mar. 29-31, 2004, pp.16-30.
[41] Ganesan P, Sun Q, Garcia-Molina H. Adlib: A self-tuning index for dynamic peer-to-peer systems. In Proc. the 21st Int. Conf. Data Engineering (ICDE 2005), Tokyo, Japan, Apr. 5-8, 2005, pp.256-257.
[42] Li J, Loo B T, Hellerstein J M, Kaashoek M F, Karger D R, Morris R. On the feasibility of peer-to-peer web indexing and search. In Proc. the Second Int. Workshop on Peerto- Peer Systems (IPTPS 2003), Berkeley, USA, Feb. 20-21, 2003, pp.207-215.
[43] Gnawali O D. A keyword-set search system for peer-to-peer networks
[Master’s Thesis]. Massachusetts Institute of Technology, Jun. 2002.
[44] Tang C, Xu Z, Dwarkadas S. Peer-to-peer information retrieval using self-organizing semantic overlay networks. In Proc. SIGCOMM 2003, Karlsruhe, Germany, Aug. 25-29, 2003, pp.175-186.
[45] Zhou F, Zhuang L, Zhao B Y, Huang L, Joseph A D, Kubiatowics J. Approximate object location and spam filtering on peer-to-peer systems. In Proc. the 2003 ACM/IFIP/USENIX Int. Middleware Conf. (Middleware 2003), Rio de Janeiro, Brazil, Jun. 16-20, 2003, pp.1-20.
[46] Shi S, Yang G, Wang D, Yu J, Qu S, Chen M. Making peerto- peer keyword searching feasible using multi-level partitioning. In Proc. the 3rd Int. Workshop on Peer-to-Peer Systems (IPTPS 2004), San Diego, USA, Feb. 26-27, 2004, pp.151-161.
[47] Aberer K, Cudre-Mauroux P, Datta A, Despotovic Z, Hauswirth M, Punceva M, Schmidt R. P-Grid: A selforganizing structured P2P system. ACM SIGMOD Record, Sep. 2003, 32(3): 29-33.
[48] Jagadish H V, Ooi B C, Vu Q H. BATON: A balanced tree structure for peer-to-peer networks. In Proc. the 31st Int. Conf. Very Large Data Bases (VLDB2005), Trondheim, Norway, Aug. 30-Sept. 2, 2005, pp.12-21.
[49] Li M, Lee W, Sivasubramaniam A. DPTree: A balanced tree based indexing framework for peer-to-peer systems. In Proc. the 2006 IEEE Int. Conf. Network Protocols (ICNP 2006), Santa Barbara, CA, Nov. 12-15, 2006, pp.12-21.
[50] Zheng C, Shen G, Li S. Segment tree based control plane protocol for peer-to-peer on-demand streaming service discovery. In Proc. Visual Communication and Image Processing (VCIP 2005), Beijing, China, Jul. 2-15, 2005.
[51] Tanenbaum A S, Steen M V. Distributed Systems: Principles and Paradigms. Prentice Hall, 2002.
[52] Trivedi K S. Probability and Statistics with Reliability, Queuing and Computer Science Applications. Second Edition, WILEY, 2002.
[53] Gnutella. http://www.gnutella.com/.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved