OpenRaiser/Intern-Atlas huggingface dataset:
Image Restoration using Total Variation with Overlapping Group Sparsity
Venue: arXiv cs.CV 2013
Year: 2013

Image restoration is one of the most fundamental issues in imaging science. Total variation (TV) regularization is widely used in image restoration problems for its capability to preserve edges. In the literature, however, it is also well known for producing staircase-like artifacts. Usually, the high-order total variation (HTV) regularizer is an good option except its over-smoothing property. In this work, we study a minimization problem where the objective includes an usual $l_2$ data-fidelity term and an overlapping group sparsity total variation regularizer which can avoid staircase effect and allow edges preserving in the restored image. We also proposed a fast algorithm for solving the corresponding minimization problem and compare our method with the state-of-the-art TV based methods and HTV based method. The numerical experiments illustrate the efficiency and effectiveness of the proposed method in terms of PSNR, relative error and computing time.
Pursuit Fractal Analysis of Time-Series Data
Venue: arXiv cs.NA 2013
Year: 2013

In this study, we present a method to measure changes over time of fractal dimension. We confirmed that our method can calculate the fractal dimension with the same precision as conventional methods, and tracking performance of our method is higher than that of the conventional methods.
Predicting college basketball match outcomes using machine learning techniques: some results and lessons learned
Venue: arXiv cs.LG 2013
Year: 2013

Most existing work on predicting NCAAB matches has been developed in a statistical context. Trusting the capabilities of ML techniques, particularly classification learners, to uncover the importance of features and learn their relationships, we evaluated a number of different paradigms on this task. In this paper, we summarize our work, pointing out that attributes seem to be more important than models, and that there seems to be an upper limit to predictive quality.
Pennants for Descriptors
Venue: arXiv cs.DL 2013
Year: 2013

We present a new technique (called pennants) for displaying the descriptors related to a descriptor across literatures, rather in a thesaurus. It has definite implications for online searching and browsing. Pennants, named for the flag they resemble, are a form of algorithmic prediction. Their cognitive base is in relevance theory (RT) from linguistic pragmatics (Sperber & Wilson 1995).
10 Inventions on laptop keyboards -A study based on US patents
Venue: arXiv cs.HC 2013
Year: 2013

A desktop keyboard has several sections like character key section, navigation key section, numeric key section, and function key section etc. each consisting of several number of keys. However, a laptop computer does not have so much of space to accommodate all these keys into the keyboard. There are several considerations while designing a laptop keyboard. This article illustrates 10 inventions on keyboards for laptop and portable computers. The inventions are selected from US patent database. The inventions try to improve various aspects of a laptop keyboard, such as reducing size, folding and concealing, ergonomic features, improving quality and reducing cost.
Multi-Sorted Inverse Frequent Itemsets Mining
Venue: arXiv cs.DB 2013
Year: 2013

The development of novel platforms and techniques for emerging "Big Data" applications requires the availability of real-life datasets for data-driven experiments, which are however out of reach for academic research in most cases as they are typically proprietary. A possible solution is to use synthesized datasets that reflect patterns of real ones in order to ensure high quality experimental findings. A first step in this direction is to use inverse mining techniques such as inverse frequent itemset mining (IFM) that consists of generating a transactional database satisfying given support constraints on the itemsets in an input set, that are typically the frequent ones. This paper introduces an extension of IFM, called many-sorted IFM, where the schemes for the datasets to be generated are those typical of Big Tables as required in emerging big data applications, e.g., social network analytics.
Distributed Algorithm for Dynamic Data-Gathering in Sensor Network
Venue: arXiv cs.DC 2013
Year: 2013

