Skip to main content
Upcoming Events:

Seminar: Yakov Nekrich

Date & Time:
   Add All to Calendar

Data Structures for Computational Geometry and Strings

Overview

Abstract

In this talk we give an overview of some recent results in geometric and string data structures. In the range reporting problem, we keep a set of points P, so that for any axis-parallel query rectangle Q all points from P\cap Q can be reported efficiently. In the two-dimensional point location problem, we store a planar sub-division so that for any query point q the polygon containing q can be found efficiently. In the first part of this talk we review the recent progress in these fundamental geometric problems.

In the second part of this talk we turn to problems related to storage and analysis of massive string data. A compressed string index is a data structure that keeps a string in compressed form and supports pattern matching queries. We present a compressed index for a collection of strings and efficient solutions for several related problems.

Bio

Yakov Nekrich is an associate professor at Michigan Technological University. He works on efficient algorithms for geometric and sequence data. He is especially interested in space-efficient and compressed data structures and their applications to the world of big data. Dr. Nekrich has authored 75 conference and journal papers, including such venues as SIAM Journal of Computing, IEEE/ACM Transactions on Bioinformatics and Computational Biology, ACM Symposium on Discrete Algorithms, ACM Transactions on Database Systems and IEEE Symposium on Foundations of Computer Science. He has held visiting research professor position at the University of Paris Est, France, and served on program committees of several conferences, including major database conferences, PODS, ICDT, and ICDE.