FastMap and Its Applications

Friday, May 7, 2021, 11:00 am - 12:00 pm PDTiCal
Virtual via Zoom WebinarThis event is open to the public.
AI Seminar
Satish Kumar Thittamaranahalli (USC/ISI)

This Talk will be Live Broadcast only, it will not be recorded. 

AI Seminar Series

Seminars for the Artificial Intelligence Division at USC Information Sciences Institute

YOU ONLY NEED TO REGISTER ONCE TO ATTEND THE ENTIRE SERIES- We will send you email announcements with details of the upcoming speakers.

Register in advance for this webinar:

After registering, you will receive a confirmation email containing information about joining the webinar.


I will present a new algorithm, called FastMap, for embedding the vertices of a given edge-weighted undirected graph into a Euclidean space. The Euclidean distance between any two vertices in this space approximates the length of the shortest path between them in the given graph. FastMap's novelty is that it preserves a quadratic number of pairwise distances between all the vertices but does not invest quadratic time for doing so. Instead, it runs in time near-linear in the size of the graph. FastMap's efficiency leads to many applications, including but not limited to: (a) speeding up shortest-path computations in goal-directed A* search, (b) solving useful graph-theoretic combinatorial problems using geometric interpretations, (c) efficiently computing measures of centrality on large graphs, (d) embedding directed graphs in potential fields, (e) new algorithms for community detection and block modeling, and (f) new ways of doing machine learning on graphs.


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 faculty member 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 such diverse areas 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 Spatio-Temporal Reasoning. He has served on the Program Committees of many international conferences and is a winner of four 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.

Host: Deborah Khider  POC: Peter Zamar

Subscribe here to learn about upcoming ISI seminars:

« Return to Upcoming Events