OpenRaiser/Intern-Atlas huggingface dataset:
On the Radius of Nonsplit Graphs and Information Dissemination in Dynamic Networks
Venue: arXiv cs.DC 2019
Year: 2019

A nonsplit graph is a directed graph where each pair of nodes has a common incoming neighbor. We show that the radius of such graphs is in $O(\log \log n)$, where $n$ is the number of nodes. We then generalize the result to products of nonsplit graphs. The analysis of nonsplit graph products has direct implications in the context of distributed systems, where processes operate in rounds and communicate via message passing in each round: communication graphs in several distributed systems naturally relate to nonsplit graphs and the graph product concisely represents relaying messages in such networks. Applying our results, we obtain improved bounds on the dynamic radius of such networks, i.e., the maximum number of rounds until all processes have received a message from a common process, if all processes relay messages in each round. We finally connect the dynamic radius to lower bounds for achieving consensus in dynamic networks.
Anchor-Based Correction of Substitutions in Indexed Sets
Venue: arXiv cs.IT 2019
Year: 2019

Motivated by DNA-based data storage, we investigate a system where digital information is stored in an unordered set of several vectors over a finite alphabet. Each vector begins with a unique index that represents its position in the whole data set and does not contain data. This paper deals with the design of error-correcting codes for such indexed sets in the presence of substitution errors. We propose a construction that efficiently deals with the challenges that arise when designing codes for unordered sets. Using a novel mechanism, called anchoring, we show that it is possible to combat the ordering loss of sequences with only a small amount of redundancy, which allows to use standard coding techniques, such as tensor-product codes to correct errors within the sequences. We finally derive upper and lower bounds on the achievable redundancy of codes within the considered channel model and verify that our construction yields a redundancy that is close to the best possible achievable one. Our results surprisingly indicate that it requires less redundancy to correct errors in the indices than in the data part of vectors.
An Experimental Study of the Treewidth of Real-World Graph Data (Extended Version)
Venue: arXiv cs.DB 2019
Year: 2019

Treewidth is a parameter that measures how tree-like a relational instance is, and whether it can reasonably be decomposed into a tree. Many computation tasks are known to be tractable on databases of small treewidth, but computing the treewidth of a given instance is intractable. This article is the first large-scale experimental study of treewidth and tree decompositions of real-world database instances (25 datasets from 8 different domains, with sizes ranging from a few thousand to a few million vertices). The goal is to determine which data, if any, can benefit of the wealth of algorithms for databases of small treewidth. For each dataset, we obtain upper and lower bound estimations of their treewidth, and study the properties of their tree decompositions. We show in particular that, even when treewidth is high, using partial tree decompositions can result in data structures that can assist algorithms.
MSO+nabla is undecidable
Venue: arXiv cs.LO 2019
Year: 2019

This paper is about an extension of monadic second-order logic over the full binary tree, which has a quantifier saying ``almost surely a branch π \in {0, 1}^w satisfies a formula ϕ(π)''. This logic was introduced by Michalewski and Mio; we call it MSO+nabla following notation of Shelah and Lehmann. The logic MSO+nabla subsumes many qualitative probabilistic formalisms, including qualitative probabilistic CTL, probabilistic LTL, or parity tree automata with probabilistic acceptance conditions. We show that it is undecidable to check if a given sentence of MSO+nabla is true in the full binary tree.
New Bounds on the Field Size for Maximally Recoverable Codes Instantiating Grid-like Topologies
Venue: arXiv cs.IT 2019
Year: 2019

In recent years, the rapidly increasing amounts of data created and processed through the internet resulted in distributed storage systems employing erasure coding based schemes. Aiming to balance the tradeoff between data recovery for correlated failures and efficient encoding and decoding, distributed storage systems employing maximally recoverable codes came up. Unifying a number of topologies considered both in theory and practice, Gopalan et al. \cite{Gopalan2017} initiated the study of maximally recoverable codes for grid-like topologies. In this paper, we focus on the maximally recoverable codes that instantiate grid-like topologies $T_{m\times n}(1,b,0)$. To characterize the property of codes for these topologies, we introduce the notion of \emph{pseudo-parity check matrix}. Then, using the Combinatorial Nullstellensatz, we establish the first polynomial upper bound on the field size needed for achieving the maximal recoverability in topologies $T_{m\times n}(1,b,0)$. And using hypergraph independent set approach, we further improve this general upper bound for topologies $T_{4\times n}(1,2,0)$ and $T_{3\times n}(1,3,0)$. By relating the problem to generalized \emph{Sidon sets} in $\mathbb{F}_q$, we also obtain non-trivial lower bounds on the field size for maximally recoverable codes that instantiate topologies $T_{4\times n}(1,2,0)$ and $T_{3\times n}(1,3,0)$.
Vardøhus Codes: Polar Codes Based on Castle Curves Kernels
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we show some applications of algebraic curves to the construction of kernels of polar codes over a discrete memoryless channel which is symmetric w.r.t the field operations. We will also study the minimum distance of the polar codes proposed, their duals and the exponents of the matrices used for defining them. All the restrictions that we make to our curves will be accomplished by the so-called Castle Curves.
Segmentation of Lumen and External Elastic Laminae in Intravascular Ultrasound Images using Ultrasonic Backscattering Physics Initialized Multiscale Random Walks
Venue: arXiv cs.CV 2019
Year: 2019

