OpenRaiser/Intern-Atlas huggingface dataset:
On the Dynamics of a Recurrent Hopfield Network
Venue: arXiv cs.NE 2015
Year: 2015

In this research paper novel real/complex valued recurrent Hopfield Neural Network (RHNN) is proposed. The method of synthesizing the energy landscape of such a network and the experimental investigation of dynamics of Recurrent Hopfield Network is discussed. Parallel modes of operation (other than fully parallel mode) in layered RHNN is proposed. Also, certain potential applications are proposed.
Derandomized Construction of Combinatorial Batch Codes
Venue: arXiv cs.DM 2015
Year: 2015

Combinatorial Batch Codes (CBCs), replication-based variant of Batch Codes introduced by Ishai et al. in STOC 2004, abstracts the following data distribution problem: $n$ data items are to be replicated among $m$ servers in such a way that any $k$ of the $n$ data items can be retrieved by reading at most one item from each server with the total amount of storage over $m$ servers restricted to $N$. Given parameters $m, c,$ and $k$, where $c$ and $k$ are constants, one of the challenging problems is to construct $c$-uniform CBCs (CBCs where each data item is replicated among exactly $c$ servers) which maximizes the value of $n$. In this work, we present explicit construction of $c$-uniform CBCs with $Ω(m^{c-1+{1 \over k}})$ data items. The construction has the property that the servers are almost regular, i.e., number of data items stored in each server is in the range $[{nc \over m}-\sqrt{{n\over 2}\ln (4m)}, {nc \over m}+\sqrt{{n \over 2}\ln (4m)}]$. The construction is obtained through better analysis and derandomization of the randomized construction presented by Ishai et al. Analysis reveals almost regularity of the servers, an aspect that so far has not been addressed in the literature. The derandomization leads to explicit construction for a wide range of values of $c$ (for given $m$ and $k$) where no other explicit construction with similar parameters, i.e., with $n = Ω(m^{c-1+{1 \over k}})$, is known. Finally, we discuss possibility of parallel derandomization of the construction.
Adaptive Random SubSpace Learning (RSSL) Algorithm for Prediction
Venue: arXiv cs.LG 2015
Year: 2015

We present a novel adaptive random subspace learning algorithm (RSSL) for prediction purpose. This new framework is flexible where it can be adapted with any learning technique. In this paper, we tested the algorithm for regression and classification problems. In addition, we provide a variety of weighting schemes to increase the robustness of the developed algorithm. These different wighting flavors were evaluated on simulated as well as on real-world data sets considering the cases where the ratio between features (attributes) and instances (samples) is large and vice versa. The framework of the new algorithm consists of many stages: first, calculate the weights of all features on the data set using the correlation coefficient and F-statistic statistical measurements. Second, randomly draw n samples with replacement from the data set. Third, perform regular bootstrap sampling (bagging). Fourth, draw without replacement the indices of the chosen variables. The decision was taken based on the heuristic subspacing scheme. Fifth, call base learners and build the model. Sixth, use the model for prediction purpose on test set of the data. The results show the advancement of the adaptive RSSL algorithm in most of the cases compared with the synonym (conventional) machine learning algorithms.
Secure Degrees of Freedom Region of the Two-User MISO Broadcast Channel with Alternating CSIT
Venue: arXiv cs.IT 2015
Year: 2015

