OpenRaiser/Intern-Atlas huggingface dataset:
League Championship Algorithm Based Job Scheduling Scheme for Infrastructure as a Service Cloud
Venue: arXiv cs.DC 2014
Year: 2014

League Championship Algorithm (LCA) is a sports-inspired population based algorithmic framework for global optimization over a continuous search space first proposed by Ali Husseinzadeh Kashan in the year 2009. A common characteristic between all population based optimization algorithms similar to the LCA is that, they attemt to move a population of achievable solutions to potential areas of the search space during optimization. In this paper, we proposed a job scheduling algorithm based on the L CA optimization technique for the infrastructure as a service (IaaS) cloud. Three other established algorithms i.e. First Come First Served (FCFS), Last Job First (LJF) and Best Effort First (BEF) were used to evaluate the performance of the proposed algorithm. All four algorithms assumed to be non-preemptive. The parameters used for this experiment are the average response time and the average completion time. The results obtained shows that, LCA scheduling algorithm perform moderately better than the other algorithms as the number of virtual machines increases.
Recognition of cDNA microarray image Using Feedforward artificial neural network
Venue: arXiv cs.CV 2014
Year: 2014

The complementary DNA (cDNA) sequence is considered to be the magic biometric technique for personal identification. In this paper, we present a new method for cDNA recognition based on the artificial neural network (ANN). Microarray imaging is used for the concurrent identification of thousands of genes. We have segmented the location of the spots in a cDNA microarray. Thus, a precise localization and segmenting of a spot are essential to obtain a more accurate intensity measurement, leading to a more precise expression measurement of a gene. The segmented cDNA microarray image is resized and it is used as an input for the proposed artificial neural network. For matching and recognition, we have trained the artificial neural network. Recognition results are given for the galleries of cDNA sequences . The numerical results show that, the proposed matching technique is an effective in the cDNA sequences process. We also compare our results with previous results and find out that, the proposed technique is an effective matching performance.
Unit-length embedding of cycles and paths on grid graphs
Venue: arXiv cs.DM 2014
Year: 2014

Although there are very algorithms for embedding graphs on unbounded grids, only few results on embedding or drawing graphs on restricted grids has been published. In this work, we consider the problem of embedding paths and cycles on grid graphs. We give the necessary and sufficient conditions for the existence of cycles of given length $k$ and paths of given length $k$ between two given vertices in $n$-vertex rectangular grid graphs and introduce two algorithms with running times O$(k)$ and O$(k^2)$ for finding respectively such cycles and paths. Also, we extend our results to $m\times n\times o$ 3D grids. Our method for finding cycle of length $k$ in rectangular grid graphs also introduces a linear-time algorithm for finding cycles of a given length $k$ in hamiltonian solid grid graphs.
Importance of realistic mobility models for vanet network simulation
Venue: arXiv cs.NI 2014
Year: 2014

In the performance evaluation of a protocol for a vehicular ad hoc network, the protocol should be tested under a realistic conditions including, representative data traffic models, and realistic movements of the mobile nodes which are the vehicles (i.e., a mobility model). This work is a comparative study between two mobility models that are used in the simulations of vehicular networks, i.e., MOVE (MObility model generator for VEhicular networks) and CityMob, a mobility pattern generator for VANET. We describe several mobility models for VANET simulations. In this paper we aim to show that the mobility models can significantly affect the simulation results in VANET networks. The results presented in this article prove the importance of choosing a suitable real world scenario for performances studies of routing protocols in this kind of network.
Extending Probabilistic Data Fusion Using Sliding Windows
Venue: arXiv cs.IR 2014
Year: 2014

