Revisiting FastMap: New Applications

Abstract: FastMap was first introduced in the Data Mining community for generating Euclidean embeddings of complex objects. In this talk, I will first generalize FastMap to generate Euclidean embeddings of graphs in near-linear time: The pairwise Euclidean distances approximate a desired graph-based distance function on the vertices. I will then apply the graph version of FastMap to efficiently solve various graph-theoretic problems of significant interest in AI: including shortest-path computations, facility location, top-K centrality computations, and community detection and block modeling. I will also present a novel learning framework, called FastMapSVM, by combining FastMap and Support Vector Machines. I will then apply FastMapSVM to predict the satisfiability of Constraint Satisfaction Problems and to classify seismograms in Earthquake Science.

Bio: Prof. Satish Kumar Thittamaranahalli (T. K. Satish Kumar) leads the Collaboratory for Algorithmic Techniques and Artificial Intelligence at the Information Sciences Institute of the University of Southern California. He is a Research Associate Professor in USC’s Department of Computer Science, Department of Physics and Astronomy, and Department of Industrial and Systems Engineering. He has published extensively on numerous topics spanning diverse areas such as Constraint Reasoning, Planning and Scheduling, Probabilistic Reasoning, Machine Learning and Data Informatics, Robotics, Combinatorial Optimization, Approximation and Randomization, Heuristic Search, Model-Based Reasoning, Computational Physics, Knowledge Representation, and Spatiotemporal Reasoning. He has served on the program committees of many international conferences and is a winner of three Best Paper Awards. Prof. Kumar received his PhD in Computer Science from Stanford University in March 2005. In the past, he has also been a Visiting Student at the NASA Ames Research Center, a Postdoctoral Research Scholar at the University of California, Berkeley, a Research Scientist at the Institute for Human and Machine Cognition, a Visiting Assistant Professor at the University of West Florida, and a Senior Research and Development Scientist at Mission Critical Technologies.