OpenRaiser/Intern-Atlas huggingface dataset:
Memetic Multi-Objective Particle Swarm Optimization-Based Energy-Aware Virtual Network Embedding
Venue: arXiv cs.DC 2015
Year: 2015

In cloud infrastructure, accommodating multiple virtual networks on a single physical network reduces power consumed by physical resources and minimizes cost of operating cloud data centers. However, mapping multiple virtual network resources to physical network components, called virtual network embedding (VNE), is known to be NP-hard. With considering energy efficiency, the problem becomes more complicated. In this paper, we model energy-aware virtual network embedding, devise metrics for evaluating performance of energy aware virtual network-embedding algorithms, and propose an energy aware virtual network-embedding algorithm based on multi-objective particle swarm optimization augmented with local search to speed up convergence of the proposed algorithm and improve solutions quality. Performance of the proposed algorithm is evaluated and compared with existing algorithms using extensive simulations, which show that the proposed algorithm improves virtual network embedding by increasing revenue and decreasing energy consumption.
Linear Spatial Pyramid Matching Using Non-convex and non-negative Sparse Coding for Image Classification
Venue: arXiv cs.CV 2015
Year: 2015

Recently sparse coding have been highly successful in image classification mainly due to its capability of incorporating the sparsity of image representation. In this paper, we propose an improved sparse coding model based on linear spatial pyramid matching(SPM) and Scale Invariant Feature Transform (SIFT ) descriptors. The novelty is the simultaneous non-convex and non-negative characters added to the sparse coding model. Our numerical experiments show that the improved approach using non-convex and non-negative sparse coding is superior than the original ScSPM[1] on several typical databases.
Node-balancing by edge-increments
Venue: arXiv cs.DM 2015
Year: 2015

Suppose you are given a graph $G=(V,E)$ with a weight assignment $w:V\rightarrow\mathbb{Z}$ and that your objective is to modify $w$ using legal steps such that all vertices will have the same weight, where in each legal step you are allowed to choose an edge and increment the weights of its end points by $1$. In this paper we study several variants of this problem for graphs and hypergraphs. On the combinatorial side we show connections with fundamental results from matching theory such as Hall's Theorem and Tutte's Theorem. On the algorithmic side we study the computational complexity of associated decision problems. Our main results are a characterization of the graphs for which any initial assignment can be balanced by edge-increments and a strongly polynomial-time algorithm that computes a balancing sequence of increments if one exists.
A Graph Theoretic Perspective on CPM(Rel)
Venue: arXiv cs.LO 2015
Year: 2015

Mixed states are of interest in quantum mechanics for modelling partial information. More recently categorical approaches to linguistics have also exploited the idea of mixed states to describe ambiguity and hyponym / hypernym relationships. In both these application areas the category Rel of sets and binary relations is often used as an alternative model. Selinger's CPM construction provides the setting for mixed states in Hilbert space based categorical quantum mechanics. By analogy, applying the CPM construction to Rel is seen as introducing mixing into a relational setting. We investigate the category CPM(Rel) of completely positive maps in Rel. We show that the states of an object in CPM(Rel) are in bijective correspondence with certain families of graphs. Via map-state duality this then allows us provide a graph theoretic characterization of the morphisms in CPM(Rel). By identifying an appropriate composition operation on graphs, we then show that CPM(Rel) is isomorphic to a category of sets and graphs between them. This isomorphism then leads to a graph based description of the complete join semilattice enriched dagger compact structure of CPM(Rel). These results allow us to reason about CPM(Rel) entirely in terms of graphs. We exploit these techniques in several examples. We give a closed form expression for the number of states of a finite set in CPM(Rel). The pure states are characterized in graph theoretic terms. We also demonstrate the possibly surprising phenomenon of a pure state that can be given as a mixture of two mixed states.
An Improvised Frequent Pattern Tree Based Association Rule Mining Technique with Mining Frequent Item Sets Algorithm and a Modified Header Table
Venue: arXiv cs.DB 2015
Year: 2015

