OpenRaiser/Intern-Atlas huggingface dataset:
Efficient and Robust Allocation Algorithms in Clouds under Memory Constraints
Venue: arXiv cs.DC 2013
Year: 2013

We consider robust resource allocation of services in Clouds. More specifically, we consider the case of a large public or private Cloud platform that runs a relatively small set of large and independent services. These services are characterized by their demand along several dimensions (CPU, memory,...) and by their quality of service requirements, that have been defined through an SLA in the case of a public Cloud or fixed by the administrator in the case of a private Cloud. This quality of service defines the required robustness of the service, by setting an upper limit on the probability that the provider fails to allocate the required quantity of resources. This maximum probability of failure can be transparently turned into a pair (price,penalty). Failures can indeed hit the platform, and resilience is provided through service replication. Our contribution is two-fold. First, we propose a resource allocation strategy whose complexity is logarithmic in the number of resources, what makes it very efficient for large platforms. Second, we propose an efficient algorithm based on rare events detection techniques in order to estimate the robustness of an allocation, a problem that has been proven to be P-complete. Finally, we provide an analysis of the proposed strategy through an extensive set of simulations, both in terms of the overall number of allocated resources and in terms of time necessary to compute the allocation.
Applications of Large Random Matrices in Communications Engineering
Venue: arXiv cs.IT 2013
Year: 2013

This work gives an overview of analytic tools for the design, analysis, and modelling of communication systems which can be described by linear vector channels such as y = Hx+z where the number of components in each vector is large. Tools from probability theory, operator algebra, and statistical physics are reviewed. The survey of analytical tools is complemented by examples of applications in communications engineering. Asymptotic eigenvalue distributions of many classes of random matrices are given. The treatment includes the problem of moments and the introduction of the Stieltjes transform. Free probability theory, which evolved from non-commutative operator algebras, is explained from a probabilistic point of view in order to better fit the engineering community. For that purpose freeness is defined without reference to non-commutative algebras. The treatment includes additive and multiplicative free convolution, the R-transform, the S-transform, and the free central limit theorem. The replica method developed in statistical physics for the purpose of analyzing spin glasses is reviewed from the viewpoint of its applications in communications engineering. Correspondences between free energy and mutual information as well as energy functions and detector metrics are established. These analytic tools are applied to the design and the analysis of linear multiuser detectors, the modelling of scattering in communication channels with dual antennas arrays, and the analysis of optimal detection for communication via code-division multiple-access and/or dual antenna array channels.
On the Optimal Scheduling in Pull-based Real-Time P2P Streaming Systems: Layered and Non-Layered Streaming
Venue: arXiv cs.NI 2013
Year: 2013

During the last decade, we witnessed a rapid growth in deployment of pull-based P2P streaming applications. In these applications, each node selects some other nodes as its neighbors and requests streaming data from them. This scheme allows eliminating data redundancy and recovering from data loss, but it pushes the complexity to the receiver node side. In this paper, we theoretically study the scheduling problem in Pull-based P2P video streaming and we model it as an assignment problem. Then, we propose AsSched, new scheduling algorithm for layered streaming, in order to optimize the throughput and the delivery ratio of the system. In second time, we derive an optimal algorithm (NAsSched) for non layered streaming. The results of simulations show that our algorithms significantly outperform classic scheduling strategies especially in stern bandwidth constraints.
GRE: A Graph Runtime Engine for Large-Scale Distributed Graph-Parallel Applications
Venue: arXiv cs.DC 2013
Year: 2013

Large-scale distributed graph-parallel computing is challenging. On one hand, due to the irregular computation pattern and lack of locality, it is hard to express parallelism efficiently. On the other hand, due to the scale-free nature, real-world graphs are hard to partition in balance with low cut. To address these challenges, several graph-parallel frameworks including Pregel and GraphLab (PowerGraph) have been developed recently. In this paper, we present an alternative framework, Graph Runtime Engine (GRE). While retaining the vertex-centric programming model, GRE proposes two new abstractions: 1) a Scatter-Combine computation model based on active message to exploit massive fined-grained edge-level parallelism, and 2) a Agent-Graph data model based on vertex factorization to partition and represent directed graphs. GRE is implemented on commercial off-the-shelf multi-core cluster. We experimentally evaluate GRE with three benchmark programs (PageRank, Single Source Shortest Path and Connected Components) on real-world and synthetic graphs of millions billion of vertices. Compared to PowerGraph, GRE shows 2.5~17 times better performance on 8~16 machines (192 cores). Specifically, the PageRank in GRE is the fastest when comparing to counterparts of other frameworks (PowerGraph, Spark,Twister) reported in public literatures. Besides, GRE significantly optimizes memory usage so that it can process a large graph of 1 billion vertices and 17 billion edges on our cluster with totally 768GB memory, while PowerGraph can only process less than half of this graph scale.
Massive Query Expansion by Exploiting Graph Knowledge Bases
Venue: arXiv cs.IR 2013
Year: 2013

