Search

Efficient learning from streaming data is important for modern data analysis due to the continuous and rapid evolution of data streams. Despite significant advancements in stream pattern mining, challenges persist, particularly in managing complex data streams like sequential and weighted itemsets. While reservoir sampling serves as a fundamental method for randomly selecting fixed-size samples from data streams, its application to such complex patterns remains largely unexplored. In this study, we introduce an approach that harnesses a weighted reservoir to facilitate direct pattern sampling from streaming batch data, thus ensuring scalability and efficiency. We present a generic algorithm capable of addressing temporal biases and handling various pattern types, including sequential, weighted, and unweighted itemsets. Through comprehensive experiments conducted on real-world datasets, we evaluate the effectiveness of our method, showcasing its ability to construct accurate incremental online classifiers for sequential data. Our approach not only enables previously unusable online machine learning models for sequential data to achieve accuracy comparable to offline baselines but also represents significant progress in the development of incremental online sequential itemset classifiers., Comment: Accepted at 2024 IEEE International Conference on Big Data

Discovering valuable insights from data through meaningful associations is a crucial task. However, it becomes challenging when trying to identify representative patterns in quantitative databases, especially with large datasets, as enumeration-based strategies struggle due to the vast search space involved. To tackle this challenge, output space sampling methods have emerged as a promising solution thanks to its ability to discover valuable patterns with reduced computational overhead. However, existing sampling methods often encounter limitations when dealing with large quantitative database, resulting in scalability-related challenges. In this work, we propose a novel high utility pattern sampling algorithm and its on-disk version both designed for large quantitative databases based on two original theorems. Our approach ensures both the interactivity required for user-centered methods and strong statistical guarantees through random sampling. Thanks to our method, users can instantly discover relevant and representative utility pattern, facilitating efficient exploration of the database within seconds. To demonstrate the interest of our approach, we present a compelling use case involving archaeological knowledge graph sub-profiles discovery. Experiments on semantic and none-semantic quantitative databases show that our approach outperforms the state-of-the art methods., Comment: Accepted at 2024 IEEE International Conference on Big Data

Creation and storage of datasets are often overlooked input costs in machine learning, as many datasets are simple image label pairs or plain text. However, datasets with more complex structures, such as those from the real time strategy game StarCraft II, require more deliberate thought and strategy to reduce cost of ownership. We introduce a serialization framework for StarCraft II that reduces the cost of dataset creation and storage, as well as improving usage ergonomics. We benchmark against the most comparable existing dataset from \textit{AlphaStar-Unplugged} and highlight the benefit of our framework in terms of both the cost of creation and storage. We use our dataset to train deep learning models that exceed the performance of comparable models trained on other datasets. The dataset conversion and usage framework introduced is open source and can be used as a framework for datasets with similar characteristics such as digital twin simulations. Pre-converted StarCraft II tournament data is also available online., Comment: 14 pages, 7 figures

Quantum computing is currently gaining significant attention, not only from the academic community but also from industry, due to its potential applications across several fields for addressing complex problems. For any practical problem which may be tackled using quantum computing, it is imperative to represent the data used onto a quantum computing system. Depending on the application, many different types of data and data structures occur, including regular numbers, higher-dimensional data structures, e.g., n-dimensional images, up to graphs. This report aims to provide an overview of existing methods for representing these data types on gate-based quantum computers., Comment: 16 pages, 2 figures

Extracting meaningful insights from large and complex datasets poses significant challenges, particularly in ensuring the accuracy and relevance of retrieved information. Traditional data retrieval methods such as sequential search and index-based retrieval often fail when handling intricate and interconnected data structures, resulting in incomplete or misleading outputs. To overcome these limitations, we introduce Structured-GraphRAG, a versatile framework designed to enhance information retrieval across structured datasets in natural language queries. Structured-GraphRAG utilizes multiple knowledge graphs, which represent data in a structured format and capture complex relationships between entities, enabling a more nuanced and comprehensive retrieval of information. This graph-based approach reduces the risk of errors in language model outputs by grounding responses in a structured format, thereby enhancing the reliability of results. We demonstrate the effectiveness of Structured-GraphRAG by comparing its performance with that of a recently published method using traditional retrieval-augmented generation. Our findings show that Structured-GraphRAG significantly improves query processing efficiency and reduces response times. While our case study focuses on soccer data, the framework's design is broadly applicable, offering a powerful tool for data analysis and enhancing language model applications across various structured domains.

The Big Data explosion has necessitated the development of search algorithms that scale sub-linearly in time and memory. While compression algorithms and search algorithms do exist independently, few algorithms offer both, and those which do are domain-specific. We present panCAKES, a novel approach to compressive search, i.e., a way to perform $k$-NN and $\rho$-NN search on compressed data while only decompressing a small, relevant, portion of the data. panCAKES assumes the manifold hypothesis and leverages the low-dimensional structure of the data to compress and search it efficiently. panCAKES is generic over any distance function for which the distance between two points is proportional to the memory cost of storing an encoding of one in terms of the other. This property holds for many widely-used distance functions, e.g. string edit distances (Levenshtein, Needleman-Wunsch, etc.) and set dissimilarity measures (Jaccard, Dice, etc.). We benchmark panCAKES on a variety of datasets, including genomic, proteomic, and set data. We compare compression ratios to gzip, and search performance between the compressed and uncompressed versions of the same dataset. panCAKES achieves compression ratios close to those of gzip, while offering sub-linear time performance for $k$-NN and $\rho$-NN search. We conclude that panCAKES is an efficient, general-purpose algorithm for exact compressive search on large datasets that obey the manifold hypothesis. We provide an open-source implementation of panCAKES in the Rust programming language.