Recent developments in the field of data fusion have seen a focus on techniques that use training queries to estimate the probability that various documents are relevant to a given query and use that information to assign scores to those documents on which they are subsequently ranked. This paper introduces SlideFuse, which builds on these techniques, introducing a sliding window in order to compensate for situations where little relevance information is available to aid in the estimation of probabilities. SlideFuse is shown to perform favourably in comparison with CombMNZ, ProbFuse and SegFuse. CombMNZ is the standard baseline technique against which data fusion algorithms are compared whereas ProbFuse and SegFuse represent the state-of-the-art for probabilistic data fusion methods.
More Natural Models of Electoral Control by Partition
Venue: arXiv cs.GT 2014
Year: 2014

"Control" studies attempts to set the outcome of elections through the addition, deletion, or partition of voters or candidates. The set of benchmark control types was largely set in the seminal 1992 paper by Bartholdi, Tovey, and Trick that introduced control, and there now is a large literature studying how many of the benchmark types various election systems are vulnerable to, i.e., have polynomial-time attack algorithms for. However, although the longstanding benchmark models of addition and deletion model relatively well the real-world settings that inspire them, the longstanding benchmark models of partition model settings that are arguably quite distant from those they seek to capture. In this paper, we introduce--and for some important cases analyze the complexity of--new partition models that seek to better capture many real-world partition settings. In particular, in many partition settings one wants the two parts of the partition to be of (almost) equal size, or is partitioning into more than two parts, or has groups of actors who must be placed in the same part of the partition. Our hope is that having these new partition types will allow studies of control attacks to include such models that more realistically capture many settings.
Technical Report: Towards Efficient Indexing of Spatiotemporal Trajectories on the GPU for Distance Threshold Similarity Searches
Venue: arXiv cs.DC 2014
Year: 2014

Applications in many domains require processing moving object trajectories. In this work, we focus on a trajectory similarity search that finds all trajectories within a given distance of a query trajectory over a time interval, which we call the distance threshold similarity search. We develop three indexing strategies with spatial, temporal and spatiotemporal selectivity for the GPU that differ significantly from indexes suitable for the CPU, and show the conditions under which each index achieves good performance. Furthermore, we show that the GPU implementations outperform multithreaded CPU implementations in a range of experimental scenarios, making the GPU an attractive technology for processing moving object trajectories. We test our implementations on two synthetic and one real-world dataset of a galaxy merger.
A concavity property for the reciprocal of Fisher information and its consequences on Costa's EPI
Venue: arXiv cs.IT 2014
Year: 2014

We prove that the reciprocal of Fisher information of a log-concave probability density $X$ in ${\bf{R}}^n$ is concave in $t$ with respect to the addition of a Gaussian noise $Z_t = N(0, tI_n)$. As a byproduct of this result we show that the third derivative of the entropy power of a log-concave probability density $X$ in ${\bf{R}}^n$ is nonnegative in $t$ with respect to the addition of a Gaussian noise $Z_t$. For log-concave densities this improves the well-known Costa's concavity property of the entropy power.
Faster Sorting Networks for $17$, $19$ and $20$ Inputs
Venue: arXiv cs.DS 2014
Year: 2014

We present new parallel sorting networks for $17$ to $20$ inputs. For $17, 19,$ and $20$ inputs these new networks are faster (i.e., they require less computation steps) than the previously known best networks. Therefore, we improve upon the known upper bounds for minimal depth sorting networks on $17, 19,$ and $20$ channels. The networks were obtained using a combination of hand-crafted first layers and a SAT encoding of sorting networks.
Multiuser Joint Energy-Bandwidth Allocation with Energy Harvesting - Part II: Multiple Broadcast Channels & Proportional Fairness
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the energy-bandwidth allocation for a network with multiple broadcast channels, where the transmitters access the network orthogonally on the assigned frequency band and each transmitter communicates with multiple receivers orthogonally or non-orthogonally. We assume that the energy harvesting state and channel gain of each transmitter can be predicted for $K$ slots {\em a priori}. To maximize the weighted throughput, we formulate an optimization problem with $O(MK)$ constraints, where $M$ is the number of the receivers, and decompose it into the energy and bandwidth allocation subproblems. In order to use the iterative algorithm proposed in [1] to solve the problem, we propose efficient algorithms to solve the two subproblems, so that the optimal energy-bandwidth allocation can be obtained with an overall complexity of ${\cal O}(MK^2)$, even though the problem is non-convex when the broadcast channel is non-orthogonal. For the orthogonal broadcast channel, we further formulate a proportionally-fair (PF) throughput maximization problem and derive the equivalence conditions such that the optimal solution can be obtained by solving a weighted throughput maximization problem. Further, the algorithm to obtain the proper weights is proposed. Simulation results show that the proposed algorithm can make efficient use of the harvested energy and the available bandwidth, and achieve significantly better performance than some heuristic policies for energy and bandwidth allocation. Moreover, it is seen that with energy-harvesting transmitters, non-orthogonal broadcast offers limited gain over orthogonal broadcast.
The Henchman Problem: Measuring Secrecy by the Minimum Distortion in a List
Venue: arXiv cs.IT 2014
Year: 2014