Coronary artery disease accounts for a large number of deaths across the world and clinicians generally prefer using x-ray computed tomography or magnetic resonance imaging for localizing vascular pathologies. Interventional imaging modalities like intravascular ultrasound (IVUS) are used to adjunct diagnosis of atherosclerotic plaques in vessels, and help assess morphological state of the vessel and plaque, which play a significant role for treatment planning. Since speckle intensity in IVUS images are inherently stochastic in nature and challenge clinicians with accurate visibility of the vessel wall boundaries, it requires automation. In this paper we present a method for segmenting the lumen and external elastic laminae of the artery wall in IVUS images using random walks over a multiscale pyramid of Gaussian decomposed frames. The seeds for the random walker are initialized by supervised learning of ultrasonic backscattering and attenuation statistical mechanics from labelled training samples. We have experimentally evaluated the performance using $77$ IVUS images acquired at $40$ MHz that are available in the IVUS segmentation challenge dataset\footnote{http://www.cvc.uab.es/IVUSchallenge2011/dataset.html} to obtain a Jaccard score of $0.89 \pm 0.14$ for lumen and $0.85 \pm 0.12$ for external elastic laminae segmentation over a $10$-fold cross-validation study.
Hybrid Design Tools - Image Quality Assessment of a Digitally Augmented Blackboard Integrated System
Venue: arXiv cs.CY 2019
Year: 2019

In the last two decades, Interactive White Boards (IWBs) have been widely available as a pedagogic tool. The usability of these boards for teaching disciplines where complex drawings are needed, we consider debatable in multiple regards. In a previous study, we proposed an alternative to the IWBs as a blackboard augmented with a minimum of necessary digital elements. The current study continues our previous research on hybrid design tools, analyzing the limitations of the developed hybrid system regarding the perceived quality of the images being repeatedly captured, annotated, and reprojected onto the board. We validated the hybrid system by evaluating the quality of the projected and reprojected images over a blackboard, using both objective measurements and subjective human perception in extensive and realistic case studies. Based on the results achieved in the current research, we conclude that the proposed hybrid system provides good quality support for teaching disciplines that require complex drawings and board interaction.
Automatic Synthesis of Totally Self-Checking Circuits
Venue: arXiv cs.AI 2019
Year: 2019

Totally self-checking (TSC) circuits are synthesised with a grid of computers running a distributed population based stochastic optimisation algorithm. The presented method is the first to automatically synthesise TSC circuits from arbitrary logic as all previous methods fail to guarantee the checker is self-testing (ST) for circuits with limited output codespaces. The circuits synthesised by the presented method have significantly lower overhead than the previously reported best for every one of a set of 11 frequently used benchmarks. Average overhead across the entire set is 23% of duplication and comparison overhead, compared with an average of 69% for the previous best reported values across the set. The methodology presented represents a breakthrough in concurrent error detection (CED). The highly efficient, novel designs produced are tailored to each circuit's function, rather than being constrained by a particular modular CED design methodology. Results are synthesised using two-input gates and are TSC with respect to all gate input and output stuck-at faults. The method can be used to add CED with or without modifications to the original logic, and can be generalised to any implementation technology and fault model. An example circuit is analysed and rigorously proven to be TSC.
Temporal Discounting in Technical Debt: How do Software Practitioners Discount the Future?
Venue: arXiv cs.SE 2019
Year: 2019

Technical Debt management decisions always imply a trade-off among outcomes at different points in time. In such intertemporal choices, distant outcomes are often valued lower than close ones, a phenomenon known as temporal discounting. Technical Debt research largely develops prescriptive approaches for how software engineers should make such decisions. Few have studied how they actually make them. This leaves open central questions about how software practitioners make decisions. This paper investigates how software practitioners discount uncertain future outcomes and whether they exhibit temporal discounting. We adopt experimental methods from intertemporal choice, an active area of research. We administered an online questionnaire to 33 developers from two companies in which we presented choices between developing a feature and making a longer-term investment in architecture. The results show wide-spread temporal discounting with notable differences in individual behavior. The results are consistent with similar studies in consumer behavior and raise a number of questions about the causal factors that influence temporal discounting in software engineering. As the first empirical study on intertemporal choice in SE, the paper establishes an empirical basis for understanding how software developers approach intertemporal choice and provides a blueprint for future studies.
Robust Angular Local Descriptor Learning
Venue: arXiv cs.CV 2019
Year: 2019

In recent years, the learned local descriptors have outperformed handcrafted ones by a large margin, due to the powerful deep convolutional neural network architectures such as L2-Net [1] and triplet based metric learning [2]. However, there are two problems in the current methods, which hinders the overall performance. Firstly, the widely-used margin loss is sensitive to incorrect correspondences, which are prevalent in the existing local descriptor learning datasets. Second, the L2 distance ignores the fact that the feature vectors have been normalized to unit norm. To tackle these two problems and further boost the performance, we propose a robust angular loss which 1) uses cosine similarity instead of L2 distance to compare descriptors and 2) relies on a robust loss function that gives smaller penalty to triplets with negative relative similarity. The resulting descriptor shows robustness on different datasets, reaching the state-of-the-art result on Brown dataset , as well as demonstrating excellent generalization ability on the Hpatches dataset and a Wide Baseline Stereo dataset.
Using Big Data Technologies for HEP Analysis
Venue: arXiv cs.DC 2019
Year: 2019