This research focuses on assessing the ability of AI foundation models in representing the trajectories of movements. We utilize one of the large language models (LLMs) (i.e., GPT-J) to encode the string format of trajectories and then evaluate the effectiveness of the LLM-based representation for trajectory data analysis. The experiments demonstrate that while the LLM-based embeddings can preserve certain trajectory distance metrics (i.e., the correlation coefficients exceed 0.74 between the Cosine distance derived from GPT-J embeddings and the Hausdorff and Dynamic Time Warping distances on raw trajectories), challenges remain in restoring numeric values and retrieving spatial neighbors in movement trajectory analytics. In addition, the LLMs can understand the spatiotemporal dependency contained in trajectories and have good accuracy in location prediction tasks. This research highlights the need for improvement in terms of capturing the nuances and complexities of the underlying geospatial data and integrating domain knowledge to support various GeoAI applications using LLMs., Comment: 7 pages, 3 figures

High-strength composite hydrogels cellulose-polyacrylamide were synthesized by free-radical polymerization of acrylamide conducted inside the previously formed physical network of regenerated plant cellulose. Partial hydrolysis of the amide groups of these hydrogels yielded their ionic forms with a degree of hydrolysis of 0.1 and 0.25. The cylindrical hydrogel samples of three compositions were implanted in the preformed osteochondral defects of the rabbit's femoral knee joints. No signs of migration or disintegration of the tested implants were revealed in the course of in vivo tests as long as 90 and 120 days after the implantation. The mechanical behavior of both the virgin hydrogels-implants and the implants extracted from the joints after in vivo experiments was studied in detail. The morphology and chemical composition of the extracted implants were studied by SEM combined with the EDX method. The results obtained were shown that the mechanical characteristics of hydrogel implants remained practically unchanged after in vivo tests. The extracted implants, as well as the initial hydrogels, endured cyclic compression loading at the amplitude up to 50 %. Compression stresses up to 3-10 MPa were recorded in these tests, which is close to the data obtained by several authors for natural articular cartilages in the same conditions of loading. The principal differences in the chemical composition and morphology of the implant area adjacent to the subchondral bone for non-ionic and ionic types of implants have been revealed. If for non-ionic types of implants in this area intensive mineralization with formation of calcium phosphates inside the polymeric hydrogel network is observed, the border area of ionic implants practically does not undergo mineralization., Comment: 39 pages, 19 figures, 8 tables

In this paper, we introduce LearnedKV, a novel tiered key-value (KV) store that seamlessly integrates a Log-Structured Merge (LSM) tree with a Learned Index. This integration yields superior read and write performance compared to standalone indexing structures on SSDs. Our design capitalizes on the LSM tree's high write/update throughput and the Learned Index's fast read capabilities, enabling each component to leverage its strengths. We analyze the impact of size on LSM tree performance and demonstrate how the tiered Learned Index significantly mitigates the LSM tree's size-related performance degradation, particularly by reducing the intensive I/O operations resulting from re-insertions after Garbage Collection (GC). To maintain rapid read performance for newly inserted keys, we introduce a non-blocking conversion mechanism that efficiently transforms the existing LSM tree into a new Learned Index with minimal overhead during GC. Our experimental results, conducted across diverse workloads, show that LearnedKV outperforms state-of-the-art solutions by up to 1.32x in read requests and 1.31x in write performance., Comment: 17 pages, 13 figures

Deliberative processes play a vital role in shaping opinions, decisions and policies in our society. In contrast to persuasive debates, deliberation aims to foster understanding of conflicting perspectives among interested parties. The exchange of arguments in deliberation serves to elucidate viewpoints, to raise awareness of conflicting interests, and to finally converge on a resolution. To better understand and analyze the underlying processes of deliberation, we propose PAKT, a Perspectivized Argumentation Knowledge Graph and Tool. The graph structures the argumentative space across diverse topics, where arguments i) are divided into premises and conclusions, ii) are annotated for stances, framings and their underlying values and iii) are connected to background knowledge. We show how to construct PAKT and conduct case studies on the obtained multifaceted argumentation graph. Our findings show the analytical potential offered by our framework, highlighting the capability to go beyond individual arguments and to reveal structural patterns in the way participants and stakeholders argue in a debate. The overarching goal of our work is to facilitate constructive discourse and informed decision making as a special form of argumentation. We offer public access to PAKT and its rich capabilities to support analytics, visualizaton, navigation and efficient search, for diverse forms of argumentation., Comment: Accepted at the 1st International Conference on Robust Argumentation Machines (RATIO24); 18 pages and 13 pages supplementary materials

