We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 25 Issue 2
March  2010
Turn off MathJax
Article Contents
Abstract
References
Related Articles
InSung Kang, SungJin Choi, SoonYoung Jung, SangKeun Lee. Tree-Based Index Overlay in Hybrid Peer-to-Peer Systems[J]. Journal of Computer Science and Technology, 2010, 25(2): 313-329.
Citation: InSung Kang, SungJin Choi, SoonYoung Jung, SangKeun Lee. Tree-Based Index Overlay in Hybrid Peer-to-Peer Systems[J]. Journal of Computer Science and Technology, 2010, 25(2): 313-329.
shu

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

  • 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

Funds: This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) under Grant No. KRF-2007-314-D00223.
More Information
  • Author Bio:

    InSung Kang is a Ph.D. candidate in the College of Information andCommunication, Korea University since 1999. He had been working onthe electronic data processing job in the Bank. His current researchinterests include P2P computing, grids, fault tolerance anddistributed systems. He received the M.S. degree in computer sciencefrom Yonsei University in 1988. Contact him at iskang@korea.ac.kr.

    SungJin Choi is a manager in corporate centerKT (Korea Telecom), Seoul, Korea. His current research interestsinclude P2P computing, desktop grids, volunteer computing, cloudcomputing, ubiquitous computing, mobile agents, and distributedsystems. He is a member of the IEEE Computer Society. Dr. Choireceived the M.S. and the Ph.D. degrees in computer science from KoreaUniversity in 2003 and 2007, respectively. Contact him at lotieye@gmail.com.

    SoonYoung Jung is a professor in the Department of Computer ScienceEducation at Korea University. His research interests include gridcomputing, web-based education systems, database systems, knowledgemanagement systems, and mobile computing. Dr. Jung received hisPh.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 andengineering from Korea University in 1994, 1996, and 1999,respectively. He was a recipient of the Japan Society for thePromotion of Science (JSPS) Postdoctoral Fellowship in 2000. Since2003, he has been an assistant/associate professor in the College ofInformation and Communication, Korea University. His researchinterests include data management in mobile/pervasive computingsystems, location-based information systems, XML databases, and datamanagement in mobile ad hoc networks. Contact him at yalphy@korea.ac.kr.

  • Received Date: February 01, 2009
  • Revised Date: January 19, 2010
  • Published Date: March 04, 2010
    Abstract
  • 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.
    • FullText(HTML)
    • References (53)
  • [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/.
    • Relative Articles

  • Related Articles

    [1]Qi Wang, Jia-Rui Li, Dong-Hui Wang. Improving the Performance and Energy Efficiency of Phase Change Memory Systems[J]. Journal of Computer Science and Technology, 2015, 30(1): 110-120. DOI: 10.1007/s11390-015-1508-3
    [2]Hai-Bo Chen, Feng-Zhe Zhang, Rong Chen, Bin-Yu Zang, Pen-Chung Yew. Mercury: Combining Performance with Dependability Using Self-Virtualization[J]. Journal of Computer Science and Technology, 2012, 27(1): 92-104. DOI: 10.1007/s11390-012-1208-1
    [3]Gang Huang, Li Zhou, Xuan-Zhe Liu, Hong Mei, Shing-Chi Cheung. Performance Aware Service Pool in Dependable Service Oriented Architecture[J]. Journal of Computer Science and Technology, 2006, 21(4): 565-573.
    [4]Ben Leslie, Peter Chubb, Nicholas Fitzroy-Dale, Stefan Gotz, Charles Gray, Luke Macpherson, Daniel Potts, Yue-Ting Shen, Kevin Elphinstone. User-Level Device Drivers: Achieved Performance[J]. Journal of Computer Science and Technology, 2005, 20(5): 654-664.
    [5]Chun-Hua Yang, Geert Deconinck, Wei-Hua Gui. Fault-Tolerant Scheduling for Real-Time Embedded Control Systems[J]. Journal of Computer Science and Technology, 2004, 19(2).
    [6]JIN Zhigang, SHU Yantai, Oliver W.W.Yang. The Impact of Non-Gaussian Distribution Traffic on Network Performance[J]. Journal of Computer Science and Technology, 2002, 17(1).
    [7]WEI Xiaohui, JU Jiubin. SCR Algorithm: Saving/Restoring States of File Systems[J]. Journal of Computer Science and Technology, 2000, 15(4): 393-400.
    [8]LI Layuan, LI Chunlin. A Semantics-Based Approach for Achieving Self Fault-Tolerance of Protocols[J]. Journal of Computer Science and Technology, 2000, 15(2): 176-183.
    [9]WEI Hua, LUO Yupin, YANG Shiyuan. Fault Tolerance of Reconfigurable Bi-Directional Double-Loop LANs[J]. Journal of Computer Science and Technology, 1999, 14(4): 379-385.
    [10]Yao Rong, Chen Tinghuai, Kang Tai. Fault-Tolerance Analysis of Multibus Multiprocessor System[J]. Journal of Computer Science and Technology, 1989, 4(2): 172-177.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (20) PDF downloads (1900) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return