期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

结构化覆盖网络CayDHT的复杂搜索算法

Complex Search Algorithm for Structured Overlay Network CayDHT
下载PDF
导出
摘要 CayDHT是一种基于Cayley图的常数度结构化对等覆盖网络,对于精确的单关键字搜索效率非常高,但不支持不限定搜索形式的复杂搜索.通过分析CayDHT的拓扑性质,提出了一种基于虚拟搜索树的复杂搜索算法VTCS.该算法无需维护额外的树结构,根据消息参数就可以获得下一跳节点的地址.理论分析表明该算法可以在O(logN)的时间复杂度内完成无冗余消息的搜索.仿真实验比较了Flooding、RW和VTCS,结果表明VTCS是较为合理的方案. CayDHT is a constant-degree structured peer-to-peer overlay network based on Cayley graph,and it is very efficient in accurate single keyword search but does not support complex searches with unrestricted form.In this paper,by analyzing the topological properties of CayDHT,a virtual tree-based complex search（VTCS） algorithm is proposed,which needs no maintenance of the extra tree structure and can obtain the address of the next hop only according to the parameters inside the messages.Theoretical analyses indicate that the proposed algorithm can complete the search without redundant messages within O（logN） hops.Simulation results show that VTCS is more reasonable than Flooding and RW.
作者 梁活民 肖文俊 魏文红
机构地区 华南理工大学计算机科学与工程学院 华南理工大学软件学院 华南理工大学电子与信息学院
出处 《华南理工大学学报（自然科学版）》 EI CAS CSCD 北大核心 2011年第10期84-89,共6页 Journal of South China University of Technology(Natural Science Edition)
基金 国家自然科学基金资助项目(61170313 61103037) 博士后科学基金资助项目(20110490883)
关键词 覆盖网络 CayDHT CAYLEY图 复杂搜索 overlay networks CayDHT Cayley graph complex search
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献12

  • 1Reynolds P, Vahdat A. Efficient peer-to-peer keyword searching [ C ] Jj Proceeding of the ACM/IFIP/USENIX 2003 International Conference on Middleware. Rio de Ja- neiro : Springer, 2003 : 21 - 40.
  • 2Joung Y, Yang L, Fang C, et al. Keyword search in dht- based peer-to-peer networks [ J ]. IEEE Journal on Se- lected Areas in Communications,2007,25:46-61.
  • 3Xiao W, Parhami B. Cayley graphs as models of determini- stic small-world networks [ J ]. Information Processing Letters ,2006,97 ( 3 ) : 115-117.
  • 4Qu c, Nejdl W, Kriesell M. Cayley DHTs-a group-theore- tic framework for analyzing DHTs based on cayley graphs [ C ] //Proceedings of the Second International Symposium on Parallel and Distributed Processing and Applications. Hong Kong : Springer,2004:914-925.
  • 5魏文红,肖文俊.一种具有小世界特征的结构化P2P覆盖网络[J].华南理工大学学报（自然科学版）,2009,37(10):66-72. 被引量：2
  • 6梁活民,肖文俊.一种具有小世界网络特征的常数度结构化覆盖网络[J].计算机学报,2010,33(9):1541-1547. 被引量：9
  • 7Hautakorpi J, Schultz G. A feasibility study of an arbitrary search in structured peer-to-peer networks [ C ] //Pro- ceedings of the 19th International Conference on Computer Communications and Networks. Zurich : IEEE, 2010 : 1 -8.
  • 8Kalogeraki V, Gunopulos D, Zeinalipour-Yazti D. A local search mechanism for peer-to-peer networks [ C ]// Pro- ceedings of the 11 th International Conference on Informa- tion and Knowledge Management. McLean : ACM, 2002 : 300-307.
  • 9Lv Q, Cao P, Cohen E,et al. Search and replication in un- structured peer-to-peer networks [ C ]//Proceedings of the 16th ACM International Conference on Supercomputing. New York : ACM, 2002 : 84- 95.
  • 10Vishnevsky V, Safonov A, Yakimov M, et al. Scalable blind search and broadcasting over distributed Hash ta- bles [ J ]. Computer Communications, 2008,31 ( 2 ) : 292- 303.

二级参考文献21

  • 1陈贵海,须成忠,沈海英,叶懋,刘之育.一种新的常数度数的P2P覆盖网络[J].计算机学报,2005,28(7):1084-1095. 被引量：16
  • 2Aberer K, Alima L O, Ghodsi A, et al. The essence of P2P : a reference architecture for overlay networks [ C ]//Fifth IEEE International Conference on Peer-to-Peer Computing. LOS Alamitos : IEEE Computer Society Press, 2005 : 11-20.
  • 3Qu c, Nejdl W, Kriesell M. Cayley DHTs:a group-theoretic framework for analyzing DHTs based on cayley graphs [ C ]//The Second International Symposium on Parallel and Distributed Processing and Applications. Berlin: Springer,2004:89-105.
  • 4Stoica I, Morris R, Karger D, et al. Chord : a scalable peer- to-peer lookup service for internet applications [ J ]. Computer Communication Review,2001,31 (4) :149-160.
  • 5Ratnasamy S, Francis P, Handley M, et al. A scalable content addressable network [ J ]. Computer Communication Review,2001,31 (4) : 161-172.
  • 6Kumar A, Merugu S, Xu J, et al. Ulysses : a robust, low-diameter, low-latency peer-to-peer network [ J ]. European transaction on telecommunications ,2004,15 (6) :571-587.
  • 7Watts D J, Strogatz S H. Collective dynamics of "small- world" networks [ J ]. Nature, 1998,393 ( 6 684 ) :440- 442.
  • 8Xu J, Kumar A, Yu X. On the fundamental tradeoffs between routing table size and network diameter in peer-to- peer networks [ J ]. IEEE Journal on Selected Areas in Communications ,2004,22( 1 ) :151-163.
  • 9Akers S B, Krishnamurthy B. A group-theoretic model for symmetric interconnection networks [ J]. IEEE Transactions on Computing, 1989,38 ( 4 ) : 555- 566.
  • 10Stoica I,Morris R,Karger D et al.Chord:A scalable peer-to-peer lookup service for internet applications//Proceedings of the ACM SIGCOMM.San Diego,2001:149-160.

共引文献9

华南理工大学学报（自然科学版）
2011年 第10期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部