Monday March 17, 2008
8:20 - 10:00AM

 

 

Abstract
The accumulated tools of human history can all profitably be regarded as prostheses—not in the sense that they compensate for the specific disabilities of any given individual, but rather because they enable us to overcome the biological limitations shared by all of us. Cognitive, robotic, and social prostheses are computational systems that leverage and extend human intellectual, perceptual, physical, and collaborative capacities, just as the steam shovel was a sort of muscular prosthesis or eyeglasses a sort of visual prosthesis. Unlike the tools of traditional Artificial Intelligence, these prostheses are not designed to replace the human role in tasks but rather to augment human capabilities and enable people to focus their unique strengths on ever-more challenging problems. In this talk I will describe and demonstrate some of the exciting developments in this emerging field.

Speaker's Bio
Dr. Jeffrey M. Bradshaw is a Senior Research Scientist at the Florida Institute for Human and Machine Cognition (IHMC) where he leads the research group developing the KAoS policy and domain services framework. He has been a Fulbright Senior Scholar at the European Institute for Cognitive Sciences and Engineering (EURISCO) in Toulouse, France; an Honorary Visiting Researcher at the Center for Intelligent Systems and their Applications and AIAI at the University of Edinburgh, Scotland; a visiting professor at the Institut Cognitique at the University of Bordeaux; is former chair of ACM SIGART; and former chair of the RIACS Science Council for NASA Ames Research Center. He is a member of the National Research Council (NRC)Committee on Military and Intelligence Methodology for Emergent Physiological and Cognitive/Neural Science Research in the Next Two Decades, and is a scientific advisor to the Japanese NEC Technology Paradigm Shifts initiative and the HCIV program at the German National AI Research Center (DFKI). He is a member of the Technical Committee for IEEE Systems, Man and Cybernetics and for the Aerospace Human Factors and Ergonomics of the IEA. He will serve as co-program chair for Intelligent User Interfaces (IUI 2008) and as Program Vice Chair, 2008 IEEE International Conference on Distributed Human-Machine Systems (DHMS 2008). Dr. Bradshaw serves on the Autonomous Agents Steering committee and on the editorial board of the Journal of Autonomous Agents and Multi-Agent Systems, the Web Semantics Journal, Schedae Informaticae, and the Web Intelligence Journal, and was formerly on the board of the Knowledge Acquisition Journal and the International Journal of Human-Computer Studies. He led the DARPA and NASA funded ITAC study team "Software Agents for the Warfighter." Among other publications, he edited the books Knowledge Acquisition as a Modeling Activity (with Ken Ford, Wiley, 1993), Software Agents (AAAI Press/The MIT Press, 1997).

=========================================================================

Wednesday March 19, 2008
8:20 - 10:00AM

 

 

Abstract
Minimal perfect hash functions are widely used for memory efficient storage and fast retrieval of items from static sets. A perfect hash function (PHF) for a key set is a function that maps the keys of to unique values. A minimal perfect hash function (MPHF) is a PHF with the smallest range, i.e., . The objective of this paper is to present two time efficient and near space-optimal perfect hashing algorithms. We present: (1) an internal memory based algorithm that assume uniform hashing to build a family of PHFs (for ) or MPHFs (for ) based on random graphs, and (2) an external memory based algorithm that has experimentally proven practicality for sets in the order of billions of keys. Both internal and external algorithms have the following properties: (i) evaluation of a PHF or a MPHF requires constant time, (ii) the algorithms are simple to describe and implement, and generate the functions in linear time, (iii) for the internal algorithm, the amount of space needed to represent a PHF is approximately bits and a MPHF is approximately bits, which is around a factor of 2 from the information theoretical minimum of approximately and bits, respectively; for the external algorithm, the amount of space needed to represent a PHF is approximately bits and a MPHF is approximately bits. To our knowledge, no previously known algorithm has these properties and any algorithm in the literature with the property (iii) either requires exponential time for construction and evaluation, or uses near-optimal space only asymptotically, for extremely large . The internal algorithm is used in one phase of the external algorithm. We demonstrate the scalability of the external algorithm by constructing MPHFs for a set of 1.024 billion URLs from the World Wide Web of average length 64 characters in approximately 62 minutes, using a commodity PC.

Speaker's Bio
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).