In WSN, each sensor is responsible for sensing environmental conditions and sending them to the one or more base stations. Battery-operated sensors are severely constrained by the amount of energy that can be spend for transmitting these sensed data. However, aggregation of data (including removal of redundant data) at intermediate sensors and forwarding of aggregate data reduce overall energy consumptions in WSN. In general, data gathering refers to the process of periodic collection of sensed data from various sensors to one or more base stations (BS). Energy efficient data gathering scheduling is essential for improving the lifetime of WSN. In this paper, we propose a distributed algorithm to compute data-gathering schedule that aim to improve the lifetime of WSN by suitably selecting energy-efficient data-flow paths from various sensors to the base station. For a multihop WSN with $n$ sensors, the proposed algorithm first computes a schedule in $O(n^2)$ time steps, and then this schedule is periodically updated based the residual energy and the feedback received from the BS. The system performs approximately $\log(\mathcal{L})$ schedule updates where $\mathcal{L}$ is the expected lifetime of the system in number of data-gathering rounds. Moreover, each updation process uses the existing active schedule (data-flow path) - thus consuming only a small fraction of a single data gathering round activity. Such an algorithm thus could precisely incorporate the energy consumptions due to updates and related activities. Moreover, our algorithm does not assume any global knowledge of the topology or the positions of various sensors. Through simulation study, we found that our proposed algorithm achieves significantly higher network lifetime compared to existing data-flow schedules based on the Minimum Spanning Tree (MST), the Shortest Path Tree (SPT), the Weighted Rooted Tree (WRT).
A Secure Method for Signing in Using Quick Response Codes with Mobile Authentication
Venue: arXiv cs.CR 2013
Year: 2013

The emerging threats to user privacy over the internet are increasing at an alarming rate. Signing in from an unreliable terminal into a web account may result in compromising private details of a user such as username and password, by means of keylogger software. Such software are capable of recording keystrokes secretly, via covert channels without the knowledge of the user. In this paper we propose a secure method for signing in using Quick Response (QR) codes with mobile authentication. Through this method, the user can securely sign-in into a web account by authenticating the user session on an unreliable terminal browser, using a mobile device.
Scalable Locality-Sensitive Hashing for Similarity Search in High-Dimensional, Large-Scale Multimedia Datasets
Venue: arXiv cs.DC 2013
Year: 2013

Similarity search is critical for many database applications, including the increasingly popular online services for Content-Based Multimedia Retrieval (CBMR). These services, which include image search engines, must handle an overwhelming volume of data, while keeping low response times. Thus, scalability is imperative for similarity search in Web-scale applications, but most existing methods are sequential and target shared-memory machines. Here we address these issues with a distributed, efficient, and scalable index based on Locality-Sensitive Hashing (LSH). LSH is one of the most efficient and popular techniques for similarity search, but its poor referential locality properties has made its implementation a challenging problem. Our solution is based on a widely asynchronous dataflow parallelization with a number of optimizations that include a hierarchical parallelization to decouple indexing and data storage, locality-aware data partition strategies to reduce message passing, and multi-probing to limit memory usage. The proposed parallelization attained an efficiency of 90% in a distributed system with about 800 CPU cores. In particular, the original locality-aware data partition reduced the number of messages exchanged in 30%. Our parallel LSH was evaluated using the largest public dataset for similarity search (to the best of our knowledge) with $10^9$ 128-d SIFT descriptors extracted from Web images. This is two orders of magnitude larger than datasets that previous LSH parallelizations could handle.
Dynamic Load Balancing in GPU-Based Systems - Early Experiments
Venue: arXiv cs.DC 2013
Year: 2013

The dynamic load-balancing framework in Charm++/AMPI, developed at the University of Illinois, is based on using processor virtualization to allow thread migration across processors. This framework has been successfully applied to many scientific applications in the past, such as BRAMS, NAMD, ChaNGa, and others. Most of these applications use only CPUs to perform their operations. However, the use of GPUs to improve computational performance is quickly getting massively disseminated in the high-performance computing community. This paper aims to investigate how the same Charm++/AMPI framework can be extended to balance load in a synthetic application inspired by the BRAMS numerical forecast model, running mostly on GPUs rather than on CPUs. Many major questions involving the use of GPUs with AMPI where handled in this work, including: how to measure the GPU's load, how to use and share GPUs among user-level threads, and what results are obtained when applying the mandatory over-decomposition technique to a GPU-accelerated program.
A Nash Equilibrium Need Not Exist in the Locational Marginal Pricing Mechanism
Venue: arXiv cs.GT 2013
Year: 2013

