OpenRaiser/Intern-Atlas huggingface dataset:
Canonical Labelling of Site Graphs
Venue: arXiv cs.DM 2013
Year: 2013

We investigate algorithms for canonical labelling of site graphs, i.e. graphs in which edges bind vertices on sites with locally unique names. We first show that the problem of canonical labelling of site graphs reduces to the problem of canonical labelling of graphs with edge colourings. We then present two canonical labelling algorithms based on edge enumeration, and a third based on an extension of Hopcroft's partition refinement algorithm. All run in quadratic worst case time individually. However, one of the edge enumeration algorithms runs in sub-quadratic time for graphs with "many" automorphisms, and the partition refinement algorithm runs in sub-quadratic time for graphs with "few" bisimulation equivalences. This suite of algorithms was chosen based on the expectation that graphs fall in one of those two categories. If that is the case, a combined algorithm runs in sub-quadratic worst case time. Whether this expectation is reasonable remains an interesting open problem.
Cloud Security Challenges: Investigating Policies, Standards, and Guidelines in a Fortune 500 Organization
Venue: arXiv cs.CR 2013
Year: 2013

Cloud computing is quickly becoming pervasive in today's globally integrated networks. The cloud offers organizations opportunities to potentially deploy software and data solutions that are accessible through numerous mechanisms, in a multitude of settings, at a reduced cost with increased reliability and scalability. The increasingly pervasive and ubiquitous nature of the cloud creates an environment that is potentially conducive to security risks. While previous discussions have focused on security and privacy issues in the cloud from the end-users perspective, minimal empirical research has been conducted from the perspective of a corporate environment case study. This paper presents the results of an initial case study identifying real-world information security documentation issues for a Global Fortune 500 organization, should the organization decide to implement cloud computing services in the future. The paper demonstrates the importance of auditing policies, standards and guidelines applicable to cloud computing environments along with highlighting potential corporate concerns. The results from this case study has revealed that from the 1123 'relevant' statements found in the organization's security documentation, 175 statements were considered to be 'inadequate' for cloud computing. Furthermore, the paper provides a foundation for future analysis and research regarding implementation concerns for corporate cloud computing applications and services
Large Margin Low Rank Tensor Analysis
Venue: arXiv cs.LG 2013
Year: 2013

Other than vector representations, the direct objects of human cognition are generally high-order tensors, such as 2D images and 3D textures. From this fact, two interesting questions naturally arise: How does the human brain represent these tensor perceptions in a "manifold" way, and how can they be recognized on the "manifold"? In this paper, we present a supervised model to learn the intrinsic structure of the tensors embedded in a high dimensional Euclidean space. With the fixed point continuation procedures, our model automatically and jointly discovers the optimal dimensionality and the representations of the low dimensional embeddings. This makes it an effective simulation of the cognitive process of human brain. Furthermore, the generalization of our model based on similarity between the learned low dimensional embeddings can be viewed as counterpart of recognition of human brain. Experiments on applications for object recognition and face recognition demonstrate the superiority of our proposed model over state-of-the-art approaches.
Indexed Labels for Loop Iteration Dependent Costs
Venue: arXiv cs.PL 2013
Year: 2013

We present an extension to the labelling approach, a technique for lifting resource consumption information from compiled to source code. This approach, which is at the core of the annotating compiler from a large fragment of C to 8051 assembly of the CerCo project, looses preciseness when differences arise as to the cost of the same portion of code, whether due to code transformation such as loop optimisations or advanced architecture features (e.g. cache). We propose to address this weakness by formally indexing cost labels with the iterations of the containing loops they occur in. These indexes can be transformed during the compilation, and when lifted back to source code they produce dependent costs. The proposed changes have been implemented in CerCo's untrusted prototype compiler from a large fragment of C to 8051 assembly.
Cache-Enabled Opportunistic Cooperative MIMO for Video Streaming in Wireless Systems
Venue: arXiv cs.IT 2013
Year: 2013

We propose a cache-enabled opportunistic cooperative MIMO (CoMP) framework for wireless video streaming. By caching a portion of the video files at the relays (RS) using a novel MDS-coded random cache scheme, the base station (BS) and RSs opportunistically employ CoMP to achieve spatial multiplexing gain without expensive payload backhaul. We study a two timescale joint optimization of power and cache control to support real-time video streaming. The cache control is to create more CoMP opportunities and is adaptive to the long-term popularity of the video files. The power control is to guarantee the QoS requirements and is adaptive to the channel state information (CSI), the cache state at the RS and the queue state information (QSI) at the users. The joint problem is decomposed into an inner power control problem and an outer cache control problem. We first derive a closed-form power control policy from an approximated Bellman equation. Based on this, we transform the outer problem into a convex stochastic optimization problem and propose a stochastic subgradient algorithm to solve it. Finally, the proposed solution is shown to be asymptotically optimal for high SNR and small timeslot duration. Its superior performance over various baselines is verified by simulations.
Horizontal and Vertical Ensemble with Deep Representation for Classification
Venue: arXiv cs.LG 2013
Year: 2013

