| Meno: | Michelle |
|---|---|
| Priezvisko: | Gavlák |
| Názov: | Efficient algorithms for transforming JSON data streams |
| Vedúci: | RNDr. Jana Kostičová, PhD. |
| Rok: | 2026 |
| Kµúčové slová: | JSON, stream processing, JSON transformations, transducers, space complexity |
| Abstrakt: | The prevalence of JSON data streams requires efficient transformation methods. Analyzing space complexity is crucial because it is often desirable to load only the necessary data segments into memory rather than the entire file. Moreover, in real-time scenarios, memory consumption often directly affects latency. We surveyed existing tools for processing JSON data and found that few practical solutions exist for transforming JSON data streams, and there is limited formal research on the complexity of such transformations. In response, we introduce the JSON Specification (JS) language, which utilizes a JSON-based specification file to define transformations. We present seven commonly used transformation operations: identity, rename, remove, replace, add, copy, and move. The corresponding algorithms are described using our formal model, the JSON Stream Transducer (JST), which incorporates two memory management components: a stack for evaluating the current path and a queue for auxiliary storage. Each transformation is implemented as a transducer instance and classified into one of three complexity classes: no-memory, stack, or buffer. For the stack and buffer classes, we provide a detailed space complexity analysis. The stack class exhibits complexity linear to the depth of the tree structure of the JSON file. The buffer class encompasses more scenarios, but in all cases, its complexity can reach the size of the file. Therefore, for the buffer class, spatial complexity is linear with respect to file size in the worst case. We validate these findings by developing a Java prototype and measuring memory allocation using the Java Flight Recorder (JFR) profiler. |
Súbory diplomovej práce:
| JSONStreamTransformationsGavlakv2.pdf |
| JSONTransformator.zip |
Súbory prezentácie na obhajobe: