OpenRaiser/Intern-Atlas huggingface dataset:
Streaming k-Means Clustering with Fast Queries
Venue: arXiv cs.DS 2018
Year: 2018

We present methods for k-means clustering on a stream with a focus on providing fast responses to clustering queries. Compared to the current state-of-the-art, our methods provide substantial improvement in the query time for cluster centers while retaining the desirable properties of provably small approximation error and low space usage. Our algorithms rely on a novel idea of "coreset caching" that systematically reuses coresets (summaries of data) computed for recent queries in answering the current clustering query. We present both theoretical analysis and detailed experiments demonstrating their correctness and efficiency
The flip Markov chain for connected regular graphs
Venue: arXiv cs.DM 2018
Year: 2018

Mahlmann and Schindelhauer (2005) defined a Markov chain which they called $k$-Flipper, and showed that it is irreducible on the set of all connected regular graphs of a given degree (at least 3). We study the 1-Flipper chain, which we call the flip chain, and prove that the flip chain converges rapidly to the uniform distribution over connected $2r$-regular graphs with $n$ vertices, where $n\geq 8$ and $r = r(n)\geq 2$. Formally, we prove that the distribution of the flip chain will be within $\varepsilon$ of uniform in total variation distance after $\text{poly}(n,r,\log(\varepsilon^{-1}))$ steps. This polynomial upper bound on the mixing time is given explicitly, and improves markedly on a previous bound given by Feder et al.(2006). We achieve this improvement by using a direct two-stage canonical path construction, which we define in a general setting. This work has applications to decentralised networks based on random regular connected graphs of even degree, as a self-stabilising protocol in which nodes spontaneously perform random flips in order to repair the network.
Validity of Clusters Produced By kernel-$k$-means With Kernel-Trick
Venue: arXiv cs.LG 2018
Year: 2018

This paper corrects the proof of the Theorem 2 from the Gower's paper \cite[page 5]{Gower:1982} as well as corrects the Theorem 7 from Gower's paper \cite{Gower:1986}. The first correction is needed in order to establish the existence of the kernel function used commonly in the kernel trick e.g. for $k$-means clustering algorithm, on the grounds of distance matrix. The correction encompasses the missing if-part proof and dropping unnecessary conditions. The second correction deals with transformation of the kernel matrix into a one embeddable in Euclidean space.
Ologisms
Venue: arXiv cs.LO 2018
Year: 2018

We introduce ologisms. They generate from ologs by extending their logical expressivity, from the possibility of considering constraints of equational nature only to the possibility of considering constraints of syllogistic nature, in addition. This is obtained by taking advantage of the peculiar features of an original diagrammatic logical calculus for the syllogistic, that make it well-behaved with respect to the design of ologs.
Dual Recovery Network with Online Compensation for Image Super-Resolution
Venue: arXiv cs.CV 2018
Year: 2018

Image super-resolution (SR) methods essentially lead to a loss of some high-frequency (HF) information when predicting high-resolution (HR) images from low-resolution (LR) images without using external references. To address this issue, we additionally utilize online retrieved data to facilitate image SR in a unified deep framework. A novel dual high-frequency recovery network (DHN) is proposed to predict an HR image with three parts: an LR image, an internal inferred HF (IHF) map (HF missing part inferred solely from the LR image) and an external extracted HF (EHF) map. In particular, we infer the HF information based on both the LR image and similar HR references which are retrieved online. For the EHF map, we align the references with affine transformation and then in the aligned references, part of HF signals are extracted by the proposed DHN to compensate for the HF loss. Extensive experimental results demonstrate that our DHN achieves notably better performance than state-of-the-art SR methods.
Conflict-Free Coloring of Planar Graphs
Venue: arXiv cs.DM 2018
Year: 2018

A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well-studied in graph theory. Here we study the natural problem of the conflict-free chromatic number chi_CF(G) (the smallest k for which conflict-free k-colorings exist). We provide results both for closed neighborhoods N[v], for which a vertex v is a member of its neighborhood, and for open neighborhoods N(v), for which vertex v is not a member of its neighborhood. For closed neighborhoods, we prove the conflict-free variant of the famous Hadwiger Conjecture: If an arbitrary graph G does not contain K_{k+1} as a minor, then chi_CF(G) <= k. For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. We also give a complete characterization of the computational complexity of conflict-free coloring. Deciding whether chi_CF(G)<= 1 is NP-complete for planar graphs G, but polynomial for outerplanar graphs. Furthermore, deciding whether chi_CF(G)<= 2 is NP-complete for planar graphs G, but always true for outerplanar graphs. For the bicriteria problem of minimizing the number of colored vertices subject to a given bound k on the number of colors, we give a full algorithmic characterization in terms of complexity and approximation for outerplanar and planar graphs. For open neighborhoods, we show that every planar bipartite graph has a conflict-free coloring with at most four colors; on the other hand, we prove that for k in {1,2,3}, it is NP-complete to decide whether a planar bipartite graph has a conflict-free k-coloring. Moreover, we establish that any general} planar graph has a conflict-free coloring with at most eight colors.
Evaluating QBF Solvers: Quantifier Alternations Matter
Venue: arXiv cs.LO 2018
Year: 2018

