基于本体的分布式语义Web服务发现研究
|
摘要
近年来,web服务作为一种新兴的web应用模式,发展非常迅速。随着web服务的增多,在海量的web服务中准备而有效地找到满足需求的服务的重要性显得愈加突出。传统的web服务发现主要基于集中式网络结构,很难提供动态的服务发现并且具有单点失败和性能瓶颈等缺点;另一方面,语义信息的不足和依赖关键字匹配容易造成查找精确度不够,难以保证服务发现的性能和质量。
本文以Web服务中的服务发现问题为出发点,在语义web服务技术的基础上,对在大规模分布式环境下如何进行语义Web服务的发现和定位展开了深入的研究。论文对研究过程中取得的主要成果进行了详细阐述。这些工作简要归纳如下:
(1)提出了一种基于P2P思想的融合语义信息的网络结构一—SAN(Semantic Addressable Network),SAN中每个结点都维护了一定的语义信息,从而可以使语义相近的服务注册在SAN空间中相近的结点之上,从而为实现语义路由提供基础。
(2)针对服务发现中缺乏对语义的支持,提出了根据用来描述服务的本体概念之间的语义关系对服务进行编码并将其映射到SAN空间的方案。
(3)提出了一种基于通用余弦相似度度量GCSM(GeneralizedCosine－Similarity Measure)的服务相似度计算方法,与一般的对每个概念分别寻找和它相似度最大的概念的多概念匹配方法相比,本文的方法通过服务向量来计算服务相似度,可以提高计算的速度,降低系统的开销。
With the growing of Service-oriented computing and Web Services, more and more Web Services are becoming available on the Internet. The increasing number of Web Services demands for a scalable, flexible and reliable solution to discover the most appropriate services. Traditional web services discovery mechanisms, which publish WSDL-described Web Services in UDDIs , can not support queries that seek neer matches to a Web Service according to their semantic information, and UDDI has became the bottleneck of the whole system and would cause single node failure problems, A distributed and dynamic service discovery mechanism becomes a key requirement for service requestors.
According to the research trends in this area, the thesis is focused on distributed Web Services discovery problem and makes an in-depth study on how to find a service on internet by distributed infrastructure and semantic information. The main contributions of this thesis are summarized as follows:
First, We proposed a Semantic Addressable Network(SAN) that replace the traditional centralized web service discovery model, by distributing the semantic information among all the peers in the P2P network , which provide fundamental basis for semantic routing.
At the same time, In view of Web Service Discovery's lack of semantic oriented support, a mapping mechanism is proposed based on ontology, so as to ensure that every service be registered on the specific node that in charge of corresponding semantic information,
Then a semantic Web service matching algorithm is proposed to calculate the semantic similarity between services based on their semantic description such as IOPE. Comparing with the traditional method, this method has lower time complexity, because it does not need to traverse all the concepts recursively.
本文以Web服务中的服务发现问题为出发点,在语义web服务技术的基础上,对在大规模分布式环境下如何进行语义Web服务的发现和定位展开了深入的研究。论文对研究过程中取得的主要成果进行了详细阐述。这些工作简要归纳如下:
(1)提出了一种基于P2P思想的融合语义信息的网络结构一—SAN(Semantic Addressable Network),SAN中每个结点都维护了一定的语义信息,从而可以使语义相近的服务注册在SAN空间中相近的结点之上,从而为实现语义路由提供基础。
(2)针对服务发现中缺乏对语义的支持,提出了根据用来描述服务的本体概念之间的语义关系对服务进行编码并将其映射到SAN空间的方案。
(3)提出了一种基于通用余弦相似度度量GCSM(GeneralizedCosine－Similarity Measure)的服务相似度计算方法,与一般的对每个概念分别寻找和它相似度最大的概念的多概念匹配方法相比,本文的方法通过服务向量来计算服务相似度,可以提高计算的速度,降低系统的开销。
With the growing of Service-oriented computing and Web Services, more and more Web Services are becoming available on the Internet. The increasing number of Web Services demands for a scalable, flexible and reliable solution to discover the most appropriate services. Traditional web services discovery mechanisms, which publish WSDL-described Web Services in UDDIs , can not support queries that seek neer matches to a Web Service according to their semantic information, and UDDI has became the bottleneck of the whole system and would cause single node failure problems, A distributed and dynamic service discovery mechanism becomes a key requirement for service requestors.
According to the research trends in this area, the thesis is focused on distributed Web Services discovery problem and makes an in-depth study on how to find a service on internet by distributed infrastructure and semantic information. The main contributions of this thesis are summarized as follows:
First, We proposed a Semantic Addressable Network(SAN) that replace the traditional centralized web service discovery model, by distributing the semantic information among all the peers in the P2P network , which provide fundamental basis for semantic routing.
At the same time, In view of Web Service Discovery's lack of semantic oriented support, a mapping mechanism is proposed based on ontology, so as to ensure that every service be registered on the specific node that in charge of corresponding semantic information,
Then a semantic Web service matching algorithm is proposed to calculate the semantic similarity between services based on their semantic description such as IOPE. Comparing with the traditional method, this method has lower time complexity, because it does not need to traverse all the concepts recursively.
引文
[1]W3C, Web Services Glossary, http://www.w3.org/tr/2004/note-ws-gloss-20040211
[2]Tim Berners-Lee, James Hendler, and Ora Lassila. The semantic web. Scientific American, May 2001.
[3]F.Baader,D.McGuinness,D.Nardi,and P.F.Patel-Schneider. Description Logic Handbook:Theory,Implemtation,and Applications.Cambridge University Press,2002
[4]W3C; OWL-S: Semantic Markup for Web Services; Online: http://www.w3.org/submission/OWL-S, W3C, 2004.
[5]罗杰文. Peer to Peer综述. http:www.intsci.ac.cn/users/luojw/papers/p2p/htm.2005
[6]. Napster: http://www.napster.com/
[7] M. Ripeanu. Peer-to-peer Architecture Case Study: Gnutella. In Proceedings of International Conference on P2P Computing, 2001.
[8] Ben Y. Zhao, John Kubiatowicz and Anthony D. Joseph. Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Technical Report No. UCB/CSD-01-1141, University of California Berkeley.
[9] Antony Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. IFIP/ACM International Conference on Distributed Systems Platforms(Middleware 2001).
[10] Ion Stoica, Robert Morris, David Karger, M.Frans Kaashoek, Hari Balakrishnan,Chord A Scalable Peer-to-peer Lookup Service for Internet Applications. In Proceeding of ACM SIGCOMM 2001, San Diego, California, USA.
[11] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker. A Scalable Content-Addressable Network. In Proceedings of ACM SIGCOMM2001,San Diego, California, USA.
[12]. C.Greg Plaxton, Rajmohan Rajaraman, and Andrea W. Richa, "Accessing nearby copies of replicated objects in a distributed environment," in Proceedings of ACM SPAA. ACM, June 1997. [online]: http://www.public.asu.edu/~aricha/publs.html.
[13] J. Aspnes and G. Shah. Skip Graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Jan. 2003.
[14] Pugh, William, Skip Lists: A Probabilistic Alternative to Balanced Trees,Communications of the ACM, Jun. 1990,
[15]N. J.A. Harvey, M. B. Jones, S. Saroiu, M. Theimer,. A.Wolman, "SkipNet: A Scalable Overlay Network with. Practical Locality Properties," In Proc. USITS 2003
[16]J. Broekstra, M. Ehrig, P. Haase, F. van Harmelen, A. Kampman, M. Saboul,R.Siebes, S. Staab, H. Stuckenschmidt, and C. Tempich, "A metadata model for semantics-based peer-to-peer systems," in Proceedings of the 1st Workshop on Semantics in Peer-to-Peer and Grid Computing at the Twelfth International World Wide Web Conference, May 2003.
[17]J. Broekstra, A. Kampman, and F. van Harmelen, "Sesame: A generic architecture for storing and querying rdf and rdf schema," in ISWC '02: Proceedings of the First International Semantic Web Conference on The Semantic Web. London, UK: Springer-Verlag, 2002, pp. 54-68.
[18]J. Broekstra, "SeRQL: Sesame RDF query language." Tech. Rep., 2003. [Online].Available:http://swap.semanticweb.org.proxy.lib.uwaterloo.ca/public/Publications/swapd3.2.pdf
[19] J. Broekstra, M. Ehrig, P. Haase, F. v. Harmelen, P. Mika, B. Schnizler, R. Siebes.Bibster - A Semantics-Based Bibliographic Peer-to-Peer System. In 2nd Workshop on Semantics in Peer-to-Peer and Grid Computing at the 13th International World Wide Web Conference, New York, USA, May 18 2004.
[20]Broekstra, J., Kampman, A., van Harmelen, F.: Sesame: An architecture for storing and querying rdf data and schema information .2001.
[21]P. Haase, R. Siebes, and F. van Harmelen. Expertise-based Peer selection Peerto-Peer Networks. Knowledge and Information Systems, Springer, 2006.
[22] U. Basters and M. Klusch. RS2D: Fast adaptive search for semantic Web services in unstructured P2P networks. In 5th International Semantic Web Conference —ISWC '06, pages 87-100, 2006. Lecture Notes in Computer Science 4273.
[23] Crespo A,Garcia-Molina H.Semantic overlay networks for P2P systems[R].America:Stanford University,2003.
[24]Nizamuddin Channa,Shanping Li,Wei SHi,Gang Peng, A CAN-Based P2P infrestructure for Semantic Web Services Publishing and Discovery, Internet,2005.The First IEEE and IFIP International Conference in Central Asia.pp.1-4.26-28Sept.2005
[25] Cristina Schmidt and Manish Parashar.A Peer-to-Peer Approach to Web Service Discovery. world wide web.2004
[26] Yong Li. Sen Su, and Fangchun Yang. A Peer-to-Peer Approach to Semantic Web Services Discovery. International Conference on Computational Science (4) 2006: 73-80
[27] C. Zhang, A. Krishnamurthy, and R. Wang. Brushwood: Distributed Trees in Peer-to-Peer Systems. IPTPS2005, 2005.
[28] Jianjun Yu, Hao Su, Gang Zhou, Ke Xu. SNet: Skip Graph based Semantic Web Services Discovery,SAC'07, March 11-15, 2007, Seoul, Korea.
[29] Gang Zhou,Jianjun Yu,Rui Chen,Hui Zhang.Scalable Web Service Discovery on P2P Overlay Network,2007 IEEE International Conference on Services Computing (SCC 2007)
[30] Weifeng Lv,Jianjun Yu. pService: Peer-to-Peer based Web Services Discovery and Matching,Second International Conference on Systems and Networks Communications (ICSNC 2007)
[31] JianJun Yu, Rui Chen, Hao Su, Shengmin Guo. Web Services Publishing and Discovery on Peer-to-Peer Overlay. Proceedings of the 2006 IEEE Asia-Pacific Conference on Services Computing (APSCC'06)
[32]M. Schlosser, M. Sintek, S. Decker, and W. Nejdl. A scalable and ontology-based P2P infrastructure for semantic Web services. In Proceedings of the Second IEEE International Conference on Peer-to-Peer Computing
[33]W. Nejdl, B. Wolf, C. Qu, S. Decker, M. Sintek, A. Naeve, M. Nilsson, M. Palmer,and T. Risch, "EDUTELLA: a P2P networking infrastructure based on RDF," in WWW '02: Proceedings of the 11th international conference on World Wide Web.New York, NY, USA: ACM Press, 2002, pp. 604-615.
[34]W. Nejdl, M. Wolpers, W. Siberski, C. Schmitz, M. T. Schlosser, I. Brunkhorst,and A. L¨oser, "Super-peer-based routing strategies for RDF-based peer-to-peer networks," J. Web Sem., vol. 1, no. 2, pp. 177-186, 2004.
[35] Loser A, Naumann F, Siberski W, Nejdl W, Thaden U. Semantic overlay clusters within super-peer networks. In: Aberer K, Koubarakis M, Kalogeraki V, eds. Proc. of the Int'l Workshop on Databases, Information Systems and Peer-to-Peer Computing. Berlin: Springer-Verlag, 2003. 33-47.
[36]Nejdl, W, Wolpers, M., Siberski, W, Schmitz, C, Schlosser, M., Brunkhorst, I.and Loser, A., Super-Peer-Based Routing and Clustering Strategies for RDF-Based Peer-To-Peer Networks. in The Twelfth International World Wide Web Conference,(Budapest, Hungary, 2002)
[37] S. Castano, A. Ferrara, S. Montanelli, E. Pagain, and G. Rossi, "Ontology addressable contents in P2P networks," in Proc. of the 1st WWW Int. Workshop on Semantics in Peer-to-Peer and Grid Computing(SemPGRID 2003),May 2003.
[38]Paolucci,M.,Kawamura,T.,Payne,T.R.and Sycara,K.(2002)Semantic Matching of Web Services Capabilities.The First International Semantic Web Conference,2002..
[39]Yong Li,Fangchun Yang,Kai Shuang and Sen Su.A Semantic Peer-to-Peer Overlay for Web Services Discovery.In SOFSEM 2007:Theory and Practice of Computer Science - 33rd Conference on Current Trends in Theory and Practice of Computer Science.750-760,Harrachov,Czech Republic,January 20-26,2007.
[40]MCGILL,M.J.Introduction to Modern Information Retrieval.McGraw-Hill,New York.1983
[41]SALTON,G.AND BUCKLEY,C.Term-weighting approaches in automatic text retrieval.Inf.Process.Manage.24,5,513-523.1988
[42]Exploiting Hierarchical Domain Structure to Compute Similarity.PRASANNA GANESAN,HECTOR GARCIA-MOLINA,and JENNIFER WIDOM.ACM Transactions on Information Systems,Vol.21,No.1,January 2003
[43]Risson J,Moors T.Survey of research towards robust peer-to-peer networks:Search methods.Technical Report,UNSWEE-P2P-1-1,Sydney:University of New South Wales,2004.1-36.
[44]刘业.杜庆伟.杨鹏.基于语义路由的P2P系统综述.计算机科学 2004
[45]Chonggang Wang and Bo Li,"Peer-to-peer overlay,networks:A survey,"Technical Report,Department of.Computer Science,HKUST,Feb.2003
[46]Lua EK,Crowcroft J,Pias M,Sharma R,Lim S.A survey and comparison of peer-to-peer overlay network schemes.Journal of IEEE Communications Survey and Tutorial,2005,7(2):72-93.
[47]H.Tangmunarunkit,R.Govindan,S.Jamin,S.Shenker,and w.Willinger.network topologies,power laws and hierarchy.Technical Report TRO1-746,Technical Report,University of Southern California,2001
[48]W.Aiello,F.Chung,and L.Lu.A random graph model for massive graphs,In 32nd Annual ACM Symposium on Theory of Computing,ACM,2000.
[2]Tim Berners-Lee, James Hendler, and Ora Lassila. The semantic web. Scientific American, May 2001.
[3]F.Baader,D.McGuinness,D.Nardi,and P.F.Patel-Schneider. Description Logic Handbook:Theory,Implemtation,and Applications.Cambridge University Press,2002
[4]W3C; OWL-S: Semantic Markup for Web Services; Online: http://www.w3.org/submission/OWL-S, W3C, 2004.
[5]罗杰文. Peer to Peer综述. http:www.intsci.ac.cn/users/luojw/papers/p2p/htm.2005
[6]. Napster: http://www.napster.com/
[7] M. Ripeanu. Peer-to-peer Architecture Case Study: Gnutella. In Proceedings of International Conference on P2P Computing, 2001.
[8] Ben Y. Zhao, John Kubiatowicz and Anthony D. Joseph. Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Technical Report No. UCB/CSD-01-1141, University of California Berkeley.
[9] Antony Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. IFIP/ACM International Conference on Distributed Systems Platforms(Middleware 2001).
[10] Ion Stoica, Robert Morris, David Karger, M.Frans Kaashoek, Hari Balakrishnan,Chord A Scalable Peer-to-peer Lookup Service for Internet Applications. In Proceeding of ACM SIGCOMM 2001, San Diego, California, USA.
[11] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker. A Scalable Content-Addressable Network. In Proceedings of ACM SIGCOMM2001,San Diego, California, USA.
[12]. C.Greg Plaxton, Rajmohan Rajaraman, and Andrea W. Richa, "Accessing nearby copies of replicated objects in a distributed environment," in Proceedings of ACM SPAA. ACM, June 1997. [online]: http://www.public.asu.edu/~aricha/publs.html.
[13] J. Aspnes and G. Shah. Skip Graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Jan. 2003.
[14] Pugh, William, Skip Lists: A Probabilistic Alternative to Balanced Trees,Communications of the ACM, Jun. 1990,
[15]N. J.A. Harvey, M. B. Jones, S. Saroiu, M. Theimer,. A.Wolman, "SkipNet: A Scalable Overlay Network with. Practical Locality Properties," In Proc. USITS 2003
[16]J. Broekstra, M. Ehrig, P. Haase, F. van Harmelen, A. Kampman, M. Saboul,R.Siebes, S. Staab, H. Stuckenschmidt, and C. Tempich, "A metadata model for semantics-based peer-to-peer systems," in Proceedings of the 1st Workshop on Semantics in Peer-to-Peer and Grid Computing at the Twelfth International World Wide Web Conference, May 2003.
[17]J. Broekstra, A. Kampman, and F. van Harmelen, "Sesame: A generic architecture for storing and querying rdf and rdf schema," in ISWC '02: Proceedings of the First International Semantic Web Conference on The Semantic Web. London, UK: Springer-Verlag, 2002, pp. 54-68.
[18]J. Broekstra, "SeRQL: Sesame RDF query language." Tech. Rep., 2003. [Online].Available:http://swap.semanticweb.org.proxy.lib.uwaterloo.ca/public/Publications/swapd3.2.pdf
[19] J. Broekstra, M. Ehrig, P. Haase, F. v. Harmelen, P. Mika, B. Schnizler, R. Siebes.Bibster - A Semantics-Based Bibliographic Peer-to-Peer System. In 2nd Workshop on Semantics in Peer-to-Peer and Grid Computing at the 13th International World Wide Web Conference, New York, USA, May 18 2004.
[20]Broekstra, J., Kampman, A., van Harmelen, F.: Sesame: An architecture for storing and querying rdf data and schema information .2001.
[21]P. Haase, R. Siebes, and F. van Harmelen. Expertise-based Peer selection Peerto-Peer Networks. Knowledge and Information Systems, Springer, 2006.
[22] U. Basters and M. Klusch. RS2D: Fast adaptive search for semantic Web services in unstructured P2P networks. In 5th International Semantic Web Conference —ISWC '06, pages 87-100, 2006. Lecture Notes in Computer Science 4273.
[23] Crespo A,Garcia-Molina H.Semantic overlay networks for P2P systems[R].America:Stanford University,2003.
[24]Nizamuddin Channa,Shanping Li,Wei SHi,Gang Peng, A CAN-Based P2P infrestructure for Semantic Web Services Publishing and Discovery, Internet,2005.The First IEEE and IFIP International Conference in Central Asia.pp.1-4.26-28Sept.2005
[25] Cristina Schmidt and Manish Parashar.A Peer-to-Peer Approach to Web Service Discovery. world wide web.2004
[26] Yong Li. Sen Su, and Fangchun Yang. A Peer-to-Peer Approach to Semantic Web Services Discovery. International Conference on Computational Science (4) 2006: 73-80
[27] C. Zhang, A. Krishnamurthy, and R. Wang. Brushwood: Distributed Trees in Peer-to-Peer Systems. IPTPS2005, 2005.
[28] Jianjun Yu, Hao Su, Gang Zhou, Ke Xu. SNet: Skip Graph based Semantic Web Services Discovery,SAC'07, March 11-15, 2007, Seoul, Korea.
[29] Gang Zhou,Jianjun Yu,Rui Chen,Hui Zhang.Scalable Web Service Discovery on P2P Overlay Network,2007 IEEE International Conference on Services Computing (SCC 2007)
[30] Weifeng Lv,Jianjun Yu. pService: Peer-to-Peer based Web Services Discovery and Matching,Second International Conference on Systems and Networks Communications (ICSNC 2007)
[31] JianJun Yu, Rui Chen, Hao Su, Shengmin Guo. Web Services Publishing and Discovery on Peer-to-Peer Overlay. Proceedings of the 2006 IEEE Asia-Pacific Conference on Services Computing (APSCC'06)
[32]M. Schlosser, M. Sintek, S. Decker, and W. Nejdl. A scalable and ontology-based P2P infrastructure for semantic Web services. In Proceedings of the Second IEEE International Conference on Peer-to-Peer Computing
[33]W. Nejdl, B. Wolf, C. Qu, S. Decker, M. Sintek, A. Naeve, M. Nilsson, M. Palmer,and T. Risch, "EDUTELLA: a P2P networking infrastructure based on RDF," in WWW '02: Proceedings of the 11th international conference on World Wide Web.New York, NY, USA: ACM Press, 2002, pp. 604-615.
[34]W. Nejdl, M. Wolpers, W. Siberski, C. Schmitz, M. T. Schlosser, I. Brunkhorst,and A. L¨oser, "Super-peer-based routing strategies for RDF-based peer-to-peer networks," J. Web Sem., vol. 1, no. 2, pp. 177-186, 2004.
[35] Loser A, Naumann F, Siberski W, Nejdl W, Thaden U. Semantic overlay clusters within super-peer networks. In: Aberer K, Koubarakis M, Kalogeraki V, eds. Proc. of the Int'l Workshop on Databases, Information Systems and Peer-to-Peer Computing. Berlin: Springer-Verlag, 2003. 33-47.
[36]Nejdl, W, Wolpers, M., Siberski, W, Schmitz, C, Schlosser, M., Brunkhorst, I.and Loser, A., Super-Peer-Based Routing and Clustering Strategies for RDF-Based Peer-To-Peer Networks. in The Twelfth International World Wide Web Conference,(Budapest, Hungary, 2002)
[37] S. Castano, A. Ferrara, S. Montanelli, E. Pagain, and G. Rossi, "Ontology addressable contents in P2P networks," in Proc. of the 1st WWW Int. Workshop on Semantics in Peer-to-Peer and Grid Computing(SemPGRID 2003),May 2003.
[38]Paolucci,M.,Kawamura,T.,Payne,T.R.and Sycara,K.(2002)Semantic Matching of Web Services Capabilities.The First International Semantic Web Conference,2002..
[39]Yong Li,Fangchun Yang,Kai Shuang and Sen Su.A Semantic Peer-to-Peer Overlay for Web Services Discovery.In SOFSEM 2007:Theory and Practice of Computer Science - 33rd Conference on Current Trends in Theory and Practice of Computer Science.750-760,Harrachov,Czech Republic,January 20-26,2007.
[40]MCGILL,M.J.Introduction to Modern Information Retrieval.McGraw-Hill,New York.1983
[41]SALTON,G.AND BUCKLEY,C.Term-weighting approaches in automatic text retrieval.Inf.Process.Manage.24,5,513-523.1988
[42]Exploiting Hierarchical Domain Structure to Compute Similarity.PRASANNA GANESAN,HECTOR GARCIA-MOLINA,and JENNIFER WIDOM.ACM Transactions on Information Systems,Vol.21,No.1,January 2003
[43]Risson J,Moors T.Survey of research towards robust peer-to-peer networks:Search methods.Technical Report,UNSWEE-P2P-1-1,Sydney:University of New South Wales,2004.1-36.
[44]刘业.杜庆伟.杨鹏.基于语义路由的P2P系统综述.计算机科学 2004
[45]Chonggang Wang and Bo Li,"Peer-to-peer overlay,networks:A survey,"Technical Report,Department of.Computer Science,HKUST,Feb.2003
[46]Lua EK,Crowcroft J,Pias M,Sharma R,Lim S.A survey and comparison of peer-to-peer overlay network schemes.Journal of IEEE Communications Survey and Tutorial,2005,7(2):72-93.
[47]H.Tangmunarunkit,R.Govindan,S.Jamin,S.Shenker,and w.Willinger.network topologies,power laws and hierarchy.Technical Report TRO1-746,Technical Report,University of Southern California,2001
[48]W.Aiello,F.Chung,and L.Lu.A random graph model for massive graphs,In 32nd Annual ACM Symposium on Theory of Computing,ACM,2000.