OpenRaiser/Intern-Atlas huggingface dataset:
A gauge-invariant reversible cellular automaton
Venue: arXiv cs.FL 2018
Year: 2018

Gauge-invariance is a fundamental concept in physics---known to provide the mathematical justification for all four fundamental forces. In this paper, we provide discrete counterparts to the main gauge theoretical concepts, directly in terms of Cellular Automata. More precisely, we describe a step-by-step gauging procedure to enforce local symmetries upon a given Cellular Automaton. We apply it to a simple Reversible Cellular Automaton for concreteness. From a Computer Science perspective, discretized gauge theories may be applied to numerical analysis, quantum simulation, fault-tolerant (quantum) computation. From a mathematical perspective, discreteness provides a simple yet rigorous route straight to the core concepts.
RStore: A Distributed Multi-version Document Store
Venue: arXiv cs.DB 2018
Year: 2018

We address the problem of compactly storing a large number of versions (snapshots) of a collection of keyed documents or records in a distributed environment, while efficiently answering a variety of retrieval queries over those, including retrieving full or partial versions, and evolution histories for specific keys. We motivate the increasing need for such a system in a variety of application domains, carefully explore the design space for building such a system and the various storage-computation-retrieval trade-offs, and discuss how different storage layouts influence those trade-offs. We propose a novel system architecture that satisfies the key desiderata for such a system, and offers simple tuning knobs that allow adapting to a specific data and query workload. Our system is intended to act as a layer on top of a distributed key-value store that houses the raw data as well as any indexes. We design novel off-line storage layout algorithms for efficiently partitioning the data to minimize the storage costs while keeping the retrieval costs low. We also present an online algorithm to handle new versions being added to system. Using extensive experiments on large datasets, we demonstrate that our system operates at the scale required in most practical scenarios and often outperforms standard baselines, including a delta-based storage engine, by orders-of-magnitude.
Medical Volume Reconstruction Techniques
Venue: arXiv cs.GR 2018
Year: 2018

Medical visualization is the use of computers to create 3D images from medical imaging data sets, almost all surgery and cancer treatment in the developed world relies on it.Volume visualization techniques includes iso-surface visualization, mesh visualization and point cloud visualization techniques, these techniques have revolutionized medicine. Much of modern medicine relies on the 3D imaging that is possible with magnetic resonance imaging (MRI) scanners, functional magnetic resonance imaging (fMRI)scanners, positron emission tomography (PET) scanners, ultrasound imaging (US) scanners, X-Ray scanners, bio-marker microscopy imaging scanners and computed tomography (CT) scanners, which make 3D images out of 2D slices. The primary goal of this report is the application-oriented optimization of existing volume rendering methods providing interactive frame rates. Techniques are presented for traditional alpha-blending rendering, surface-shaded display, maximum intensity projection (MIP), and fast previewing with fully interactive parameter control. Different preprocessing strategies are proposed for interactive iso-surface rendering and fast previewing, such as the well-known marching cube algorithm.
Lossless Image Compression Algorithm for Wireless Capsule Endoscopy by Content-Based Classification of Image Blocks
Venue: arXiv cs.CV 2018
Year: 2018

Recent advances in capsule endoscopy systems have introduced new methods and capabilities. The capsule endoscopy system, by observing the entire digestive tract, has significantly improved diagnosing gastrointestinal disorders and diseases. The system has challenges such as the need to enhance the quality of the transmitted images, low frame rates of transmission, and battery lifetime that need to be addressed. One of the important parts of a capsule endoscopy system is the image compression unit. Better compression of images increases the frame rate and hence improves the diagnosis process. In this paper a high precision compression algorithm with high compression ratio is proposed. In this algorithm we use the similarity between frames to compress the data more efficiently.
Optimal Multi-User Scheduling of Buffer-Aided Relay Systems
Venue: arXiv cs.IT 2018
Year: 2018

