2024 Summer internships
Saint Petersburg Research Center
STIL
Подать заявку
Расписание
апрель - 25 мая
апрель - 25 мая
Подайте заявку
Подайте заявку на 1-3 интересных вам проекта. Каждый проект рассчитан на 1 человека.
15 мая - июнь
15 мая - июнь
Пройдите интервью
Команда проекта, на который вы подались, проведет с вами собеседование. Собеседование займет 1-1.5 часа, оно будет посвящено вашему бэкграунду и знаниям математики и програмирования.
конец июня
конец июня
Получите приглашение на проект
Мы сообщим результаты собеседования по почте.
июль - август
июль - август
Работайте над проектом
Стажировка рассчитана на 2 месяца с нагрузкой 40 часов в неделю и проходит в очном формате.
конец августа
конец августа
Представьте свои результаты
Для всех стажеров будет организована очная защита, на которой каждый сможет рассказать о своем проекте. После защиты вы получите сертификат о прохождении стажировки.
Вступайте в наши ряды
Наши проекты
Команда: Graph Algorithm
Презентация
Landmarks + A* shortest path acceleration
Finding a shortest path from one vertex to another as fast as possible is a well known problem that has many various solutions. One of them is A*. the idea behind the algorithm is to use some estimation on distance to the target vertex. Using them as potentials one reduces edge distances on the shortest paths, while leaving distances on other edges quite big, thus reducing number of seen vertices during search.

The remaining problem is to get the bounds on shortest path distances. For plane graphs one usually can use euclidean distances. But for arbitrary graphs one has to apply different techniques. One of them are landmarks. The idea is to precompute distances to some vertices and then estimate distances using triangle inequality.

The goal of this project is to implement this technique and incorporate it in products.
GPU accelerated shortest path algorithm
Many computational problems gain significant solution improvement due to raise of computational power. The leading technique here is GPU acceleration due to a good balance between generality and speed. But not all algorithms could be adopted to GPU in a way that gains better performance. For example: Dijkstra algorithm.

But there are some well known algorithms that allow good parallelization. For example: Δ-stepping algorithm.

The goal of the project is to implement this and some other algorithms and adopt it to currently existing framework.
Contraction Hierarchies min-cost max flow
Contraction hierarchies algorithm was developed to accelerate shortest path queries on road maps.
The idea is to calculate importance of nodes. This gives some order of nodes which one calls contraction order. Contract nodes starting with lower important and add shortcuts (new edges) in a way, that the distances between remaining vertices stays the same. In the graph with old edges and new shortcuts any edge has up and down directions. The main point is that the shortest path in that graph is always up-down path, which could be found by bidirectional Dijkstra (for example).

This significantly reduces number of vertices to be seen.

On the other hand Min-Cost Max Flow problem which is a strong tool to plan network traffic is based on shortest path computation. The only complication is that edges are directed and edge costs could be negative.

The goal of this project is to adopt the existing solution with CH for MCMF computation and other related problems like computation of Gomory-Hu tree.
Multiconstraint graph partitioning
The partitioning technique is often used to reduce problem to smaller instances. But often it has it's own meaning. In that case one often has more parameters than (for example) number of vertices inside one part but some restrictions to diameter of the parts, etc.

The goal of the project is to implement classical flow-based methods like PUNCH or Inertial Flow in multiconstraint context.
Fast k-closest segment detection
In many practical applications one has to deal with plane graphs originated for example from road networks.

To add new vertex to the graph one usually has not only to supply it with coordinates, but to connect it to closest existing edge. Sometimes the closest edge could be not the optimal one in some sense, thus leading to the problem of finding k-closest segments. Other possible issues could be to find all sufficiently close pairs of edges etc.

The general approach to such problems is to use spatial indices like R-tree, KD-tree, or Quad-tree. Some of them could be more useful for edge finding procedure than others. We expect that you will implement some of this structures and adopt them to the solution or provide your own approach to the problem.
Data processing scheduling
Processing large data is often challenging due to time and memory limitations. Time overhead in executing such queries appears in redundant file reads and processing files by parts if they are to big to fit into memory. Often queries can be represented as graphs with vertices as files and edges connecting pair of files which is involved in one query. The goal of the project is to provide a scheduling engine that speeds up query execution.
Команда: Embedded Solver and Component Library
Презентация
Pseudo cost branching strategy
Planning / scheduling / resource allocation are often modelled as MILP problems which are NP-hard.
The core part of MILP solvers is Branch&Bound (B&B) algorithm which can be imagined as DFS search. The branching strategy during B&B is the biggest secret of commercial solvers, as improper branching can make B&B to grow exponentially.

You will study basics of solving MILP problems, and get familiar with general branching rules.
After that, you will try to create your own branching rule to beat the others.
Cholesky factorization update
Some problems that occur in Autonomous Driving are formulated as Quadratic Programming (QP), e.g. to minimize a quadratic function subject to some linear constraints. The bottleneck of QP solver is solving linear system with a Symmetric Positive Defined (SPD) matrix. This can be done with Cholesky decomposition.