In todays world there is a wide availability of huge amount of data and thus there is a need for turning this data into useful information which is referred to as knowledge. This demand for knowledge discovery process has led to the development of many algorithms used to determine the association rules. One of the major problems faced by these algorithms is generation of candidate sets. The FP Tree algorithm is one of the most preferred algorithms for association rule mining because it gives association rules without generating candidate sets. But in the process of doing so, it generates many CP trees which decreases its efficiency. In this research paper, an improvised FP tree algorithm with a modified header table, along with a spare table and the MFI algorithm for association rule mining is proposed. This algorithm generates frequent item sets without using candidate sets and CP trees.
Exploring semantically-related concepts from Wikipedia: the case of SeRE
Venue: arXiv cs.CL 2015
Year: 2015

In this paper we present our web application SeRE designed to explore semantically related concepts. Wikipedia and DBpedia are rich data sources to extract related entities for a given topic, like in- and out-links, broader and narrower terms, categorisation information etc. We use the Wikipedia full text body to compute the semantic relatedness for extracted terms, which results in a list of entities that are most relevant for a topic. For any given query, the user interface of SeRE visualizes these related concepts, ordered by semantic relatedness; with snippets from Wikipedia articles that explain the connection between those two entities. In a user study we examine how SeRE can be used to find important entities and their relationships for a given topic and to answer the question of how the classification system can be used for filtering.
Scheduling Bidirectional Traffic on a Path
Venue: arXiv cs.DS 2015
Year: 2015

We study the fundamental problem of scheduling bidirectional traffic along a path composed of multiple segments. The main feature of the problem is that jobs traveling in the same direction can be scheduled in quick succession on a segment, while jobs in opposing directions cannot cross a segment at the same time. We show that this tradeoff makes the problem significantly harder than the related flow shop problem, by proving that it is NP-hard even for identical jobs. We complement this result with a PTAS for a single segment and non-identical jobs. If we allow some pairs of jobs traveling in different directions to cross a segment concurrently, the problem becomes APX-hard even on a single segment and with identical jobs. We give polynomial algorithms for the setting with restricted compatibilities between jobs on a single and any constant number of segments, respectively.
Trip-Based Public Transit Routing
Venue: arXiv cs.DS 2015
Year: 2015

We study the problem of computing all Pareto-optimal journeys in a public transit network regarding the two criteria of arrival time and number of transfers taken. We take a novel approach, focusing on trips and transfers between them, allowing fine-grained modeling. Our experiments on the metropolitan network of London show that the algorithm computes full 24-hour profiles in 70 ms after a preprocessing phase of 30 s, allowing fast queries in dynamic scenarios.
A Probabilistic Framework for Representing Dialog Systems and Entropy-Based Dialog Management through Dynamic Stochastic State Evolution
Venue: arXiv cs.AI 2015
Year: 2015

In this paper, we present a probabilistic framework for goal-driven spoken dialog systems. A new dynamic stochastic state (DS-state) is then defined to characterize the goal set of a dialog state at different stages of the dialog process. Furthermore, an entropy minimization dialog management(EMDM) strategy is also proposed to combine with the DS-states to facilitate a robust and efficient solution in reaching a user's goals. A Song-On-Demand task, with a total of 38117 songs and 12 attributes corresponding to each song, is used to test the performance of the proposed approach. In an ideal simulation, assuming no errors, the EMDM strategy is the most efficient goal-seeking method among all tested approaches, returning the correct song within 3.3 dialog turns on average. Furthermore, in a practical scenario, with top five candidates to handle the unavoidable automatic speech recognition (ASR) and natural language understanding (NLU) errors, the results show that only 61.7\% of the dialog goals can be successfully obtained in 6.23 dialog turns on average when random questions are asked by the system, whereas if the proposed DS-states are updated with the top 5 candidates from the SLU output using the proposed EMDM strategy executed at every DS-state, then a 86.7\% dialog success rate can be accomplished effectively within 5.17 dialog turns on average. We also demonstrate that entropy-based DM strategies are more efficient than non-entropy based DM. Moreover, using the goal set distributions in EMDM, the results are better than those without them, such as in sate-of-the-art database summary DM.
QoS-Based Pricing and Scheduling of Batch Jobs in OpenStack Clouds
Venue: arXiv cs.DC 2015
Year: 2015