Keyword based search engines have problems with term ambiguity and vocabulary mismatch. In this paper, we propose a query expansion technique that enriches queries expressed as keywords and short natural language descriptions. We present a new massive query expansion strategy that enriches queries using a knowledge base by identifying the query concepts, and adding relevant synonyms and semantically related terms. We propose two approaches: (i) lexical expansion that locates the relevant concepts in the knowledge base; and, (ii) topological expansion that analyzes the network of relations among the concepts, and suggests semantically related terms by path and community analysis of the knowledge graph. We perform our expansions by using two versions of the Wikipedia as knowledge base, concluding that the combination of both lexical and topological expansion provides improvements of the system's precision up to more than 27%.
Exploring Scientists' Working Timetable: A Global Survey
Venue: arXiv cs.DL 2013
Year: 2013

In our previous study (Wang et al., 2012), we analyzed scientists' working timetable of 3 countries, using realtime downloading data of scientific literatures. In this paper, we make a through analysis about global scientists' working habits. Top 30 countries/territories from Europe, Asia, Australia, North America, Latin America and Africa are selected as representatives and analyzed in detail. Regional differences for scientists' working habits exists in different countries. Besides different working cultures, social factors could affect scientists' research activities and working patterns. Nevertheless, a common conclusion is that scientists today are often working overtime. Although scientists may feel engaged and fulfilled about their hard working, working too much still warns us to reconsider the work - life balance.
Contracting Graphs to Split Graphs and Threshold Graphs
Venue: arXiv cs.DS 2013
Year: 2013

We study the parameterized complexity of Split Contraction and Threshold Contraction. In these problems we are given a graph G and an integer k and asked whether G can be modified into a split graph or a threshold graph, respectively, by contracting at most k edges. We present an FPT algorithm for Split Contraction, and prove that Threshold Contraction on split graphs, i.e., contracting an input split graph to a threshold graph, is FPT when parameterized by the number of contractions. To give a complete picture, we show that these two problems admit no polynomial kernels unless NP\subseteq coNP/poly.
An Operational Approach For Wimax At Ultra High Bandwidth With Spectrum 60 Ghz
Venue: arXiv cs.NI 2013
Year: 2013

WiMax is a promising network of today industry. It provides P2P and P2MP point to multipoint broadband services up to thirty miles. Its operational frequency range is 10 GHz to 60 GHz. It provides data rate of 75Mbps per channel; with an end-to-end encryption called CCMP (Counter Mode with Cipher Block Chaining Message Authentication Code Protocol). CCMP is an Advanced Encryption Standard AES based encryption method, which delivers secure communication. Telecom industry seeks secure, cheaper, wireless metro area network, that full fill the today internet demand in most efficient way. Our research explores the new dimension of WiMax with HEMT High Electron Mobility Transistor using un-licensed Band. The Aim of this paper is to simulate 60GHz unlicensed WiMax band in Matlab. This research explores millimeter waves, related electronics, mathematics of WiMax and simulated graph comparison. It determines available capacity verses coverage area and transmission bit error probability. Further it highlights the ideal modulation condition in different terrains. Research proofs that WiMax will be the future promising wireless network.
Proposal for a multilevel university cybermetric analysis model
Venue: arXiv cs.DL 2013
Year: 2013

University online seats have gradually become complex systems of dynamic information where all their institutions and services are linked and potentially accessible. These online seats now constitute a central node around which universities construct and document their main activities and services. This information can be quantitative measured by cybermetric techniques in order to design university web rankings, taking the university as a global reference unit. However, previous research into web subunits shows that it is possible to carry out systemic web analyses, which open up the possibility of carrying out studies which address university diversity, necessary for both describing the university in greater detail and for establishing comparable ranking units. To address this issue, a multilevel university cybermetric analysis model is proposed, based on parts (core and satellite), levels (institutional and external) and sublevels (contour and internal), providing a deeper analysis of institutions. Finally the model is integrated into another which is independent of the technique used, and applied by analysing Harvard University as an example of use.
Stable Recovery from the Magnitude of Symmetrized Fourier Measurements
Venue: arXiv cs.IT 2013
Year: 2013