Locational marginal pricing (LMP) is a widely employed method for pricing electricity in the wholesale electricity market. Although it is well known that the LMP mechanism is vulnerable to market manipulation, there is little literature providing a systematic analysis of this phenomenon. In the first part of this paper, we investigate the economic dispatch outcomes of the LMP mechanism with strategic agents. We show via counterexamples, that contrary to popular belief, a Nash equilibrium may not exist. And when it exists, the price of anarchy may be arbitrarily large. We then provide two sufficient conditions under either of which an efficient Nash equilibria exists. Last, we propose a new market mechanism for electricity markets, the Power Network Second Price (PNSP) mechanism that always induces an efficient Nash equilibrium. We briefly address the extensions on the demand side.
A Hybrid Linear Logic for Constrained Transition Systems with Applications to Molecular Biology
Venue: arXiv cs.LO 2013
Year: 2013

Linear implication can represent state transitions, but real transition systems operate under temporal, stochastic or probabilistic constraints that are not directly representable in ordinary linear logic. We propose a general modal extension of intuitionistic linear logic where logical truth is indexed by constraints and hybrid connectives combine constraint reasoning with logical reasoning. The logic has a focused cut-free sequent calculus that can be used to internalize the rules of particular constrained transition systems; we illustrate this with an adequate encoding of the synchronous stochastic pi-calculus. We also present some preliminary experiments of direct encoding of biological systems in the logic.
M-ary Detection and q-ary Decoding in Large-Scale MIMO: A Non-Binary Belief Propagation Approach
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose a non-binary belief propagation approach (NB-BP) for detection of $M$-ary modulation symbols and decoding of $q$-ary LDPC codes in large-scale multiuser MIMO systems. We first propose a message passing based symbol detection algorithm which computes vector messages using a scalar Gaussian approximation of interference, which results in a total complexity of just $O(KN\sqrt{M})$, where $K$ is the number of uplink users and $N$ is the number of base station (BS) antennas. The proposed NB-BP detector does not need to do a matrix inversion, which gives a complexity advantage over MMSE detection. We then design optimized $q$-ary LDPC codes by matching the EXIT charts of the proposed detector and the LDPC decoder. Simulation results show that the proposed NB-BP detection-decoding approach using the optimized LDPC codes achieve significantly better performance (by about 1 dB to 7 dB at $10^{-5}$ coded BER for various system loading factors with number of users ranging from 16 to 128 and number of BS antennas fixed at 128) compared to using linear detectors (e.g., MMSE detector) and off-the-shelf $q$-ary irregular LDPC codes. Also, even with estimated channel knowledge (e.g., with MMSE channel estimate), the performance of the proposed NB-BP detector is better than that of the MMSE detector.
An Improved Majority-Logic Decoder Offering Massively Parallel Decoding for Real-Time Control in Embedded Systems
Venue: arXiv cs.IT 2013
Year: 2013

We propose an easy-to-implement hard-decision majority-logic decoding algorithm for Reed-Muller codes RM(r,m) with m >= 3, m/2 >= r >= 1. The presented algorithm outperforms the best known majority-logic decoding algorithms and offers highly parallel decoding. The result is of special importance for safety- and time-critical applications in embedded systems. A simple combinational circuit can perform the proposed decoding. In particular, we show how our decoder for the three-error-correcting code RM(2,5) of dimension 16 and length 32 can be realized on hardware level.
Electrotactile vision substitution for 3D trajectory following
Venue: arXiv cs.HC 2013
Year: 2013