Representation learning, especially which by using deep learning, has been widely applied in classification. However, how to use limited size of labeled data to achieve good classification performance with deep neural network, and how can the learned features further improve classification remain indefinite. In this paper, we propose Horizontal Voting Vertical Voting and Horizontal Stacked Ensemble methods to improve the classification performance of deep neural networks. In the ICML 2013 Black Box Challenge, via using these methods independently, Bing Xu achieved 3rd in public leaderboard, and 7th in private leaderboard; Jingjing Xie achieved 4th in public leaderboard, and 5th in private leaderboard.
Solving Parity Games on Integer Vectors
Venue: arXiv cs.LO 2013
Year: 2013

We consider parity games on infinite graphs where configurations are represented by control-states and integer vectors. This framework subsumes two classic game problems: parity games on vector addition systems with states (vass) and multidimensional energy parity games. We show that the multidimensional energy parity game problem is inter-reducible with a subclass of single-sided parity games on vass where just one player can modify the integer counters and the opponent can only change control-states. Our main result is that the minimal elements of the upward-closed winning set of these single-sided parity games on vass are computable. This implies that the Pareto frontier of the minimal initial credit needed to win multidimensional energy parity games is also computable, solving an open question from the literature. Moreover, our main result implies the decidability of weak simulation preorder/equivalence between finite-state systems and vass, and the decidability of model checking vass with a large fragment of the modal mu-calculus.
The Quantum Challenge in Concept Theory and Natural Language Processing
Venue: arXiv cs.CL 2013
Year: 2013

The mathematical formalism of quantum theory has been successfully used in human cognition to model decision processes and to deliver representations of human knowledge. As such, quantum cognition inspired tools have improved technologies for Natural Language Processing and Information Retrieval. In this paper, we overview the quantum cognition approach developed in our Brussels team during the last two decades, specifically our identification of quantum structures in human concepts and language, and the modeling of data from psychological and corpus-text-based experiments. We discuss our quantum-theoretic framework for concepts and their conjunctions/disjunctions in a Fock-Hilbert space structure, adequately modeling a large amount of data collected on concept combinations. Inspired by this modeling, we put forward elements for a quantum contextual and meaning-based approach to information technologies in which 'entities of meaning' are inversely reconstructed from texts, which are considered as traces of these entities' states.
Hierarchical structuring of Cultural Heritage objects within large aggregations
Venue: arXiv cs.DL 2013
Year: 2013

Huge amounts of cultural content have been digitised and are available through digital libraries and aggregators like Europeana.eu. However, it is not easy for a user to have an overall picture of what is available nor to find related objects. We propose a method for hier- archically structuring cultural objects at different similarity levels. We describe a fast, scalable clustering algorithm with an automated field selection method for finding semantic clusters. We report a qualitative evaluation on the cluster categories based on records from the UK and a quantitative one on the results from the complete Europeana dataset.
An audio CAPTCHA to distinguish humans from computers
Venue: arXiv cs.CR 2013
Year: 2013

CAPTCHAs are employed as a security measure to differentiate human users from bots. A new sound-based CAPTCHA is proposed in this paper, which exploits the gaps between human voice and synthetic voice rather than relays on the auditory perception of human. The user is required to read out a given sentence, which is selected randomly from a specified book. The generated audio file will be analyzed automatically to judge whether the user is a human or not. In this paper, the design of the new CAPTCHA, the analysis of the audio files, and the choice of the audio frame window function are described in detail. And also, some experiments are conducted to fix the critical threshold and the coefficients of three indicators to ensure the security. The proposed audio CAPTCHA is proved accessible to users. The user study has shown that the human success rate reaches approximately 97% and the pass rate of attack software using Microsoft SDK 5.1 is only 4%. The experiments also indicated that it could be solved by most human users in less than 14 seconds and the average time is only 7.8 seconds.
Defining a Simulation Strategy for Cancer Immunocompetence
Venue: arXiv cs.CE 2013
Year: 2013