Multi-User scheduling is a challenging problem under the relaying scenarios. Traditional schemes, which are based on the instantaneous signal-to-interference-plus-noises ratios (SINRs), cannot solve the inherent disparities of the qualities between different links. Hence, the system performance is always limited by the weaker links. In this paper, from the whole system throughput view, we propose an optimal multi-user scheduling scheme for the multi-user full-duplex (FD) buffer aided relay systems. We first formulate the throughput maximization problem. Then, according to the characteristics of the Karush-Kuhn-Tucker conditions, we obtain the optimal decision functions and the optimal weighted factors of different links of the proposed scheme. Simulation results show that the proposed scheme not only solves the disparities of the qualities between $S_i$-$R$ and $R$-$D_i$ links, but also that between different $S_{i}$-$R$ or $D_{i}$-$R$ links, which can be used as guidance in the design of the practical systems.
Comparative study of finite element methods using the Time-Accuracy-Size (TAS) spectrum analysis
Venue: arXiv cs.MS 2018
Year: 2018

We present a performance analysis appropriate for comparing algorithms using different numerical discretizations. By taking into account the total time-to-solution, numerical accuracy with respect to an error norm, and the computation rate, a cost-benefit analysis can be performed to determine which algorithm and discretization are particularly suited for an application. This work extends the performance spectrum model in Chang et. al. 2017 for interpretation of hardware and algorithmic tradeoffs in numerical PDE simulation. As a proof-of-concept, popular finite element software packages are used to illustrate this analysis for Poisson's equation.
An Affordable Bio-Sensing and Activity Tagging Platform for HCI Research
Venue: arXiv cs.HC 2018
Year: 2018

We present a novel multi-modal bio-sensing platform capable of integrating multiple data streams for use in real-time applications. The system is composed of a central compute module and a companion headset. The compute node collects, time-stamps and transmits the data while also providing an interface for a wide range of sensors including electroencephalogram, photoplethysmogram, electrocardiogram, and eye gaze among others. The companion headset contains the gaze tracking cameras. By integrating many of the measurements systems into an accessible package, we are able to explore previously unanswerable questions ranging from open-environment interactions to emotional response studies. Though some of the integrated sensors are designed from the ground-up to fit into a compact form factor, we validate the accuracy of the sensors and find that they perform similarly to, and in some cases better than, alternatives.
RT-DAP: A Real-Time Data Analytics Platform for Large-scale Industrial Process Monitoring and Control
Venue: arXiv cs.NI 2018
Year: 2018

In most process control systems nowadays, process measurements are periodically collected and archived in historians. Analytics applications process the data, and provide results offline or in a time period that is considerably slow in comparison to the performance of the manufacturing process. Along with the proliferation of Internet-of-Things (IoT) and the introduction of "pervasive sensors" technology in process industries, increasing number of sensors and actuators are installed in process plants for pervasive sensing and control, and the volume of produced process data is growing exponentially. To digest these data and meet the ever-growing requirements to increase production efficiency and improve product quality, there needs to be a way to both improve the performance of the analytics system and scale the system to closely monitor a much larger set of plant resources. In this paper, we present a real-time data analytics platform, called RT-DAP, to support large-scale continuous data analytics in process industries. RT-DAP is designed to be able to stream, store, process and visualize a large volume of realtime data flows collected from heterogeneous plant resources, and feedback to the control system and operators in a realtime manner. A prototype of the platform is implemented on Microsoft Azure. Our extensive experiments validate the design methodologies of RT-DAP and demonstrate its efficiency in both component and system levels.
Video Person Re-identification by Temporal Residual Learning
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we propose a novel feature learning framework for video person re-identification (re-ID). The proposed framework largely aims to exploit the adequate temporal information of video sequences and tackle the poor spatial alignment of moving pedestrians. More specifically, for exploiting the temporal information, we design a temporal residual learning (TRL) module to simultaneously extract the generic and specific features of consecutive frames. The TRL module is equipped with two bi-directional LSTM (BiLSTM), which are respectively responsible to describe a moving person in different aspects, providing complementary information for better feature representations. To deal with the poor spatial alignment in video re-ID datasets, we propose a spatial-temporal transformer network (ST^2N) module. Transformation parameters in the ST^2N module are learned by leveraging the high-level semantic information of the current frame as well as the temporal context knowledge from other frames. The proposed ST^2N module with less learnable parameters allows effective person alignments under significant appearance changes. Extensive experimental results on the large-scale MARS, PRID2011, ILIDS-VID and SDU-VID datasets demonstrate that the proposed method achieves consistently superior performance and outperforms most of the very recent state-of-the-art methods.
Two theorems on distribution of Gaussian quadratic forms
Venue: arXiv cs.IT 2018
Year: 2018