We introduce a new measure of information-theoretic secrecy based on rate-distortion theory and study it in the context of the Shannon cipher system. Whereas rate-distortion theory is traditionally concerned with a single reconstruction sequence, in this work we suppose that an eavesdropper produces a list of $2^{nR_{\sf L}}$ reconstruction sequences and measure secrecy by the minimum distortion over the entire list. We show that this setting is equivalent to one in which an eavesdropper must reconstruct a single sequence, but also receives side information about the source sequence and public message from a rate-limited henchman (a helper for an adversary). We characterize the optimal tradeoff of secret key rate, list rate, and eavesdropper distortion. The solution hinges on a problem of independent interest: lossy compression of a codeword drawn uniformly from a random codebook. We also characterize the solution to the lossy communication version of the problem in which distortion is allowed at the legitimate receiver. The analysis in both settings is greatly aided by a recent technique for proving source coding results with the use of a likelihood encoder.
Optimizing Pilot Length for a Go/No-Go Decision in Two-State Block Fading Channels with Feedback
Venue: arXiv cs.IT 2014
Year: 2014

We propose an approach where each user independently seeks to minimize the amount of time that they occupy the channel. Essentially, we seek to minimize the number of transmitted symbols required to communicate a packet assuming variable-length coding with feedback. Users send a pilot sequence to estimate the channel quality and decide whether to proceed with a transmission or wait for the next opportunity. Thus a user may choose to leave the channel even though it has already gained access, in order to increase the network throughput and also save its own energy resources. This paper optimizes the number of pilots and the channel identification threshold to minimize the total number of transmitted symbols (including pilots) required to communicate the packet. We prove a sufficient condition for the optimal pilot length and the channel identification threshold. This optimal parameter pair is solved numerically and the reduction in channel occupancy is shown for various channel settings.
Batch Codes through Dense Graphs without Short Cycles
Venue: arXiv cs.IT 2014
Year: 2014

Consider a large database of $n$ data items that need to be stored using $m$ servers. We study how to encode information so that a large number $k$ of read requests can be performed in parallel while the rate remains constant (and ideally approaches one). This problem is equivalent to the design of multiset Batch Codes introduced by Ishai, Kushilevitz, Ostrovsky and Sahai [17]. We give families of multiset batch codes with asymptotically optimal rates of the form $1-1/\text{poly}(k)$ and a number of servers $m$ scaling polynomially in the number of read requests $k$. An advantage of our batch code constructions over most previously known multiset batch codes is explicit and deterministic decoding algorithms and asymptotically optimal fault tolerance. Our main technical innovation is a graph-theoretic method of designing multiset batch codes using dense bipartite graphs with no small cycles. We modify prior graph constructions of dense, high-girth graphs to obtain our batch code results. We achieve close to optimal tradeoffs between the parameters for bipartite graph based batch codes.
Direct Processing of Document Images in Compressed Domain
Venue: arXiv cs.CV 2014
Year: 2014