The HEP community is approaching an era were the excellent performances of the particle accelerators in delivering collision at high rate will force the experiments to record a large amount of information. The growing size of the datasets could potentially become a limiting factor in the capability to produce scientific results timely and efficiently. Recently, new technologies and new approaches have been developed in industry to answer to the necessity to retrieve information as quickly as possible to analyze PB and EB datasets. Providing the scientists with these modern computing tools will lead to rethinking the principles of data analysis in HEP, making the overall scientific process faster and smoother. In this paper, we are presenting the latest developments and the most recent results on the usage of Apache Spark for HEP analysis. The study aims at evaluating the efficiency of the application of the new tools both quantitatively, by measuring the performances, and qualitatively, focusing on the user experience. The first goal is achieved by developing a data reduction facility: working together with CERN Openlab and Intel, CMS replicates a real physics search using Spark-based technologies, with the ambition of reducing 1 PB of public data in 5 hours, collected by the CMS experiment, to 1 TB of data in a format suitable for physics analysis. The second goal is achieved by implementing multiple physics use-cases in Apache Spark using as input preprocessed datasets derived from official CMS data and simulation. By performing different end-analyses up to the publication plots on different hardware, feasibility, usability and portability are compared to the ones of a traditional ROOT-based workflow.
Virtual Immersive Reality based Analysis of Behavioral Responses in Connected and Autonomous Vehicle Environment
Venue: arXiv cs.HC 2019
Year: 2019

Recently, we developed a dynamic distributed end-to-end vehicle routing system (E2ECAV) using a network of intelligent intersections and level 5 CAVs (Djavadian & Farooq, 2018). The case study of the downtown Toronto Network showed that E2ECAV has the ability to maximize throughput and reduce travel time up to 40%. However, the efficiency of these new technologies relies on the acceptance of users in adapting to them and their willingness to give control fully or partially to CAVs. In this study a stated preference laboratory experiment is designed employing Virtual Reality Immersive Environment (VIRE) driving simulator to evaluate the behavioral response of drivers to E2ECAV. The aim is to investigate under what conditions drivers are more willing to adapt. The results show that factors such as locus of control, congestion level and ability to multi-task have significant impact.
Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete
Venue: arXiv cs.LO 2019
Year: 2019

Checking whether two pushdown automata with restricted silent actions are weakly bisimilar was shown decidable by Sénizergues (1998, 2005). We provide the first known complexity upper bound for this famous problem, in the equivalent setting of first-order grammars. This ACKERMANN upper bound is optimal, and we also show that strong bisimilarity is primitive-recursive when the number of states of the automata is fixed.
Enhancing Semantic Word Representations by Embedding Deeper Word Relationships
Venue: arXiv cs.AI 2019
Year: 2019

Word representations are created using analogy context-based statistics and lexical relations on words. Word representations are inputs for the learning models in Natural Language Understanding (NLU) tasks. However, to understand language, knowing only the context is not sufficient. Reading between the lines is a key component of NLU. Embedding deeper word relationships which are not represented in the context enhances the word representation. This paper presents a word embedding which combines an analogy, context-based statistics using Word2Vec, and deeper word relationships using Conceptnet, to create an expanded word representation. In order to fine-tune the word representation, Self-Organizing Map is used to optimize it. The proposed word representation is compared with semantic word representations using Simlex 999. Furthermore, the use of 3D visual representations has shown to be capable of representing the similarity and association between words. The proposed word representation shows a Spearman correlation score of 0.886 and provided the best results when compared to the current state-of-the-art methods, and exceed the human performance of 0.78.
A Time-driven Data Placement Strategy for a Scientific Workflow Combining Edge Computing and Cloud Computing
Venue: arXiv cs.DC 2019
Year: 2019