In this note we show that stable recovery of complex-valued signals $x\in\mathbb{C}^n$ up to global sign can be achieved from the magnitudes of $4n-1$ Fourier measurements when a certain "symmetrization and zero-padding" is performed before measurement ($4n-3$ is possible in certain cases). For real signals, symmetrization itself is linear and therefore our result is in this case a statement on uniform phase retrieval. Since complex conjugation is involved, such measurement procedure is not complex-linear but recovery is still possible from magnitudes of linear measurements on, for example, $(\Re(x),\Im(x))$.
Computing in permutation groups without memory
Venue: arXiv cs.CC 2013
Year: 2013

Memoryless computation is a new technique to compute any function of a set of registers by updating one register at a time while using no memory. Its aim is to emulate how computations are performed in modern cores, since they typically involve updates of single registers. The memoryless computation model can be fully expressed in terms of transformation semigroups, or in the case of bijective functions, permutation groups. In this paper, we consider how efficiently permutations can be computed without memory. We determine the minimum number of basic updates required to compute any permutation, or any even permutation. The small number of required instructions shows that very small instruction sets could be encoded on cores to perform memoryless computation. We then start looking at a possible compromise between the size of the instruction set and the length of the resulting programs. We consider updates only involving a limited number of registers. In particular, we show that binary instructions are not enough to compute all permutations without memory when the alphabet size is even. These results, though expressed as properties of special generating sets of the symmetric or alternating groups, provide guidelines on the implementation of memoryless computation.
Graph Clustering with Surprise: Complexity and Exact Solutions
Venue: arXiv cs.DS 2013
Year: 2013

Clustering graphs based on a comparison of the number of links within clusters and the expected value of this quantity in a random graph has gained a lot of attention and popularity in the last decade. Recently, Aldecoa and Marin proposed a related, but slightly different approach leading to the quality measure surprise, and reported good behavior in the context of synthetic and real world benchmarks. We show that the problem of finding a clustering with optimum surprise is NP-hard. Moreover, a bicriterial view on the problem permits to compute optimum solutions for small instances by solving a small number of integer linear programs, and leads to a polynomial time algorithm on trees.
Word Spotting in Cursive Handwritten Documents using Modified Character Shape Codes
Venue: arXiv cs.CV 2013
Year: 2013

There is a large collection of Handwritten English paper documents of Historical and Scientific importance. But paper documents are not recognized directly by computer. Hence the closest way of indexing these documents is by storing their document digital image. Hence a large database of document images can replace the paper documents. But the document and data corresponding to each image cannot be directly recognized by the computer. This paper applies the technique of word spotting using Modified Character Shape Code to Handwritten English document images for quick and efficient query search of words on a database of document images. It is different from other Word Spotting techniques as it implements two level of selection for word segments to match search query. First based on word size and then based on character shape code of query. It makes the process faster and more efficient and reduces the need of multiple pre-processing.
A two-step model and the algorithm for recalling in recommender systems
Venue: arXiv cs.IR 2013
Year: 2013

When a user finds an interesting recommendation in a recommender system, the user may want to recall related items recommended in the past to reconsider or to enjoy them again. If the system can pick up such "recalled" items at each user's request, it must deepen the user experience. We propose a model and the algorithm for such personalized "recalling" in conventional recommender systems, which is an application of neural networks for associative memory. In our model, the "recalled" items can reflect each user's personality beyond naive similarities between items.
Practical Full Duplex Physical Layer Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

We propose a practical network code for the wireless two-way relay channel where all nodes communicate in full duplex (FD) mode. The physical layer network coding (PNC) operation is applied with the FD operating nodes, reducing the transmission time to a single time slot, hence doubling the spectral efficiency when compared to classical PNC systems. In our system model, binary phase shift keying modulated signals are transmitted over Rayleigh fading channels. We derive the theoretical error rates at relay and end nodes according to the maximum likelihood detection rule, in case of non-ideal self-interference cancellation. Theoretical results are also verified via simulations.
Google Scholar Metrics evolution: an analysis according to languages
Venue: arXiv cs.DL 2013
Year: 2013

In November 2012 the Google Scholar Metrics (GSM) journal rankings were updated, making it possible to compare bibliometric indicators in the 10 languages indexed and their stability with the April 2012 version. The h-index and h 5 median of 1000 journals were analysed, comparing their averages, maximum and minimum values and the correlation coefficient within rankings. The bibliometric figures grew significantly. In just seven and a half months the h index of the journals increased by 15% and the median h-index by 17%. This growth was observed for all the bibliometric indicators analysed and for practically every journal. However, we found significant differences in growth rates depending on the language in which the journal is published. Moreover, the journal rankings seem to be stable between April and November, reinforcing the credibility of the data held by Google Scholar and the reliability of the GSM journal rankings, despite the uncontrolled growth of Google Scholar. Based on the findings of this study we suggest, firstly, that Google should upgrade its rankings at least semiannually and, secondly, that the results should be displayed in each ranking proportionally to the number of journals indexed by language
Stacked Patch Antenna With Cross Slot Electronic Band Gap Structure
Venue: arXiv cs.OH 2013
Year: 2013