Navigation for blind persons represents a challenge for researchers in vision substitution. In this field, one of the used techniques to navigate is guidance. In this study, we develop a new approach for 3D trajectory following in which the requested task is to track a light path using computer input devices (keyboard and mouse) or a rigid body handled in front of a stereoscopic camera. The light path is visualized either on direct vision or by way of a electro-stimulation device, the Tongue Display Unit, a 12x12 matrix of electrodes. We improve our method by a series of experiments in which the effect of the modality of perception and that of the input device. Preliminary results indicated a close correlation between the stimulated and recorded trajectories.
Matching LBO eigenspace of non-rigid shapes via high order statistics
Venue: arXiv cs.GR 2013
Year: 2013

A fundamental tool in shape analysis is the virtual embedding of the Riemannian manifold describing the geometry of a shape into Euclidean space. Several methods have been proposed to embed isometric shapes in flat domains while preserving distances measured on the manifold. Recently, attention has been given to embedding shapes into the eigenspace of the Lapalce-Beltrami operator. The Laplace-Beltrami eigenspace preserves the diffusion distance, and is invariant under isometric transformations. However, Laplace-Beltrami eigenfunctions computed independently for different shapes are often incompatible with each other. Applications involving multiple shapes, such as pointwise correspondence, would greatly benefit if their respective eigenfunctions were somehow matched. Here, we introduce a statistical approach for matching eigenfunctions. We consider the values of the eigenfunctions over the manifold as sampling of random variables, and try to match their multivariate distributions. Comparing distributions is done indirectly, using high order statistics. We show that the permutation and sign ambiguities of low order eigenfunctions, can be inferred by minimizing the difference of their third order moments. The sign ambiguities of antisymmetric eigenfunctions can be resolved by exploiting isometric invariant relations between the gradients of the eigenfunctions and the surface normal. We present experiments demonstrating the success of the proposed method applied to feature point correspondence.
Choreography Synthesis as Contract Agreement
Venue: arXiv cs.LO 2013
Year: 2013

We propose a formal model for distributed systems, where each participant advertises its requirements and obligations as behavioural contracts, and where multiparty sessions are started when a set of contracts allows to synthesise a choreography. Our framework is based on the CO2 calculus for contract-oriented computing, and borrows concepts and results from the session type literature. It supports sessions where the number of participants is not determined beforehand, and keeps CO2's ability to rule out participants that are culpable if contracts are not fulfilled at runtime. We show that we have progress and session fidelity in CO2, as a result of the honesty of participants - i.e., their ability to always adhere to their contracts.
ABS-NET: Fully Decentralized Runtime Adaptation for Distributed Objects
Venue: arXiv cs.DC 2013
Year: 2013

We present a formalized, fully decentralized runtime semantics for a core subset of ABS, a language and framework for modelling distributed object-oriented systems. The semantics incorporates an abstract graph representation of a network infrastructure, with network endpoints represented as graph nodes, and links as arcs with buffers, corresponding to OSI layer 2 interconnects. The key problem we wish to address is how to allocate computational tasks to nodes so that certain performance objectives are met. To this end, we use the semantics as a foundation for performing network-adaptive task execution via object migration between nodes. Adaptability is analyzed in terms of three Quality of Service objectives: node load, arc load and message latency. We have implemented the key parts of our semantics in a simulator and evaluated how well objectives are achieved for some application-relevant choices of network topology, migration procedure and ABS program. The evaluation suggests that it is feasible in a decentralized setting to continually meet both the objective of a node-balanced task allocation and make headway towards minimizing communication, and thus arc load and message latency.
Energy-Efficient Cooperative Protocols for Full-Duplex Relay Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this work, energy-efficient cooperative protocols are studied for full-duplex relaying (FDR) with loopback interference. In these protocols, relay assistance is only sought under certain conditions on the different link outages to ensure effective cooperation. Recently, an energy-efficient selective decode-and-forward protocol was proposed for FDR, and was shown to outperform existing schemes in terms of outage. Here, we propose an incremental selective decode-and-forward protocol that offers additional power savings, while keeping the same outage performance. We compare the performance of the two protocols in terms of the end-to-end signal-to-noise ratio cumulative distribution function via closed-form expressions. Finally, we corroborate our theoretical results with simulation, and show the relative relay power savings in comparison to non-selective cooperation in which the relay cooperates regardless of channel conditions.
Society Functions Best with an Intermediate Level of Creativity
Venue: arXiv cs.MA 2013
Year: 2013