You will look for a way of fast (e.g. <O(N3) ) refactorization of similar SPD matrices, i.e. matrices that differ in 1 column and 1 row. This may help to dramatically accelerate the iterations of QP solver.
Cholesky preconditioner
Some problems that occur in Autonomous Driving are formulated as Quadratic Programming (QP), e.g. to minimize a quadratic function subject to some linear constraints. The bottleneck of QP solver is solving linear system with a Symmetric Positive Defined (SPD) matrix. This can be done with Cholesky decomposition.

You will research how to improve a stability of LLT factorization by preconditioning, and how to do it fast.
This will help to find more reliable solutions of QP.
L2O: Learn to Optimize
Coverage optimization of a large-scale wireless network can be formulated as a series of N black-box (gradient free) optimization problems. Each problem concerns the single antenna parameters such as azimuth, tilt and beam pattern.

Since in a city like St. Petersburg the number of antennas can reach tens of thousands, we would like to train our optimizer to evolve through this process.

Learn to Optimize (L2O) is a recent technology that aims to achieve this goal. Let's see if this applies to black box optimization.
Команда: Data Governance
Презентация
Content defined Chunking on kernel-level
Content-Defined Chunking is an approach used in data deduplication systems to identify and split data into chunks based on the actual content of the data stream. Unlike traditional methods that rely on fixed-size chunks or byte offsets, CDC dynamically determines chunk boundaries by analyzing the data itself. In order to reduce space usage, we need to provide an efficient and convenient way to store different snapshots of filesystem. One approach is to use filesystem with built-in data deduplication and compression. Another approach - is to create virtual device that supports of mentioned above methods. Then we can use any filesystem on top of this device. The main challenge is to create efficient chunking algorithm within Linux module.
Tensor decomposition for LLM compression
In the last years there is a lot of research on Tensor Decomposition topic and it’s application to neural networks in order to reduce the computation cost and compress the neural networks by reducing the number of parameters without significant quality loss. In the project it is proposed to study and implement neural networks whose layers are decomposed by tensor decomposition and compare the quality metrics and computational costs with the conventional ones.
Low level optimization of existing compression codecs
Any optimization is extremely important during data collection due to the high load of base stations. One of the important approaches to speed up data processing is to rewrite it for architecture. The main challenge is speed up lossless compression algorithms (Delta, RLE, Gorilla and other) by low level optimization. As part of this work, it will be proposed to explore new approaches to lossless compression.
Index structures (B trees, LSM and other) for compressed computing
One of the open topics in data storage is the ability to quickly find or calculate functions on compressed data. The most popular approach is data decompression and further computation. To speed up this process, it is proposed to conduct a research on the construction of tree indexes (B trees, LSM and other) to reduce the amount of data that needs to be decompressed.
Lossy compression
Exponential data growth leads to the problem that existing lossless compression algorithms are not enough. Data collected from base stations as a rule is not structured (low local continuity) and standard lossy compression methods do not work. As part of this practice, research is proposed to identify the best algorithm for pre-processing and lossy compression.
Команда: Math Modelling and Optimization
Презентация
Surrogate modelling of a wireless network digital twin
A wireless network digital twin produces accurate simulations which are used for network performance optimization. Unfortunately, the computational complexity of the digital twin is huge making quasi-real-time optimization infeasible. To overcome this issue, we plan to build a surrogate model of the digital twin using the latter as a generative model.
Large model compression via extreme quantization
Large language models (LLMs) have driven rapid advances across diverse fields. However, the massive size of these models poses significant challenges to their deployment. In the last year, we have seen a lot of research on model quantization, especially in post-training approaches. In this project, we will study and re-implement different post-training quantization techniques for MindSpore, a deep learning framework.
Message passing for fast and scalable approximate inference
Finding a close-packing shape arrangement with obstacles is an important problem in engineering design known to be hard given many objects and complicated obstacles. The message passing algorithms provide flexible and heuristic scalable solutions to the inference in hard combinatorial optimization problems. Its application to close-packing in different dimensions is one of such problems where the heuristics of message passing can be employed for finding an MAP estimator for object positions. We will consider a problem of placing subintervals on a circle with obstacles without overlaps, as well in higher dimensions, where neighboring shape positions are updated according to the computed pairwise overlaps. More generally such a placement problem can be considered as a black-box problem if the information on shapes dimensions is hidden. Here the solution can be competitive to CMA-ES (Covariance Matrix Adaptation Evolutionary Strategy). We will investigate convergence and different strategies for message updates and benchmark against CMA-ES.
Discrete-time dynamic graph time series forecasting with missing data
Graph-based deep learning is a popular framework for modelling spatiotemporal data. Compared with traditional multivariate forecasting, spatiotemporal graph neural networks operate on the graph where each node usually represents a sensor that collects the data, and edge accounts for local correlations between the nodes. In many scenarios, modeling such correlations can significantly increase the forecasting accuracy. In this project, we plan to study and implement such models on top of our internal library for spatiotemporal modeling.
Multiple hypothesis testing problem in the PC algorithm
The PC algorithm is an algorithm for identifying the causal structure in data and is often used for root-cause analysis. In a nutshell, the algorithm is based on multiple testing of independence for different variables. As such, multiple hypothesis testing problem leads to the high sensitivity of the PC. We suggest considering different statistical techniques and PC modifications to overcome this issue.
Вопросы и ответы
Контакты
Если у вас остались вопросы, пожалуйста, напишите нам.
Email: komandastazirovok@gmail.com