The current Cloud infrastructure services (IaaS) market employs a resource-based selling model: customers rent nodes from the provider and pay per-node per-unit-time. This selling model places the burden upon customers to predict their job resource requirements and durations. Inaccurate prediction by customers can result in over-provisioning of resources, or under-provisioning and poor job performance. Thanks to improved resource virtualization and multi-tenant performance isolation, as well as common frameworks for batch jobs, such as MapReduce, Cloud providers can predict job completion times more accurately. We offer a new definition of QoS-levels in terms of job completion times and we present a new QoS-based selling mechanism for batch jobs in a multi-tenant OpenStack cluster. Our experiments show that the QoS-based solution yields up to 40% improvement over the revenue of more standard selling mechanisms based on a fixed per-node price across various demand and supply conditions in a 240-VCPU OpenStack cluster.
On Potential Equations of Finite Games
Venue: arXiv cs.GT 2015
Year: 2015

In this paper, some new criteria for detecting whether a finite game is potential are proposed by solving potential equations. The verification equations with the minimal number for checking a potential game are obtained for the first time. Some connections between the potential equations and the existing characterizations of potential games are established. It is revealed that a finite game is potential if and only if its every bi-matrix sub-game is potential.
A New Approach to Linear Estimation Problem in Multi-user Massive MIMO Systems
Venue: arXiv cs.SY 2015
Year: 2015

A novel approach for solving linear estimation problem in multi-user massive MIMO systems is proposed. In this approach, the difficulty of matrix inversion is attributed to the incomplete definition of the dot product. The general definition of dot product implies that the columns of channel matrix are always orthogonal whereas, in practice, they may be not. If the latter information can be incorporated into dot product, then the unknowns can be directly computed from projections without inverting the channel matrix. By doing so, the proposed method is able to achieve an exact solution with a 25% reduction in computational complexity as compared to the QR method. Proposed method is stable, offers an extra flexibility of computing any single unknown, and can be implemented in just twelve lines of code.
Identifying Reliable Annotations for Large Scale Image Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

Challenging computer vision tasks, in particular semantic image segmentation, require large training sets of annotated images. While obtaining the actual images is often unproblematic, creating the necessary annotation is a tedious and costly process. Therefore, one often has to work with unreliable annotation sources, such as Amazon Mechanical Turk or (semi-)automatic algorithmic techniques. In this work, we present a Gaussian process (GP) based technique for simultaneously identifying which images of a training set have unreliable annotation and learning a segmentation model in which the negative effect of these images is suppressed. Alternatively, the model can also just be used to identify the most reliably annotated images from the training set, which can then be used for training any other segmentation method. By relying on "deep features" in combination with a linear covariance function, our GP can be learned and its hyperparameter determined efficiently using only matrix operations and gradient-based optimization. This makes our method scalable even to large datasets with several million training instances.
Cited Half-Life of the Journal Literature
Venue: arXiv cs.DL 2015
Year: 2015

Analyzing 13,455 journals listed in the Journal Citation Report (Thomson Reuters) from 1997 through 2013, we report that the mean cited half-life of the scholarly literature is 6.5 years and growing at a rate of 0.13 years per annum. Focusing on a subset of journals (N=4,937) for which we have a continuous series of half-life observations, 209 of 229 (91%) subject categories experienced increasing cited half-lives. Contrary to the overall trend, engineering and chemistry journals experienced declining cited half-lives. Last, as journals attracted more citations, a larger proportion of them were directed toward older papers. The trend to cite older papers is not fully explained by technology (digital publishing, search and retrieval, etc.), but may be the result of a structural shift to fund incremental and applied research over fundamental science.
Decode-Forward Transmission for the Two-Way Relay Channels
Venue: arXiv cs.IT 2015
Year: 2015

