Search

The past two decades have witnessed columnar storage revolutionizing data warehousing and analytics. However, the rapid growth of machine learning poses new challenges to this domain. This paper presents Bullion, a columnar storage system tailored for machine learning workloads. Bullion addresses the complexities of data compliance, optimizes the encoding of long sequence sparse features, efficiently manages wide-table projections, and introduces feature quantization in storage. By aligning with the evolving requirements of ML applications, Bullion extends columnar storage to various scenarios, from advertising and recommendation systems to the expanding realm of Generative AI. Preliminary experimental results and theoretical analysis demonstrate Bullion's superior performance in handling the unique demands of machine learning workloads compared to existing columnar storage solutions. Bullion significantly reduces I/O costs for deletion compliance, achieves substantial storage savings with its optimized encoding scheme for sparse features, and drastically improves metadata parsing speed for wide-table projections. These advancements position Bullion as a critical component in the future of machine learning infrastructure, enabling organizations to efficiently manage and process the massive volumes of data required for training and inference in modern AI applications.

The ubiquity of variable-length integers in data storage and communication necessitates efficient decoding techniques. In this paper, we present SFVInt, a simple and fast approach to decode the prevalent Little Endian Base-128 (LEB128) varints. Our approach effectively utilizes the Bit Manipulation Instruction Set 2 (BMI2) in modern Intel and AMD processors, achieving significant performance improvement while maintaining simplicity and avoiding overengineering. SFVInt, with its generic design, effectively processes both 32-bit and 64-bit unsigned integers using a unified code template, marking a significant leap forward in varint decoding efficiency. We thoroughly evaluate SFVInt's performance across various datasets and scenarios, demonstrating that it achieves up to a 2x increase in decoding speed when compared to varint decoding methods used in established frameworks like Facebook Folly and Google Protobuf., Comment: DaMoN 2024

Existing serverless data analytics systems rely on external storage services like S3 for data shuffling and communication between cloud functions. While this approach provides the elasticity benefits of serverless computing, it incurs additional latency and cost overheads. We present Flock, a novel cloud-native streaming query engine that leverages the on-demand scalability of FaaS platforms for real-time data analytics. Flock utilizes function invocation payloads for efficient data exchange, eliminating the need for external storage. This not only reduces latency and cost but also simplifies the architecture by removing the requirement for a centralized coordinator. Flock employs a template-based approach to dynamically create cloud functions for each query stage and a function group mechanism for handling data aggregation and shuffling. It supports both SQL and DataFrame APIs, making it easy to use. Our evaluation shows that Flock provides significant performance gains and cost savings compared to existing serverless and serverful streaming systems. It outperforms Apache Flink by 10-20x in cost while achieving similar latency and throughput.

In this paper we investigate the Margulis-Ruelle inequality for general Riemannian manifolds (possibly noncompact and with boundary) and show that it always holds under integrable condition.

We prove that every $\mathcal{C}^{r}$ diffeomorphism with $r>1$ on a three-dimensional manifold admits symbolic extensions, i.e. topological extensions which are subshifts over a finite alphabet. This answers positively a conjecture of Downarowicz and Newhouse in dimension three.

The folding entropy is a quantity originally proposed by Ruelle in 1996 during the study of entropy production in the non-equilibrium statistical mechanics. As derived through a limiting process to the non-equilibrium steady state, the continuity of entropy production plays a key role in its physical interpretations. In this paper, we study the continuity of folding entropy for a general (non-invertible) differentiable dynamical system with degeneracy. By introducing a notion called degenerate rate, we prove that on any subset of measures with uniform degenerate rate, the folding entropy, and hence the entropy production, is upper semi-continuous. This extends the upper semi-continuity result from endomorphisms to all $C^r(r>1)$ maps. We further apply in the one-dimensional setting. In achieving this, an equality between the folding entropy and (Kolmogorov-Sinai) metric entropy, as well as a general dimension formula are established. These admit their own interests. The upper semi-continuity of metric entropy and dimension are then valid when measures with uniform degenerate rate are considered. Moreover, the sharpness of uniform degenerate rate is also investigated by examples in the scope of positive metric (or folding) entropy., Comment: 25 pages

For differentiable dynamical systems with dominated splittings, we give upper estimates on the measure-theoretic tail entropy in terms of Lyapunov exponents. As our primary application, we verify the upper semi-continuity of metric entropy in various settings with domination.

We prove that entropy map is upper semi-continuous for C1 nonuniformly hyperbolic systems with domination, while it is not true for C1+alpha nonuniformly hyperbolic systems in general. This goes a little against a common intuition that conclusions are parallel between C1+domination systems and C1+alpha systems., Comment: 15 pages, 2 figures

We study the rate of convergence to zero of the tail entropy of $C^\infty$ maps. We give an upper bound of this rate in terms of the growth in $k$ of the derivative of order $k$ and give examples showing the optimality of the established rate of convergence. We also consider the case of multimodal maps of the interval. Finally we prove that homoclinic tangencies give rise to $C^r$ $(r\geq 2)$ robustly non $h$-expansive dynamical systems.

Let $M$ be a compact real analytic manifold of finite dimension. There is a function $a: (0,+\infty)\to [0,+\infty)$ with $\lim_{t\to0}a(t)=0$ such that, the tail entropy $h^{*}(f,\varepsilon)$ of any real analytic map $f$ on $M$ is uniformly bounded above by the scale $a(\varepsilon)$.