The two user multiple-input single-output (MISO) broadcast channel with confidential messages (BCCM) is studied in which the nature of channel state information at the transmitter (CSIT) from each user can be of the form $I_{i}$, $i=1,2$ where $I_{1}, I_{2}\in \{\mathsf{P}, \mathsf{D}, \mathsf{N}\}$, and the forms $\mathsf{P}$, $\mathsf{D}$ and $\mathsf{N}$ correspond to perfect and instantaneous, completely delayed, and no CSIT, respectively. Thus, the overall CSIT can alternate between $9$ possible states corresponding to all possible values of $I_{1}I_{2}$, with each state occurring for $λ_{I_{1}I_{2}}$ fraction of the total duration. The main contribution of this paper is to establish the secure degrees of freedom (s.d.o.f.) region of the MISO BCCM with alternating CSIT with the symmetry assumption, where $λ_{I_{1} I_{2}}=λ_{I_{2}I_{1}}$. The main technical contributions include developing a) novel achievable schemes for MISO BCCM with alternating CSIT with security constraints which also highlight the synergistic benefits of inter-state coding for secrecy, b) new converse proofs via local statistical equivalence and channel enhancement; and c) showing the interplay between various aspects of channel knowledge and their impact on s.d.o.f.
Virtual Network Embedding Algorithms Based on Best-Fit Subgraph Detection
Venue: arXiv cs.DC 2015
Year: 2015

One of the main objectives of cloud computing providers is increasing the revenue of their cloud datacenters by accommodating virtual network requests as many as possible. However, arrival and departure of virtual network requests fragment physical network's resources and reduce the possibility of accepting more virtual network requests. To increase the number of virtual network requests accommodated by fragmented physical networks, we propose two virtual network embedding algorithms, which coarsen virtual networks using Heavy Edge Matching (HEM) technique and embed coarsened virtual networks on best-fit sub-substrate networks. The performance of the proposed algorithms are evaluated and compared with existing algorithms using extensive simulations, which show that the proposed algorithms increase the acceptance ratio and the revenue.
The Wisdom of the Few? "Supertaggers" in Collaborative Tagging Systems
Venue: arXiv cs.SI 2015
Year: 2015

A folksonomy is ostensibly an information structure built up by the "wisdom of the crowd", but is the "crowd" really doing the work? Tagging is in fact a sharply skewed process in which a small minority of "supertagger" users generate an overwhelming majority of the annotations. Using data from three large-scale social tagging platforms, we explore (a) how to best quantify the imbalance in tagging behavior and formally define a supertagger, (b) how supertaggers differ from other users in their tagging patterns, and (c) if effects of motivation and expertise inform our understanding of what makes a supertagger. Our results indicate that such prolific users not only tag more than their counterparts, but in quantifiably different ways. Specifically, we find that supertaggers are more likely to label content in the long tail of less popular items, that they show differences in patterns of content tagged and terms utilized, and are measurably different with respect to tagging expertise and motivation. These findings suggest we should question the extent to which folksonomies achieve crowdsourced classification via the "wisdom of the crowd", especially for broad folksonomies like Last.fm as opposed to narrow folksonomies like Flickr.
The Benefit of Sex in Noisy Evolutionary Search
Venue: arXiv cs.NE 2015
Year: 2015

The benefit of sexual recombination is one of the most fundamental questions both in population genetics and evolutionary computation. It is widely believed that recombination helps solving difficult optimization problems. We present the first result, which rigorously proves that it is beneficial to use sexual recombination in an uncertain environment with a noisy fitness function. For this, we model sexual recombination with a simple estimation of distribution algorithm called the Compact Genetic Algorithm (cGA), which we compare with the classical $μ+1$ EA. For a simple noisy fitness function with additive Gaussian posterior noise $\mathcal{N}(0,σ^2)$, we prove that the mutation-only $μ+1$ EA typically cannot handle noise in polynomial time for $σ^2$ large enough while the cGA runs in polynomial time as long as the population size is not too small. This shows that in this uncertain environment sexual recombination is provably beneficial. We observe the same behavior in a small empirical study.
On Forgetting in Tractable Propositional Fragments
Venue: arXiv cs.AI 2015
Year: 2015

Distilling from a knowledge base only the part that is relevant to a subset of alphabet, which is recognized as forgetting, has attracted extensive interests in AI community. In standard propositional logic, a general algorithm of forgetting and its computation-oriented investigation in various fragments whose satisfiability are tractable are still lacking. The paper aims at filling the gap. After exploring some basic properties of forgetting in propositional logic, we present a resolution-based algorithm of forgetting for CNF fragment, and some complexity results about forgetting in Horn, renamable Horn, q-Horn, Krom, DNF and CNF fragments of propositional logic.
Transaction Level Analysis for a Clustered and Hardware-Enhanced Task Manager on Homogeneous Many-Core Systems
Venue: arXiv cs.DC 2015
Year: 2015

