Dr. Yakov Nekrich’s project aims to tackle the challenges of organizing and managing geometric data structures, which are becoming increasingly complex.
Author: Jessica Brassard
All of us, from the tech wizard to the average kindergartener, have a sense of the vast amount of data collected and stored in the world. With the ever-growing volume of data being collected and stored, efficient methods of navigating and querying large data volumes are crucial. Dr.Yakov Nekrich‘s project focuses on the “geometric” data structures that large data sets are organized into and their potential applications in various areas of computer science.
Dr. Yakov Nekrich (Associate Professor, Computer Science) has been awarded $594,059 from the National Science Foundation (NSF) for his project “AF: Small: Fundamental Geometric Data.” Dr. Nekrich and his team focus on the data structures that work with, process, and manage geometric data.
Efficient methods of storing and querying large data volumes are crucial in most computer applications. In many situations, the stored data and the queries can be represented as geometric objects, such as points, lines, and rectangles.
Nekrich notes that this project attempts to solve some challenging problems that have been open for a long time. “This project could increase our understanding of geometric data structuring problems,” he says.
This scenario is traditionally studied in computational geometry. However, geometric data structures have numerous applications in other areas of Computer Science, from spatial databases to geographic information systems, from computer graphics to bioinformatics. The connection to other areas of theoretical computer science is what makes this project exciting.
Nekrich’s project will study the implementations of obtained algorithms and their potential applications. This becomes increasingly important as the data and approaches to data start to blend the boundaries between disciplines. This project will focus on fundamental geometric data structuring problems: the orthogonal range searching problem, the point location problem, the nearest neighbor problem, and the dynamic convex hull problem. Despite several decades of extensive study, there are still a number of important open questions related to these problems.
Nekrich was drawn to this topic because of its importance and connections to other areas. “In order to obtain new results, you need a deep understanding of data structuring techniques and certain geometric thinking,” he says.
The project aims to extend and deepen the knowledge of fundamental geometric structuring problems with specific tasks such as reducing or eliminating the gaps between the lower and upper bounds, investigating the relative complexities of problems in different models of computation, and finding more efficient ways to dynamize the static data structures. In addition to the tasks mentioned above, the project will explore the connections between geometric data structures and algorithms in the external memory model.
The research team will build upon and extend several established approaches to achieve their objectives: shallow cuttings and fractional cascading. Shallow cuttings is a geometric concept that plays a crucial role in solving some geometric problems of interest in this work, including the nearest neighbor problem and the range reporting problem. Fractional cascading is a general technique used to speed up queries in data structures. Although these approaches were studied thoroughly, their application to geometric problems can be challenging. This research looks at both these techniques’ potential improvements and limitations.
This research is funded by the National Science Foundation (award #: 2203278), and the project is expected to run from 10/1/2022 to 9/30/2025. Nekritch will collaborate with Saladi Rahul (the Indian Institute of Science in Bangalore) and John Iacono (Université libre de Bruxelles in Belgium). The project will also include two doctoral students.