With the rapid increase in the volume of Big data of this digital era, fax documents, invoices, receipts, etc are traditionally subjected to compression for the efficiency of data storage and transfer. However, in order to process these documents, they need to undergo the stage of decompression which indents additional computing resources. This limitation induces the motivation to research on the possibility of directly processing of compressed images. In this research paper, we summarize the research work carried out to perform different operations straight from run-length compressed documents without going through the stage of decompression. The different operations demonstrated are feature extraction; text-line, word and character segmentation; document block segmentation; and font size detection, all carried out in the compressed version of the document. Feature extraction methods demonstrate how to extract the conventionally defined features such as projection profile, run-histogram and entropy, directly from the compressed document data. Document segmentation involves the extraction of compressed segments of text-lines, words and characters using the vertical and horizontal projection profile features. Further an attempt is made to segment randomly a block of interest from the compressed document and subsequently facilitate absolute and relative characterization of the segmented block which finds real time applications in automatic processing of Bank Cheques, Challans, etc, in compressed domain. Finally an application to detect font size at text line level is also investigated. All the proposed algorithms are validated experimentally with sufficient data set of compressed documents.
An Algorithm for Mining High Utility Closed Itemsets and Generators
Venue: arXiv cs.DB 2014
Year: 2014

Traditional association rule mining based on the support-confidence framework provides the objective measure of the rules that are of interest to users. However, it does not reflect the utility of the rules. To extract non-redundant association rules in support-confidence framework frequent closed itemsets and their generators play an important role. To extract non-redundant association rules among high utility itemsets, high utility closed itemsets (HUCI) and their generators should be extracted in order to apply traditional support-confidence framework. However, no efficient method exists at present for mining HUCIs with their generators. This paper addresses this issue. A post-processing algorithm, called the HUCI-Miner, is proposed to mine HUCIs with their generators. The proposed algorithm is implemented using both synthetic and real datasets.
QoE Support for Multi-Layered Multimedia Applications
Venue: arXiv cs.NI 2014
Year: 2014

Congestion control protocol and bandwidth allocation problems are often formulated into Network Utility Maximization (NUM) framework. Existing solutions for NUM generally focus on single-layered applications. As applications such as video streaming grow in importance and popularity, addressing user utility function for these multi-layered multimedia applications in NUM formulation becomes vital. In this paper, we propose a new multi-layered user utility model that leverages on studies of human visual perception and quality of experience (QoE) from the fields of computer graphics and human computer interaction (HCI). Using this new utility model to investigate network activities, we demonstrate that solving NUM with multi-layered utility is intractable, and that rate allocation and network pricing may oscillate due to user behavior specific to multi-layered applications. To address this, we propose a new approach for admission control to ensure quality of service (QoS) and quality of experience (QoE).
Secret Image Sharing Using Grayscale Payload Decomposition and Irreversible Image Steganography
Venue: arXiv cs.MM 2014
Year: 2014

To provide an added security level most of the existing reversible as well as irreversible image steganography schemes emphasize on encrypting the secret image (payload) before embedding it to the cover image. The complexity of encryption for a large payload where the embedding algorithm itself is complex may adversely affect the steganographic system. Schemes that can induce same level of distortion, as any standard encryption technique with lower computational complexity, can improve the performance of stego systems. In this paper we propose a secure secret image sharing scheme, which bears minimal computational complexity. The proposed scheme, as a replacement for encryption, diversifies the payload into different matrices which are embedded into carrier image (cover image) using bit X-OR operation. A payload is a grayscale image which is divided into frequency matrix, error matrix, and sign matrix. The frequency matrix is scaled down using a mapping algorithm to produce Down Scaled Frequency (DSF) matrix. The DSF matrix, error matrix, and sign matrix are then embedded in different cover images using bit X-OR operation between the bit planes of the matrices and respective cover images. Analysis of the proposed scheme shows that it effectively camouflages the payload with minimum computation time.
Characteristic Length and Clustering
Venue: arXiv cs.DM 2014
Year: 2014