We present an experimental study of the effects of quantifier alternations on the evaluation of quantified Boolean formula (QBF) solvers. The number of quantifier alternations in a QBF in prenex conjunctive normal form (PCNF) is directly related to the theoretical hardness of the respective QBF satisfiability problem in the polynomial hierarchy. We show empirically that the performance of solvers based on different solving paradigms substantially varies depending on the numbers of alternations in PCNFs. In related theoretical work, quantifier alternations have become the focus of understanding the strengths and weaknesses of various QBF proof systems implemented in solvers. Our results motivate the development of methods to evaluate orthogonal solving paradigms by taking quantifier alternations into account. This is necessary to showcase the broad range of existing QBF solving paradigms for practical QBF applications. Moreover, we highlight the potential of combining different approaches and QBF proof systems in solvers.
Error correction based on partial information
Venue: arXiv cs.IT 2018
Year: 2018

We consider the decoding of linear and array codes from errors when we are only allowed to download a part of the codeword. More specifically, suppose that we have encoded $k$ data symbols using an $(n,k)$ code with code length $n$ and dimension $k.$ During storage, some of the codeword coordinates might be corrupted by errors. We aim to recover the original data by reading the corrupted codeword with a limit on the transmitting bandwidth, namely, we can only download an $α$ proportion of the corrupted codeword. For a given $α,$ our objective is to design a code and a decoding scheme such that we can recover the original data from the largest possible number of errors. A naive scheme is to read $αn$ coordinates of the codeword. This method used in conjunction with MDS codes guarantees recovery from any $\lfloor(αn-k)/2\rfloor$ errors. In this paper we show that we can instead read an $α$ proportion from each of the codeword's coordinates. For a well-designed MDS code, this method can guarantee recovery from $\lfloor (n-k/α)/2 \rfloor$ errors, which is $1/α$ times more than the naive method, and is also the maximum number of errors that an $(n,k)$ code can correct by downloading only an $α$ proportion of the codeword. We present two families of such optimal constructions and decoding schemes. One is a Reed-Solomon code with evaluation points in a subfield and the other is based on Folded Reed-Solomon codes. We further show that both code constructions attain asymptotically optimal list decoding radius when downloading only a part of the corrupted codeword. We also construct an ensemble of random codes that with high probability approaches the upper bound on the number of correctable errors when the decoder downloads an $α$ proportion of the corrupted codeword.
Locally Repairable Codes with Unequal Local Erasure Correction
Venue: arXiv cs.IT 2018
Year: 2018

When a node in a distributed storage system fails, it needs to be promptly repaired to maintain system integrity. While typical erasure codes can provide a significant storage advantage over replication, they suffer from poor repair efficiency. Locally repairable codes (LRCs) tackle this issue by reducing the number of nodes participating in the repair process (locality), at the cost of reduced minimum distance. In this paper, we study the tradeoff between locality and minimum distance of LRCs with local codes that have arbitrary distance requirements. Unlike existing methods where both the locality and the local distance requirements imposed on every node are identical, we allow the requirements to vary arbitrarily from node to node. Such a property can be an advantage for distributed storage systems with non-homogeneous characteristics. We present Singleton-type distance upper bounds and also provide an optimal code construction with respect to these bounds. In addition, the feasible rate region is characterized by dimension upper bounds that do not depend on the distance.
Wiretap channel capacity: Secrecy criteria, strong converse, and phase change
Venue: arXiv cs.IT 2018
Year: 2018

This paper employs equal-image-size source partitioning techniques to derive the capacities of the general discrete memoryless wiretap channel (DM-WTC) under four different secrecy criteria. These criteria respectively specify requirements on the expected values and tail probabilities of the differences, in absolute value and in exponent, between the joint probability of the secret message and the eavesdropper's observation and the corresponding probability if they were independent. Some of these criteria reduce back to the standard leakage and variation distance constraints that have been previously considered in the literature. The capacities under these secrecy criteria are found to be different when non-vanishing error and secrecy tolerances are allowed. Based on these new results, we are able to conclude that the strong converse property generally holds for the DM-WTC only under the two secrecy criteria based on constraining the tail probabilities. Under the secrecy criteria based on the expected values, an interesting phase change phenomenon is observed as the tolerance values vary.
SOS-based Modal Decomposition on Nondeterministic Probabilistic Processes
Venue: arXiv cs.LO 2018
Year: 2018