New results on comparison of distributions of Gaussian quadratic forms are presented
The Clever Shopper Problem
Venue: arXiv cs.DS 2018
Year: 2018

We investigate a variant of the so-called "Internet Shopping Problem" introduced by Blazewicz et al. (2010), where a customer wants to buy a list of products at the lowest possible total cost from shops which offer discounts when purchases exceed a certain threshold. Although the problem is NP-hard, we provide exact algorithms for several cases, e.g. when each shop sells only two items, and an FPT algorithm for the number of items, or for the number of shops when all prices are equal. We complement each result with hardness proofs in order to draw a tight boundary between tractable and intractable cases. Finally, we give an approximation algorithm and hardness results for the problem of maximising the sum of discounts.
Generating High-Quality Query Suggestion Candidates for Task-Based Search
Venue: arXiv cs.IR 2018
Year: 2018

We address the task of generating query suggestions for task-based search. The current state of the art relies heavily on suggestions provided by a major search engine. In this paper, we solve the task without reliance on search engines. Specifically, we focus on the first step of a two-stage pipeline approach, which is dedicated to the generation of query suggestion candidates. We present three methods for generating candidate suggestions and apply them on multiple information sources. Using a purpose-built test collection, we find that these methods are able to generate high-quality suggestion candidates.
Employment of Multiple Algorithms for Optimal Path-based Test Selection Strategy
Venue: arXiv cs.SE 2018
Year: 2018

Executing various sequences of system functions in a system under test represents one of the primary techniques in software testing. The natural way to create effective, consistent and efficient test sequences is to model the system under test and employ an algorithm to generate the tests that satisfy a defined test coverage criterion. Several criteria of test set optimality can be defined. In addition, to optimize the test set from an economic viewpoint, the priorities of the various parts of the system model under test must be defined. Using this prioritization, the test cases exercise the high priority parts of the system under test more intensely than those with low priority. Evidence from the literature and our observations confirm that finding a universal algorithm that produces an optimal test set for all test coverage and test set optimality criteria is a challenging task. Moreover, for different individual problem instances, different algorithms provide optimal results. In this paper, we present a path-based strategy to perform optimal test selection. The strategy first employs a set of current algorithms to generate test sets; then, it assesses the optimality of each test set by the selected criteria, and finally, chooses the optimal test set. The experimental results confirm the validity and usefulness of this strategy. For individual instances of 50 system under test models, different algorithms provided optimal results; these results varied by the required test coverage level, the size of the priority parts of the model, and the selected test set optimality criteria.
Finding Top-k Optimal Sequenced Routes -- Full Version
Venue: arXiv cs.DB 2018
Year: 2018

