|
|
Distributed Graph Query Engine Improvements for Big Data Graphs
Faltín, Tomáš ; Yaghob, Jakub (advisor) ; Tommasini, Riccardo (referee) ; Vora, Keval (referee)
Graph pattern matching queries enable flexible graph exploration, similar to what SQL provides for relational databases. In this thesis, we design and improve key compo- nents of a distributed in-memory graph querying engine. First, we optimize a distributed depth-first search (DFS) asynchronous pattern matching algorithm by combining it with breadth-first search (BFS), thus improving the overall engine performance by leveraging strengths of both approaches: ability to strictly bound the consumed memory of DFS and better parallelization, locality, and load balancing of BFS. Second, we further ex- tend the distributed pattern matching with a novel solution for reachability regular path queries (RPQs) that supports variable-length patterns based on regular expressions. Our design retains the underlying runtime characteristics, allowing for efficient memory con- trol during path exploration with great performance and scalability. Third, we improve query planning, which is one of the most crucial aspects impacting the performance of any querying system. Choosing the "best" query plan is challenging due to the many aspects influencing the performance, especially in a distributed system. We present a lightweight mechanism for gathering runtime information, which can be used to select the most effective query plan...
|
|
|
Fuzz testing of network subsystem in PikeOS
Piroutek, Jan ; Parízek, Pavel (advisor) ; Yaghob, Jakub (referee)
Stability under every possible circumstance is a goal for a lot of applications. This problem applies to the network stack ANIS of the real-time operating system PikeOS developed by SYSGO. PikeOS requires security and stability because it is used in areas, e.g., airborne systems, where unstable software could cause severe damage. A proven way to ensure the stability and security of software is testing. Fuzzing is an automated testing technique that generates randomized inputs for the application to find bugs, vulnerabilities, or crashes within the application. Another testing technique is long- run testing, which exposes an application to some input for longer periods. Because ANIS is a product usually shipped with PikeOS, it must follow the same security standards. We have developed a testing tool for the ANIS network stack, using the two mentioned techniques and emphasizing the option to configure such a test. This testing tool exposes the ANIS to various scenarios that could stress the stack and uses fuzzing to create a combination of these scenarios automatically, which could crash the network stack. The developed test is implemented with a small set of scenarios that expose ANIS to various network traffic. The test can be extended to work with more scenarios. All scenarios have a predefined set of...
|
|
|
Meeting the challenges of k-nearest neighbor search implementation for GPU accelerators
Hanák, Drahomír ; Kruliš, Martin (advisor) ; Yaghob, Jakub (referee)
Similarity search is a commonly used technique in databases for finding objects si- milar to a query. It finds applications in content-based retrieval of complex objects like images, information retrieval, and statistical learning. Our thesis focuses on the imple- mentation and optimization of the k nearest neighbours (kNN) algorithm on a GPU, a commonly used technique in similarity search. We analyze and evaluate several existing GPU kNN implementations in various configurations and propose the best algorithm for each configuration. We also suggest optimizations of k-selection. In particular, we suggest a small k-selection approach, which achieves up to 80% of peak theoretical throughput on a typical configuration used in many applications of kNN and is faster than the current state-of-the-art. We implemented a fused algorithm, which solves kNN without mate- rializing the distance matrix, and a large k-selection, which outperforms an optimized, parallel sorting of the whole database by a significant margin. 1
|
|
|
Performance of Open vSwitch-based Kubernetes Cluster in Pathological Cases
Šraier, Václav ; Benc, Jiří (advisor) ; Yaghob, Jakub (referee)
With the adoption of cloud computing, horizontally scalable infrastruc- ture, and containerized deployments, Software Defined Networking (SDN) became an integral part of data centers, Kubernetes and Open vSwitch (OVS) being one of the commonly deployed solutions. Our work explores the possible performance limitations of OVS under Kubernetes, focusing on pathological traffic patterns. We discovered several types of packets causing excess system load on the cluster nodes. We identified the root cause as a series of drop rules in OpenFlow and a design flaw in OVS that prevents their efficient evaluation. We investigated the impact of this problem and our research revealed a specific system configurations under which an adversary can use the discovered inefficiencies for a practical denial of service attack on the local cluster node, bringing the whole networking stack down for all neighbouring containers.
|
|
|
Virtual file system in user space
Veselý, Milan ; Yaghob, Jakub (advisor) ; Horký, Vojtěch (referee)
This thesis presents a custom Virtual File System (VFS) built with C++, using a custom wrapper for the FUSE library. The VFS is modular in design, facilitating easy extension with new features. Two prototype modules for ver- sioning and encryption are also included, each accompanied by a command- line interface tool for control, such as restoring versions or encrypting files. Thanks to its password/key protection and encryption capabilities, the VFS enhances file management, enabling secure storage and retrieval of sensitive data. In addition, built-in versioning functionality allows users to access and restore previous file versions with ease. Once the VFS is mounted, it can be accessed in the same standard way as any other file system, making it user-friendly and accessible.
|
|
|
Modular backup system for virtualization
Výkruta, Jan ; Yaghob, Jakub (advisor) ; Klímek, Jakub (referee)
Backing up of a virtual machine is the act of capturing a static image, that can be subsequently used for restoration in case of the target machine failure. We contribute a pilot implementation of a modular system suitable for virtual machine backup and restoration on the VMware vSphere virtualization stack. The application can be ex- tended with support for other platforms. It supports deduplication and transformation of the backed up data, automatic periodic backups and consolidation of the backups ac- cording to a policy. Moreover, the appliance stores the backed up data into a user-defined location. The software can be extended and modified in all of the above cases. Finally, we provide documentation of the system, suggestions for possible extensions and a guide to implement them. 1
|
|
|
SQL parser for data lineage with support for multiple dialects
Kukaň, Tomáš ; Yaghob, Jakub (advisor) ; Parízek, Pavel (referee)
The main goal of this work was to create a program that would be able to use static analysis of SQL code to detect the data line between database objects. In this paper we will find examples of the data line in SQL, various techniques of static analysis and detailed analysis of the data line in SQL and it's procedural extension. This theoretical part is followed by a description of the architecture and implementation of the program. This implementation is for PostgreSQL dialect, but the architecture assumes future implementation for multiple dialects. Finally, I compare this implementation with currently available tools.
|
|
|
Graphical engine for FPS
Forch, Jan ; Yaghob, Jakub (advisor) ; Plch, Tomáš (referee)
Title: Graphical engine for FPS Author: Jan Forch Department: Department of Software Engineering Supervisor: RNDr. Jakub Yaghob, Ph.D. Supervisor's email address: Jakub.Yaghob@mff.cuni.cz Abstract: The aim of the present thesis are technologies of computer games development. Thesis is mainly focused on FPS (first person shooter) type of games. For that type of games is typical three dimensional graphics. Main topics of that text are related algorithms, structures, libraries and optimalizations, which lead to successful realization of computer game. Important part of the thesis is concrete implementation of game which uses described solutions. Keywords: engine, 3D graphics, artificial intelligence, navigation, game
|
|
|
Reverse parallel configuration manager
Doležal, Petr ; Yaghob, Jakub (advisor) ; Adámek, Jiří (referee)
Existing tools for build and configuration management of software projects often suffer from various drawbacks, the typical problems include, for example, a complicated notation of a project's configuration or difficulties with the portability of a configuration description between various platforms. This work analyses the advantages and disadvantages of the approaches used by existing implementations and it proposes the solution that is based on merging the well-established and interesting ideas of various existing solutions. An important part of the work is the implementation of a fully functional program according to the proposed design, which allows to test the solution in practice. The goal of the implementation is to avoid the disadvantages of existing similar programs while keeping their advantages.
|
|
|
The influence of caches on the efficiency of sorting
Hrdina, Karol ; Koubková, Alena (advisor) ; Yaghob, Jakub (referee)
Classical algorithms for sorting in internal memory were designed with an assumption, that the memory is homogenous. But modern computers have hierarchically structured memory with various speeds of it's layers. Execution time of algortihm is dependant not only on operation count, but also on count of transfers between memory layers. Therefore internal algorithms are having some characteristics of external algorithms. In this paper we set our goal to summarize some existing approaches to this problem and summarize known optimalizations of internal sorting algorithms. Our main goal however is to impelent chosen algorithms and measure their performance experimentally.
|
guest ::