We propose a method for the decomposition of modal formulae on processes with nondeterminism and probability with respect to Structural Operational Semantics. The purpose is to reduce the satisfaction problem of a formula for a process to verifying whether its subprocesses satisfy certain formulae obtained from the decomposition. To deal with the probabilistic behavior of processes, and thus with the decomposition of formulae characterizing it, we introduce a SOS-like machinery allowing for the specification of the behavior of open distribution terms. By our decomposition, we obtain (pre)congruence formats for probabilistic bisimilarity, ready similarity and similarity.
Fully Convolutional Architectures for Multi-Class Segmentation in Chest Radiographs
Venue: arXiv cs.CV 2018
Year: 2018

The success of deep convolutional neural networks on image classification and recognition tasks has led to new applications in very diversified contexts, including the field of medical imaging. In this paper we investigate and propose neural network architectures for automated multi-class segmentation of anatomical organs in chest radiographs, namely for lungs, clavicles and heart. We address several open challenges including model overfitting, reducing number of parameters and handling of severely imbalanced data in CXR by fusing recent concepts in convolutional networks and adapting them to the segmentation problem task in CXR. We demonstrate that our architecture combining delayed subsampling, exponential linear units, highly restrictive regularization and a large number of high resolution low level abstract features outperforms state-of-the-art methods on all considered organs, as well as the human observer on lungs and heart. The models use a multi-class configuration with three target classes and are trained and tested on the publicly available JSRT database, consisting of 247 X-ray images the ground-truth masks for which are available in the SCR database. Our best performing model, trained with the loss function based on the Dice coefficient, reached mean Jaccard overlap scores of 95.0\% for lungs, 86.8\% for clavicles and 88.2\% for heart. This architecture outperformed the human observer results for lungs and heart.
Stochastic Graphlet Embedding
Venue: arXiv cs.CV 2018
Year: 2018

Graph-based methods are known to be successful in many machine learning and pattern classification tasks. These methods consider semi-structured data as graphs where nodes correspond to primitives (parts, interest points, segments, etc.) and edges characterize the relationships between these primitives. However, these non-vectorial graph data cannot be straightforwardly plugged into off-the-shelf machine learning algorithms without a preliminary step of -- explicit/implicit -- graph vectorization and embedding. This embedding process should be resilient to intra-class graph variations while being highly discriminant. In this paper, we propose a novel high-order stochastic graphlet embedding (SGE) that maps graphs into vector spaces. Our main contribution includes a new stochastic search procedure that efficiently parses a given graph and extracts/samples unlimitedly high-order graphlets. We consider these graphlets, with increasing orders, to model local primitives as well as their increasingly complex interactions. In order to build our graph representation, we measure the distribution of these graphlets into a given graph, using particular hash functions that efficiently assign sampled graphlets into isomorphic sets with a very low probability of collision. When combined with maximum margin classifiers, these graphlet-based representations have positive impact on the performance of pattern comparison and recognition as corroborated through extensive experiments using standard benchmark databases.
An O(n^2) algorithm for Many-To-Many Matching of Points with Demands in One Dimension
Venue: arXiv cs.DS 2018
Year: 2018

Given two point sets S and T, we study the many-to-many matching with demands problem (MMD problem) which is a generalization of the many-to-many matching problem (MM problem). In an MMD, each point of one set must be matched to a given number of the points of the other set (each point has a demand). In this paper we consider a special case of MMD problem, the one-dimensional MMD (OMMD), where the input point sets S and T lie on the line. That is, the cost of matching a pair of points is equal to the distance between the two points. we present the first O(n^2)time algorithm for computing an OMMD between S and T, where |S| + |T| = n.
Class attendance, peer similarity, and academic performance in a large field study
Venue: arXiv cs.SI 2018
Year: 2018

Identifying the factors that determine academic performance is an essential part of educational research. Existing research indicates that class attendance is a useful predictor of subsequent course achievements. The majority of the literature is, however, based on surveys and self-reports, methods which have well-known systematic biases that lead to limitations on conclusions and generalizability as well as being costly to implement. Here we propose a novel method for measuring class attendance that overcomes these limitations by using location and bluetooth data collected from smartphone sensors. Based on measured attendance data of nearly 1,000 undergraduate students, we demonstrate that early and consistent class attendance strongly correlates with academic performance. In addition, our novel dataset allows us to determine that attendance among social peers was substantially correlated ($>$0.5), suggesting either an important peer effect or homophily with respect to attendance.
Time Series Cube Data Model
Venue: arXiv cs.DB 2018
Year: 2018