We propose composite decode-forward (DF) schemes for the two-way relay channel in both the full- and half-duplex modes by combining coherent relaying, independent relaying and partial relaying strategies. For the full-duplex mode, the relay partially decodes each user's information in each block and forwards this partial information coherently with the source user to the destination user in the next block as in block Markov coding. In addition, the relay independently broadcasts a binning index of both users' decoded information parts in the next block as in independent network coding. Each technique has a different impact on the relay power usage and the rate region. We further analyze in detail the independent partial DF scheme and derive in closed-form link regimes when this scheme achieves a strictly larger rate region than just time-sharing between its constituent techniques, direct transmission and independent DF relaying, and when it reduces to a simpler scheme. For the half-duplex mode, we propose a 6-phase time-division scheme that incorporates all considered relaying techniques and uses joint decoding simultaneously over all receiving phases. Numerical results show significant rate gains over existing DF schemes, obtained by performing link adaptation of the composite scheme based on the identified link regimes.
Efficient Equilibria in Polymatrix Coordination Games
Venue: arXiv cs.GT 2015
Year: 2015

We consider polymatrix coordination games with individual preferences where every player corresponds to a node in a graph who plays with each neighbor a separate bimatrix game with non-negative symmetric payoffs. In this paper, we study $α$-approximate $k$-equilibria of these games, i.e., outcomes where no group of at most $k$ players can deviate such that each member increases his payoff by at least a factor $α$. We prove that for $α\ge 2$ these games have the finite coalitional improvement property (and thus $α$-approximate $k$-equilibria exist), while for $α< 2$ this property does not hold. Further, we derive an almost tight bound of $2α(n-1)/(k-1)$ on the price of anarchy, where $n$ is the number of players; in particular, it scales from unbounded for pure Nash equilibria ($k = 1)$ to $2α$ for strong equilibria ($k = n$). We also settle the complexity of several problems related to the verification and existence of these equilibria. Finally, we investigate natural means to reduce the inefficiency of Nash equilibria. Most promisingly, we show that by fixing the strategies of $k$ players the price of anarchy can be reduced to $n/k$ (and this bound is tight).
A New Secure Mobile Cloud Architecture
Venue: arXiv cs.DC 2015
Year: 2015

The demand and use of mobile phones, PDAs and smart phones are constantly on the rise as such, manufacturers of these devices are improving the technology and usability of these devices constantly. Due to the handy shape and size these devices come in, their processing capabilities and functionalities, they are preferred by many over the conventional desktop or laptop computers. Mobile devices are being used today to perform most tasks that a desktop or laptop computer could be used for. On this premise, mobile devices are also used to connect to the resources of cloud computing hence, mobile cloud computing (MCC). The seemingly ubiquitous and pervasive nature of most mobile devices has made it acceptable and adequate to match the ubiquitous and pervasive nature of cloud computing. Mobile cloud computing is said to have increased the challenges known to cloud computing due to the security loop holes that most mobile devices have.
Designing Wireless Broadband Access for Energy Efficiency: Are Small Cells the Only Answer?
Venue: arXiv cs.IT 2015
Year: 2015

The main usage of cellular networks has changed from voice to data traffic, mostly requested by static users. In this paper, we analyze how a cellular network should be designed to provide such wireless broadband access with maximal energy efficiency (EE). Using stochastic geometry and a detailed power consumption model, we optimize the density of access points (APs), number of antennas and users per AP, and transmission power for maximal EE. Small cells are of course a key technology in this direction, but the analysis shows that the EE improvement of a small-cell network saturates quickly with the AP density and then "massive MIMO" techniques can further improve the EE.
A Robust Lane Detection and Departure Warning System
Venue: arXiv cs.CV 2015
Year: 2015