The paper tackles the issue of mapping logic axioms formalised in the Ontology Web Language (OWL) within the Object-Oriented Programming (OOP) paradigm. The issues of mapping OWL axioms hierarchies and OOP objects hierarchies are due to OWL-based reasoning algorithms, which might change an OWL hierarchy at runtime; instead, OOP hierarchies are usually defined as static structures. Although programming paradigms based on reflection allow changing the OOP hierarchies at runtime and mapping OWL axioms dynamically, there are no currently available mechanisms that do not limit the reasoning algorithms. Thus, the factory-based paradigm is typically used since it decouples the OWL and OOP hierarchies. However, the factory inhibits OOP polymorphism and introduces a paradigm shift with respect to widely accepted OOP paradigms. We present the OWLOOP API, which exploits the factory to not limit reasoning algorithms, and it provides novel OOP interfaces concerning the axioms in an ontology. OWLOOP is designed to limit the paradigm shift required for using ontologies while improving, through OOP-like polymorphism, the modularity of software architectures that exploit logic reasoning. The paper details our OWL to OOP mapping mechanism, and it shows the benefits and limitations of OWLOOP through examples concerning a robot in a smart environment., Comment: This manuscript details the implementation of the OWLOOP API. A simplified (and "citable") presentation of our API has been published in the SoftwareX Elsevier journal with the title "OWLOOP: A modular API to describe OWL axioms in OOP objects hierarchies" ( https://doi.org/10.1016/j.softx.2021.100952). The OWLOOP API repository is available at https://github.com/buoncubi/owloop

Learning and Artificial Intelligence (ML/AI) techniques have become increasingly prevalent in high performance computing (HPC). However, these methods depend on vast volumes of floating point data for training and validation which need methods to share the data on a wide area network (WAN) or to transfer it from edge devices to data centers. Data compression can be a solution to these problems, but an in-depth understanding of how lossy compression affects model quality is needed. Prior work largely considers a single application or compression method. We designed a systematic methodology for evaluating data reduction techniques for ML/AI, and we use it to perform a very comprehensive evaluation with 17 data reduction methods on 7 ML/AI applications to show modern lossy compression methods can achieve a 50-100x compression ratio improvement for a 1% or less loss in quality. We identify critical insights that guide the future use and design of lossy compressors for ML/AI., Comment: 12 pages, 4 figures

Consistent range-hashing is a technique used in distributed systems, either directly or as a subroutine for consistent hashing, commonly to realize an even and stable data distribution over a variable number of resources. We introduce FlipHash, a consistent range-hashing algorithm with constant time complexity and low memory requirements. Like Jump Consistent Hash, FlipHash is intended for applications where resources can be indexed sequentially. Under this condition, it ensures that keys are hashed evenly across resources and that changing the number of resources only causes keys to be remapped from a removed resource or to an added one, but never shuffled across persisted ones. FlipHash differentiates itself with its low computational cost, achieving constant-time complexity. We show that FlipHash beats Jump Consistent Hash's cost, which is logarithmic in the number of resources, both theoretically and in experiments over practical settings., Comment: 16 pages, 3 figures, 4 tables

The "Graph pre-training and fine-tuning" paradigm has significantly improved Graph Neural Networks(GNNs) by capturing general knowledge without manual annotations for downstream tasks. However, due to the immense gap of data and tasks between the pre-training and fine-tuning stages, the model performance is still limited. Inspired by prompt fine-tuning in Natural Language Processing(NLP), many endeavors have been made to bridge the gap in graph domain. But existing methods simply reformulate the form of fine-tuning tasks to the pre-training ones. With the premise that the pre-training graphs are compatible with the fine-tuning ones, these methods typically operate in transductive setting. In order to generalize graph pre-training to inductive scenario where the fine-tuning graphs might significantly differ from pre-training ones, we propose a novel graph prompt based method called Inductive Graph Alignment Prompt(IGAP). Firstly, we unify the mainstream graph pre-training frameworks and analyze the essence of graph pre-training from graph spectral theory. Then we identify the two sources of the data gap in inductive setting: (i) graph signal gap and (ii) graph structure gap. Based on the insight of graph pre-training, we propose to bridge the graph signal gap and the graph structure gap with learnable prompts in the spectral space. A theoretical analysis ensures the effectiveness of our method. At last, we conduct extensive experiments among nodes classification and graph classification tasks under the transductive, semi-inductive and inductive settings. The results demonstrate that our proposed method can successfully bridge the data gap under different settings.

We introduce a method for computing immediately human interpretable yet accurate classifiers from tabular data. The classifiers obtained are short Boolean formulas, computed via first discretizing the original data and then using feature selection coupled with a very fast algorithm for producing the best possible Boolean classifier for the setting. We demonstrate the approach via 12 experiments, obtaining results with accuracies comparable to ones obtained via random forests, XGBoost, and existing results for the same datasets in the literature. In most cases, the accuracy of our method is in fact similar to that of the reference methods, even though the main objective of our study is the immediate interpretability of our classifiers. We also prove a new result on the probability that the classifier we obtain from real-life data corresponds to the ideally best classifier with respect to the background distribution the data comes from., Comment: Preprint of a paper in DAO-XAI 2024 (Data meets Applied Ontologies in Explainable AI)

With the rise of "Metaverse" and "Web 3.0", Non-Fungible Token (NFT) has emerged as a kind of pivotal digital asset, garnering significant attention. By the end of March 2024, more than 1.7 billion NFTs have been minted across various blockchain platforms. To effectively locate a desired NFT, conducting searches within a vast array of NFTs is essential. The challenge in NFT retrieval is heightened due to the high degree of similarity among different NFTs, regarding regional and semantic aspects. In this paper, we will introduce a benchmark dataset named "NFT Top1000 Visual-Text Dataset" (NFT1000), containing 7.56 million image-text pairs, and being collected from 1000 most famous PFP1 NFT collections2 by sales volume on the Ethereum blockchain. Based on this dataset and leveraging the CLIP series of pre-trained models as our foundation, we propose the dynamic masking fine-tuning scheme. This innovative approach results in a 7.4\% improvement in the top1 accuracy rate, while utilizing merely 13\% of the total training data (0.79 million vs. 6.1 million). We also propose a robust metric Comprehensive Variance Index (CVI) to assess the similarity and retrieval difficulty of visual-text pairs data. The dataset will be released as an open-source resource. For more details, please refer to: https://github.com/ShuxunoO/NFT-Net.git., Comment: 11 pages,12figures to be published in ACM Multimedia 2024, see https://openreview.net/forum?id=xUtNrKH8iB&noteId=xUtNrKH8iB

The random walk $d$-ary cuckoo hashing algorithm was defined by Fotakis, Pagh, Sanders, and Spirakis to generalize and improve upon the standard cuckoo hashing algorithm of Pagh and Rodler. Random walk $d$-ary cuckoo hashing has low space overhead, guaranteed fast access, and fast in practice insertion time. In this paper, we give a theoretical insertion time bound for this algorithm. More precisely, for every $d\ge 3$ hashes, let $c_d^*$ be the sharp threshold for the load factor at which a valid assignment of $cm$ objects to a hash table of size $m$ likely exists. We show that for any $d\ge 4$ hashes and load factor $c

The increasing need for causal analysis in large-scale industrial datasets necessitates the development of efficient and scalable causal algorithms for real-world applications. This paper addresses the challenge of scaling causal algorithms in the context of conducting causal analysis on extensive datasets commonly encountered in industrial settings. Our proposed solution involves enhancing the scalability of causal algorithm libraries, such as EconML, by leveraging the parallelism capabilities offered by the distributed computing framework Ray. We explore the potential of parallelizing key iterative steps within causal algorithms to significantly reduce overall runtime, supported by a case study that examines the impact on estimation times and costs. Through this approach, we aim to provide a more effective solution for implementing causal analysis in large-scale industrial applications.

Data lakes, increasingly adopted for their ability to store and analyze diverse types of data, commonly use columnar storage formats like Parquet and ORC for handling relational tables. However, these traditional setups fall short when it comes to efficiently managing graph data, particularly those conforming to the Labeled Property Graph (LPG) model. To address this gap, this paper introduces GraphAr, a specialized storage scheme designed to enhance existing data lakes for efficient graph data management. Leveraging the strengths of Parquet, GraphAr captures LPG semantics precisely and facilitates graph-specific operations such as neighbor retrieval and label filtering. Through innovative data organization, encoding, and decoding techniques, GraphAr dramatically improves performance. Our evaluations reveal that GraphAr outperforms conventional Parquet and Acero-based methods, achieving an average speedup of 4452x for neighbor retrieval, 14.8x for label filtering, and 29.5x for end-to-end workloads. These findings highlight GraphAr's potential to extend the utility of data lakes by enabling efficient graph data management.

Compared to LHC Run 1 and Run 2, future HEP experiments, e.g., at the HL-LHC, will increase the volume of generated data by an order of magnitude. In order to sustain the expected analysis throughput, ROOT's RNTuple I/O subsystem has been engineered to overcome the bottlenecks of the TTree I/O subsystem, focusing also on a compact data format, asynchronous and parallel requests, and a layered architecture that allows supporting distributed filesystem-less storage systems, e.g. HPC-oriented object stores. In a previous publication, we introduced and evaluated the RNTuple's native backend for Intel DAOS. Since its first prototype, we carried out a number of improvements both on RNTuple and its DAOS backend aiming to saturate the physical link, such as support for vector writes and an improved RNTuple-to-DAOS mapping, only to name a few. In parallel, the latest developments allow for better integration between RNTuple and ROOT's storage-agnostic, declarative interface to write HEP analyses, RDataFrame. In this work, we contribute with the following: (i) a redesign of the RNTuple DAOS backend, including a mechanism for efficient population of the object store based on existing data; and (ii) an experimental evaluation on a single-node platform, showing a significant increase in the analysis throughput for typical HEP workflows., Comment: 21st International Workshop on Advanced Computing and Analysis Techniques in Physics Research (ACAT 2022), 5 pages

The ENDF-6 format, widely used worldwide for storing and disseminating nuclear data, is managed by the Cross Sections Evaluation Working Group (CSEWG) and fully documented in the ENDF-6 formats manual. This manual employs a combination of formal and natural language, introducing the possibility of ambiguity in certain parts of the format specification. To eliminate the possibility of ambiguity, this contribution proposes a generalization of the formal language used in the ENDF-6 formats manual, which is precisely defined in extended Backus-Naur form (EBNF). This formalization also offers several other advantages, notably reducing the complexity of creating and updating parsing and validation programs for ENDF-6 formatted files. Moreover, the availability of a formal description enables the automatic mapping of the low-level ENDF-6 representation, provided by a sequence of numbers, to a more human-friendly hierarchical representation with variable names. Demonstrating these advantages, almost the entire ENDF-6 format description has been translated into the proposed formal language, accompanied by a reference implementation of a parser/translator. This implementation leverages the formal format specification to enable reading, writing, and validating ENDF-6 formatted files., Comment: 31 pages

A huge amount of information is produced in digital form. The Semantic Web stems from the realisation that dealing efficiently with this production requires getting better at interlinking digital informational resources together. Its focus is on linking data. Linking data isn't enough. We need to provide infrastructural support for linking all sorts of informational resources including resources whose understanding and fine interlinking requires domain-specific human expertise. At times when many problems scale to planetary dimensions, it is essential to scale coordination of information processing and information production, without giving up on expertise and depth of analysis, nor forcing languages and formalisms onto thinkers, decision-makers and innovators that are only suitable to some forms of intelligence. This article makes a proposal in this direction and in line with the idea of interlinking championed by the Semantic Web., Comment: Supplementary material by Guillaume Bouzige and Mathilde Noual

We introduce linear probing hashing schemes that construct a hash table of size $n$, with constant load factor $\alpha$, on which the worst-case unsuccessful search time is asymptotically almost surely $O(\log \log n)$. The schemes employ two linear probe sequences to find empty cells for the keys. Matching lower bounds on the maximum cluster size produced by any algorithm that uses two linear probe sequences are obtained as well., Comment: 31 pages, 8 figures, 5 tables, references added

Mars' thin, CO$_2$-rich atmosphere poses a unique puzzle involving composition, climate history, and habitability. This work explores the intrincate relationship between Mars' atmospheric variations and dynamic solar activity patterns. We focus on periodic oscillations in H$_2$O vapor and the Pectinton solar flux index in the $\lambda$ = 10.7 cm radio band, around the characteristic 11-year solar cycle. Periodic Mars activity was studied using data from Mars Express' SPICAM instrument spanning 2004-2018. The Lomb-Scargle Periodogram method was applied to analyze the power spectra of both signals around this period, calibrated using peaks associated with the seasonal Martian cycle. This method was validated by analyzing power spectra of chemical species abundances in Earth's atmosphere, obtained from the NRLMSISE 00 empirical model provided by the National Oceanic and Atmospheric Administration (NOAA). Model executions reproduced chemical abundance data for various atmospheric species (N$_2$, O$_2$, N, H$_2$, Ar, and He) at two reference heights (upper mesosphere and low ionosphere) over a 1961-2021 time span. Results suggest a connection between variability in H$_2$O vapor concentration in Mars' atmosphere and fluctuations in the Pectinton solar flux index. We propose the Lomb-Scargle Periodogram method as a heuristic for studying oscillatory activity in planetary atmospheres with non-uniformly sampled data. While our results provide valuable insights, further analysis, cross-referencing with data from different orbiters, is required to deepen our understanding of these findings in the fields of planetary climatology and atmospheric physics., Comment: 25 pages, 24 figures. Submitted to MNRAS

We present a technical enhancement within the p4est software for parallel adaptive mesh refinement. In p4est primitives are stored as octants in three and quadrants in two dimensions. While, classically, they are encoded by the native approach using its spatial and refinement level, any other mathematically equivalent encoding might be used instead. Recognizing this, we add two alternative representations to the classical, explicit version, based on a long monotonic index and 128-bit AVX quad integers, respectively. The first one requires changes in logic for low-level quadrant manipulating algorithms, while the other exploits data level parallelism and requires algorithms to be adapted to SIMD instructions. The resultant algorithms and data structures lead to higher performance and lesser memory usage in comparison with the standard baseline. We benchmark selected algorithms on a cluster with two Intel(R) Xeon(R) Gold 6130 Skylake family CPUs per node, which provides support for AVX2 extensions, 192 GB RAM per node, and up to 512 computational cores in total., Comment: 10 pages, 7 figures and 12 algorithms, submitted to Proceedings of the 2024 SIAM Conference on Parallel Processing for Scientific Computing (PP). For reprodusing results use branches https://github.com/cburstedde/p4est/tree/p4est-virtual and https://github.com/cburstedde/libsc/tree/feature-sc3 and executable build_dir>/example/timings/p8est3_p3time

Recursive queries and recursive derived tables constitute an important part of the SQL standard. Their efficient processing is important for many real-life applications that rely on graph or hierarchy traversal. Position-enabled column-stores offer a novel opportunity to improve run times for this type of queries. Such systems allow the engine to explicitly use data positions (row ids) inside its core and thus, enable novel efficient implementations of query plan operators. In this paper, we present an approach that significantly speeds up recursive query processing inside RDBMSes. Its core idea is to employ a particular aspect of column-store technology (late materialization) which enables the query engine to manipulate data positions during query execution. Based on it, we propose two sets of Volcano-style operators intended to process different query cases. In order validate our ideas, we have implemented the proposed approach in PosDB, an RDBMS column-store with SQL support. We experimentally demonstrate the viability of our approach by providing a comparison with PostgreSQL. Experiments show that for breadth-first search: 1) our position-based approach yields up to 6x better results than PostgreSQL, 2) our tuple-based one results in only 3x improvement when using a special rewriting technique, but it can work in a larger number of cases, and 3) both approaches can't be emulated in row-stores efficiently.