In a society, a proportion of the individuals can benefit from creativity without being creative themselves by copying the creators. This paper uses an agent-based model of cultural evolution to investigate how society is affected by different levels of individual creativity. We performed a time series analysis of the mean fitness of ideas across the artificial society varying both the percentage of creators, C, and how creative they are, p using two discounting methods. Both analyses revealed a valley in the adaptive landscape, indicating a tradeoff between C and p. The results suggest that excess creativity at the individual level can be detrimental at the level of the society because creators invest in unproven ideas at the expense of propagating proven ideas.
High-order algorithms for solving eigenproblems over discrete surfaces
Venue: arXiv cs.NA 2013
Year: 2013

The eigenvalue problem of the Laplace-Beltrami operators on curved surfaces plays an essential role in the convergence analysis of the numerical simulations of some important geometric partial differential equations which involve this operator. In this note we shall combine the local tangential lifting (LTL) method with the configuration equation to develop a new effective and convergent algorithm to solve the eigenvalue problems of the Laplace-Beltrami operators acting on functions over discrete surfaces. The convergence rates of our algorithms of discrete Laplace-Beltrami operators over surfaces is $O(r^n)$, $n \geq 1$, where $r$ represents the size of the mesh of discretization of the surface. The problem of high-order accuracies will also be discussed and used to compute geometric invariants of the underlying surfaces. Some convergence tests and eigenvalue computations on the sphere, tori and a dumbbell are presented.
Scalable Boolean Tensor Factorizations using Random Walks
Venue: arXiv cs.DS 2013
Year: 2013

Tensors are becoming increasingly common in data mining, and consequently, tensor factorizations are becoming more and more important tools for data miners. When the data is binary, it is natural to ask if we can factorize it into binary factors while simultaneously making sure that the reconstructed tensor is still binary. Such factorizations, called Boolean tensor factorizations, can provide improved interpretability and find Boolean structure that is hard to express using normal factorizations. Unfortunately the algorithms for computing Boolean tensor factorizations do not usually scale well. In this paper we present a novel algorithm for finding Boolean CP and Tucker decompositions of large and sparse binary tensors. In our experimental evaluation we show that our algorithm can handle large tensors and accurately reconstructs the latent Boolean structure.
Traffic Control for Network Protection Against Spreading Processes
Venue: arXiv cs.SY 2013
Year: 2013

Epidemic outbreaks in human populations are facilitated by the underlying transportation network. We consider strategies for containing a viral spreading process by optimally allocating a limited budget to three types of protection resources: (i) Traffic control resources, (ii), preventative resources and (iii) corrective resources. Traffic control resources are employed to impose restrictions on the traffic flowing across directed edges in the transportation network. Preventative resources are allocated to nodes to reduce the probability of infection at that node (e.g. vaccines), and corrective resources are allocated to nodes to increase the recovery rate at that node (e.g. antidotes). We assume these resources have monetary costs associated with them, from which we formalize an optimal budget allocation problem which maximizes containment of the infection. We present a polynomial time solution to the optimal budget allocation problem using Geometric Programming (GP) for an arbitrary weighted and directed contact network and a large class of resource cost functions. We illustrate our approach by designing optimal traffic control strategies to contain an epidemic outbreak that propagates through a real-world air transportation network.