Although there are various types of cancer treatments, none of these currently take into account the effect of ageing of the immune system and hence altered responses to cancer. Recent studies have shown that in vitro stimulation of T cells can help in the treatment of patients. There are many factors that have to be considered when simulating an organism's immunocompetence. Our particular interest lies in the study of loss of immunocompetence with age. We are trying to answer questions such as: Given a certain age of a patient, how fit is their immune system to fight cancer? Would an immune boost improve the effectiveness of a cancer treatment given the patient's immune phenotype and age? We believe that understanding the processes of immune system ageing and degradation through computer simulation may help in answering these questions. Specifically, we have decided to look at the change in numbers of naive T cells with age, as they play a important role in responses to cancer and anti-tumour vaccination. In this work we present an agent-based simulation model to understand the interactions which influence the naive T cell populations over time. Our agent model is based on existing mathematical system dynamic model, but in comparisons offers better scope for customisation and detailed analysis. We believe that the results obtained can in future help with the modelling of T cell populations inside tumours.
Graphs with Plane Outside-Obstacle Representations
Venue: arXiv cs.CG 2013
Year: 2013

An \emph{obstacle representation} of a graph consists of a set of polygonal obstacles and a distinct point for each vertex such that two points see each other if and only if the corresponding vertices are adjacent. Obstacle representations are a recent generalization of classical polygon--vertex visibility graphs, for which the characterization and recognition problems are long-standing open questions. In this paper, we study \emph{plane outside-obstacle representations}, where all obstacles lie in the unbounded face of the representation and no two visibility segments cross. We give a combinatorial characterization of the biconnected graphs that admit such a representation. Based on this characterization, we present a simple linear-time recognition algorithm for these graphs. As a side result, we show that the plane vertex--polygon visibility graphs are exactly the maximal outerplanar graphs and that every chordal outerplanar graph has an outside-obstacle representation.
Dynamic Infinite Mixed-Membership Stochastic Blockmodel
Venue: arXiv cs.SI 2013
Year: 2013

Directional and pairwise measurements are often used to model inter-relationships in a social network setting. The Mixed-Membership Stochastic Blockmodel (MMSB) was a seminal work in this area, and many of its capabilities were extended since then. In this paper, we propose the \emph{Dynamic Infinite Mixed-Membership stochastic blockModel (DIM3)}, a generalised framework that extends the existing work to a potentially infinite number of communities and mixture memberships for each of the network's nodes. This model is in a dynamic setting, where additional model parameters are introduced to reflect the degree of persistence between one's memberships at consecutive times. Accordingly, two effective posterior sampling strategies and their results are presented using both synthetic and real data.
Second Order Swarm Intelligence
Venue: arXiv cs.NE 2013
Year: 2013

An artificial Ant Colony System (ACS) algorithm to solve general-purpose combinatorial Optimization Problems (COP) that extends previous AC models [21] by the inclusion of a negative pheromone, is here described. Several Travelling Salesman Problem (TSP) were used as benchmark. We show that by using two different sets of pheromones, a second-order co-evolved compromise between positive and negative feedbacks achieves better results than single positive feedback systems. The algorithm was tested against known NP-complete combinatorial Optimization Problems, running on symmetrical TSP's. We show that the new algorithm compares favourably against these benchmarks, accordingly to recent biological findings by Robinson [26,27], and Gruter [28] where "No entry" signals and negative feedback allows a colony to quickly reallocate the majority of its foragers to superior food patches. This is the first time an extended ACS algorithm is implemented with these successful characteristics.
An implementation of CAD in Maple utilising problem formulation, equational constraints and truth-table invariance
Venue: arXiv cs.SC 2013
Year: 2013

Cylindrical algebraic decomposition (CAD) is an important tool for the investigation of semi-algebraic sets, with applications within algebraic geometry and beyond. We recently reported on a new implementation of CAD in Maple which implemented the original algorithm of Collins and the subsequent improvement to projection by McCallum. Our implementation was in contrast to Maple's in-built CAD command, based on a quite separate theory. Although initially developed as an investigative tool to compare the algorithms, we found and reported that our code offered functionality not currently available in any other existing implementations. One particularly important piece of functionality is the ability to produce order-invariant CADs. This has allowed us to extend the implementation to produce CADs invariant with respect to either equational constraints (ECCADs) or the truth-tables of sequences of formulae (TTICADs). This new functionality is contained in the second release of our code, along with commands to consider problem formulation which can be a major factor in the tractability of a CAD. In the report we describe the new functionality and some theoretical discoveries it prompted. We describe how the CADs produced using equational constraints are able to take advantage of not just improved projection but also improvements in the lifting phase. We also present an extension to the original TTICAD algorithm which increases both the applicability of TTICAD and its relative benefit over other algorithms. The code and an introductory Maple worksheet / pdf demonstrating the full functionality of the package are freely available online.
Modeling and Control of Rare Segments in BitTorrent with Epidemic Dynamics
Venue: arXiv cs.NI 2013
Year: 2013