Modern computer systems are characterized by deep memory hierarchies, composed of main memory, multiple layers of cache, and other specialized types of memory. In parallel and distributed systems, additional memory layers are added to this hierarchy. Achieving good performance for computational science applications, in terms of execution time, depends on the efficient use of this diverse and hierarchical memory. This paper revisits the use of space-filling curves to specify the ordering in memory of data structures used in representative scientific applications executing on parallel machines containing clusters of multicore CPUs with attached GPUs. This work examines the hypothesis that space-filling curves, such as Hilbert and Morton ordering, can improve data locality and hence result in more efficient data movement than row or column-based orderings. First, performance results are presented that show for what application parameterizations and machine characteristics this is the case, and are interpreted in terms of how an application interacts with the computer hardware and low-level software. This research particularly focuses on the use of stencil-based applications that form the basis of many scientific computations. Second, how space-filling curves impact data sharing in nearest-neighbour and stencil-based codes is considered.

This paper investigates the employment of various encoders in text transformation, converting characters into bytes. It discusses local encoders such as ASCII and GB-2312, which encode specific characters into shorter bytes, and universal encoders like UTF-8 and UTF-16, which can encode the complete Unicode set with greater space requirements and are gaining widespread acceptance. Other encoders, including SCSU, BOCU-1, and binary encoders, however, lack self-synchronizing capabilities. Duncode is introduced as an innovative encoding method that aims to encode the entire Unicode character set with high space efficiency, akin to local encoders. It has the potential to compress multiple characters of a string into a Duncode unit using fewer bytes. Despite offering less self-synchronizing identification information, Duncode surpasses UTF8 in terms of space efficiency. The application is available at \url{https://github.com/laohur/duncode}. Additionally, we have developed a benchmark for evaluating character encoders across different languages. It encompasses 179 languages and can be accessed at \url{https://github.com/laohur/wiki2txt}.

In this work, long-term spatiotemporal changes in rainfall are analysed and evaluated using whole-year data from Rajasthan, India, at the meteorological divisional level. In order to determine how the rainfall pattern has changed over the past 10 years, I examined the data from each of the thirteen tehsils in the Jaipur district. For the years 2012 through 2021, daily rainfall information is available from the Indian Meteorological Department (IMD) in Jaipur. We primarily compare data broken down by tehsil in the Jaipur district of Rajasthan, India., Comment: 10 pages, 3 figures

Open and permissionless blockchains are distributed systems with thousands to tens of thousands of nodes, establishing novel platforms for decentralized applications. When realizing such an application, data might be stored and retrieved from one or more blockchains by distributed network nodes without relying on centralized coordination and trusted third parties. Data access could be provided through a query language such as SQL at the application level, establishing a unified view on application-level data that is verifiably stored. However, when accessing multiple blockchains through their node software and APIs, interoperability cannot be assumed today, resulting in challenges of inhomogeneous data access. In addition, different feature sets and trade-offs exist, e.g., regarding smart contract functionality, availability, distribution, scalability, and security. For increasing interoperability, the paper at hand suggests pursuing the development of a cross-chain query language at the application level. The language abstracts from implementation by providing a standardized syntax, an integrated data model, and a processing architecture for data queries. This research is an extended and updated paper of a prior publication demonstrating the language syntax, data model, and architecture with an evaluation of compatibility against the largest open and permissionless blockchains today., Comment: Version 3. Extended, updated and revised paper of the prior publication: H\"arer, Felix (2022): Towards Interoperability of Open and Permissionless Blockchains: A Cross-Chain Query Language, in: Proceedings of the 2022 IEEE International Conference on E-Business Engineering (IEEE ICEBE 2022), October 14-16, 2022, Bournemouth, UK. DOI: 10.1109/ICEBE55470.2022.00041. arXiv admin note: text overlap with arXiv:2209.07224

The practical Byzantine fault tolerant (PBFT) consensus protocol is one of the basic consensus protocols in the development of blockchain technology. At the same time, the PBFT consensus protocol forms a basis for some other important BFT consensus protocols, such as Tendermint, Streamlet, HotStuff, and LibraBFT. In general, the voting nodes may always fail so that they can leave the PBFT-based blockchain system in a random time interval, making the number of timely available voting nodes uncertain. Thus, this uncertainty leads to the analysis of the PBFT-based blockchain systems with repairable voting nodes being more challenging. In this paper, we develop a novel PBFT consensus protocol with repairable voting nodes and study such a new blockchain system using a multi-dimensional Markov process and the first passage time method. Based on this, we provide performance and reliability analysis, including throughput, availability, and reliability, for the new PBFT-based blockchain system with repairable voting nodes. Furthermore, we provide an approximate algorithm for computing the throughput of the new PBFT-based blockchain system. We employ numerical examples to demonstrate the validity of our theoretical results and illustrate how the key system parameters influence performance measures of the PBFT-based blockchain system with repairable voting nodes. We hope the methodology and results developed in this paper will stimulate future research endeavors and open up new research trajectories in this field., Comment: 55 pages, 17 figures

In database design, Composite Keys are used to uniquely identify records and prevent data duplication. However, they require more memory and storage space than single keys, and can make queries more CPU-intensive. Surrogate Keys are an alternative that can overcome some of these limitations, but they can also introduce new disadvantages. To address these challenges, a new type of key called a Reversible Numeric Composite Key (RNCK) has been developed. RNCK is a single number that encodes multiple data attributes, and can be decoded back to the original values. This makes it possible to achieve the benefits of both Composite Keys and Surrogate Keys, while overcoming some of their limitations. RNCK has been shown to improve query performance and reduce memory and storage requirements. It can be used in relational databases, large static datasets, and key-value caching systems. RNCK has been successfully used in production systems for several years., Comment: 5 pages

We propose an axiomatic foundation of mathematics based on the finite sequence as the foundational concept, rather than based on logic and set, as in set theory, or based on type as in dependent type theories. Finite sequences lead to a concept of pure data, which is used to represent all mathematical objects. As an axiomatic system, the foundation has only one axiom which defines what constitutes a valid definition. Using the axiom, an internal true/false/undecided valued logic and an internal language are defined, making logic and language-related axioms unnecessary. Valid proof and valid computation are defined in terms of equality of pure data. An algebra of pure data leads to a rich theory of spaces and morphisms which play a role similar to the role of Category Theory in modern Mathematics. As applications, we explore Mathematical Machine Learning, the consistency of Mathematics and address paradoxes due to Godel, Berry, Curry and Yablo., Comment: 14 pages

In column-oriented query processing, a materialization strategy determines when lightweight positions (row IDs) are translated into tuples. It is an important part of column-store architecture, since it defines the class of supported query plans, and, therefore, impacts the overall system performance. In this paper we continue investigating materialization strategies for a distributed disk-based column-store. We start with demonstrating cases when existing approaches impose fundamental limitations on the resulting system performance. Then, in order to address them, we propose a new hybrid materialization model. The main feature of hybrid materialization is the ability to manipulate both positions and values at the same time. This way, query engine can flexibly combine advantages of all the existing strategies and support a new class of query plans. Moreover, hybrid materialization allows the query engine to flexibly customize the materialization policy of individual attributes. We describe our vision of how hybrid materialization can be implemented in a columnar system. As an example, we use PosDB~ -- a distributed, disk-based column-store. We present necessary data structures, the internals of a hybrid operator, and describe the algebra of such operators. Based on this implementation, we evaluate performance of late, ultra-late, and hybrid materialization strategies in several scenarios based on TPC-H queries. Our experiments demonstrate that hybrid materialization is almost two times faster than its counterparts, while providing a more flexible query model.

Exponential growth in the amount of data generated by the Internet of Things currently pose significant challenges for data communication, storage and analytics and leads to high costs for organisations hoping to leverage their data. Novel techniques are therefore needed to holistically improve the efficiency of data storage and analytics in IoT systems. The emerging compression technique Generalized Deduplication (GD) has been shown to deliver high compression and enable direct compressed data analytics with low storage and memory requirements. In this paper, we propose a new GD-based data compression algorithm called GreedyGD that is designed for analytics. Compared to existing versions of GD, GreedyGD enables more reliable analytics with less data, while running 11.2x faster and delivering even better compression.

Decentralized applications rely on non-centralized technical infrastructures and coordination principles. Without trusted third parties, their execution is not controlled by entities exercising centralized coordination but is instead realized through technologies supporting distribution such as blockchains and serverless computing. Executing decentralized applications with these technologies, however, is challenging due to the limited transparency and insight in the execution, especially when involving centralized cloud platforms. This paper extends an approach for execution and instance tracking on blockchains and cloud platforms permitting distributed parties to observe the instances and states of executable models. The approach is extended with (1.) a metamodel describing the concepts for instance tracking on cloud platforms independent of concrete models or implementation, (2.) a multidimensional data model realizing the concepts accordingly, permitting the verifiable storage, tracking, and analysis of execution states for distributed parties, and (3.) an implementation on the Ethereum blockchain and Amazon Web Services (AWS) using state machine models. Towards supporting decentralized applications with high scalability and distribution requirements, the approach establishes a consistent view on instances for distributed parties to track and analyze the execution along multiple dimensions such as specific clients and execution engines., Comment: This is an unpublished preprint; both versions archived on arXiv.org have not been published. Although initially intended for publication, the preprint has undergone further improvements and has been utilized as input for new publications. (see also: https://www.unifr.ch/inf/digits/en/group/team/haerer.html)

In a democratic setting, we introduce a commitment scheme which allows for transparent validation of transfers and reversible delegations of voting power between citizens without sacrificing their privacy. A unit of voting power is publicly represented by the Merkle root of a tree consisting of its latest owner's public key, a random nonce and the Merkle root of the tree of its previous owner's public key and random nonce and so on. A transition includes the input units, their owner's public keys and signatures, the hashes of their nonces and the output units generated with the new owners' public keys and random nonces. In case of a delegation, the receiver provides the sender with the hashed random nonces and hashed public keys for the output units. In case of a transfer, only the precomputed output units are provided by the receiver. In a reversal, a historical owner reveals the hashes of the nonces and public keys that resulted in the subsequent units. To vote, the owner reveals the actual nonces and public keys., Comment: 11 pages, 2 figures

This paper describes a novel Python package, named causalgraph, for modeling and saving causal graphs embedded in knowledge graphs. The package has been designed to provide an interface between causal disciplines such as causal discovery and causal inference. With this package, users can create and save causal graphs and export the generated graphs for use in other graph-based packages. The main advantage of the proposed package is its ability to facilitate the linking of additional information and metadata to causal structures. In addition, the package offers a variety of functions for graph modeling and plotting, such as editing, adding, and deleting nodes and edges. It is also compatible with widely used graph data science libraries such as NetworkX and Tigramite and incorporates a specially developed causalgraph ontology in the background. This paper provides an overview of the package's main features, functionality, and usage examples, enabling the reader to use the package effectively in practice.

In this article we present the effects of our work on the subject of the technical approach to the 3D point cloud data analysis through the use of the Octree method to compress, analyse and compute the initial data., Comment: 6 pages, 12 figures, 7 citations

With rapid development of blockchain technology as well as integration of various application areas, performance evaluation, performance optimization, and dynamic decision in blockchain systems are playing an increasingly important role in developing new blockchain technology. This paper provides a recent systematic overview of this class of research, and especially, developing mathematical modeling and basic theory of blockchain systems. Important examples include (a) performance evaluation: Markov processes, queuing theory, Markov reward processes, random walks, fluid and diffusion approximations, and martingale theory; (b) performance optimization: Linear programming, nonlinear programming, integer programming, and multi-objective programming; (c) optimal control and dynamic decision: Markov decision processes, and stochastic optimal control; and (d) artificial intelligence: Machine learning, deep reinforcement learning, and federated learning. So far, a little research has focused on these research lines. We believe that the basic theory with mathematical methods, algorithms and simulations of blockchain systems discussed in this paper will strongly support future development and continuous innovation of blockchain technology., Comment: 42 pages, 9 figures

A \emph{resizable array} is an array that can \emph{grow} and \emph{shrink} by the addition or removal of items from its end, or both its ends, while still supporting constant-time \emph{access} to each item stored in the array given its \emph{index}. Since the size of an array, i.e., the number of items in it, varies over time, space-efficient maintenance of a resizable array requires dynamic memory management. A standard doubling technique allows the maintenance of an array of size~$N$ using only $O(N)$ space, with $O(1)$ amortized time, or even $O(1)$ worst-case time, per operation. Sitarski and Brodnik et al.\ describe much better solutions that maintain a resizable array of size~$N$ using only $N+O(\sqrt{N})$ space, still with $O(1)$ time per operation. Brodnik et al.\ give a simple proof that this is best possible. We distinguish between the space needed for \emph{storing} a resizable array, and accessing its items, and the \emph{temporary} space that may be needed while growing or shrinking the array. For every integer $r\ge 2$, we show that $N+O(N^{1/r})$ space is sufficient for storing and accessing an array of size~$N$, if $N+O(N^{1-1/r})$ space can be used briefly during grow and shrink operations. Accessing an item by index takes $O(1)$ worst-case time while grow and shrink operations take $O(r)$ amortized time. Using an exact analysis of a \emph{growth game}, we show that for any data structure from a wide class of data structures that uses only $N+O(N^{1/r})$ space to store the array, the amortized cost of grow is $\Omega(r)$, even if only grow and access operations are allowed. The time for grow and shrink operations cannot be made worst-case, unless $r=2$., Comment: Preliminary version appeared in SOSA 2023. Section 6.3 revised

The execution of decentralized applications on blockchains is limited today by technical and organizational barriers, including scalability and the high complexity to specify execution correctly for developers as well as for domain experts in organizations. Overcoming these limitations could allow for decentralized coordination beyond data, where distributed parties rely on higher-level abstractions for coordinating their actions using decentralized applications, not limited to organizations. Towards this goal, the paper at hand proposes executable models as high-level abstraction that can be observed and tracked by distributed parties. In particular, it is investigated how executable models on cloud platforms can be coupled with smart contracts for tracking their execution, concluding with an architecture as exploratory research result towards supporting scalability and decentralized coordination., Comment: Submission for PoEM'2022 Workshops and Models at Work Papers, November 23-25, 2022, London, UK

In a practical Byzantine fault tolerance (PBFT) blockchain network, the voting nodes may always leave the network while some new nodes can also enter the network, thus the number of voting nodes is constantly changing. Such a new PBFT with dynamic nodes is called a dynamic PBFT. Clearly, the dynamic PBFT can more strongly support the decentralization and distributed structure of blockchain. However, analyzing dynamic PBFT blockchain systems will become more interesting and challenging. In this paper, we propose a large-scale Markov modeling technique to analyze the dynamic PBFT voting processes and its dynamic PBFT blockchain system. To this end, we set up a large-scale Markov process (and further a multi-dimensional Quasi-Birth-and-Death (QBD) process) and provide performance analysis for both the dynamic PBFT voting processes and the dynamic PBFT blockchain system. In particular, we obtain an effective computational method for the throughput of the complicated dynamic PBFT blockchain system. Finally, we use numerical examples to check the validity of our theoretical results and indicate how some key system parameters influence the performance measures of the dynamic PBFT voting processes and of the dynamic PBFT blockchain system. Therefore, by using the theory of multi-dimensional QBD processes and the RG-factorization technique, we hope that the methodology and results developed in this paper shed light on the study of dynamic PBFT blockchain systems such that a series of promising research can be developed potentially., Comment: 46 pages, 13 figures

Many distributed applications implement complex data flows and need a flexible mechanism for routing data between producers and consumers. Recent advances in programmable network interface cards, or SmartNICs, represent an opportunity to offload data-flow tasks into the network fabric, thereby freeing the hosts to perform other work. System architects in this space face multiple questions about the best way to leverage SmartNICs as processing elements in data flows. In this paper, we advocate the use of Apache Arrow as a foundation for implementing data-flow tasks on SmartNICs. We report on our experiences adapting a partitioning algorithm for particle data to Apache Arrow and measure the on-card processing performance for the BlueField-2 SmartNIC. Our experiments confirm that the BlueField-2's (de)compression hardware can have a significant impact on in-transit workflows where data must be unpacked, processed, and repacked., Comment: This is an expansion of the paper with the same name published in HPEC'22

The rise of open and permissionless blockchains has introduced novel platforms for applications based on distributed data storage. At the application and business levels, long-established query languages such as SQL provide interoperability that can be complemented by blockchain-based data storage today, enabling permissionless and verifiable data storage along with decentralized execution across tens of thousands of nodes. However, when accessing one or more blockchains, interoperability is not provided today, posing challenges such as inhomogeneous data access in addition to different features and trade-offs, e.g. in data and distribution, scalability, and security. Towards interoperability in data access among the increasing number of blockchain platforms, this paper introduces a cross-chain query language for data access across blockchains. Similar to SQL, the language abstracts from implementation based on a data model compatible with the largest open and permissionless blockchains (OPB) today. The language, data model, and processing architecture are demonstrated and evaluated with an implemented prototype, aiming to contribute to the discussion on blockchain interoperability among OPB.

Note that the serial structure of blockchain has many essential pitfalls, thus a data network structure and its DAG-based blockchain are introduced to resolve the blockchain pitfalls. From such a network perspective, analysis of the DAG-based blockchain systems becomes interesting and challenging. So, the simulation models are adopted widely. In this paper, we first describe a simple Markov model for the DAG-based blockchain with IOTA Tangle by means of two layers of tips and internal tips' impatient connection behavior. Then we set up a continuous-time Markov process to analyze the DAG-based blockchain system and show that this Markov process is a level-dependent quasi-birth-and-death (QBD) process. Based on this, we prove that the QBD process must be irreducible and positive recurrent. Furthermore, once the stationary probability vector of the QBD process is given, we provide performance analysis of the DAG-based blockchain system. Next, we propose a new effective method for computing the average confirmation time of any arriving internal tip at this system by means of the first passage times and the PH distributions. Finally, we use numerical examples to check the validity of our theoretical results and indicate how some key system parameters influence the performance measures of this system. Therefore, we hope that the methodology and results developed in this paper can be applicable to deal with more general DAG-based blockchain systems such that a series of promising research can be developed potentially., Comment: 49 pages, 9 figures

The most pressing problems in science are neither empirical nor theoretical, but infrastructural. Scientific practice is defined by coproductive, mutually reinforcing infrastructural deficits and incentive systems that everywhere constrain and contort our art of curiosity in service of profit and prestige. Our infrastructural problems are not unique to science, but reflective of the broader logic of digital enclosure where platformatized control of information production and extraction fuels some of the largest corporations in the world. I have taken lessons learned from decades of intertwined digital cultures within and beyond academia like wikis, pirates, and librarians in order to draft a path towards more liberatory infrastructures for both science and society. Based on a system of peer-to-peer linked data, I sketch interoperable systems for shared data, tools, and knowledge that map onto three domains of platform capture: storage, computation and communication. The challenge of infrastructure is not solely technical, but also social and cultural, and so I attempt to ground a practical development blueprint in an ethics for organizing and maintaining it. I intend this draft as a rallying call for organization, to be revised with the input of collaborators and through the challenges posed by its implementation. I argue that a more liberatory future for science is neither utopian nor impractical -- the truly impractical choice is to continue to organize science as prestige fiefdoms resting on a pyramid scheme of underpaid labor, playing out the clock as every part of our work is swallowed whole by circling information conglomerates. It was arguably scientists looking for a better way to communicate that created something as radical as the internet in the first place, and I believe we can do it again., Comment: Original Web Document: https://jon-e.net/infrastructure

The pairing heap is a simple "self-adjusting" implementation of a heap (priority queue). Inserting an item into a pairing heap or decreasing the key of an item takes O(1) time worst-case, as does melding two heaps. But deleting an item of minimum key can take time linear in the heap size in the worst case. The paper that introduced the pairing heap proved an O(log n) amortized time bound for each heap operation, where n is the number of items in the heap or heaps involved in the operation, by charging all but O(log n) of the time for each deletion to non-deletion operations, O(log n) to each. Later Iacono found a way to reduce the amortized time per insertion to O(1) and that of meld to zero while preserving the O(log n) amortized time bound for the other update operations. We give a simpler proof of Iacono's result with significantly smaller constant factors. Our analysis uses the natural representation of pairing heaps instead of the conversion to a binary tree used in the original analysis and in Iacono's., Comment: 13 pages, 1 figure, submitted to SOSA 2023

Given a directed graph, G=(V,E), a path query, path(u,v), returns whether there is a directed path from u to v in G, for u,v vertices in V. Given only V, exactly learning all the edges in G using path queries is often impossible, since path queries cannot detect transitive edges. In this paper, we study the query complexity of exact learning for cases when learning G is possible using path queries. In particular, we provide efficient learning algorithms, as well as lower bounds, for multitrees and almost-trees, including butterfly networks.

This article describes the features of a compiler for a superset language of the well-known PL/0 created by Niklaus Wirth. The main feature is that it implements the build phases in such a way that the information passed between each one is reflected as an XML file., Comment: in Spanish language. Presented at "Congreso de Electr\'onica e Inform\'atica 2010", Universidad Centroamericana "Jos\'e Sime\'on Ca\~nas"