A cross slotted electronic band gap (EBG) with stacked rectangular patches shorted with a shorting pin is proposed in this paper. The study is being done on how the various parameters are varied by changing the probe feed location. The design is constructed by using stacking of patches, shorting pin and cross slotted EBG to form an optimized antenna design with antenna efficiency of approximately 99.06%. The radiation patterns are given at 2.586 GHz which can be used for wireless communications.
Simulation Over One-counter Nets is PSPACE-Complete
Venue: arXiv cs.FL 2013
Year: 2013

One-counter nets (OCN) are Petri nets with exactly one unbounded place. They are equivalent to a subclass of one-counter automata with just a weak test for zero. Unlike many other semantic equivalences, strong and weak simulation preorder are decidable for OCN, but the computational complexity was an open problem. We show that both strong and weak simulation preorder on OCN are PSPACE-complete.
Variance Based Scheduling Algorithm with Relay Selection and Resource Allocation in Cooperative OFDMA Networks
Venue: arXiv cs.NI 2013
Year: 2013

Nowadays the radio interface of several standards is enhanced with advanced technologies such as OFDMA and extension technology such as relay. By using those promising transmission technology for the next generation wireless communications, scheduling problem becomes more crucial and challenging. In our work, we aim to maximize the overall system capacity while selecting the most suitable relay station under fairness constraint among both users and relay station by proposing a Gap- based scheduling. This one considers the channel state information and the unbalanced rate capacity of the two hops links. Simulations results show the effectiveness of our approach in terms of fairness and the overall system performance.
Knowledge-Based Programs as Plans: Succinctness and the Complexity of Plan Existence
Venue: arXiv cs.AI 2013
Year: 2013

Knowledge-based programs (KBPs) are high-level protocols describing the course of action an agent should perform as a function of its knowledge. The use of KBPs for expressing action policies in AI planning has been surprisingly overlooked. Given that to each KBP corresponds an equivalent plan and vice versa, KBPs are typically more succinct than standard plans, but imply more on-line computation time. Here we make this argument formal, and prove that there exists an exponential succinctness gap between knowledge-based programs and standard plans. Then we address the complexity of plan existence. Some results trivially follow from results already known from the literature on planning under incomplete knowledge, but many were unknown so far.
Model Checking an Epistemic mu-calculus with Synchronous and Perfect Recall Semantics
Venue: arXiv cs.GT 2013
Year: 2013

We identify a subproblem of the model-checking problem for the epistemic μ-calculus which is decidable. Formulas in the instances of this subproblem allow free variables within the scope of epistemic modalities in a restricted form that avoids embodying any form of common knowledge. Our subproblem subsumes known decidable fragments of epistemic CTL/LTL, may express winning strategies in two-player games with one player having imperfect information and non-observable objectives, and, with a suitable encoding, decidable instances of the model-checking problem for ATLiR.
Hybrid-Logical Reasoning in False-Belief Tasks
Venue: arXiv cs.GT 2013
Year: 2013

The main aim of the present paper is to use a proof system for hybrid modal logic to formalize what are called falsebelief tasks in cognitive psychology, thereby investigating the interplay between cognition and logical reasoning about belief. We consider two different versions of the Smarties task, involving respectively a shift of perspective to another person and to another time. Our formalizations disclose that despite this difference, the two versions of the Smarties task have exactly the same underlying logical structure. We also consider the Sally-Anne task, having a somewhat more complicated logical structure, presupposing a "principle of inertia" saying that a belief is preserved over time, unless there is belief to the contrary.
Strategic Voting and the Logic of Knowledge
Venue: arXiv cs.GT 2013
Year: 2013

We propose a general framework for strategic voting when a voter may lack knowledge about other votes or about other voters' knowledge about her own vote. In this setting we define notions of manipulation and equilibrium. We also model action changing knowledge about votes, such as a voter revealing its preference or as a central authority performing a voting poll. Some forms of manipulation are preserved under such updates and others not. Another form of knowledge dynamics is the effect of a voter declaring its vote. We envisage Stackelberg games for uncertain profiles. The purpose of this investigation is to provide the epistemic background for the analysis and design of voting rules that incorporate uncertainty.