Compared to traditional distributed computing environments such as grids, cloud computing provides a more cost-effective way to deploy scientific workflows. Each task of a scientific workflow requires several large datasets that are located in different datacenters from the cloud computing environment, resulting in serious data transmission delays. Edge computing reduces the data transmission delays and supports the fixed storing manner for scientific workflow private datasets, but there is a bottleneck in its storage capacity. It is a challenge to combine the advantages of both edge computing and cloud computing to rationalize the data placement of scientific workflow, and optimize the data transmission time across different datacenters. Traditional data placement strategies maintain load balancing with a given number of datacenters, which results in a large data transmission time. In this study, a self-adaptive discrete particle swarm optimization algorithm with genetic algorithm operators (GA-DPSO) was proposed to optimize the data transmission time when placing data for a scientific workflow. This approach considered the characteristics of data placement combining edge computing and cloud computing. In addition, it considered the impact factors impacting transmission delay, such as the band-width between datacenters, the number of edge datacenters, and the storage capacity of edge datacenters. The crossover operator and mutation operator of the genetic algorithm were adopted to avoid the premature convergence of the traditional particle swarm optimization algorithm, which enhanced the diversity of population evolution and effectively reduced the data transmission time. The experimental results show that the data placement strategy based on GA-DPSO can effectively reduce the data transmission time during workflow execution combining edge computing and cloud computing.
Unsupervised Automated Event Detection using an Iterative Clustering based Segmentation Approach
Venue: arXiv cs.CV 2019
Year: 2019

A class of vision problems, less commonly studied, consists of detecting objects in imagery obtained from physics-based experiments. These objects can span in 4D (x, y, z, t) and are visible as disturbances (caused due to physical phenomena) in the image with background distribution being approximately uniform. Such objects, occasionally referred to as `events', can be considered as high energy blobs in the image. Unlike the images analyzed in conventional vision problems, very limited features are associated with such events, and their shape, size and count can vary significantly. This poses a challenge on the use of pre-trained models obtained from supervised approaches. In this paper, we propose an unsupervised approach involving iterative clustering based segmentation (ICS) which can detect target objects (events) in real-time. In this approach, a test image is analyzed over several cycles, and one event is identified per cycle. Each cycle consists of the following steps: (1) image segmentation using a modified k-means clustering method, (2) elimination of empty (with no events) segments based on statistical analysis of each segment, (3) merging segments that overlap (correspond to same event), and (4) selecting the strongest event. These four steps are repeated until all the events have been identified. The ICS approach consists of a few hyper-parameters that have been chosen based on statistical study performed over a set of test images. The applicability of ICS method is demonstrated on several 2D and 3D test examples.
RICERCANDO: Data Mining Toolkit for Mobile Broadband Measurements
Venue: arXiv cs.NI 2019
Year: 2019

Increasing reliance on mobile broadband (MBB) networks for communication, vehicle navigation, healthcare, and other critical purposes calls for improved monitoring and troubleshooting of such networks. While recent advances in monitoring with crowdsourced as well as network infrastructure-based methods allow us to tap into a number of performance metrics from all layers of networking, huge swaths of data remain poorly or completely unexplored due to a lack of tools suitable for rapid, interactive, and rigorous MBB data analysis. In this paper we present RICERCANDO, a MBB data mining toolkit developed in a unique collaboration of networking and data mining experts. RICERCANDO consists of a preprocessing module that ensures that time-series data is stored in the most appropriate form for mining, a rapid exploration module that enables iterative analysis of time-series and geomobile data, so that anomalies are detected and singled out, and the advanced mining module that lets the analyst deduce root causes of observed anomalies. We implement and release RICERCANDO as open-source software, and validate its usability on case studies from MONROE pan-European MBB measurement testbed.
The reach of commercially motivated junk news on Facebook
Venue: arXiv cs.CY 2019
Year: 2019

Commercially motivated junk news -- i.e. money-driven, highly shareable clickbait with low journalistic production standards -- constitutes a vast and largely unexplored news media ecosystem. Using publicly available Facebook data, we compared the reach of junk news on Facebook pages in the Netherlands to the reach of Dutch mainstream news on Facebook. During the period 2013-2017 the total number of user interactions with junk news significantly exceeded that with mainstream news. Over 5 Million of the 10 Million Dutch Facebook users have interacted with a junk news post at least once. Junk news Facebook pages also had a significantly stronger increase in the number of user interactions over time than mainstream news. Since the beginning of 2016 the average number of user interactions per junk news post has consistently exceeded the average number of user interactions per mainstream news post.