Keynote Speaker

Abstract

Peer-to-peer meets wireless: Opportunities and challenges
In general, peer-to-peer technologies for the Internet have been shown to be scalable and efficient for content distribution, and are increasingly been used for more than just simple file distribution. In this talk I will talk about how the field of wireless networking is being impacted by P2P. First, I will discuss the convergence of structured overlays and network routing protocols. Protocols, like Virtual Ring Routing, exploit some of the techniques used in structured overlays to create a new generation of scalable routing protocols, aimed at wireless mesh networks. These routing protocols are designed to enable the next generation of mesh-based infrastructure for use in the enterprise. Secondly, I will discuss how P2P ideas and concepts for scalability are impacting wireless vehicular networking.

Biography

Antony Rowstron is a senior researcher at Microsoft Research, Cambridge, UK and currently co-leads their systems and networking research group. His research interests are broad, covering the spectrum of systems and networking. He is well known for his contributions to large-scale overlay research, including Pastry one of the early DHTs. He received a MEng degree in Computer Systems and Software Engineering in 1993 from the University of York, UK, and a DPhil degree in Computer Science in 1996 from the University of York, UK. Prior to working at Microsoft Research he held research posts at the Computer Laboratory and Engineering Departments at Cambridge University.

Abstract

Towards a Distributed Web Search Engine
In the ocean of Web data, Web search engines are the primary way to access content. As the data is on the order of petabytes, current search engines are very large centralized systems based on replicated clusters. Web data, however, is always evolving. The number of Web sites continues to grow rapidly (170 millions in March 2008) and there are currently more than 20 billion indexed pages. On the other hand, Internet users are above one billion and hundreds of million of queries are issued each day. In the near future, centralized systems are likely to become less effective against such a data-query load, thus suggesting the need of fully distributed search engines. Such engines need to maintain high quality answers, fast response time, high query throughput, high availability and scalability; in spite of network latency and scattered data. In this talk we present the main challenges behind the design of a distributed Web retrieval system and our past and on-going work in solving them, including crawling, indexing and query processing.

Biography

Ricardo Baeza-Yates is VP of Yahoo! Research for Europe, Middle East and Latin America, leading the labs at Barcelona, Spain and Santiago, Chile. Until 2005 he was the director of the Center for Web Research at the Dept. of Computer Science of the Engineering School of the University of Chile; and ICREA Professor at the Dept. of Technology of Univ. Pompeu Fabra in Barcelona, Spain. He is co-author of the book Modern Information Retrieval, published in 1999 by Addison-Wesley, as well as co-author of the 2nd edition of the Handbook of Algorithms and Data Structures, Addison-Wesley, 1991; and co-editor of Information Retrieval: Algorithms and Data Structures, Prentice-Hall, 1992, among more than 150 other publications. He has received the Organization of American States award for young researchers in exact sciences (1993) and with two Brazilian colleagues obtained the COMPAQ prize for the best CS Brazilian research article (1997). In 2003 he was the first computer scientist to be elected to the Chilean Academy of Sciences.

Abstract

A Highly Scalable Perfect Hashing Algorithm
Minimal perfect hash functions are widely used for memory efficient storage and fast retrieval of items from static sets. A perfect hash function (PHF) is an injective function that maps a key set S of size n to unique values into the range [0, m - 1]. A minimal perfect hash function (MPHF) is a PHF with the smallest range, i.e., m = n. We present a sequential and a parallel version of a simple, highly scalable and near-space optimal perfect hashing algorithm. Evaluation of a PHF on a given element of S requires constant time, and the dominating phase in the construction algorithm consists of sorting n fingerprints of O(log n) bits in O(n) time. The space usage depends on the relation between m and n. For m = n the space usage is in the range 2.62 n to 3.3 n bits, depending on the constants involved in the construction and in the evaluation phases. For m = 1.23 n the space usage is in the range 1.95 n to 2.7 n bits. In all cases, this is within a small constant factor from the information theoretical minimum of approximately 1.44 n bits for MPHFs and 0.89 n bits for PHFs, something that has not been achieved by previous algorithms in practical situations. We demonstrate the scalability of the sequential algorithm by constructing an MPHF for a set of 1.024 billion URLs of average length 64 bytes collected from the Web in approximately 50 minutes using one machine of a cluster with 14 commodity PCs. The parallel version (i) constructs an MPHF for the same set of 1.024 billion URLs in approximately 4 minutes; (ii) constructs an MPHF for a set of 14.336 billion 16-byte random integers in approximately 50 minutes with a performance degradation of 20%.

Biography

Nivio Ziviani has a Ph.D. in Computer Science from the University of Waterloo, Canada, 1982. He is a Professor Emeritus at the Department of Computer Science of the Federal University of Minas Gerais (UFMG), Brazil, where he coordinates the Laboratory for Treating Information (LATIN). He is a member of the Brazilian Academy of Sciences and of the National Order of the Scientific Merit in the class Comendador. He is a co-founder of Miner Technology Group, sold to Folha de São Paulo / UOL group in 1999, and Akwan Information Technologies, sold to Google Inc. in 2005. He has co-authored of over 100 refereed papers and 2 books in the areas of algorithm design and information retrieval, the latter his primary area of research. He was General Co-Chair of the 28th ACM SIGIR Conference on Research and Development in Information Retrieval and co-founder of the International Conference on String Processing and Information Retrieval (SPIRE).