The increasing parallelism of many-core systems demands for efficient strategies for the run-time system management. Due to the large number of cores the management overhead has a rising impact to the overall system performance. This work analyzes a clustered infrastructure of dedicated hardware nodes to manage a homogeneous many-core system. The hardware nodes implement a message passing protocol and perform the task mapping and synchronization at run-time. To make meaningful mapping decisions, the global management nodes employ a workload status communication mechanism. This paper discusses the design-space of the dedicated infrastructure by means of task mapping use-cases and a parallel benchmark including application-interference. We evaluate the architecture in terms of application speedup and analyze the mechanism for the status communication. A comparison versus centralized and fully-distributed configurations demonstrates the reduction of the computation and communication management overhead for our approach.
Real Time Implementation of Spatial Filtering On FPGA
Venue: arXiv cs.CV 2015
Year: 2015

Field Programmable Gate Array (FPGA) technology has gained vital importance mainly because of its parallel processing hardware which makes it ideal for image and video processing. In this paper, a step by step approach to apply a linear spatial filter on real time video frame sent by Omnivision OV7670 camera using Zynq Evaluation and Development board based on Xilinx XC7Z020 has been discussed. Face detection application was chosen to explain above procedure. This procedure is applicable to most of the complex image processing algorithms which needs to be implemented using FPGA.
Video Primal Sketch: A Unified Middle-Level Representation for Video
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a middle-level video representation named Video Primal Sketch (VPS), which integrates two regimes of models: i) sparse coding model using static or moving primitives to explicitly represent moving corners, lines, feature points, etc., ii) FRAME /MRF model reproducing feature statistics extracted from input video to implicitly represent textured motion, such as water and fire. The feature statistics include histograms of spatio-temporal filters and velocity distributions. This paper makes three contributions to the literature: i) Learning a dictionary of video primitives using parametric generative models; ii) Proposing the Spatio-Temporal FRAME (ST-FRAME) and Motion-Appearance FRAME (MA-FRAME) models for modeling and synthesizing textured motion; and iii) Developing a parsimonious hybrid model for generic video representation. Given an input video, VPS selects the proper models automatically for different motion patterns and is compatible with high-level action representations. In the experiments, we synthesize a number of textured motion; reconstruct real videos using the VPS; report a series of human perception experiments to verify the quality of reconstructed videos; demonstrate how the VPS changes over the scale transition in videos; and present the close connection between VPS and high-level action models.
A DCT And SVD based Watermarking Technique To Identify Tag
Venue: arXiv cs.MM 2015
Year: 2015

With the rapid development of the multimedia,the secure of the multimedia is get more concerned. as far as we know , Digital watermarking is an effective way to protect copyright. The watermark must be generally hidden does not affect the quality of the original image. In this paper,a novel way based on discrete cosine transform(DCT) and singular value decomposition(SVD) .In the proposed way,we decomposition the image into 8*8 blocks, next we use the DCT to get the transformed block,then we choose the diagonal to embed the information, after we do this, we recover the image and then we decomposition the image to 8*8 blocks,we use the SVD way to get the diagonal matrix and embed the information in the matrix. next we extract the information use both inverse of DCT and SVD, as we all know,after we embed the information seconded time , the information we first information we embed must be changed, we choose a measure way called Peak Signal to Noise Ratio(PSNR) to estimate the similarity of the two image, and set a threshold to ensure whether the information is same or not.
Gender Gap Through Time and Space: A Journey Through Wikipedia Biographies and the "WIGI" Index
Venue: arXiv cs.CY 2015
Year: 2015