Motivated by many practical applications in logistics and mobility-as-a-service, we study the top-k optimal sequenced routes (KOSR) querying on large, general graphs where the edge weights may not satisfy the triangle inequality, e.g., road network graphs with travel times as edge weights. The KOSR querying strives to find the top-k optimal routes (i.e., with the top-k minimal total costs) from a given source to a given destination, which must visit a number of vertices with specific vertex categories (e.g., gas stations, restaurants, and shopping malls) in a particular order (e.g., visiting gas stations before restaurants and then shopping malls). To efficiently find the top-k optimal sequenced routes, we propose two algorithms PruningKOSR and StarKOSR. In PruningKOSR, we define a dominance relationship between two partially-explored routes. The partially-explored routes that can be dominated by other partially-explored routes are postponed being extended, which leads to a smaller searching space and thus improves efficiency. In StarKOSR, we further improve the efficiency by extending routes in an A* manner. With the help of a judiciously designed heuristic estimation that works for general graphs, the cost of partially explored routes to the destination can be estimated such that the qualified complete routes can be found early. In addition, we demonstrate the high extensibility of the proposed algorithms by incorporating Hop Labeling, an effective label indexing technique for shortest path queries, to further improve efficiency. Extensive experiments on multiple real-world graphs demonstrate that the proposed methods significantly outperform the baseline method. Furthermore, when k=1, StarKOSR also outperforms the state-of-the-art method for the optimal sequenced route queries.
Comparative analysis of SVIT and Skype features in e-Learning process
Venue: arXiv cs.CY 2018
Year: 2018

The article discusses capabilities of the SVIT and Skype programs in terms of use in e-Learning process. Also various types of connections, image and sound quality were investigated.
Data Consistency Simulation Tool for NoSQL Database Systems
Venue: arXiv cs.DB 2018
Year: 2018

Various data consistency levels have an important part in the integrity of data and also affect performance especially the data that is replicated many times across or over the cluster. Based on BASE and the theorem of CAP tradeoffs, most systems of NoSQL have more relaxed consistency guarantees than another kind of databases which implement ACID. Most systems of NoSQL gave different methods to adjust a required level of consistency to ensure the minimal numbering of the replicas accepted in each operation. Simulations are always depending on a simplified model and ignore many details and facts about the real system. Therefore, a simulation can only work as an estimation or an explanation vehicle for observed behavior. So to create simulation tool, I have to characterize a model, identify influence factors and simply implement that depending on a (modeled) workload. In this paper, I have a model of simulation to measure the consistency of the data and to detect the data consistency violations in simulated network partition settings. So workloads are needed with the set of users who make requests and then put the results for analysis.
VBALD - Variational Bayesian Approximation of Log Determinants
Venue: arXiv cs.LG 2018
Year: 2018

Evaluating the log determinant of a positive definite matrix is ubiquitous in machine learning. Applications thereof range from Gaussian processes, minimum-volume ellipsoids, metric learning, kernel learning, Bayesian neural networks, Determinental Point Processes, Markov random fields to partition functions of discrete graphical models. In order to avoid the canonical, yet prohibitive, Cholesky $\mathcal{O}(n^{3})$ computational cost, we propose a novel approach, with complexity $\mathcal{O}(n^{2})$, based on a constrained variational Bayes algorithm. We compare our method to Taylor, Chebyshev and Lanczos approaches and show state of the art performance on both synthetic and real-world datasets.
Computing the concurrency threshold of sound free-choice workflow nets
Venue: arXiv cs.LO 2018
Year: 2018

Workflow graphs extend classical flow charts with concurrent fork and join nodes. They constitute the core of business processing languages such as BPMN or UML Activity Diagrams. The activities of a workflow graph are executed by humans or machines, generically called resources. If concurrent activities cannot be executed in parallel by lack of resources, the time needed to execute the workflow increases. We study the problem of computing the minimal number of resources necessary to fully exploit the concurrency of a given workflow, and execute it as fast as possible (i.e., as fast as with unlimited resources). We model this problem using free-choice Petri nets, which are known to be equivalent to workflow graphs. We analyze the computational complexity of two versions of the problem: computing the resource and concurrency thresholds. We use the results to design an algorithm to approximate the concurrency threshold, and evaluate it on a benchmark suite of 642 industrial examples. We show that it performs very well in practice: It always provides the exact value, and never takes more than 30 milliseconds for any workflow, even for those with a huge number of reachable markings.
Understanding the Performance of Ceph Block Storage for Hyper-Converged Cloud with All Flash Storage
Venue: arXiv cs.DC 2018
Year: 2018