We explore relations between various variational problems for graphs like Euler characteristic chi(G), characteristic length mu(G), mean clustering nu(G), inductive dimension iota(G), edge density epsilon(G), scale measure sigma(G), Hilbert action eta(G) and spectral complexity xi(G). A new insight in this note is that the local cluster coefficient C(x) in a finite simple graph can be written as a relative characteristic length L(x) of the unit sphere S(x) within the unit ball B(x) of a vertex. This relation L(x) = 2-C(x) will allow to study clustering in more general metric spaces like Riemannian manifolds or fractals. If eta is the average of scalar curvature s(x), a formula mu ~ 1+log(epsilon)/log(eta) of Newman, Watts and Strogatz relates mu with the edge density epsilon and average scalar curvature eta telling that large curvature correlates with small characteristic length. Experiments show that the statistical relation mu ~ log(1/nu) holds for random or deterministic constructed networks, indicating that small clustering is often associated to large characteristic lengths and lambda=mu/log(nu) can converge in some graph limits of networks. Mean clustering nu, edge density epsilon and curvature average eta therefore can relate with characteristic length mu on a statistical level. We also discovered experimentally that inductive dimension iota and cluster-length ratio lambda correlate strongly on Erdos-Renyi probability spaces.
Evidence of spatial embedding in the IPv4 router-level Internet network
Venue: arXiv cs.NI 2014
Year: 2014

Much interest has been taken in understanding the global routing structure of the Internet, both to model and protect the current structures and to modify the structure to improve resilience. These studies rely on trace-routes and algorithmic inference to resolve individual IP addresses into connected routers, yielding a network of routers. Using WHOIS registries, parsing of DNS registries, as well as simple latency-based triangulation, these routers can often be geolocated to at least their country of origin, if not specific regions. In this work, we use node subgraph summary statistics to present evidence that the router-level (IPv4) network is spatially embedded, with the similarity (or dissimilarity) of a node from it's neighbor strongly correlating with the attributes of other routers residing in the same country or region. We discuss these results in context of the recently proposed gravity models of the Internet, as well as the potential application to geolocation inferrence.
Behavioral Metrics via Functor Lifting
Venue: arXiv cs.LO 2014
Year: 2014

We study behavioral metrics in an abstract coalgebraic setting. Given a coalgebra alpha: X -> FX in Set, where the functor F specifies the branching type, we define a framework for deriving pseudometrics on X which measure the behavioral distance of states. A first crucial step is the lifting of the functor F on Set to a functor in the category PMet of pseudometric spaces. We present two different approaches which can be viewed as generalizations of the Kantorovich and Wasserstein pseudometrics for probability measures. We show that the pseudometrics provided by the two approaches coincide on several natural examples, but in general they differ. Then a final coalgebra for F in Set can be endowed with a behavioral distance resulting as the smallest solution of a fixed-point equation, yielding the final coalgebra in PMet. The same technique, applied to an arbitrary coalgebra alpha: X -> FX in Set, provides the behavioral distance on X. Under some constraints we can prove that two states are at distance 0 if and only if they are behaviorally equivalent.
Testing Poisson Binomial Distributions
Venue: arXiv cs.DS 2014
Year: 2014

A Poisson Binomial distribution over $n$ variables is the distribution of the sum of $n$ independent Bernoullis. We provide a sample near-optimal algorithm for testing whether a distribution $P$ supported on $\{0,...,n\}$ to which we have sample access is a Poisson Binomial distribution, or far from all Poisson Binomial distributions. The sample complexity of our algorithm is $O(n^{1/4})$ to which we provide a matching lower bound. We note that our sample complexity improves quadratically upon that of the naive "learn followed by tolerant-test" approach, while instance optimal identity testing [VV14] is not applicable since we are looking to simultaneously test against a whole family of distributions.