In this paper, a contrastive evaluation of massively parallel implementations of suffix tree and suffix array to accelerate genome sequence matching are proposed based on Intel Core i7 3770K quad-core and NVIDIA GeForce GTX680 GPU. Besides suffix array only held approximately 20%~30% of the space relative to suffix tree, the coalesced binary search and tile optimization make suffix array clearly outperform suffix tree using GPU. Consequently, the experimental results show that multiple genome sequence matching based on suffix array is more than 99 times speedup than that of CPU serial implementation. There is no doubt that massively parallel matching algorithm based on suffix array is an efficient approach to high-performance bioinformatics applications., Comment: The 2013 International Conference on High Performance Computing & Simulation (ACM/IEEE HPCS 2013)

In this paper, we focus on the need for two approaches to optimize producer and consumer synchronization for auto-parallelizing compiler. Emphasis is placed on the construction of a criterion model by which the compiler reduce the number of synchronization operations needed to synchronize the dependence in a loop and perform optimization reduces the overhead of enforcing all dependence. In accordance with our study, we transform to modify and eliminate dependence on iteration space diagram (ISD), and carry out the problems of acyclic and cyclic dependence in detail. we eliminate partial dependence and optimize the synchronize instructions. Some didactic examples are included to illustrate the optimize procedure.

In this computer era of rapid development, software development can be seen everywhere, but a lot of softwares are dead in modern development of software. Just as The Mythical Man-Month said, it exists a problem in the software development, and the problem is interflow.A lock of interflow can be said great calamity. Clustering is a environment to breed new life. In this thesis, we elaborate how P2N can be used to thinking, planning, developing, collaborating, releasing. And the approach that make your team and organization more perfect.

Software design is gradually becoming open, distributed, pervasive, and connected. It is a sad statistical fact that software projects are scientifically fragile and tend to fail more than other engineering fields. Agile development is a philosophy. And agile methods are processes that support the agile philosophy. XP places a strong emphasis on technical practices in addition to the more common teamwork and structural practices. In this paper, we elaborate how XP practices can be used to thinking, collaborating, releasing, planning, developing. And the state that make your team and organization more successful., Comment: 15 pages,6 figures

In this article, hybrid parallel bidirectional sieve method is implemented by SMP Cluster, the individual computational units joined together by the communication network, are usually shared-memory systems with one or more multicore processor. To high-efficiency optimization, we propose average divide data into nodes, generating double-ended queues (deque) for sieve method that are able to exploit dual-cores simultaneously start sifting out primes from the head and tail.And each node create a FIFO queue as dynamic data buffer to ache temporary data from another nodes send to. The approach obtains huge speedup and efficiency on SMP Cluster., Comment: 11 pages,7 figures

We prove that the Oseledets splittings of an ergodic hyperbolic measure of a $C^{1+ r}$ diffeomorphism can be approximated by that of atomic measures on hyperbolic periodic orbits. This removes the assumption on simple spectrum in \cite{Liang} and strengthens Katok's closing lemma., Comment: 10 pages

Given any $K>0$, we construct two equivalent $C^2$ flows, one of which has positive topological entropy larger than $K$ and admits zero as the exponential growth of periodic orbits, in contrast, the other has zero topological entropy and super-exponential growth of periodic orbits. Moreover we establish a $C^{\infty}$ flow on $\mathbb{S}^2$ with super-exponential growth of periodic orbits, which is also equivalent to another flow with zero exponential growth of periodic orbits. On the other hand, any two dimensional flow has only zero topological entropy., Comment: 23 pages

In this paper we prove that for an ergodic hyperbolic measure $\omega$ of a $C^{1+\alpha}$ diffeomorphism $f$ on a Riemannian manifold $M$, there is an $\omega$-full measured set $\widetilde{\Lambda}$ such that for every invariant probability $\mu\in \mathcal{M}_{inv}(\widetilde{\Lambda},f)$, the metric entropy of $\mu$ is equal to the topological entropy of saturated set $G_{\mu}$ consisting of generic points of $\mu$: $$h_\mu(f)=h_{\top}(f,G_{\mu}).$$ Moreover, for every nonempty, compact and connected subset $K$ of $\mathcal{M}_{inv}(\widetilde{\Lambda},f)$ with the same hyperbolic rate, we compute the topological entropy of saturated set $G_K$ of $K$ by the following equality: $$\inf\{h_\mu(f)\mid \mu\in K\}=h_{\top}(f,G_K).$$ In particular these results can be applied (i) to the nonuniformy hyperbolic diffeomorphisms described by Katok, (ii) to the robustly transitive partially hyperbolic diffeomorphisms described by ~Ma{\~{n}}{\'{e}}, (iii) to the robustly transitive non-partially hyperbolic diffeomorphisms described by Bonatti-Viana. In all these cases $\mathcal{M}_{inv}(\widetilde{\Lambda},f)$ contains an open subset of $\mathcal{M}_{erg}(M,f)$., Comment: Transactions of the American Mathematical Society, to appear,see http://www.ams.org/journals/tran/0000-000-00/S0002-9947-2016-06780-X/