Hyper-converged cloud refers to an architecture that an operator runs compute and storage services on the same set of physical servers. Although the hyper-converged design comes with a number of benefits, it makes crucial operational tasks, such as capacity planning and cost analysis, fairly complicated. The problem becomes more onerous if we consider a complex distributed system, such as Ceph, for the cloud with the proliferation of SSD drives. In this paper, we aim to answer some of these questions based on comprehensive microbenchmarks, and consequently better understand the behavior of Ceph in a hyper-converged cloud with all-flash storage. We reported our findings based on the study, devised a cost model and compared the cost of hyper-converged architecture with dedicated storage architecture. Additionally we summarized our experience based on the interactions with many teams at AT&T in the past couple of years.
High order time integrators for the simulation of charged particle motion in magnetic quadrupoles
Venue: arXiv cs.CE 2018
Year: 2018

Magnetic quadrupoles are essential components of particle accelerators like the Large Hadron Collider. In order to study numerically the stability of the particle beam crossing a quadrupole, a large number of particle revolutions in the accelerator must be simulated, thus leading to the necessity to preserve numerically invariants of motion over a long time interval and to a substantial computational cost, mostly related to the repeated evaluation of the magnetic vector potential. In this paper, in order to reduce this cost, we first consider a specific gauge transformation that allows to reduce significantly the number of vector potential evaluations. We then analyze the sensitivity of the numerical solution to the interpolation procedure required to compute magnetic vector potential data from gridded precomputed values at the locations required by high order time integration methods. Finally, we compare several high order integration techniques, in order to assess their accuracy and efficiency for these long term simulations. Explicit high order Lie methods are considered, along with implicit high order symplectic integrators and conventional explicit Runge Kutta methods. Among symplectic methods, high order Lie integrators yield optimal results in terms of cost/accuracy ratios, but non symplectic Runge Kutta methods perform remarkably well even in very long term simulations. Furthermore, the accuracy of the field reconstruction and interpolation techniques are shown to be limiting factors for the accuracy of the particle tracking procedures.
Collaboratively Learning the Best Option, Using Bounded Memory
Venue: arXiv cs.LG 2018
Year: 2018

We consider multi-armed bandit problems in social groups wherein each individual has bounded memory and shares the common goal of learning the best arm/option. We say an individual learns the best option if eventually (as $t \to \infty$) it pulls only the arm with the highest average reward. While this goal is provably impossible for an isolated individual, we show that, in social groups, this goal can be achieved easily with the aid of social persuasion, i.e., communication. Specifically, we study the learning dynamics wherein an individual sequentially decides on which arm to pull next based on not only its private reward feedback but also the suggestions provided by randomly chosen peers. Our learning dynamics are hard to analyze via explicit probabilistic calculations due to the stochastic dependency induced by social interaction. Instead, we employ the mean-field approximation method from statistical physics and we show: (1) With probability $\to 1$ as the social group size $N \to \infty $, every individual in the social group learns the best option. (2) Over an arbitrary finite time horizon $[0, T]$, with high probability (in $N$), the fraction of individuals that prefer the best option grows to 1 exponentially fast as $t$ increases ($t\in [0, T]$). A major innovation of our mean-filed analysis is a simple yet powerful technique to deal with absorbing states in the interchange of limits $N \to \infty$ and $t \to \infty $. The mean-field approximation method allows us to approximate the probabilistic sample paths of our learning dynamics by a deterministic and smooth trajectory that corresponds to the unique solution of a well-behaved system of ordinary differential equations (ODEs). Such an approximation is desired because the analysis of a system of ODEs is relatively easier than that of the original stochastic system.