布鲁姆过滤器查询算法及其应用研究
|
摘要
资源交互共享是计算机网络和分布式系统的核心，如何有效的表示信息和查询信息是资源交互共享中最本质的问题。高速发展的计算机网络和计算机系统中，当数据不断膨胀时，数据集合的表示和访问越来越困难。因此，设计精简数据结构支持日益增长的数据存储需求，设计与之对应的算法支持海量数据下的高效查询交互成为当前网络、数据库、分布式系统中资源交互共享的核心问题与严峻挑战。
布鲁姆过滤器(Bloom filter)采用一个位串表示数据集合并能有效支持元素的哈希查找，是一种能够简洁的表示集合并支持集合查询的数据结构，广泛应用于数据库、网络和分布式系统中。本文从理论和应用两个方面对布鲁姆过滤器查询算法进行了深入的研究。系统地综述了布鲁姆过滤器查询算法迄今为止的主要研究成果，分析了目前布鲁姆过滤器查询算法的研究现状和缺陷，针对目前算法的不足，提出了分档布鲁姆过滤器查询算法、可扩展布鲁姆过滤器查询算法、联合多维布鲁姆过滤器查询算法、基于布鲁姆过滤器距离的集合变动评估算法，并探讨了布鲁姆过滤器代数运算和集合查询的关系。研究布鲁姆过滤器在分布式系统中的应用，提出了基于布鲁姆过滤器的节点轨迹标签P2P副本一致性维护算法和基于布鲁姆过滤器的混合移动自组织网络服务发现模型。本文的创新性成果主要体现在以下几个方面：
1)提出代价敏感的分档布鲁姆过滤器查询算法
针对现有的布鲁姆过滤器查询算法没有考虑查询失效代价这一缺陷，本文提出一种新的代价敏感的分档布鲁姆过滤器查询算法。它将元素根据不同的查询代价分为不同的子集，通过考查每档子集最低查询失效率的关系，建立由每档子集最低查询失效率表示的集合最低查询失效总代价目标函数，使用类目标函数梯度遗传算法获得每档的最优哈希函数个数k_i，完成集合到向量的映射与查找。仿真实验结果表明，新的分档布鲁姆过滤器查询算法和标准布鲁姆过滤器算法相比，所用的查询计算时间基本相同，而查询失效总代价降低至少40％。
2)提出基于H_3哈希函数的可扩展布鲁姆过滤器查询算法
布鲁姆过滤器可扩展性主要是当集合元素动态增长超出过滤器算法设计的容量时，如何调整布鲁姆过滤器参数，使得布鲁姆过滤器查询算法有较低的查询误判率，同时具有可接受的计算性能，保证过滤器的可用性。本文研究布鲁姆过滤器的可扩展性问题，提出基于H_3哈希函数的可扩展布鲁姆过滤器查询算法，当集合元素增长超过布鲁姆过滤器集合容量限制时，通过增加成倍数扩大的布鲁姆过滤器向量来保持很低的误判率，利用H_3哈希函数实现可扩展布鲁姆过滤器的设计以及过滤器中元素的插入、查询过程。实验分析表明，新的可扩展布鲁姆过滤器的元素查询误判率永远小于动态布鲁姆过滤器，平均为它的21.3％，且查询时间呈对数增长，解决了现有算法查询时间增长过快问题。
3)研究多维布鲁姆过滤器查询算法
针对现有多维布鲁姆过滤器查询算法(MDBF)在多维元素表示和查询时分割了各维属性为一体的缺陷，提出一种改进的两步表示和查询的联合多维布鲁姆过滤器查询算法(CMDBF)。CMDBF在MDBF的基础上，增加一个联合标准布鲁姆过滤器CBF，将多维元素整体经过两次哈希运算表示到CBF中。CMDBF的元素表示和查找分两步进行，将MDBF作为元素表示和查找第一步，第二步联合元素各属性值利用CBF进行确认。仿真实验表明，CMDBF相比MDBF查询误判率降低明显。
4)探讨布鲁姆过滤器的代数运算
布鲁姆过滤器是集合到向量的一个映射，本文探讨布鲁姆过滤器的代数运算和集合查询的关系。定义布鲁姆过滤器的“并”，“交”，“异或”，“补”，“差”代数运算，从理论和仿真实验两方面分析布鲁姆过滤器的代数运算和集合代数运算并集，交集，异或集，补集，差集的元素查询性质。理论分析和实验结果表明，布鲁姆过滤器的“并”，“交”运算能够支持集合并集交集的元素查询，这一结论可以大大简化利用布鲁姆过滤器进行的系统设计。
5)提出基于布鲁姆过滤器的节点轨迹标签P2P副本一致性维护算法
本文研究P2P系统副本一致性维护算法，从直接更改消息报文角度出发，提出一种基于布鲁姆过滤器的节点轨迹标签无结构P2P副本一致性维护算法。通过在传输消息的报文中添加已接收更新消息的节点轨迹地址链表标签，可在消息传输源节点进行冗余判断来减少冗余消息数目。因为直接存储节点地址轨迹标签算法的消息长度随着消息传输轮数和网络度数增加而不断加大，论文采用布鲁姆过滤器表示地址链表轨迹标签。通过布鲁姆过滤器这种简洁的结构表示地址链表，可以减少添加到报文中的轨迹长度，同时利用布鲁姆过滤器的“并”运算还可以简化传输节点的冗余判断。仿真实验表明：基于布鲁姆过滤器的节点轨迹标签算法可以大大降低冗余消息数目，提高P2P系统的可扩展性。副本节点网络连通性越强，消息数目和传输带宽减少越明显。
6)提出基于布鲁姆过滤器的混合移动自组织网络服务发现模型
研究服务发现中服务信息的精简存储和查询方法，提出基于布鲁姆过滤器的混合移动自组织网络服务发现模型。模型采用计数式布鲁姆过滤器表示注册服务目录，采用两层混合服务发现体系结构和两级服务信息存储方式。论文详细描述了基于布鲁姆过滤器的服务发布、服务查询、服务取消、服务注册信息的扩散与同步和节点移动时对应在服务协调者节点的相关操作和过程。定义布鲁姆过滤器距离，从分析布鲁姆过滤器的统计特性出发，提出了基于计数式布鲁姆过滤器距离的集合变动评估算法。将距离的评估算法用于服务注册信息的扩散与同步中，用于制定有效的服务注册信息发散和同步更新策略。实验仿真和理论分析表明，距离评估算法评估准确性高，准确率高达99.7％，提出的基于布鲁姆过滤器的混合移动自组织网服务发现模型具有良好的性能。
Information representation and query are two core problems of exchanging data objects for most application systems. The size of data sets encountered in databases, networks and many other applications has expanded dramatically in recent years. When data sets become very big or expensive to access, querying is a challenge for accessing and representing the set. It becomes increasingly important to handle massive data set using compact data structure with efficient representation and membership query operations. Thus, how to make membership queries by the aid of a compact structure becomes urgent with the data expanding in modern computer systems. This is a common issue for distributed systems that need to share information.
A Bloom filter is an excellent data structure that can succinctly represent a data set in order to support membership queries, and filter out effectively any element that does not belong to the set. It is widely used in databases, networks and distributed systems and it has great potential for distributed applications where systems need to share information about available data. This thesis surveys the mathematics behind Bloom filters, some important variations and network-related applications of Bloom filters. The analysis of current research shows that although Bloom filters are now starting to receive significant attention from the algorithmic community and there have been a number of recent results, there may well be further improvements to be found. This thesis concentrates on the algorithm of Bloom filter. Some creative works in this thesis are mainly focused on the following aspects:
1) This thesis presents a novel Bloom filter, called Basket Bloom filter (BBF). The BBF differentiates elements in a data set depending on their query invalidation cost, by clustering elements into different baskets. The total query invalidation cost function is defined. In order to minimize the total query invalidation cost, the genetic algorithm is employed to find the optimal number of hash functions for every basket. Simulation results show that, the BBF has 40% lower total query invalidation cost than the standard Bloom filters while the executing time is almost the same.
2) To solve the scalability problem of Bloom filters, this thesis presents a new design of a scalable Bloom filter (SBF) for an expanding data set. The SBF keeps a low false positive rate by adding Bloom filter vectors with double length when necessary. The thesis proposes algorithms for element insertion and query operation of SBF by employing the H_3 class of universal hash functions. Theoretical and experimental results demonstrate that the new SBF provides false positive rate as low as 21.3% of the dynamic Bloom filter presented before and the querying CPU time increasing with logarithmic rather than linear. Therefore, the proposed SBF outperforms other current scalable Bloom filters significantly.
3) Based on the analysis of the current Multi-dimension Bloom filter (MDBF), this thesis find that MDBF separates each attribute from whole element and any attribute's false positive will result in the whole element's false positive. This thesis proposes a new Multi-dimension Bloom filter, termed Combine Multi-dimension Bloom filter (CMDBF). CMDBF adds a Combine Bloom filter to represent the whole element comparing with the MDBF. When represent or query an element, CMDBF needs two steps, the first step is hashing or checking every attribute with the MDBF, the second step is further hashing or checking the whole element with Combine Bloom filter for further validation. Simulation results show that the CMDBF outperforms MDBF for large reduction of false positive rate.
4) This thesis comprehensively discusses the relationship between algebraic operations on Bloom filters and algebraic operations on data sets. This thesis completely define algebraic operations including OR, AND, XOR, NOT, MINUS on Bloom filter, and study the membership query performance on Bloom filter and data set. Theoretical analyses and simulation results show that the Bloom filter ORed (ANDed) from the original Bloom filters can support element membership query on data set ORed (ANDed) from the original data sets.
5) This thesis presents a new trace label based consistency maintenance algorithm in unstructured P2P systems, with the trace label is denoted by Bloom filter. It modifies the message datagram by attaching the address list of peers to which message have been sent. This can help to tell the duplicated message from the source peer by the aid of the attached address list in message datagram. Considering that the address list can become longer with the transmit time lapsing and the degree of P2P increasing, in this thesis we use Bloom filter to denote the address list. The Bloom filter can succinctly represent the address list and simplify the query actions in the list by OR operations. Simulation results show that the new trace label based consistency maintenance algorithm can reduce the number of duplicated message largely. Moreover, the higher the degree of P2P, the more reduction of the number of duplicated messages and bandwidth utilization.
6) This thesis presents a new hybrid service discovery scheme for MANET which is based on Bloom filter. In order to represent service information compactly and search service efficiently, the counting Bloom filter is used to represent the published service index. The scheme adopts two-level hybrid service discovery architecture and two-level storages. This thesis gives the main processes of server discovery, such as service publish, service query, service withdrawal, service consistency maintenance among several service coordinators, service update when node moving. The Bloom filter distance is also defined. A variation evaluation algorithm for dynamic data sets based on the Bloom filter distance is presented, called Bloom filter distance evaluation algorithm (BFDE). Experimental and theoretical results show that the BFDE has 99.7% evaluation accuracy rate and the scheme has merits of compact storage and good searching performance.
布鲁姆过滤器(Bloom filter)采用一个位串表示数据集合并能有效支持元素的哈希查找，是一种能够简洁的表示集合并支持集合查询的数据结构，广泛应用于数据库、网络和分布式系统中。本文从理论和应用两个方面对布鲁姆过滤器查询算法进行了深入的研究。系统地综述了布鲁姆过滤器查询算法迄今为止的主要研究成果，分析了目前布鲁姆过滤器查询算法的研究现状和缺陷，针对目前算法的不足，提出了分档布鲁姆过滤器查询算法、可扩展布鲁姆过滤器查询算法、联合多维布鲁姆过滤器查询算法、基于布鲁姆过滤器距离的集合变动评估算法，并探讨了布鲁姆过滤器代数运算和集合查询的关系。研究布鲁姆过滤器在分布式系统中的应用，提出了基于布鲁姆过滤器的节点轨迹标签P2P副本一致性维护算法和基于布鲁姆过滤器的混合移动自组织网络服务发现模型。本文的创新性成果主要体现在以下几个方面：
1)提出代价敏感的分档布鲁姆过滤器查询算法
针对现有的布鲁姆过滤器查询算法没有考虑查询失效代价这一缺陷，本文提出一种新的代价敏感的分档布鲁姆过滤器查询算法。它将元素根据不同的查询代价分为不同的子集，通过考查每档子集最低查询失效率的关系，建立由每档子集最低查询失效率表示的集合最低查询失效总代价目标函数，使用类目标函数梯度遗传算法获得每档的最优哈希函数个数k_i，完成集合到向量的映射与查找。仿真实验结果表明，新的分档布鲁姆过滤器查询算法和标准布鲁姆过滤器算法相比，所用的查询计算时间基本相同，而查询失效总代价降低至少40％。
2)提出基于H_3哈希函数的可扩展布鲁姆过滤器查询算法
布鲁姆过滤器可扩展性主要是当集合元素动态增长超出过滤器算法设计的容量时，如何调整布鲁姆过滤器参数，使得布鲁姆过滤器查询算法有较低的查询误判率，同时具有可接受的计算性能，保证过滤器的可用性。本文研究布鲁姆过滤器的可扩展性问题，提出基于H_3哈希函数的可扩展布鲁姆过滤器查询算法，当集合元素增长超过布鲁姆过滤器集合容量限制时，通过增加成倍数扩大的布鲁姆过滤器向量来保持很低的误判率，利用H_3哈希函数实现可扩展布鲁姆过滤器的设计以及过滤器中元素的插入、查询过程。实验分析表明，新的可扩展布鲁姆过滤器的元素查询误判率永远小于动态布鲁姆过滤器，平均为它的21.3％，且查询时间呈对数增长，解决了现有算法查询时间增长过快问题。
3)研究多维布鲁姆过滤器查询算法
针对现有多维布鲁姆过滤器查询算法(MDBF)在多维元素表示和查询时分割了各维属性为一体的缺陷，提出一种改进的两步表示和查询的联合多维布鲁姆过滤器查询算法(CMDBF)。CMDBF在MDBF的基础上，增加一个联合标准布鲁姆过滤器CBF，将多维元素整体经过两次哈希运算表示到CBF中。CMDBF的元素表示和查找分两步进行，将MDBF作为元素表示和查找第一步，第二步联合元素各属性值利用CBF进行确认。仿真实验表明，CMDBF相比MDBF查询误判率降低明显。
4)探讨布鲁姆过滤器的代数运算
布鲁姆过滤器是集合到向量的一个映射，本文探讨布鲁姆过滤器的代数运算和集合查询的关系。定义布鲁姆过滤器的“并”，“交”，“异或”，“补”，“差”代数运算，从理论和仿真实验两方面分析布鲁姆过滤器的代数运算和集合代数运算并集，交集，异或集，补集，差集的元素查询性质。理论分析和实验结果表明，布鲁姆过滤器的“并”，“交”运算能够支持集合并集交集的元素查询，这一结论可以大大简化利用布鲁姆过滤器进行的系统设计。
5)提出基于布鲁姆过滤器的节点轨迹标签P2P副本一致性维护算法
本文研究P2P系统副本一致性维护算法，从直接更改消息报文角度出发，提出一种基于布鲁姆过滤器的节点轨迹标签无结构P2P副本一致性维护算法。通过在传输消息的报文中添加已接收更新消息的节点轨迹地址链表标签，可在消息传输源节点进行冗余判断来减少冗余消息数目。因为直接存储节点地址轨迹标签算法的消息长度随着消息传输轮数和网络度数增加而不断加大，论文采用布鲁姆过滤器表示地址链表轨迹标签。通过布鲁姆过滤器这种简洁的结构表示地址链表，可以减少添加到报文中的轨迹长度，同时利用布鲁姆过滤器的“并”运算还可以简化传输节点的冗余判断。仿真实验表明：基于布鲁姆过滤器的节点轨迹标签算法可以大大降低冗余消息数目，提高P2P系统的可扩展性。副本节点网络连通性越强，消息数目和传输带宽减少越明显。
6)提出基于布鲁姆过滤器的混合移动自组织网络服务发现模型
研究服务发现中服务信息的精简存储和查询方法，提出基于布鲁姆过滤器的混合移动自组织网络服务发现模型。模型采用计数式布鲁姆过滤器表示注册服务目录，采用两层混合服务发现体系结构和两级服务信息存储方式。论文详细描述了基于布鲁姆过滤器的服务发布、服务查询、服务取消、服务注册信息的扩散与同步和节点移动时对应在服务协调者节点的相关操作和过程。定义布鲁姆过滤器距离，从分析布鲁姆过滤器的统计特性出发，提出了基于计数式布鲁姆过滤器距离的集合变动评估算法。将距离的评估算法用于服务注册信息的扩散与同步中，用于制定有效的服务注册信息发散和同步更新策略。实验仿真和理论分析表明，距离评估算法评估准确性高，准确率高达99.7％，提出的基于布鲁姆过滤器的混合移动自组织网服务发现模型具有良好的性能。
Information representation and query are two core problems of exchanging data objects for most application systems. The size of data sets encountered in databases, networks and many other applications has expanded dramatically in recent years. When data sets become very big or expensive to access, querying is a challenge for accessing and representing the set. It becomes increasingly important to handle massive data set using compact data structure with efficient representation and membership query operations. Thus, how to make membership queries by the aid of a compact structure becomes urgent with the data expanding in modern computer systems. This is a common issue for distributed systems that need to share information.
A Bloom filter is an excellent data structure that can succinctly represent a data set in order to support membership queries, and filter out effectively any element that does not belong to the set. It is widely used in databases, networks and distributed systems and it has great potential for distributed applications where systems need to share information about available data. This thesis surveys the mathematics behind Bloom filters, some important variations and network-related applications of Bloom filters. The analysis of current research shows that although Bloom filters are now starting to receive significant attention from the algorithmic community and there have been a number of recent results, there may well be further improvements to be found. This thesis concentrates on the algorithm of Bloom filter. Some creative works in this thesis are mainly focused on the following aspects:
1) This thesis presents a novel Bloom filter, called Basket Bloom filter (BBF). The BBF differentiates elements in a data set depending on their query invalidation cost, by clustering elements into different baskets. The total query invalidation cost function is defined. In order to minimize the total query invalidation cost, the genetic algorithm is employed to find the optimal number of hash functions for every basket. Simulation results show that, the BBF has 40% lower total query invalidation cost than the standard Bloom filters while the executing time is almost the same.
2) To solve the scalability problem of Bloom filters, this thesis presents a new design of a scalable Bloom filter (SBF) for an expanding data set. The SBF keeps a low false positive rate by adding Bloom filter vectors with double length when necessary. The thesis proposes algorithms for element insertion and query operation of SBF by employing the H_3 class of universal hash functions. Theoretical and experimental results demonstrate that the new SBF provides false positive rate as low as 21.3% of the dynamic Bloom filter presented before and the querying CPU time increasing with logarithmic rather than linear. Therefore, the proposed SBF outperforms other current scalable Bloom filters significantly.
3) Based on the analysis of the current Multi-dimension Bloom filter (MDBF), this thesis find that MDBF separates each attribute from whole element and any attribute's false positive will result in the whole element's false positive. This thesis proposes a new Multi-dimension Bloom filter, termed Combine Multi-dimension Bloom filter (CMDBF). CMDBF adds a Combine Bloom filter to represent the whole element comparing with the MDBF. When represent or query an element, CMDBF needs two steps, the first step is hashing or checking every attribute with the MDBF, the second step is further hashing or checking the whole element with Combine Bloom filter for further validation. Simulation results show that the CMDBF outperforms MDBF for large reduction of false positive rate.
4) This thesis comprehensively discusses the relationship between algebraic operations on Bloom filters and algebraic operations on data sets. This thesis completely define algebraic operations including OR, AND, XOR, NOT, MINUS on Bloom filter, and study the membership query performance on Bloom filter and data set. Theoretical analyses and simulation results show that the Bloom filter ORed (ANDed) from the original Bloom filters can support element membership query on data set ORed (ANDed) from the original data sets.
5) This thesis presents a new trace label based consistency maintenance algorithm in unstructured P2P systems, with the trace label is denoted by Bloom filter. It modifies the message datagram by attaching the address list of peers to which message have been sent. This can help to tell the duplicated message from the source peer by the aid of the attached address list in message datagram. Considering that the address list can become longer with the transmit time lapsing and the degree of P2P increasing, in this thesis we use Bloom filter to denote the address list. The Bloom filter can succinctly represent the address list and simplify the query actions in the list by OR operations. Simulation results show that the new trace label based consistency maintenance algorithm can reduce the number of duplicated message largely. Moreover, the higher the degree of P2P, the more reduction of the number of duplicated messages and bandwidth utilization.
6) This thesis presents a new hybrid service discovery scheme for MANET which is based on Bloom filter. In order to represent service information compactly and search service efficiently, the counting Bloom filter is used to represent the published service index. The scheme adopts two-level hybrid service discovery architecture and two-level storages. This thesis gives the main processes of server discovery, such as service publish, service query, service withdrawal, service consistency maintenance among several service coordinators, service update when node moving. The Bloom filter distance is also defined. A variation evaluation algorithm for dynamic data sets based on the Bloom filter distance is presented, called Bloom filter distance evaluation algorithm (BFDE). Experimental and theoretical results show that the BFDE has 99.7% evaluation accuracy rate and the scheme has merits of compact storage and good searching performance.
引文
[1] Weiser M. The computer for the 21st century. American. 1991, 265(3): 66-75
[2] 吴朝晖，潘纲．普适计算．中国计算机科学技术发展报告2005．2006：175-189
[3] 李国杰．计算所：创新三期追求什么?http://www.cas.ac.cn/html/Dir/2006/02/21/13/89/13.htm，2006-2-21
[4] 中国互联网络信息中心．第19次中国互联网络发展状况统计报告．http://www.cnnic.net.cn/uploadfiles/doc/2007/1/22/212245.doc, 2007-2
[5] 中国互联网络信息中心．第1次中国互联网络发展状况统计报告．http://www.cnnic.cn/download/2003/10/13/93603.pdf. 1997-10
[6] 林闯，任丰原．可控可信可扩展的新一代互联网．软件学报．2004，15(12)：1815-1821
[7] 林闯，彭雪海．可信网络研究．计算机学报．2005，28(5)：751-758
[8] Next Generation Internet. http://www.ngi.gov, 2004
[9] Internet2. http://www.internet2.edu, http://www.internet2.org, 2006
[10] VBNS. http://www.vbns.net, 2005
[11] Abilene. http://abilene.internet2.edu/, 2006
[12] ARDNOC. http://205.189.33.72/about/about.html, 2005
[13] GEANT. http://www.dante.net/geant/, 2005
[14] Asia-Pacific Advanced Network. http://www.apan.net/,2005
[15] Marco L, Vincenzo E. Architectural and Technological Issues for Future Optical Internet Networks. IEEE Communications Magazine. 2000, 38(9): 82-92
[16] Rajagopalan B, Pendarakis D, Saha D, et al. IP over Optical Networks: Architectural Aspects. IEEE Communications Magazine. 2000, 38(9): 94-102
[17] 戴汝为，操龙兵．Internet—一个开放的复杂巨系统．中国科学E辑．2003，33(4)：289-296
[18] 朱广菁．胡启恒院士：“网络影响力”调查结果告诉我们什么．http://www.cas.ac.cn/html/Dir/2006/04/13/13/96/63.htm, 2006-4-13
[19] 李晓明，刘建国．搜索引擎技术、市场及其发展趋势．中国计算机科学技术发展报告2005．2006：91-109
[20] 李晓明，闫宏飞，王继民．搜索引擎——原理、技术与系统．第1版，北京：科学出版社，2005，19-29
[21] 李晓明，刘建国．搜索引擎技术及趋势．http://sewm.pku.edu.cn/TianwangLiterature/Report/, 2005-12-15
[22] 洪小文．下一代互联网搜索发展趋势．中国计算机学会通讯．2005，4
[23] 任丰原，林闯．无线传感器网络的现状与发展．中国计算机科学技术发展报告2005．2006：110-127
[24] 王家廞，王喆．传感器网络综述．信息技术快报．2005，3(12)，24-36
[25] Tilak S, Abu-Ghazaleh NB, Heinzelman W. A taxonomy of wireless micro-sensor network models. Mobile Computing and Communications Review. 2002, 1(2): 1-8
[26] 李建中，李金宝，石胜飞．传感器网络及其数据管理的概念、问题与进展．软件学报．2003，14(10)：1717-1727
[27] 海沫，刘淘英．网格环境下的资源发现机制．信息技术快报．2006，4(4)：14-24
[28] 胡春明，怀进鹏，沃天宇等．一种支持端到端QoS的服务网格体系结构．软件学报，2006，17(6)：1448-1458
[29] Bloom B. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM. 1970, 13(7): 422-426
[30] Mitzenmacher M. Compressed Bloom filters. IEEE/ACM Trans on Networking. 2002, 10(5):604-612
[31] Mullin J K. Optimal semijoins for distributed database systems. IEEE Trans on Software Engineering. 1990, 16(5):558-560
[32] McIlroy M. Development of a spelling list. IEEE Trans on Communications. 1982, 30(1):91-99
[33] Mullin J K. Estimating the Size of a Relational Join. Information Systems. 1993, 18(3):189-196
[34] Manber U, Wu S. An Algorithm for Approximate Membership Checking with Application to Password Security. Information Processing Letters. 1994,50 (44), 191-197
[35] Gremilion L L. Designing a Bloom filter for differential file access. Communications of ACM. 1982, 25(9):600-604
[36] Mullin J k. A Second Look at Bloom Filters. Communications of ACM. 1983, 26(8):570-571
[37] Bonomi F, Mitzenmacher M, Panigraphy R, et al. Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines. In: Proc of ACM SIGCOMM 2006. Pisa, Italy: ACM Press, 315-326
[38] Broder A, Mitzenmacher M. Network Applications of Bloom Filters: A Survey. Internet Mathematics. 2005, 1(4): 485-509
[39] Druschel P, Rowstron A. PAST, a large-scale, persistent peer-to-peer storage utility. In: Proc of 8th Workshop on Hot Topics in Operations Systems. Elmau/Oberbayern, Germany: IEEE Computer Society, 2001:65-70
[40] Stoica I, Morris R, Karger D, et al. Chord: A scalable peerto-peer lookup service for Internet applications. In: Proc of ACM SIGCOMM 2001. San Francisco. USA:ACM Press, 2001:149-160
[41] Ratnasamy S, Francis P, Handley M, et al. A scalable content-addressable network. In: Proc ofACM SIGCOMM 2001. San Francisco, USA: ACM Press, 2001, 161-172
[42] Li J, Taylor J, Serban L, et al. Self-organization in peer-to-peer system. In: Proc of the 10th European SIGOPS Workshop, 2002
[43] Cuena-Acuna F.M, Peery C, Martin R.P, et al. PlantP: Using gossiping to build content addressable peer-to-peer information sharing communities. In: Proc of 12th IEEE International Symposium on High Performance Distributed Computing. IEEE Computer Society, 2003, 236-246
[44] 范俊梅，王斌，王国仁等．分布式环境下改进的Bloom Filter过滤技术．华中科技大学学报(自然科学版)．2005，33(z)：205-208
[45] Rhea S.C, Kubiatowicz J. Probabilistic location and routing. In: Proc of INFOCOM2002. New York: IEEE Computer Society, 2002, 1248-1257
[46] Whitaker A, Wetherall D. Forwarding without loops in Icarus. In: Proc of Open Architectures and Network Programming. New York: IEEE Computer Society, 2002, 63-75
[47] Estan C, Varghese G. New directions in trace measurement and accounting. In: Proc of ACM SIGCOMM. Pittsburgh. USA: ACM Press, 2002, 323-336
[48] Sarang D, Praveen K, David E. T. Longest prefix matching using bloom filters. In: Proc of ACM Sigcomm 2003. Karlsruhe, Germany:ACM Press, 2003, 201-212
[49] Snoeren A. C, Partridge C, Sanchez L. A, et al. Hash-Based IP Traceback. ACM SIGCOMM Computer Communication Review. 2001, 31(4):3-14
[50] Dinesh S, Zhi G, Betul B, et al. Automatic compilation framework for Bloom filter based intrusion detection. In: Proc of ARC2006. Delft, The Netherlands:2006
[51] Gross P, Parekh J, Kaiser G. Secure Selecticast for Collaborative Intrusion Detection Systems. In:Proc of International Workshop on Distributed Event-Based Systems. Edinburgh, UK:2004
[52] Michael E, Locasto, Janak J, et al. Towards Collaborative Security and P2P Intrusion Detection. In:Proc of the 2005 IEEE Workshop on Information Assurance and Security. United States Military Academy, West Point, NY: IEEE Computer Society, 2005, 30-36
[53] Danyu Zh, Matt M. Sharing Presence Information and Message Notification in an Ad Hoc Network. In: Proc of the First IEEE International Conference on Pervasive Computing and Communications. IEEE Computer Society, 2003, 351-358
[54] Fan Y, Haiyun L, Songwu L, et al. Statistical En-Route Filtering of Injected False Data in Sensor Networks. IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS. 2005, 23(4):839-850
[55] 金澈清，钱卫宁，周傲英．流数据分析与管理综述．软件学报．2004，15(8)1172-1181
[56] 龚俭，彭艳兵，杨望等．基于BloomFilter的大规模异常TCP连接参数再现方法．软件学报．2006，17f3)：434-444
[57] 彭艳兵，龚俭，刘卫江等．Bloom filter哈希空间的元素还原．电子学报．2006，34(5)：822-827
[58] Fan L, Cao P, Almeida J, et al. Summary cache: a scalable wide-area Web cache sharing protocol. IEEE/ACM Trans on Networking. 2000, 8(3):281-293
[59] Mitzenmacher M. Compressed bloom filters. IEEE/ACM Trans on Networking. 2002, 10(5):604-612
[60] Saar C, Yossi M. Spectral bloom filters. In: Proc ACM SIGMOD international conference on Management of data. San Diego. California: ACM Press, 2003, 241-252
[61] 肖明忠，代业非，李晓明．拆分型Bloom Filter．电子学报．2004，32(2)：241-245
[62] Deke G, Honghui Ch, Jie W, et al. Theory and Network Application of Dynamic Bloom Filters. In: Proc of IEEE Infocom. Barcelona, Spain: IEEE Computer Society, 2006
[63] http://www.cnki.net/gycnki/gycnki.htm, 2006-10-26
[64] Shaffer C A. Data Structures and Algorithm Analysis. Englewood Cliffes, N. J:Prentice Hall, 1997
[65] Carter L, Floyd R, Gill J, et al. Exact and approximate membership testers. In:Proc of the tenth annual ACM symposium on Theory of computing. San Diego, California, United States:ACM Press, 1978, 59-65
[66] Jun-Ichi A. A Compendium of Key Search References. In: Proc of ACM SIGIR Forum. ACM Press, 1990, 26-42
[67] Faloutsos C, Oard D. A survey of information retrieval and filtering methods. Technical Report CS-TR-3541, University of Maryland, 1995
[68] Faloutos C. Access methods for text. Computer Survey. 1985, 17(1):49-74
[69] Maurer W D, Lewis T G.. Hash table methods. Computer Survey. 1975, 7(1):5-19
[70] 李晓明，凤旺森．两种对URL的散列效果很好的函数．软件学报．2004，15(2)：179-184
[71] 郑卫斌，张德运，丁会宁等．基于哈希表德高性能URL过滤器研究．小型微型计算机系统．2005，26(2)：178-180
[72] 陈伟，何炎祥，彭文灵．一种轻量级的拒绝服务攻击检测方法．计算机学报．2006，29(8)：1392-1400
[73] 肖明忠，闵博楠，王佳聪等．一个实用的针对url的哈希函数．小型微型计算机系统．2006，27(3)：538-541
[74] 张勇，雷振明．基于流应用中的哈希查表性能研究．计算机工程与应用．2003，25：8-12
[75] Thomas H.C, Charles E.L, Ronald L.R, et al. Introduction to Algorithms. Second Edition, The MIT Press, 2002, 221-252
[76] Intel IXP2800 Network Processor Hardware Reference Manual. 2002
[77] Paxson V. Bro: A system for detecting network intruders in real-time. Computer Networks. 1999, (31):23-24
[78] Snort-The Open Source Network Intrusion Detection System. http://www.snort.org, 2005
[79] Cisco netflow, http://www.cisco.com/warp/public/732/Tech/netflow, 2004
[80] Estan C, Keys K, Moore D, et al. Building a better netflow. ACM SIGCOMM Computer Communication Review. 2004, 34(4):245-256
[81] 程光，龚俭，丁伟等．而向IP流测量的哈希算法研究．软件学报．2005，16(5)：652-658
[82] Hans V, Koen D B. XOR-Based Hash Functionsl IEEE TRANSACTIONS ON COMPUTERS. 2005, 54(7):800-812
[83] Fuller V, Li T, Yu J, et al. RFC1519: Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy, 1993
[84] Waldvogel M, Varghese G., Turner J, et al. Scalable high speed IP routing lookups. In Proceedings of ACM SIGCOMM 1997. Cannes, French: ACM Press. 1997, 25-36
[85] Sarang D, Haoyu S, Jonathan T, et al. Fast Packet Classification Using Bloom Filters. In Proceedings of the ACM Symposim on Architectures for Networking and Communications Systems (ANCS), 2006
[86] Lunteren JV.Searching very large routing tables in wide embedded memory.In:Proc of IEEE Globecom 01． San Antonio,USA:IEEE Computer Society,2001,1615-1619
[87] Lakshman TV,Stiliadis D.High-speed policy-based packet forwarding using efficient multi-dimensional range matching.In ACM Sigcomm 1998． Vancouver,UK:ACM Press.1998,203-214
[88] Florin B,George V.Scalable packet classification.In:Proc of ACM Sigcomm 2001． San Diego,CA,USA:ACM Press.2001,147-160
[89] Lunteren J,Engbersen T.Fast and Scalable Packet Classification.IEEE Journal on Selected Areas in Communications.2003,21(4) :560-571
[90] Anja F,Muthukrishnan S.Tradeoffs for packet classification.In Proc of IEEE INFOCOM 2000． Tel Aviv,Israel:IEEE Computer Society.2000,1193-1202
[91] Srinivasan V,Subhash S,George V. Packet classification using tuple space search.In:Proc of the conference on Applications,technologies,architectures,and protocols for computer communication.Massachusetts,USA:ACM Press,1999,135-146
[92] Litwin W,Neimat MA,Schneider DA.A scalable,distributed data structure.ACM Transactions on Database Systems.1996,21(4) :480-525
[93] Fan D,Davood R.Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters.In:Proc of SIGMOD 2006． Illinois,USA:ACM Press,2006,27-29
[94] Zhao BY,Kubiatowicz JD,Joseph AD.Tapestry:An infrastructure for fault-tolerant wide-area location and routing.U.C.Berkeley.Technical Report,2001．
[95] Roberto T.Data Structure.ACM Computering Survey.1996,28(1)
[96] Jeffrey S V. External Memory Algorithm and Data Structures:Dealing with Massive Data.ACM Computer Surveys.2001,33(2) :209-271
[97] Schollmeier R,Kellerer W.Suitability of Bloom Filters for Network Applications.In Proc of SPECTS 2004． San Jose,CA,USA:LNCS.2004,25-29
[98] Ratnakrtshna M.Hashing Practice:Analysis of Hashing and Universal Hashing.In:Proc of the 1988 ACM SIGMOD international conference.Illinois,USA:ACM Press.1988,191-199
[99] Giancarlo B,Paolo P.XOR-based schemes for fast parallel IP lookups.Lecture notes in computer science.2003,2653:238-250
[100] HDL Design House.HCR MD5:MD5 crypto core family,December,2002．
[101] Ramakrishna M,Portice G.Perfect hash functions for hardware applications.In Proc of Seventh International Conference on Data Engineering.Kobe,Japan:IEEE Computer Society.1991,464-470
[102] Richard J,Cichelli.Minimal perfect hash functions made simple.Communications of the ACM.1980,23(1) :17-19
[103] Srinivasan V,Varghese G.Fast Address Lookup using Controlled Prefix Expansion.ACM Transactions on Computer Systems.1999,17(1) :1-40
[104] Yatin C,Sylvia R,Lee B,et al.Making Gnutella-like P2P Systems Scalable.In:Proc of ACM SIGCOMM 2003． Karlsruhe,Germany:ACM Press,2003,407-418
[105] Broder A,Karlin A.Multilevel adaptive hashing.In:Proc of 1st ACM-SIAM Symposium on Discrete Algorithm.USA:ACM Press,1990,43-53
[106] Andrei B,Michael M.Using multiple hash functions to improve IP lookups.In Proc of IEEE INFOCOM.San Francisco:IEEE Computer Society,2001,1454-1463
[107] Hyesook L,Hye-Ran K,Yeo-Jin J.Parallel Multiple Hashing for Packet Classification.In:Proc of High Performance Switching and Routing.USA:IEEE Computer Society,2005,104-107 [108] Vocking B.How asymmetry helps load balancing.Journal of the ACM.2003,50(4) :568-589
[109] Czerwinski S,Zhao BY,Hodes T,et al.An Architecture for a Secure Service Discovery Service.In Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking.New York:ACM Press,1999,24-35
[110] Snoeren A C,Partridge A,Sanchez C,et al.Single-packet IP traceback.IEEE/ACM Transactions on Networking.2002,10(6) :721-734
[111] Kumar K,Xu J,Jia W,et al.Space-Code bloom filter for efficient per-flow traffic measurement.In Proc of the INFOCOM 2004． New York:ACM Press,2004,1762-1773
[112] Nicolas H,Darryl V.Inverting sampled traffic.In Proc of the 3rd ACM SIGCOMM Conf.on Internet Measurement.Florida,USA:ACM Press,2003,222-233
[113] Kumar A,Sung M,Xu J,Wang J.Data streaming algorithms for efficient and accurate estimation of flow size distribution.In Proc of ACM Sigmetrics.New York:ACM Press,2004,177-188
[114] Manish R, John W. Scalable coordination techniques for distributed network monitoring. Lecture notes in computer science. 2005, 3431:349-352
[115] Dharmapurikar S, Krishnamurthy P, Sproull T, et al. Deep Packet Inspection using Parallel Bloom Filters. In IEEE Hot Interconnects 12. Stanford, CA: IEEE Computer Society, 2003, 44-51
[116] Witten I, Moffat A, Bell T. Managing Gigabytes. 2nd Edition. San Francisco: Morgan Kaufmaan, 1999
[117] Kirsch A, Mitzenmacher M. Distance-Sensitive Bloom Filters. IN Proc of ALENEX06. Florida, USA, 2006
[118] Lumetta S, Mitzenmacher M. Using the Power of Two Choices to Improve Bloom Filters. http://www.eecs.harvard.edu/～michaelm/ListByYear.html, 2006
[119] Kirsch A, Mitzenmacher M. Less Hashing, Same Performance: Building A Better Bloom Filter. In Proc of ESA 2006. Zurich, Switzerland:LNCS, 2006
[120] 陈磊，李三立．网格数据复本管理的动态自适应软件体系结构．软件学报．2006，17(6)：1436-1447
[121] Bonomi F, Mitzenmacher M, PanigrahyR, et al. Bloom Filters via d-Left Hashing and Dynamic Bit Reassignment. In Proc of Allerton 2006. Illinois, USA, 2006
[122] Bonomi F, Mitzenmacher M, PanigrahyR, et al. An Improved Construction for Counting Bloom Filters. In Proc of ESA 2006. Zurich, Switzerland:LNCS, 2006
[123] Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning. 1st edition. Addison-Wesley Longman, 1989
[124] 何新贵，梁久祯．利用目标函数梯度的遗传算法．软件学报．2001，12(7)：981-986
[125] J Grefenstette. Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man and Cybernetics. 1996, 16(1): 122-128
[126] The Harvest Information Discovery and Access System. http://archive.ncsa.uiuc.edu/SDG/IT94/Proceedings/Searching/schwartz.harvest/schwartz.harvest.html, 1994
[127] Wessels D, Claffy K. RFC 2186:Internet Cache Protocol (ICP), version 2, 1997
[128] Wessels D, Claffy K. RFC 2187:Application of Internet Cache Protocol (ICP), version 2, 1997
[129] 姜彩萍，李子木，杨凤杰．集中管理web缓存系统及性能．小型微型计算机 系统．2004 25(8)：1428-1431
[130] http://www.nlanr.net/, 2006
[131] http://www.squid-cache.org/, 2006
[132] http://www.netapp.com/products/netcache/, 2006
[133] Rousskov A, Wessels D. Cache Digests. Computer Networks and ISDN Systems archive. 1998, 30(22-23): 2155-2168
[134] Li X, Xiaodong Zh, Artur A, et al. Building a large and efficient hybrid peer-to-peer Internet caching system. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(6): 754-769
[135] Xiaodong Zh. The Power of P2P beyond File Sharing. dragonstar.ict.ac.cn/course_05/(1)-p2p-beyond-file-sharing.ppt, 2005-8-8
[136] Carter L, Wegman M. Universal classes of hash functions. Computer and System Sciences. 1979, 18(2): 143-154
[137] Ramakrishna MV. Practical performance of Bloom filter and parallel free-text searching. Communications of ACM. 1989, 32(10): 1237-1239
[138] Kaya I, Kocak T.. A low power lookup technique for multi-hashing network applications. In Proc of IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures. Karlsruhe, Germany: IEEE Computer Society, 2006, 179-184
[139] Ramakrishna M V, Fu E, E. Bahcekapili. Efficient hardware hashing functions for high performance computers. IEEE Trans on Computers. 1997, 46(12): 1378-1381
[140] Xu J, Singhal M, Degroat J. A novel cache architecture to support layer-four packet classification at memory access speeds. In Proc of INFOCOM 2000. Tel Aviv, Israel: IEEE Computer Society, 2000, 1445-1454
[141] 田春虎．国内语音Web研究综述．情报学报．2005，2(24)：243-249
[142] Bellovin S, Cheswick W. Network firewalls. IEEE Communications Magazine. 1994, 32 (9): 50-57
[143] yh-haw Y, Randy C, Richard N W. Interdomain access control with policy routing. In Proc of the IEEE Computer Society Workshop on Future Trends of Distributed Computing Systems. Beijing: IEEE Computer Society, 1997, 46-52
[144] Weiss W. QoS with differentiated services. Technical Journal. 1998, 3(4): 48-62
[145] Guerin R, Orda A, Williams D. et al. QoS routing mechanisms and OSPF extensions. In Proc of IEEE Global Telecommunications Mini-Conference. USA: IEEE Computer Society, 1997. 1903-1908
[146] Richard E, Nick M, Pravin V. Billing users and pricing for TCE IEEE Journal on SelectedAreas in Communications. 1995, 13 (7):1162-1175
[147] 李治军，廖明宏．基于信任的P2P真实性查询及副本管理算法．软件学报．2006，17(4)：939-948
[148] Bool, G. The Mathematical Analysis of Logic. Cambridge: Blackwell, 1948
[149] Boole, G. An Investigation of the Laws of Thought. Dover Publication Inc, 1951
[150] 戴世虎．布尔代数．长沙：湖南教育出版社，1984
[151] 马宗民，严丽．含有空值关系数据库的查询处理．计算机研究与发展．1995，32(9)：31-36
[152] 郝忠孝，马宗民．空值环境下关系数据库的更新Ⅰ：扩展关系模型及其基本运算．计算机学报．1994，17(3)：218-222．
[153] 吕家俊，朱月秋，孙耕田．布尔代数．山东：山东教育出版社，1982
[154] 张骞，张霞，刘积仁等，混合P2P环境下有效的查询扩展及其搜索算法，软件学报．2006，17(4)：782-793
[155] 窦文，王怀民，贾焰等．模拟谣言传播机制的无结构P2P网络中广播机制的研究．计算机研究与发展．2004，141(19)：1460-1465．
[156] Ion S, Robert M, David K, et al. Chord: A scalable peer-to-peer lookup protocol for internet applications. In: Proc of ACM SIGCOMM'01. San Diego, CA, USA: ACM Press, 2001, 149-160
[157] Ranjita B, Stefan S, Geoffrey V. Replication Strategies for Highly Available Peer-to-peer Storage Systems. Technical Report CS2002-0726, UCSD, 2002
[158] Qin L, Pei C, Edith C, et al. Search and Replication in Unstructured Peer-to-Peer networks. In: Proc of 16th ACM International Conference on Supercomputing (ICS'02). New York, USA: ACM Press, 2002, 84-95
[159] Wang QB, Dai YF, Tian J, et al. An Infrastructure for Attribute Addressable P2P Network: Barnet. Journal of Software, 2003, 14(8): 1481-1488
[160] The Gnutella Protocol Specification v0.4. http://www9.limewire.com/developer/gnutella_protocol_0.4.pdf, 2003-5-15
[161] Datta A, Hauswirth M, Aberer K. Updates in Highly Unreliable, Replicated Peer-to-Peer Systems. In: Proc of 23rd International Conference on Distributed Computing Systems. Providence, Rhode Island, USA: IEEE Computer Society, 2003, 76-85
[162] Zhijun W, Das SK, Kumar M, et al. Update Propagation through Replica Chain in Decentralized and Unstructured P2P Systems. In: Proc of the Fourth International Conference on Peer-to-Peer Computing. Zurich, Switzerland: IEEE Computer Society, 2004, 64-71
[163] Jiang L, Xiaotao L, Prashant S, et al. Consistency Maintenance in Peer-to-Peer File Sharing Networks. In: Proc of Third IEEE Workshop on Internet Applications. San Jose, CA: IEEE Computer Society, 2002, 90-94
[164] Xin C, Shansi R, Haining W, et al. SCOPE: Scalable Consistency Maintenance in Structured P2P Systems. In: Proc of IEEE Infocom 2005. Miami: IEEE Computer Society, 2005, 1502-1513
[165] Marius P, Aruna S. The cost of application-level broadcast in a fully decentralized peer-to-peer network. In: Proc of eventh International Symposium on Computers and Communications. Taormina Italy: IEEE Computer Society, 2002, 941-946
[166] Barabasi AL, Albert R, Emergence of Scaling in Random Networks. Science, 1999, 286(5439): 509-512
[167] Alberto M, Anukool L, Ibrahim M, et al. BRITE: An Approach to Universal Topology Generation. In: Proc of the International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunications SystemsMASCOTS'01. Cincinnati, Ohio, USA:IEEE Computer Society, 2001, 346-353
[168] Qin L, Sylvia R, Scott S. Can heterogeneity make gnutella scalable? In: Proc of The 1st International Workshop on Peer-to-Peer Systems (IPTPS). Cambridge: Springer-Verlag, 2002, 94-103
[169] Rodriguez P, Spanner C, Biersack E.W. Analysis of Web caching architectures: hierarchical and distributed caching. IEEE/ACM Transactions on Networking. 2001, 9(4): 404-418
[170] Rowstron A, Druschel P. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proc of Middleware 2001. Heidelberg, Germany: ACM Press, 2001, 329-350
[171] Stoica I, Morris R, Karger D, et al. Chord:A scalable peer-to-peer lookup service for internet applications. In Proc of SIGCOMM. California, USA: ACM Press, 2001, 149-160
[172] 殷人昆，陶永雷，谢若阳等．数据结构(用面向对象方法与C++描述)．第一版．清华大学出版社，1999，227-258
[173] Cheng L, Marsic I. Service discovery and invocation for mobile ad hoc networked appliances. In Proc of the 2nd International Workshop on Networked Appliances(IWNA2000) .New Brunswick:2000．
[174] Chakraborty D,Joshi A,Yesha Y,et al.GSD:A.novel group based service discovery protocol for MANETs.In Proc of 4th IEEE Conference on Mobile and Wireless Communications Networks(MWCN).Stockholm,Sweden:IEEE Computer Society,2002,140-144
[175] Ratsimor O,Chakraborty D,Joshi A,et al.Allia:Alliance-based service discovery for ad hoc environments.In Proc of ACM Workshop on Mobile Commerce WMC 02． Atlanta,USA:ACM Press,2002,1-9
[176] Helal S,Desai N,Verma V,et al.Konark-a service discovery and delivery protocol for ad hoc networks.In Proc of the Third IEEE Conference on Wireless Communication Networks WCNC.IEEE Computer Society,2003． 2107-2113
[177] Klein M,Konig-Ries B,Obreiter P.Service rings-a semantic overlay for service discovery in ad hoc networks.In Proc of 14th International Conference on Database and Expert Systems Applications DEXA2003． 2003,180-185
[178] Klein M,Konig-Ries B,Obreiter P.Lanes-a light weight overlay for service discovery in mobile ad hoc networks.In Proc of 3rd Workshop on Applications and Services in Wireless Networks(ASWN).2003
[179] Kozart U C,Tassiulas L.Network layer support for service discovery in mobile ad-hoc networks.In Proc of INFOCOM-2003． San Francisco California,USA:IEEE Computer Society,2003,1965-1975
[180] Feng Zhu,Mutka M,Ni L.Splendor:A secure,private and location-aware service discovery protocol supporting mobile services.In:Proc of the First International Conference on Pervasive Computing and Communication PerCom 03． IEEE Computer Society,2003,235-242 [181] Varshavsky A,Reid B,Lara E.A cross layer approach to service discovery and selection in MANETs.In Proc.2nd International Conference on Mobile Ad-Hoc and Sensor Systems.2005,459-466
[182] Tyan J,Qusay H.Mahmoud.A network layer based architecture for service discovery in mobile ad hoc networks.In Proc of Electrical and Computer Engineering.2004
[183] Lenders V,May M,Plattner B.Service discovery in mobile ad hoc networks:A field theoretic approach.Pervasive and Mobile Computing.2005,1(3) :343-370
[184] Dipanjan Chakraborty,Anupan Joshi,Yelena Yesha,Tim Finin.Toward distributed service discovery in pervasive computing environments.IEEE Transactions on Mobile Computing,February 2006．
[185] Guttman E, Perkins C, Veizades J, et al. RFC 2608: Service Location Protocol, Version 2, 1999
[186] Sun MicroSystems, Inc. Jini architecture overview, www.sun.com/software/jini/whitepapers/architecture.pdf, 2006
[187] Salutation Consortium I. Salutation architecture overview. Technical Report, 1998
[188] Microsoft Corporation. Universal Plug and Play: Background. 1999
[189] Clement L, Hately A, Riegen CV, Rogers T. Universal description discovery & integration (UDDI) 3.0.2. 2004. http://uddi.org/pubs/uddi_v3.htm, 2006
[190] Mian A N, Beraldi R, Baldoni R. Survey of Service Discovery Protocols in Mobile Ad Hoc Networks. Technical Report, http://www.dis.uniromal.it/～midlab/articoli/SSDP.pdf,2006
[191] Bluetooth SIG. Specification of the Bluetooth System, http://www.waterwood.com.cn/technology/bluetooth_documents/TestCtrl.pdf, 2006
[192] Nidd M. Service Discovery in DEAPspace. IEEE Personal Comm. 2001, 8(4):39-45.
[193] Pseudo random number generators, http://www.agner.org/random/,2007-1
[194] 周晓，陈鸣．基于散列值的广域网服务发现．软件学报．2004，15(10)：1565-1573
[195] 夏启志，谢高岗，闵应骅，李忠诚．IS-P2P：一种基于索引的结构化P2P网络模型．计算机学报．2006，29(40)：602-610
[196] 杜宗霞，怀进鹏．丰动分布式Web服务注册机制研究与实现．软件学报．2006，17(3)：454-462
[197] Engelstad P E, Zheng Y. Evaluation of Service Discovery Architectures for Mobile Ad Hoc Networks. In proc of Second Annual Conference on Wireless On-demand Network Systems and Services (WONS'05). Washington, DC, USA: IEEE Computer Society, 2005, 2-15
[2] 吴朝晖，潘纲．普适计算．中国计算机科学技术发展报告2005．2006：175-189
[3] 李国杰．计算所：创新三期追求什么?http://www.cas.ac.cn/html/Dir/2006/02/21/13/89/13.htm，2006-2-21
[4] 中国互联网络信息中心．第19次中国互联网络发展状况统计报告．http://www.cnnic.net.cn/uploadfiles/doc/2007/1/22/212245.doc, 2007-2
[5] 中国互联网络信息中心．第1次中国互联网络发展状况统计报告．http://www.cnnic.cn/download/2003/10/13/93603.pdf. 1997-10
[6] 林闯，任丰原．可控可信可扩展的新一代互联网．软件学报．2004，15(12)：1815-1821
[7] 林闯，彭雪海．可信网络研究．计算机学报．2005，28(5)：751-758
[8] Next Generation Internet. http://www.ngi.gov, 2004
[9] Internet2. http://www.internet2.edu, http://www.internet2.org, 2006
[10] VBNS. http://www.vbns.net, 2005
[11] Abilene. http://abilene.internet2.edu/, 2006
[12] ARDNOC. http://205.189.33.72/about/about.html, 2005
[13] GEANT. http://www.dante.net/geant/, 2005
[14] Asia-Pacific Advanced Network. http://www.apan.net/,2005
[15] Marco L, Vincenzo E. Architectural and Technological Issues for Future Optical Internet Networks. IEEE Communications Magazine. 2000, 38(9): 82-92
[16] Rajagopalan B, Pendarakis D, Saha D, et al. IP over Optical Networks: Architectural Aspects. IEEE Communications Magazine. 2000, 38(9): 94-102
[17] 戴汝为，操龙兵．Internet—一个开放的复杂巨系统．中国科学E辑．2003，33(4)：289-296
[18] 朱广菁．胡启恒院士：“网络影响力”调查结果告诉我们什么．http://www.cas.ac.cn/html/Dir/2006/04/13/13/96/63.htm, 2006-4-13
[19] 李晓明，刘建国．搜索引擎技术、市场及其发展趋势．中国计算机科学技术发展报告2005．2006：91-109
[20] 李晓明，闫宏飞，王继民．搜索引擎——原理、技术与系统．第1版，北京：科学出版社，2005，19-29
[21] 李晓明，刘建国．搜索引擎技术及趋势．http://sewm.pku.edu.cn/TianwangLiterature/Report/, 2005-12-15
[22] 洪小文．下一代互联网搜索发展趋势．中国计算机学会通讯．2005，4
[23] 任丰原，林闯．无线传感器网络的现状与发展．中国计算机科学技术发展报告2005．2006：110-127
[24] 王家廞，王喆．传感器网络综述．信息技术快报．2005，3(12)，24-36
[25] Tilak S, Abu-Ghazaleh NB, Heinzelman W. A taxonomy of wireless micro-sensor network models. Mobile Computing and Communications Review. 2002, 1(2): 1-8
[26] 李建中，李金宝，石胜飞．传感器网络及其数据管理的概念、问题与进展．软件学报．2003，14(10)：1717-1727
[27] 海沫，刘淘英．网格环境下的资源发现机制．信息技术快报．2006，4(4)：14-24
[28] 胡春明，怀进鹏，沃天宇等．一种支持端到端QoS的服务网格体系结构．软件学报，2006，17(6)：1448-1458
[29] Bloom B. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM. 1970, 13(7): 422-426
[30] Mitzenmacher M. Compressed Bloom filters. IEEE/ACM Trans on Networking. 2002, 10(5):604-612
[31] Mullin J K. Optimal semijoins for distributed database systems. IEEE Trans on Software Engineering. 1990, 16(5):558-560
[32] McIlroy M. Development of a spelling list. IEEE Trans on Communications. 1982, 30(1):91-99
[33] Mullin J K. Estimating the Size of a Relational Join. Information Systems. 1993, 18(3):189-196
[34] Manber U, Wu S. An Algorithm for Approximate Membership Checking with Application to Password Security. Information Processing Letters. 1994,50 (44), 191-197
[35] Gremilion L L. Designing a Bloom filter for differential file access. Communications of ACM. 1982, 25(9):600-604
[36] Mullin J k. A Second Look at Bloom Filters. Communications of ACM. 1983, 26(8):570-571
[37] Bonomi F, Mitzenmacher M, Panigraphy R, et al. Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines. In: Proc of ACM SIGCOMM 2006. Pisa, Italy: ACM Press, 315-326
[38] Broder A, Mitzenmacher M. Network Applications of Bloom Filters: A Survey. Internet Mathematics. 2005, 1(4): 485-509
[39] Druschel P, Rowstron A. PAST, a large-scale, persistent peer-to-peer storage utility. In: Proc of 8th Workshop on Hot Topics in Operations Systems. Elmau/Oberbayern, Germany: IEEE Computer Society, 2001:65-70
[40] Stoica I, Morris R, Karger D, et al. Chord: A scalable peerto-peer lookup service for Internet applications. In: Proc of ACM SIGCOMM 2001. San Francisco. USA:ACM Press, 2001:149-160
[41] Ratnasamy S, Francis P, Handley M, et al. A scalable content-addressable network. In: Proc ofACM SIGCOMM 2001. San Francisco, USA: ACM Press, 2001, 161-172
[42] Li J, Taylor J, Serban L, et al. Self-organization in peer-to-peer system. In: Proc of the 10th European SIGOPS Workshop, 2002
[43] Cuena-Acuna F.M, Peery C, Martin R.P, et al. PlantP: Using gossiping to build content addressable peer-to-peer information sharing communities. In: Proc of 12th IEEE International Symposium on High Performance Distributed Computing. IEEE Computer Society, 2003, 236-246
[44] 范俊梅，王斌，王国仁等．分布式环境下改进的Bloom Filter过滤技术．华中科技大学学报(自然科学版)．2005，33(z)：205-208
[45] Rhea S.C, Kubiatowicz J. Probabilistic location and routing. In: Proc of INFOCOM2002. New York: IEEE Computer Society, 2002, 1248-1257
[46] Whitaker A, Wetherall D. Forwarding without loops in Icarus. In: Proc of Open Architectures and Network Programming. New York: IEEE Computer Society, 2002, 63-75
[47] Estan C, Varghese G. New directions in trace measurement and accounting. In: Proc of ACM SIGCOMM. Pittsburgh. USA: ACM Press, 2002, 323-336
[48] Sarang D, Praveen K, David E. T. Longest prefix matching using bloom filters. In: Proc of ACM Sigcomm 2003. Karlsruhe, Germany:ACM Press, 2003, 201-212
[49] Snoeren A. C, Partridge C, Sanchez L. A, et al. Hash-Based IP Traceback. ACM SIGCOMM Computer Communication Review. 2001, 31(4):3-14
[50] Dinesh S, Zhi G, Betul B, et al. Automatic compilation framework for Bloom filter based intrusion detection. In: Proc of ARC2006. Delft, The Netherlands:2006
[51] Gross P, Parekh J, Kaiser G. Secure Selecticast for Collaborative Intrusion Detection Systems. In:Proc of International Workshop on Distributed Event-Based Systems. Edinburgh, UK:2004
[52] Michael E, Locasto, Janak J, et al. Towards Collaborative Security and P2P Intrusion Detection. In:Proc of the 2005 IEEE Workshop on Information Assurance and Security. United States Military Academy, West Point, NY: IEEE Computer Society, 2005, 30-36
[53] Danyu Zh, Matt M. Sharing Presence Information and Message Notification in an Ad Hoc Network. In: Proc of the First IEEE International Conference on Pervasive Computing and Communications. IEEE Computer Society, 2003, 351-358
[54] Fan Y, Haiyun L, Songwu L, et al. Statistical En-Route Filtering of Injected False Data in Sensor Networks. IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS. 2005, 23(4):839-850
[55] 金澈清，钱卫宁，周傲英．流数据分析与管理综述．软件学报．2004，15(8)1172-1181
[56] 龚俭，彭艳兵，杨望等．基于BloomFilter的大规模异常TCP连接参数再现方法．软件学报．2006，17f3)：434-444
[57] 彭艳兵，龚俭，刘卫江等．Bloom filter哈希空间的元素还原．电子学报．2006，34(5)：822-827
[58] Fan L, Cao P, Almeida J, et al. Summary cache: a scalable wide-area Web cache sharing protocol. IEEE/ACM Trans on Networking. 2000, 8(3):281-293
[59] Mitzenmacher M. Compressed bloom filters. IEEE/ACM Trans on Networking. 2002, 10(5):604-612
[60] Saar C, Yossi M. Spectral bloom filters. In: Proc ACM SIGMOD international conference on Management of data. San Diego. California: ACM Press, 2003, 241-252
[61] 肖明忠，代业非，李晓明．拆分型Bloom Filter．电子学报．2004，32(2)：241-245
[62] Deke G, Honghui Ch, Jie W, et al. Theory and Network Application of Dynamic Bloom Filters. In: Proc of IEEE Infocom. Barcelona, Spain: IEEE Computer Society, 2006
[63] http://www.cnki.net/gycnki/gycnki.htm, 2006-10-26
[64] Shaffer C A. Data Structures and Algorithm Analysis. Englewood Cliffes, N. J:Prentice Hall, 1997
[65] Carter L, Floyd R, Gill J, et al. Exact and approximate membership testers. In:Proc of the tenth annual ACM symposium on Theory of computing. San Diego, California, United States:ACM Press, 1978, 59-65
[66] Jun-Ichi A. A Compendium of Key Search References. In: Proc of ACM SIGIR Forum. ACM Press, 1990, 26-42
[67] Faloutsos C, Oard D. A survey of information retrieval and filtering methods. Technical Report CS-TR-3541, University of Maryland, 1995
[68] Faloutos C. Access methods for text. Computer Survey. 1985, 17(1):49-74
[69] Maurer W D, Lewis T G.. Hash table methods. Computer Survey. 1975, 7(1):5-19
[70] 李晓明，凤旺森．两种对URL的散列效果很好的函数．软件学报．2004，15(2)：179-184
[71] 郑卫斌，张德运，丁会宁等．基于哈希表德高性能URL过滤器研究．小型微型计算机系统．2005，26(2)：178-180
[72] 陈伟，何炎祥，彭文灵．一种轻量级的拒绝服务攻击检测方法．计算机学报．2006，29(8)：1392-1400
[73] 肖明忠，闵博楠，王佳聪等．一个实用的针对url的哈希函数．小型微型计算机系统．2006，27(3)：538-541
[74] 张勇，雷振明．基于流应用中的哈希查表性能研究．计算机工程与应用．2003，25：8-12
[75] Thomas H.C, Charles E.L, Ronald L.R, et al. Introduction to Algorithms. Second Edition, The MIT Press, 2002, 221-252
[76] Intel IXP2800 Network Processor Hardware Reference Manual. 2002
[77] Paxson V. Bro: A system for detecting network intruders in real-time. Computer Networks. 1999, (31):23-24
[78] Snort-The Open Source Network Intrusion Detection System. http://www.snort.org, 2005
[79] Cisco netflow, http://www.cisco.com/warp/public/732/Tech/netflow, 2004
[80] Estan C, Keys K, Moore D, et al. Building a better netflow. ACM SIGCOMM Computer Communication Review. 2004, 34(4):245-256
[81] 程光，龚俭，丁伟等．而向IP流测量的哈希算法研究．软件学报．2005，16(5)：652-658
[82] Hans V, Koen D B. XOR-Based Hash Functionsl IEEE TRANSACTIONS ON COMPUTERS. 2005, 54(7):800-812
[83] Fuller V, Li T, Yu J, et al. RFC1519: Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy, 1993
[84] Waldvogel M, Varghese G., Turner J, et al. Scalable high speed IP routing lookups. In Proceedings of ACM SIGCOMM 1997. Cannes, French: ACM Press. 1997, 25-36
[85] Sarang D, Haoyu S, Jonathan T, et al. Fast Packet Classification Using Bloom Filters. In Proceedings of the ACM Symposim on Architectures for Networking and Communications Systems (ANCS), 2006
[86] Lunteren JV.Searching very large routing tables in wide embedded memory.In:Proc of IEEE Globecom 01． San Antonio,USA:IEEE Computer Society,2001,1615-1619
[87] Lakshman TV,Stiliadis D.High-speed policy-based packet forwarding using efficient multi-dimensional range matching.In ACM Sigcomm 1998． Vancouver,UK:ACM Press.1998,203-214
[88] Florin B,George V.Scalable packet classification.In:Proc of ACM Sigcomm 2001． San Diego,CA,USA:ACM Press.2001,147-160
[89] Lunteren J,Engbersen T.Fast and Scalable Packet Classification.IEEE Journal on Selected Areas in Communications.2003,21(4) :560-571
[90] Anja F,Muthukrishnan S.Tradeoffs for packet classification.In Proc of IEEE INFOCOM 2000． Tel Aviv,Israel:IEEE Computer Society.2000,1193-1202
[91] Srinivasan V,Subhash S,George V. Packet classification using tuple space search.In:Proc of the conference on Applications,technologies,architectures,and protocols for computer communication.Massachusetts,USA:ACM Press,1999,135-146
[92] Litwin W,Neimat MA,Schneider DA.A scalable,distributed data structure.ACM Transactions on Database Systems.1996,21(4) :480-525
[93] Fan D,Davood R.Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters.In:Proc of SIGMOD 2006． Illinois,USA:ACM Press,2006,27-29
[94] Zhao BY,Kubiatowicz JD,Joseph AD.Tapestry:An infrastructure for fault-tolerant wide-area location and routing.U.C.Berkeley.Technical Report,2001．
[95] Roberto T.Data Structure.ACM Computering Survey.1996,28(1)
[96] Jeffrey S V. External Memory Algorithm and Data Structures:Dealing with Massive Data.ACM Computer Surveys.2001,33(2) :209-271
[97] Schollmeier R,Kellerer W.Suitability of Bloom Filters for Network Applications.In Proc of SPECTS 2004． San Jose,CA,USA:LNCS.2004,25-29
[98] Ratnakrtshna M.Hashing Practice:Analysis of Hashing and Universal Hashing.In:Proc of the 1988 ACM SIGMOD international conference.Illinois,USA:ACM Press.1988,191-199
[99] Giancarlo B,Paolo P.XOR-based schemes for fast parallel IP lookups.Lecture notes in computer science.2003,2653:238-250
[100] HDL Design House.HCR MD5:MD5 crypto core family,December,2002．
[101] Ramakrishna M,Portice G.Perfect hash functions for hardware applications.In Proc of Seventh International Conference on Data Engineering.Kobe,Japan:IEEE Computer Society.1991,464-470
[102] Richard J,Cichelli.Minimal perfect hash functions made simple.Communications of the ACM.1980,23(1) :17-19
[103] Srinivasan V,Varghese G.Fast Address Lookup using Controlled Prefix Expansion.ACM Transactions on Computer Systems.1999,17(1) :1-40
[104] Yatin C,Sylvia R,Lee B,et al.Making Gnutella-like P2P Systems Scalable.In:Proc of ACM SIGCOMM 2003． Karlsruhe,Germany:ACM Press,2003,407-418
[105] Broder A,Karlin A.Multilevel adaptive hashing.In:Proc of 1st ACM-SIAM Symposium on Discrete Algorithm.USA:ACM Press,1990,43-53
[106] Andrei B,Michael M.Using multiple hash functions to improve IP lookups.In Proc of IEEE INFOCOM.San Francisco:IEEE Computer Society,2001,1454-1463
[107] Hyesook L,Hye-Ran K,Yeo-Jin J.Parallel Multiple Hashing for Packet Classification.In:Proc of High Performance Switching and Routing.USA:IEEE Computer Society,2005,104-107 [108] Vocking B.How asymmetry helps load balancing.Journal of the ACM.2003,50(4) :568-589
[109] Czerwinski S,Zhao BY,Hodes T,et al.An Architecture for a Secure Service Discovery Service.In Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking.New York:ACM Press,1999,24-35
[110] Snoeren A C,Partridge A,Sanchez C,et al.Single-packet IP traceback.IEEE/ACM Transactions on Networking.2002,10(6) :721-734
[111] Kumar K,Xu J,Jia W,et al.Space-Code bloom filter for efficient per-flow traffic measurement.In Proc of the INFOCOM 2004． New York:ACM Press,2004,1762-1773
[112] Nicolas H,Darryl V.Inverting sampled traffic.In Proc of the 3rd ACM SIGCOMM Conf.on Internet Measurement.Florida,USA:ACM Press,2003,222-233
[113] Kumar A,Sung M,Xu J,Wang J.Data streaming algorithms for efficient and accurate estimation of flow size distribution.In Proc of ACM Sigmetrics.New York:ACM Press,2004,177-188
[114] Manish R, John W. Scalable coordination techniques for distributed network monitoring. Lecture notes in computer science. 2005, 3431:349-352
[115] Dharmapurikar S, Krishnamurthy P, Sproull T, et al. Deep Packet Inspection using Parallel Bloom Filters. In IEEE Hot Interconnects 12. Stanford, CA: IEEE Computer Society, 2003, 44-51
[116] Witten I, Moffat A, Bell T. Managing Gigabytes. 2nd Edition. San Francisco: Morgan Kaufmaan, 1999
[117] Kirsch A, Mitzenmacher M. Distance-Sensitive Bloom Filters. IN Proc of ALENEX06. Florida, USA, 2006
[118] Lumetta S, Mitzenmacher M. Using the Power of Two Choices to Improve Bloom Filters. http://www.eecs.harvard.edu/～michaelm/ListByYear.html, 2006
[119] Kirsch A, Mitzenmacher M. Less Hashing, Same Performance: Building A Better Bloom Filter. In Proc of ESA 2006. Zurich, Switzerland:LNCS, 2006
[120] 陈磊，李三立．网格数据复本管理的动态自适应软件体系结构．软件学报．2006，17(6)：1436-1447
[121] Bonomi F, Mitzenmacher M, PanigrahyR, et al. Bloom Filters via d-Left Hashing and Dynamic Bit Reassignment. In Proc of Allerton 2006. Illinois, USA, 2006
[122] Bonomi F, Mitzenmacher M, PanigrahyR, et al. An Improved Construction for Counting Bloom Filters. In Proc of ESA 2006. Zurich, Switzerland:LNCS, 2006
[123] Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning. 1st edition. Addison-Wesley Longman, 1989
[124] 何新贵，梁久祯．利用目标函数梯度的遗传算法．软件学报．2001，12(7)：981-986
[125] J Grefenstette. Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man and Cybernetics. 1996, 16(1): 122-128
[126] The Harvest Information Discovery and Access System. http://archive.ncsa.uiuc.edu/SDG/IT94/Proceedings/Searching/schwartz.harvest/schwartz.harvest.html, 1994
[127] Wessels D, Claffy K. RFC 2186:Internet Cache Protocol (ICP), version 2, 1997
[128] Wessels D, Claffy K. RFC 2187:Application of Internet Cache Protocol (ICP), version 2, 1997
[129] 姜彩萍，李子木，杨凤杰．集中管理web缓存系统及性能．小型微型计算机 系统．2004 25(8)：1428-1431
[130] http://www.nlanr.net/, 2006
[131] http://www.squid-cache.org/, 2006
[132] http://www.netapp.com/products/netcache/, 2006
[133] Rousskov A, Wessels D. Cache Digests. Computer Networks and ISDN Systems archive. 1998, 30(22-23): 2155-2168
[134] Li X, Xiaodong Zh, Artur A, et al. Building a large and efficient hybrid peer-to-peer Internet caching system. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(6): 754-769
[135] Xiaodong Zh. The Power of P2P beyond File Sharing. dragonstar.ict.ac.cn/course_05/(1)-p2p-beyond-file-sharing.ppt, 2005-8-8
[136] Carter L, Wegman M. Universal classes of hash functions. Computer and System Sciences. 1979, 18(2): 143-154
[137] Ramakrishna MV. Practical performance of Bloom filter and parallel free-text searching. Communications of ACM. 1989, 32(10): 1237-1239
[138] Kaya I, Kocak T.. A low power lookup technique for multi-hashing network applications. In Proc of IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures. Karlsruhe, Germany: IEEE Computer Society, 2006, 179-184
[139] Ramakrishna M V, Fu E, E. Bahcekapili. Efficient hardware hashing functions for high performance computers. IEEE Trans on Computers. 1997, 46(12): 1378-1381
[140] Xu J, Singhal M, Degroat J. A novel cache architecture to support layer-four packet classification at memory access speeds. In Proc of INFOCOM 2000. Tel Aviv, Israel: IEEE Computer Society, 2000, 1445-1454
[141] 田春虎．国内语音Web研究综述．情报学报．2005，2(24)：243-249
[142] Bellovin S, Cheswick W. Network firewalls. IEEE Communications Magazine. 1994, 32 (9): 50-57
[143] yh-haw Y, Randy C, Richard N W. Interdomain access control with policy routing. In Proc of the IEEE Computer Society Workshop on Future Trends of Distributed Computing Systems. Beijing: IEEE Computer Society, 1997, 46-52
[144] Weiss W. QoS with differentiated services. Technical Journal. 1998, 3(4): 48-62
[145] Guerin R, Orda A, Williams D. et al. QoS routing mechanisms and OSPF extensions. In Proc of IEEE Global Telecommunications Mini-Conference. USA: IEEE Computer Society, 1997. 1903-1908
[146] Richard E, Nick M, Pravin V. Billing users and pricing for TCE IEEE Journal on SelectedAreas in Communications. 1995, 13 (7):1162-1175
[147] 李治军，廖明宏．基于信任的P2P真实性查询及副本管理算法．软件学报．2006，17(4)：939-948
[148] Bool, G. The Mathematical Analysis of Logic. Cambridge: Blackwell, 1948
[149] Boole, G. An Investigation of the Laws of Thought. Dover Publication Inc, 1951
[150] 戴世虎．布尔代数．长沙：湖南教育出版社，1984
[151] 马宗民，严丽．含有空值关系数据库的查询处理．计算机研究与发展．1995，32(9)：31-36
[152] 郝忠孝，马宗民．空值环境下关系数据库的更新Ⅰ：扩展关系模型及其基本运算．计算机学报．1994，17(3)：218-222．
[153] 吕家俊，朱月秋，孙耕田．布尔代数．山东：山东教育出版社，1982
[154] 张骞，张霞，刘积仁等，混合P2P环境下有效的查询扩展及其搜索算法，软件学报．2006，17(4)：782-793
[155] 窦文，王怀民，贾焰等．模拟谣言传播机制的无结构P2P网络中广播机制的研究．计算机研究与发展．2004，141(19)：1460-1465．
[156] Ion S, Robert M, David K, et al. Chord: A scalable peer-to-peer lookup protocol for internet applications. In: Proc of ACM SIGCOMM'01. San Diego, CA, USA: ACM Press, 2001, 149-160
[157] Ranjita B, Stefan S, Geoffrey V. Replication Strategies for Highly Available Peer-to-peer Storage Systems. Technical Report CS2002-0726, UCSD, 2002
[158] Qin L, Pei C, Edith C, et al. Search and Replication in Unstructured Peer-to-Peer networks. In: Proc of 16th ACM International Conference on Supercomputing (ICS'02). New York, USA: ACM Press, 2002, 84-95
[159] Wang QB, Dai YF, Tian J, et al. An Infrastructure for Attribute Addressable P2P Network: Barnet. Journal of Software, 2003, 14(8): 1481-1488
[160] The Gnutella Protocol Specification v0.4. http://www9.limewire.com/developer/gnutella_protocol_0.4.pdf, 2003-5-15
[161] Datta A, Hauswirth M, Aberer K. Updates in Highly Unreliable, Replicated Peer-to-Peer Systems. In: Proc of 23rd International Conference on Distributed Computing Systems. Providence, Rhode Island, USA: IEEE Computer Society, 2003, 76-85
[162] Zhijun W, Das SK, Kumar M, et al. Update Propagation through Replica Chain in Decentralized and Unstructured P2P Systems. In: Proc of the Fourth International Conference on Peer-to-Peer Computing. Zurich, Switzerland: IEEE Computer Society, 2004, 64-71
[163] Jiang L, Xiaotao L, Prashant S, et al. Consistency Maintenance in Peer-to-Peer File Sharing Networks. In: Proc of Third IEEE Workshop on Internet Applications. San Jose, CA: IEEE Computer Society, 2002, 90-94
[164] Xin C, Shansi R, Haining W, et al. SCOPE: Scalable Consistency Maintenance in Structured P2P Systems. In: Proc of IEEE Infocom 2005. Miami: IEEE Computer Society, 2005, 1502-1513
[165] Marius P, Aruna S. The cost of application-level broadcast in a fully decentralized peer-to-peer network. In: Proc of eventh International Symposium on Computers and Communications. Taormina Italy: IEEE Computer Society, 2002, 941-946
[166] Barabasi AL, Albert R, Emergence of Scaling in Random Networks. Science, 1999, 286(5439): 509-512
[167] Alberto M, Anukool L, Ibrahim M, et al. BRITE: An Approach to Universal Topology Generation. In: Proc of the International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunications SystemsMASCOTS'01. Cincinnati, Ohio, USA:IEEE Computer Society, 2001, 346-353
[168] Qin L, Sylvia R, Scott S. Can heterogeneity make gnutella scalable? In: Proc of The 1st International Workshop on Peer-to-Peer Systems (IPTPS). Cambridge: Springer-Verlag, 2002, 94-103
[169] Rodriguez P, Spanner C, Biersack E.W. Analysis of Web caching architectures: hierarchical and distributed caching. IEEE/ACM Transactions on Networking. 2001, 9(4): 404-418
[170] Rowstron A, Druschel P. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proc of Middleware 2001. Heidelberg, Germany: ACM Press, 2001, 329-350
[171] Stoica I, Morris R, Karger D, et al. Chord:A scalable peer-to-peer lookup service for internet applications. In Proc of SIGCOMM. California, USA: ACM Press, 2001, 149-160
[172] 殷人昆，陶永雷，谢若阳等．数据结构(用面向对象方法与C++描述)．第一版．清华大学出版社，1999，227-258
[173] Cheng L, Marsic I. Service discovery and invocation for mobile ad hoc networked appliances. In Proc of the 2nd International Workshop on Networked Appliances(IWNA2000) .New Brunswick:2000．
[174] Chakraborty D,Joshi A,Yesha Y,et al.GSD:A.novel group based service discovery protocol for MANETs.In Proc of 4th IEEE Conference on Mobile and Wireless Communications Networks(MWCN).Stockholm,Sweden:IEEE Computer Society,2002,140-144
[175] Ratsimor O,Chakraborty D,Joshi A,et al.Allia:Alliance-based service discovery for ad hoc environments.In Proc of ACM Workshop on Mobile Commerce WMC 02． Atlanta,USA:ACM Press,2002,1-9
[176] Helal S,Desai N,Verma V,et al.Konark-a service discovery and delivery protocol for ad hoc networks.In Proc of the Third IEEE Conference on Wireless Communication Networks WCNC.IEEE Computer Society,2003． 2107-2113
[177] Klein M,Konig-Ries B,Obreiter P.Service rings-a semantic overlay for service discovery in ad hoc networks.In Proc of 14th International Conference on Database and Expert Systems Applications DEXA2003． 2003,180-185
[178] Klein M,Konig-Ries B,Obreiter P.Lanes-a light weight overlay for service discovery in mobile ad hoc networks.In Proc of 3rd Workshop on Applications and Services in Wireless Networks(ASWN).2003
[179] Kozart U C,Tassiulas L.Network layer support for service discovery in mobile ad-hoc networks.In Proc of INFOCOM-2003． San Francisco California,USA:IEEE Computer Society,2003,1965-1975
[180] Feng Zhu,Mutka M,Ni L.Splendor:A secure,private and location-aware service discovery protocol supporting mobile services.In:Proc of the First International Conference on Pervasive Computing and Communication PerCom 03． IEEE Computer Society,2003,235-242 [181] Varshavsky A,Reid B,Lara E.A cross layer approach to service discovery and selection in MANETs.In Proc.2nd International Conference on Mobile Ad-Hoc and Sensor Systems.2005,459-466
[182] Tyan J,Qusay H.Mahmoud.A network layer based architecture for service discovery in mobile ad hoc networks.In Proc of Electrical and Computer Engineering.2004
[183] Lenders V,May M,Plattner B.Service discovery in mobile ad hoc networks:A field theoretic approach.Pervasive and Mobile Computing.2005,1(3) :343-370
[184] Dipanjan Chakraborty,Anupan Joshi,Yelena Yesha,Tim Finin.Toward distributed service discovery in pervasive computing environments.IEEE Transactions on Mobile Computing,February 2006．
[185] Guttman E, Perkins C, Veizades J, et al. RFC 2608: Service Location Protocol, Version 2, 1999
[186] Sun MicroSystems, Inc. Jini architecture overview, www.sun.com/software/jini/whitepapers/architecture.pdf, 2006
[187] Salutation Consortium I. Salutation architecture overview. Technical Report, 1998
[188] Microsoft Corporation. Universal Plug and Play: Background. 1999
[189] Clement L, Hately A, Riegen CV, Rogers T. Universal description discovery & integration (UDDI) 3.0.2. 2004. http://uddi.org/pubs/uddi_v3.htm, 2006
[190] Mian A N, Beraldi R, Baldoni R. Survey of Service Discovery Protocols in Mobile Ad Hoc Networks. Technical Report, http://www.dis.uniromal.it/～midlab/articoli/SSDP.pdf,2006
[191] Bluetooth SIG. Specification of the Bluetooth System, http://www.waterwood.com.cn/technology/bluetooth_documents/TestCtrl.pdf, 2006
[192] Nidd M. Service Discovery in DEAPspace. IEEE Personal Comm. 2001, 8(4):39-45.
[193] Pseudo random number generators, http://www.agner.org/random/,2007-1
[194] 周晓，陈鸣．基于散列值的广域网服务发现．软件学报．2004，15(10)：1565-1573
[195] 夏启志，谢高岗，闵应骅，李忠诚．IS-P2P：一种基于索引的结构化P2P网络模型．计算机学报．2006，29(40)：602-610
[196] 杜宗霞，怀进鹏．丰动分布式Web服务注册机制研究与实现．软件学报．2006，17(3)：454-462
[197] Engelstad P E, Zheng Y. Evaluation of Service Discovery Architectures for Mobile Ad Hoc Networks. In proc of Second Annual Conference on Wireless On-demand Network Systems and Services (WONS'05). Washington, DC, USA: IEEE Computer Society, 2005, 2-15