In this study we investigate how quantification of Wikipedia biographies can shed light on worldwide longitudinal gender inequality trends. We present an academic index allowing comparative study of gender inequality through space and time, the Wikipedia Gender Index (WIGI), based on metadata available through the Wikidata database. Our research confirms that gender inequality is a phenomenon with a long history, but whose patterns can be analyzed and quantified on a larger scale than previously thought possible. Through the use of Inglehart- Welzel cultural clusters, we show that gender inequality can be analyzed with regards to world's cultures. In the dimension studied (coverage of females and other genders in reference works) we show a steadily improving trend, through one with aspects that deserve careful follow up analysis (such as the surprisingly high ranking of the Confucian and South Asian clusters). Keywords: data mining, Wikidata, Wikipedia, gender gap, demographics
Multiple Loop Self-Triggered Model Predictive Control for Network Scheduling and Control
Venue: arXiv cs.SY 2015
Year: 2015

We present an algorithm for controlling and scheduling multiple linear time-invariant processes on a shared bandwidth limited communication network using adaptive sampling intervals. The controller is centralized and computes at every sampling instant not only the new control command for a process, but also decides the time interval to wait until taking the next sample. The approach relies on model predictive control ideas, where the cost function penalizes the state and control effort as well as the time interval until the next sample is taken. The latter is introduced in order to generate an adaptive sampling scheme for the overall system such that the sampling time increases as the norm of the system state goes to zero. The paper presents a method for synthesizing such a predictive controller and gives explicit sufficient conditions for when it is stabilizing. Further explicit conditions are given which guarantee conflict free transmissions on the network. It is shown that the optimization problem may be solved off-line and that the controller can be implemented as a lookup table of state feedback gains. Simulation studies which compare the proposed algorithm to periodic sampling illustrate potential performance gains.
A Hybrid Approach for Improved Content-based Image Retrieval using Segmentation
Venue: arXiv cs.IR 2015
Year: 2015

The objective of Content-Based Image Retrieval (CBIR) methods is essentially to extract, from large (image) databases, a specified number of images similar in visual and semantic content to a so-called query image. To bridge the semantic gap that exists between the representation of an image by low-level features (namely, colour, shape, texture) and its high-level semantic content as perceived by humans, CBIR systems typically make use of the relevance feedback (RF) mechanism. RF iteratively incorporates user-given inputs regarding the relevance of retrieved images, to improve retrieval efficiency. One approach is to vary the weights of the features dynamically via feature reweighting. In this work, an attempt has been made to improve retrieval accuracy by enhancing a CBIR system based on color features alone, through implicit incorporation of shape information obtained through prior segmentation of the images. Novel schemes for feature reweighting as well as for initialization of the relevant set for improved relevance feedback, have also been proposed for boosting performance of RF- based CBIR. At the same time, new measures for evaluation of retrieval accuracy have been suggested, to overcome the limitations of existing measures in the RF context. Results of extensive experiments have been presented to illustrate the effectiveness of the proposed approaches.
Enhancing the Delay Performance of Dynamic Backpressure Algorithms
Venue: arXiv cs.IT 2015
Year: 2015