The purpose of this document is to create a data model and its serialization for expressing generic time series data. Already existing IVOA data models are reused as much as possible. The model is also made as generic as possible to be open to new extensions but at the same time closed for modifications. This enables maintaining interoperability throughout different versions of the data model. We define the necessary building blocks for metadata discovery, serialization of time series data and understanding it by clients. We present several categories of time series science cases with examples of implementation. We also take into account the most pressing topics for time series providers like tracking original images for every individual point of a light curve or time-derived axes like frequency for gravitational wave analysis. The main motivation for the creation of a new model is to provide a unified time series data publishing standard - not only for light curves but also more generic time series data, e.g., radial velocity curves, power spectra, hardness ratio, provenance linkage, etc. The flexibility is the most crucial part of our model - we are not dependent on any physical domain or frame models. While images or spectra are already stable and standardized products, the time series related domains are still not completely evolved and new ones will likely emerge in near future. That is why we need to keep models like Time Series Cube DM independent of any underlying physical models. In our opinion, this is the only correct and sustainable way for future development of IVOA standards.
Systematic Mapping Protocol - Coverage of Aspect-Oriented Methodologies for the Early Phases of the Software Development Life Cycle
Venue: arXiv cs.SE 2018
Year: 2018

The amount of aspect-oriented software development techniques and tools have been increasing for the last years but still they have not enough maturity and are not sufficiently spread to be included in a project leader's box of tools. Software development projects have to deal with many risks, and the main function of project leaders is to minimize them. The use of immature technologies, tools newcomers to the market, techniques that have not been tested enough, etc., would be very risky decisions to take by who has the responsibility to carry out a successful software development project. On the other hand, the availability of well-known tools and techniques and the adherence to standards and best practices will help professionals to make good estimates and to take better decisions. There is many proposals on aspect-oriented techniques, notations, tools, etc., but they have not yet unified on a common body of knowledge and none of them has become the most popular approach. We are interested in the early phases of the aspect-oriented SDLC which include the phases from the beginning of the life cycle until architecture design. We are interested in portraying the state of the art of aspect-oriented techniques and tools, in the identification of the standards they employ. Our goal is to collect all the available evidence, analyze it, and study the possibility of applying these techniques, tools and standards in real projects, taking advantage of the benefits of the aspect-oriented paradigm, by identifying the standard and widespread approaches, techniques, notations and tools present in the scientific literature and to verify if they were applied in the industry, by means of a systematic mapping of the literature published between 1995 and 2019.
DBFT: Efficient Byzantine Consensus with a Weak Coordinator and its Application to Consortium Blockchains
Venue: arXiv cs.DC 2018
Year: 2018

This paper introduces a deterministic Byzantine consensus algorithm that relies on a new weak coordinator. As opposed to previous algorithms that cannot terminate in the presence of a faulty or slow coordinator, our algorithm can terminate even when its coordinator is faulty, hence the name weak coordinator. The key idea is to allow processes to complete asynchronous rounds as soon as they receive a threshold of messages, instead of having to wait for a message from a coordinator that may be slow. The resulting algorithm assumes partial synchrony, is resilience optimal, time optimal and does not need signatures. Our presentation is didactic: we first present a simple safe binary Byzantine consensus algorithm, modify it to ensure termination, and finally present an optimized reduction from multivalue consensus to binary consensus that may terminate in 4 message delays. To evaluate our algorithm, we deployed it on 100 machines distributed in 5 datacenters across different continents and compared its performance against the randomized solution from Mostefaoui, Moumem and Raynal [PODC14] that terminates in O(1) rounds in expectation. Our algorithm always outperforms the latter even in the presence of Byzantine behaviors. Our algorithm has a subsecond average latency in most of our geo-distributed experiments, even when attacked by a well-engineered coalition of Byzantine processes.
Learning Concept Embeddings for Efficient Bag-of-Concepts Densification
Venue: arXiv cs.CL 2018
Year: 2018

Explicit concept space models have proven efficacy for text representation in many natural language and text mining applications. The idea is to embed textual structures into a semantic space of concepts which captures the main ideas, objects, and the characteristics of these structures. The so called Bag of Concepts (BoC) representation suffers from data sparsity causing low similarity scores between similar texts due to low concept overlap. To address this problem, we propose two neural embedding models to learn continuous concept vectors. Once they are learned, we propose an efficient vector aggregation method to generate fully continuous BoC representations. We evaluate our concept embedding models on three tasks: 1) measuring entity semantic relatedness and ranking where we achieve 1.6% improvement in correlation scores, 2) dataless concept categorization where we achieve state-of-the-art performance and reduce the categorization error rate by more than 5% compared to five prior word and entity embedding models, and 3) dataless document classification where our models outperform the sparse BoC representations. In addition, by exploiting our efficient linear time vector aggregation method, we achieve better accuracy scores with much less concept dimensions compared to previous BoC densification methods which operate in polynomial time and require hundreds of dimensions in the BoC representation.