Transcriber: Nhung Nguyen Reviewer: Ido Dekkers
Hi, I’m David Bader.
I’m a distinguished professor of data science
at the New Jersey Institute of Technology,
where I direct the Institute for Data Science.
And today I going to talk to you about solving global grand challenges
with high performance data analytics.
I'm an enthusiast for graphs,
and I want to take you on a journey to talk with you about graphs
and really the resurgence that we see as we’re coming out of this pandemic.
And as we look at new ways to solve
the types of problems that really affect populations.
Graphs, you’ve probably heard the word before.
And as I talk about them, there are objects that have vertices
and their edges that connect these vertices together.
Maybe you’ve seen a social network where you have people as the vertices,
and when you're a friend with someone, you connect them with an edge.
Now, this modern view of graphs has been around for quite a number of years.
Back in the early 18th century,
there is a city of Königsberg in Prussia
where there was a challenge given by the King.
You see, the city had a number of islands and a number of bridges
that connected them together.
In fact, there were seven bridges.
And the King had this challenge to see if anyone could start
on one of the landmasses, cross each bridge exactly once
and hopefully come back to their starting point.
So the citizens would mill around on the weekends and often on a nice Sunday,
they would try to walk around the city
and see if they could solve this challenge.
But nobody did.
It wasn’t until 1735 that Leonhard Euler came up with a abstraction.
A proof using graphs to a more general problem,
where he proved that you couldn’t do this.
He turned the city into a graph
with four vertices representing the different landmasses
and edges connecting those vertices.
Each edge representing a bridge.
So there are seven edges, each representing a bridge;
and four vertices that connected the graph together.
And Leonhard Euler proved that there was no tour around the city
by showing that if the graph is connected
and there are any odd degree vertices that couldn't be done.
And when I say odd degree,
it means that for a vertex there's a odd number of bridges connected to it.
And so in the town of Königsberg,
all four of those landmasses had an odd number of bridges connected to them,
meaning there is no solution.
Now, when I talk about real-world graphs and real-world problem solving,
often we’re looking at problems where the graphs aren’t simple
with just simple edges.
But often there are weights on those edges
and we’re trying to optimize for those weights.
So the basis and beginning of what we think of
as modern real-world graph problems goes back to almost 100 years ago.
In the Czech Republic, there was a mathematician named Otakar Borůvka,
and he had a friend, Jindřich Saxel,
who worked at the
which was the West Moravian Power Plant Company.
And this was the early days of electrical power.
And this guy, Jindřich Saxel, was trying to connect the South Moravian area
with an electric power grid and do it in a cost-effective way.
So what he was trying to do was take 40 different points in the region
and connect them with transmission lines.
And this is a graph-problem called the minimum spanning tree.
This was the problem that really taxed him.
He didn’t know how to solve it.
So his friend, Otakar Borůvka, came up with a brute-force way to do it.
And again, this was 1926, and he published that paper.
And it turned out to be the very first real-world graph problem that was solved.
So this takes us fast-forward
to what I think of as the modern era of graph theory
and applying graphs to real-world problems.
In fact, I grew up here in the United States,
and I kind of think that our government tried to sort of covertly
have all the kids in this country learn about graphs.
I don't know about you, but one of my favorite holidays was Halloween.
It happens in the fall when we have lots of apples around.
And here in New Jersey, you may know that
we have over 30 varieties of apples in New Jersey.
So I always like Halloween.
And I want to optimize for the two hours that we had to go trick-or-treating.
The amount of goodies that we got,
so we would go door to next door knocking on doors,
“Trick or treat”
And then hopefully we would get something maybe it was a candy bar, a popcorn ball,
an apple, and I really liked apples.
Or maybe it was a trick.
You never quite knew.
And what we would do is we would create a graph.
We would turn each house into a vertex
and we would connect the paths to reach these different houses by edges.
And in maybe elementary school as we were doing this;
we would learn graph theory because we would figure out the shortest tour
that would take us through the most number of houses.
And for me, I'd like to get apples.
And so I kind of think our government has been implanting into us
the idea of using graphs to solve these real-world problems.
Now today we're faced with big challenges
as we head into these massive graph problems.
For instance, we may be trying to solve problems on urban sustainability.
How do we reduce congestion within cities?
How do we improve our transportation networks?
What do we do as hurricanes come, for instance, in Louisiana
or New Jersey, in the Northeast,
where we recently had massive flooding and loss of life?
How do we evacuate people?
How do we tell people, what’s the best way to get out?
And how do we understand what they’re going to do in those populations?
Or having trustworthy and free and fair elections in this country.
Or problems such as protecting our infrastructure against cyber attack
and giving attribution to those attacks?
These are the types of problems
that really are the ones that I’d like to solve.
And I know that you would like to have solutions to these
because they really make our world a better place
and a more enjoyable place to live
and also reduce a lot of the problems that we tend to see.
So if we're trying to solve these problems,
we now have many different data sources.
Those data sources may come from the Internet of Things and sensors.
It may come from system log.
It may come from our health informatics records.
And we want to take this data and we want to build a graph out of it,
and use these graphs in order to improve the human condition.
Now, previously, these datasets would fit on our laptops,
we could go and we could download some software,
run it on our laptop and get a solution pretty fast.
But now these datasets are growing in size.
They have maybe millions, billions, trillions,
even more of records of information,
and those datasets may be on the order of petabytes in size.
And so we're working on tools that will be able to take these massive datasets,
say, for instance, tens of terabytes and
be able to democratize data science on them by allowing everybody to use
a common interface to ask their queries of these datasets.
Today, the language of data science is called Python.
This is a very productive, easy to use framework,
where people use different toolkits like NumPy and PD arrays
to operate on their datasets.
And when their data is held locally, it is interactive.
It works really, really well.
But when those datasets occur and are held in different data warehouses
or large scale storage,
it becomes very difficult to interact with them.
So we’re working on a framework called RCUDA,
and RCUDA is initially developed by the Department of Defense,
and we're building out the graph analytic capabilities within this framework.
The frontend to RCUDA looks very familiar.
It looks like Python with a very easy to use frontend,
so any data scientists can pick it up and interact with it.
But their data may be sitting on the backend in a supercomputer using
a novel programming language called Chapel from HPE Cray.
And so when you issue your commands,
it may return in near real-time, you may get your answers instantaneously.
But we're working on the algorithms and the heavy lifting in order to have
the data on the backend, be running those calculations that are needed to solve
the problems that I just discussed.
So here at NJIT, we’re really excited by doing this work
on making graph analytics at scale interactive
and really available to everyone.
And that includes citizen scientists who are really trying to learn
about data science.
Now we're also in a very interesting era of being on
the cusp of something called exascale supercomputing.
We’re about to see in this world the first machine
that can run 10 to the 18th floating-point operations per second.
That’s a lot of computing!
And these highly capable machines are going to be fantastic
for doing these types of graph analytic problems,
but only when those data sets are static,
meaning I can pick up that dataset and load it into that computer.
Where we're headed to in the future is more streaming applications,
streaming data and streaming graphs.
And we’re we’re really focused and we’re, I think, the future is,
is being able to do predictive analytics.
Taking in data streams and building new computer systems
that are able to reason about that data and make decisions in near real-time
rather than collecting data after something has happened
and analyzing the data forensically in a big supercomputer.
So I’m excited by having graphs all around us.
Every problem I see, I look at, I see graphs and I hope that you will too,
and that we’re really at this age of
this resurgence of looking at how to solve problems better
and the new world going forward
and how to really make the world a better place.
So thank you for your time and
I look forward to you using graphs and liking graphs as much as I do here.
Thank you!