Despite its existing incentives for leecher cooperation, BitTorrent file sharing fundamentally relies on the presence of seeder peers. Seeder peers essentially operate outside the BitTorrent incentives, with two caveats: slow downlinks lead to increased numbers of "temporary" seeders (who left their console, but will terminate their seeder role when they return), and the copyright liability boon that file segmentation offers for permanent seeders. Using a simple epidemic model for a two-segment BitTorrent swarm, we focus on the BitTorrent rule to disseminate the (locally) rarest segments first. With our model, we show that the rarest-segment first rule minimizes transition time to seeder (complete file acquisition) and equalizes the segment populations in steady-state. We discuss how alternative dissemination rules may {\em beneficially increase} file acquisition times causing leechers to remain in the system longer (particularly as temporary seeders). The result is that leechers are further enticed to cooperate. This eliminates the threat of extinction of rare segments which is prevented by the needed presence of permanent seeders. Our model allows us to study the corresponding trade-offs between performance improvement, load on permanent seeders, and content availability, which we leave for future work. Finally, interpreting the two-segment model as one involving a rare segment and a "lumped" segment representing the rest, we study a model that jointly considers control of rare segments and different uplinks causing "choking," where high-uplink peers will not engage in certain transactions with low-uplink peers.
Set-Difference Range Queries
Venue: arXiv cs.DS 2013
Year: 2013

We introduce the problem of performing set-difference range queries, where answers to queries are set-theoretic symmetric differences between sets of items in two geometric ranges. We describe a general framework for answering such queries based on a novel use of data-streaming sketches we call signed symmetric-difference sketches. We show that such sketches can be realized using invertible Bloom filters (IBFs), which can be composed, differenced, and searched so as to solve set-difference range queries in a wide range of scenarios.
Scalable Successive-Cancellation Hardware Decoder for Polar Codes
Venue: arXiv cs.IT 2013
Year: 2013

Polar codes, discovered by Arıkan, are the first error-correcting codes with an explicit construction to provably achieve channel capacity, asymptotically. However, their error-correction performance at finite lengths tends to be lower than existing capacity-approaching schemes. Using the successive-cancellation algorithm, polar decoders can be designed for very long codes, with low hardware complexity, leveraging the regular structure of such codes. We present an architecture and an implementation of a scalable hardware decoder based on this algorithm. This design is shown to scale to code lengths of up to N = 2^20 on an Altera Stratix IV FPGA, limited almost exclusively by the amount of available SRAM.
iCub World: Friendly Robots Help Building Good Vision Data-Sets
Venue: arXiv cs.CV 2013
Year: 2013

In this paper we present and start analyzing the iCub World data-set, an object recognition data-set, we acquired using a Human-Robot Interaction (HRI) scheme and the iCub humanoid robot platform. Our set up allows for rapid acquisition and annotation of data with corresponding ground truth. While more constrained in its scopes -- the iCub world is essentially a robotics research lab -- we demonstrate how the proposed data-set poses challenges to current recognition systems. The iCubWorld data-set is publicly available. The data-set can be downloaded from: http://www.iit.it/en/projects/data-sets.html.
Faster Deterministic Algorithms for Packing, Matching and $t$-Dominating Set Problems
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we devise three deterministic algorithms for solving the $m$-set $k$-packing, $m$-dimensional $k$-matching, and $t$-dominating set problems in time $O^*(5.44^{mk})$, $O^*(5.44^{(m-1)k})$ and $O^*(5.44^{t})$, respectively. Although recently there has been remarkable progress on randomized solutions to those problems, our bounds make good improvements on the best known bounds for deterministic solutions to those problems.
Performance and Energy Efficiency of Mobile Data Offloading with Mobility Prediction and Prefetching
Venue: arXiv cs.NI 2013
Year: 2013

We present a detailed evaluation of procedures that exploit mobility prediction and prefetching to enhance offloading of traffic from mobile networks to WiFi hotspots, for both delay tolerant and delay sensitive traffic. We consider empirical measurements and evaluate the percentage of offloaded traffic, data transfer delay, and energy consumption of the proposed procedures. Our results illustrate how various factors such as mobile, WiFi and hotspot backhaul throughput, data size, number of hotspots, along with time and throughput estimation errors, influence the performance and energy efficiency of mobile data offloading enhanced with mobility prediction and prefetching.
Low latency via redundancy
Venue: arXiv cs.NI 2013
Year: 2013

Low latency is critical for interactive networked applications. But while we know how to scale systems to increase capacity, reducing latency --- especially the tail of the latency distribution --- can be much more difficult. In this paper, we argue that the use of redundancy is an effective way to convert extra capacity into reduced latency. By initiating redundant operations across diverse resources and using the first result which completes, redundancy improves a system's latency even under exceptional conditions. We study the tradeoff with added system utilization, characterizing the situations in which replicating all tasks reduces mean latency. We then demonstrate empirically that replicating all operations can result in significant mean and tail latency reduction in real-world systems including DNS queries, database servers, and packet forwarding within networks.