In this work, we have developed a robust lane detection and departure warning technique. Our system is based on single camera sensor. For lane detection a modified Inverse Perspective Mapping using only a few extrinsic camera parameters and illuminant Invariant techniques is used. Lane markings are represented using a combination of 2nd and 4th order steerable filters, robust to shadowing. Effect of shadowing and extra sun light are removed using Lab color space, and illuminant invariant representation. Lanes are assumed to be cubic curves and fitted using robust RANSAC. This method can reliably detect lanes of the road and its boundary. This method has been experimented in Indian road conditions under different challenging situations and the result obtained were very good. For lane departure angle an optical flow based method were used.
Throughput Maximization for Two-way Relay Channels with Energy Harvesting Nodes: The Impact of Relaying Strategies
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the two-way relay channel with energy harvesting nodes. In particular, we find transmission policies that maximize the sum-throughput for two-way relay channels when the relay does not employ a data buffer. The relay can perform decode-and-forward, compress-and-forward, compute-and-forward or amplify-and-forward relaying. Furthermore, we consider throughput improvement by dynamically choosing relaying strategies, resulting in hybrid relaying strategies. We show that an iterative generalized directional water-filling algorithm solves the offline throughput maximization problem, with the achievable sum-rate from an individual or hybrid relaying scheme. In addition to the optimum offline policy, we obtain the optimum online policy via dynamic programming. We provide numerical results for each relaying scheme to support the analytic findings, pointing out to the advantage of adapting the instantaneous relaying strategy to the available harvested energy.
Fréchet Distance for Curves, Revisited
Venue: arXiv cs.CG 2015
Year: 2015

$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\eps}{\varepsilon} \newcommand{\SetX}{\mathsf{X}} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)}$ We revisit the problem of computing Fréchet distance between polygonal curves under $L_1$, $L_2$, and $L_\infty$ norms, focusing on discrete Fréchet distance, where only distance between vertices is considered. We develop efficient algorithms for two natural classes of curves. In particular, given two polygonal curves of $n$ vertices each, a $\eps$-approximation of their discrete Fréchet distance can be computed in roughly $O(nκ^3\log n/\eps^3)$ time in three dimensions, if one of the curves is \emph{$κ$-bounded}. Previously, only a $κ$-approximation algorithm was known. If both curves are the so-called \emph{\backbone~curves}, which are widely used to model protein backbones in molecular biology, we can $\eps$-approximate their Fréchet distance in near linear time in two dimensions, and in roughly $O(n^{4/3}\log nm)$ time in three dimensions. In the second part, we propose a pseudo--output-sensitive algorithm for computing Fréchet distance exactly. The complexity of the algorithm is a function of a quantity we call the \emph{\bwnumber{}}, which is quadratic in the worst case, but tends to be much smaller in practice.
Accelerating the Development of Software-Defined Network Optimization Applications Using SOL
Venue: arXiv cs.NI 2015
Year: 2015

Software-defined networking (SDN) can enable diverse network management applications such as traffic engineering, service chaining, network function outsourcing, and topology reconfiguration. Realizing the benefits of SDN for these applications, however, entails addressing complex network optimizations that are central to these problems. Unfortunately, such optimization problems require significant manual effort and expertise to express and non-trivial computation and/or carefully crafted heuristics to solve. Our vision is to simplify the deployment of SDN applications using general high-level abstractions for capturing optimization requirements from which we can efficiently generate optimal solutions. To this end, we present SOL, a framework that demonstrates that it is indeed possible to simultaneously achieve generality and efficiency. The insight underlying SOL is that SDN applications can be recast within a unifying path-based optimization abstraction, from which it efficiently generates near-optimal solutions, and device configurations to implement those solutions. We illustrate the generality of SOL by prototyping diverse and new applications. We show that SOL simplifies the development of SDN-based network optimization applications and provides comparable or better scalability than custom optimization solutions.