For general multi-hop queueing networks, delay optimal network control has unfortunately been an outstanding problem. The dynamic backpressure (BP) algorithm elegantly achieves throughput optimality, but does not yield good delay performance in general. In this paper, we obtain an asymptotically delay optimal control policy, which resembles the BP algorithm in basing resource allocation and routing on a backpressure calculation, but differs from the BP algorithm in the form of the backpressure calculation employed. The difference suggests a possible reason for the unsatisfactory delay performance of the BP algorithm, i.e., the myopic nature of the BP control. Motivated by this new connection, we introduce a new class of enhanced backpressure-based algorithms which incorporate a general queue-dependent bias function into the backpressure term of the traditional BP algorithm to improve delay performance. These enhanced algorithms exploit queue state information beyond one hop. We prove the throughput optimality and characterize the utility-delay tradeoff of the enhanced algorithms. We further focus on two specific distributed algorithms within this class, which have demonstrably improved delay performance as well as acceptable implementation complexity.
A Compressed-Gap Data-Aware Measure
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we consider the problem of efficiently representing a set $S$ of $n$ items out of a universe $U=\{0,...,u-1\}$ while supporting a number of operations on it. Let $G=g_1...g_n$ be the gap stream associated with $S$, $gap$ its bit-size when encoded with \emph{gap-encoding}, and $H_0(G)$ its empirical zero-order entropy. We prove that (1) $nH_0(G)\in o(gap)$ if $G$ is highly compressible, and (2) $nH_0(G) \leq n\log(u/n) + n \leq uH_0(S)$. Let $d$ be the number of \emph{distinct} gap lengths between elements in $S$. We firstly propose a new space-efficient zero-order compressed representation of $S$ taking $n(H_0(G)+1)+\mathcal O(d\log u)$ bits of space. Then, we describe a fully-indexable dictionary that supports \emph{rank} and \emph{select} queries in $\mathcal O(\log(u/n)+\log\log u)$ time while requiring asymptotically the same space as the proposed compressed representation of $S$.
A Full Frequency Masking Vocoder for Legal Eavesdropping Conversation Recording
Venue: arXiv cs.SD 2015
Year: 2015

This paper presents a new approach for a vocoder design based on full frequency masking by octaves in addition to a technique for spectral filling via beta probability distribution. Some psycho-acoustic characteristics of human hearing - inaudibility masking in frequency and phase - are used as a basis for the proposed algorithm. The results confirm that this technique may be useful to save bandwidth in applications requiring intelligibility. It is recommended for the legal eavesdropping of long voice conversations.
Albatross: a Privacy-Preserving Location Sharing System
Venue: arXiv cs.CR 2015
Year: 2015

Social networking services are increasingly accessed through mobile devices. This trend has prompted services such as Facebook and Google+ to incorporate location as a de facto feature of user interaction. At the same time, services based on location such as Foursquare and Shopkick are also growing as smartphone market penetration increases. In fact, this growth is happening despite concerns (growing at a similar pace) about security and third-party use of private location information (e.g., for advertising). Nevertheless, service providers have been unwilling to build truly private systems in which they do not have access to location information. In this paper, we describe an architecture and a trial implementation of a privacy-preserving location sharing system called Albatross. The system protects location information from the service provider and yet enables fine-grained location-sharing. One main feature of the system is to protect an individual's social network structure. The pattern of location sharing preferences towards contacts can reveal this structure without any knowledge of the locations themselves. Albatross protects locations sharing preferences through protocol unification and masking. Albatross has been implemented as a standalone solution, but the technology can also be integrated into location-based services to enhance privacy.
Solution sets for equations over free groups are EDT0L languages -- ICALP 2015 version
Venue: arXiv cs.LO 2015
Year: 2015

We show that, given a word equation over a finitely generated free group, the set of all solutions in reduced words forms an EDT0L language. In particular, it is an indexed language in the sense of Aho. The question of whether a description of solution sets in reduced words as an indexed language is possible has been been open for some years, apparently without much hope that a positive answer could hold. Nevertheless, our answer goes far beyond: they are EDT0L, which is a proper subclass of indexed languages. We can additionally handle the existential theory of equations with rational constraints in free products $\star_{1 \leq i \leq s}F_i$, where each $F_i$ is either a free or finite group, or a free monoid with involution. In all cases the result is the same: the set of all solutions in reduced words is EDT0L. This was known only for quadratic word equations by Ferté, Marin and Sénizergues (ToCS 2014), which is a very restricted case. Our general result became possible due to the recent recompression technique of Jeż. In this paper we use a new method to integrate solutions of linear Diophantine equations into the process and obtain more general results than in the related paper (arXiv 1405.5133). For example, we improve the complexity from quadratic nondeterministic space in (arXiv 1405.5133) to quasi-linear nondeterministic space here. This implies an improved complexity for deciding the existential theory of non-abelian free groups: NSPACE($n\log n$). The conjectured complexity is NP, however, we believe that our results are optimal with respect to space complexity, independent of the conjectured NP.