Upcoming Student Events

Efficient Algorithms for Querying Large and Uncertain Data

Ph. D. Defense
Speaker Name
Stavros Sintos
Location
On Zoom: https://duke.zoom.us/j/94990898513
Date and Time
-

Query processing is an important problem in many research fields including database systems, data mining, and geometric computing. The goal is to preprocess input data into an index to efficiently answer queries. With the data sets becoming increasingly large and complex, queries are also becoming complex, therefore new challenging problems have emerged in the area of query processing. This talk focuses on two broad themes: data uncertainty and data summarization.

Two Algorithmic Schemes for Geometric Bipartite Matching and Transportation

Ph. D. Defense
Speaker Name
Allen Xiao
Location
Talk will be virtual on Zoom
Date and Time
-

Given n red points and n blue points in d-dimensional space and a
distance function, the geometric bipartite matching problem is to find a
matching of red points to blue points, such that the sum of distances
between the matched pairs is minimized. The general graph problem,
minimum cost bipartite matching, can be solved in polynomial time using
the classical Hungarian algorithm, which leads to a cubic algorithm for
the geometric matching problem. We present several algorithms for