OpenRaiser/Intern-Atlas huggingface dataset:
A decidable weakening of Compass Logic based on cone-shaped cardinal directions
Venue: arXiv cs.LO 2015
Year: 2015

We introduce a modal logic, called Cone Logic, whose formulas describe properties of points in the plane and spatial relationships between them. Points are labelled by proposition letters and spatial relations are induced by the four cone-shaped cardinal directions. Cone Logic can be seen as a weakening of Venema's Compass Logic. We prove that, unlike Compass Logic and other projection-based spatial logics, its satisfiability problem is decidable (precisely, PSPACE-complete). We also show that it is expressive enough to capture meaningful interval temporal logics - in particular, the interval temporal logic of Allen's relations "Begins", "During", and "Later", and their transposes.
On the Smoothness of Paging Algorithms
Venue: arXiv cs.DS 2015
Year: 2015

We study the smoothness of paging algorithms. How much can the number of page faults increase due to a perturbation of the request sequence? We call a paging algorithm smooth if the maximal increase in page faults is proportional to the number of changes in the request sequence. We also introduce quantitative smoothness notions that measure the smoothness of an algorithm. We derive lower and upper bounds on the smoothness of deterministic and randomized demand-paging and competitive algorithms. Among strongly-competitive deterministic algorithms LRU matches the lower bound, while FIFO matches the upper bound. Well-known randomized algorithms like Partition, Equitable, or Mark are shown not to be smooth. We introduce two new randomized algorithms, called Smoothed-LRU and LRU-Random. Smoothed- LRU allows to sacrifice competitiveness for smoothness, where the trade-off is controlled by a parameter. LRU-Random is at least as competitive as any deterministic algorithm while smoother.
A progressive mesh method for physical simulations using lattice Boltzmann method on single-node multi-gpu architectures
Venue: arXiv cs.DC 2015
Year: 2015

In this paper, a new progressive mesh algorithm is introduced in order to perform fast physical simulations by the use of a lattice Boltzmann method (LBM) on a single-node multi-GPU architecture. This algorithm is able to mesh automatically the simulation domain according to the propagation of fluids. This method can also be useful in order to perform various types of simulations on complex geometries. The use of this algorithm combined with the massive parallelism of GPUs allows to obtain very good performance in comparison with the static mesh method used in literature. Several simulations are shown in order to evaluate the algorithm.
Variable-state Latent Conditional Random Fields for Facial Expression Recognition and Action Unit Detection
Venue: arXiv cs.CV 2015
Year: 2015

Automated recognition of facial expressions of emotions, and detection of facial action units (AUs), from videos depends critically on modeling of their dynamics. These dynamics are characterized by changes in temporal phases (onset-apex-offset) and intensity of emotion expressions and AUs, the appearance of which may vary considerably among target subjects, making the recognition/detection task very challenging. The state-of-the-art Latent Conditional Random Fields (L-CRF) framework allows one to efficiently encode these dynamics through the latent states accounting for the temporal consistency in emotion expression and ordinal relationships between its intensity levels, these latent states are typically assumed to be either unordered (nominal) or fully ordered (ordinal). Yet, such an approach is often too restrictive. For instance, in the case of AU detection, the goal is to discriminate between the segments of an image sequence in which this AU is active or inactive. While the sequence segments containing activation of the target AU may better be described using ordinal latent states, the inactive segments better be described using unordered (nominal) latent states, as no assumption can be made about their underlying structure (since they can contain either neutral faces or activations of non-target AUs). To address this, we propose the variable-state L-CRF (VSL-CRF) model that automatically selects the optimal latent states for the target image sequence. To reduce the model overfitting either the nominal or ordinal latent states, we propose a novel graph-Laplacian regularization of the latent states. Our experiments on three public expression databases show that the proposed model achieves better generalization performance compared to traditional L-CRFs and other related state-of-the-art models.
Detecting and Handling Flash-Crowd Events on Cloud Environments
Venue: arXiv cs.DC 2015
Year: 2015

Cloud computing is a highly scalable computing paradigm where resources are delivered to users on demand via Internet. There are several areas that can benefit from cloud computing and one in special is gaining much attention: the flash-crowd handling. Flash-crowd events happen when servers are unable to handle the volume of requests for a specific content (or a set of contents) that actually reach it, thus causing some requests to be denied. For the handling of flash-crowd events in Web applications, clouds can offer elastic computing and storage capacity during these events in order to process all requests. However, it is important that flash-crowd events are quickly detected and the amount of resources to be instantiated during flash crowds is correctly estimated. In this paper, a new mechanism for detection of flash crowds based on concepts of entropy and total correlation is proposed. Moreover, the Flash-Crowd Handling Problem (FCHP) is precisely defined and formulated as an integer programming problem. A new algorithm for solving it, named FCHP-ILS, is also proposed. With FCHP-ILS the Web provider is able to replicate contents in the available resources and define the types and amount of resources to instantiate in the cloud during a flash-crowd event. Finally we present a case study, based on a synthetic dataset representing flash-crowd events in small scenarios aiming at comparing the proposed approach with de facto standard Amazon's Auto Scaling mechanism.
Are Generalized Cut-Set Bounds Tight for the Deterministic Interference Channel?
Venue: arXiv cs.IT 2015
Year: 2015

We propose the idea of extended networks, which is constructed by replicating the users in the two-user deterministic interference channel (DIC) and designing the interference structure among them, such that any rate that can be achieved by each user in the original network can also be achieved simultaneously by all replicas of that user in the extended network. We demonstrate that by carefully designing extended networks and applying the generalized cut-set (GCS) bound to them, we can derive a tight converse for the two-user DIC. Furthermore, we generalize our techniques to the three-user DIC, and demonstrate that the proposed approach also results in deriving a tight converse for the three-user DIC in the symmetric case.
SAP: an Architecture for Selectively Approximate Wireless Communication
Venue: arXiv cs.NI 2015
Year: 2015

Integrity checking is ubiquitous in data networks, but not all network traffic needs integrity protection. Many applications can tolerate slightly damaged data while still working acceptably, trading accuracy versus efficiency to save time and energy. Such applications should be able to receive damaged data if they so desire. In today's network stacks, lower-layer integrity checks discard damaged data regardless of the application's wishes, violating the End-to-End Principle. This paper argues for optional integrity checking and gently redesigns a commodity network architecture to support integrity-unprotected data. Our scheme, called Selective Approximate Protocol (SAP), allows applications to coordinate multiple network layers to accept potentially damaged data. Unlike previous schemes that targeted video or media streaming, SAP is generic. SAP's improved throughput and decreased retransmission rate is a good match for applications in the domain of approximate computing. Implemented atop WiFi as a case study, SAP works with existing physical layers and requires no hardware changes. SAP's benefits increase as channel conditions degrade. In tests of an error-tolerant file-transfer application over WiFi, SAP sped up transmission by about 30% on average.
Decidability in the logic of subsequences and supersequences
Venue: arXiv cs.LO 2015
Year: 2015

We consider first-order logics of sequences ordered by the subsequence ordering, aka sequence embedding. We show that the Σ_2 theory is undecidable, answering a question left open by Kuske. Regarding fragments with a bounded number of variables, we show that the FO2 theory is decidable while the FO3 theory is undecidable.
TRAP: using TaRgeted Ads to unveil Google personal Profiles
Venue: arXiv cs.SI 2015
Year: 2015

In the last decade, the advertisement market spread significantly in the web and mobile app system. Its effectiveness is also due thanks to the possibility to target the advertisement on the specific interests of the actual user, other than on the content of the website hosting the advertisement. In this scenario, became of great value services that collect and hence can provide information about the browsing user, like Facebook and Google. In this paper, we show how to maliciously exploit the Google Targeted Advertising system to infer personal information in Google user profiles. In particular, the attack we consider is external from Google and relies on combining data from Google AdWords with other data collected from a website of the Google Display Network. We validate the effectiveness of our proposed attack, also discussing possible application scenarios. The result of our research shows a significant practical privacy issue behind such type of targeted advertising service, and call for further investigation and the design of more privacy-aware solutions, possibly without impeding the current business model involved in online advertisement.
Counting Euler Tours in Undirected Bounded Treewidth Graphs
Venue: arXiv cs.CC 2015
Year: 2015

We show that counting Euler tours in undirected bounded tree-width graphs is tractable even in parallel - by proving a $\#SAC^1$ upper bound. This is in stark contrast to #P-completeness of the same problem in general graphs. Our main technical contribution is to show how (an instance of) dynamic programming on bounded \emph{clique-width} graphs can be performed efficiently in parallel. Thus we show that the sequential result of Espelage, Gurski and Wanke for efficiently computing Hamiltonian paths in bounded clique-width graphs can be adapted in the parallel setting to count the number of Hamiltonian paths which in turn is a tool for counting the number of Euler tours in bounded tree-width graphs. Our technique also yields parallel algorithms for counting longest paths and bipartite perfect matchings in bounded-clique width graphs. While establishing that counting Euler tours in bounded tree-width graphs can be computed by non-uniform monotone arithmetic circuits of polynomial degree (which characterize $\#SAC^1$) is relatively easy, establishing a uniform $\#SAC^1$ bound needs a careful use of polynomial interpolation.
Algebraic Diagonals and Walks
Venue: arXiv cs.SC 2015
Year: 2015

The diagonal of a multivariate power series F is the univariate power series Diag(F) generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case Diag(F) is an algebraic function. We propose an algorithm that computes an annihilating polynomial for Diag(F). Generically, it is its minimal polynomial and is obtained in time quasi-linear in its size. We show that this minimal polynomial has an exponential size with respect to the degree of the input rational function. We then address the related problem of enumerating directed lattice walks. The insight given by our study leads to a new method for expanding the generating power series of bridges, excursions and meanders. We show that their first N terms can be computed in quasi-linear complexity in N, without first computing a very large polynomial equation.
Universal and Determined Constructors of Multisets of Objects
Venue: arXiv cs.AI 2015
Year: 2015

This paper contains analysis of creation of sets and multisets as an approach for modeling of some aspects of human thinking. The creation of sets is considered within constructive object-oriented version of set theory (COOST), from different sides, in particular classical set theory, object-oriented programming (OOP) and development of intelligent information systems (IIS). The main feature of COOST in contrast to other versions of set theory is an opportunity to describe essences of objects more precisely, using their properties and methods, which can be applied to them. That is why this version of set theory is object-oriented and close to OOP. Within COOST, the author proposes universal constructor of multisets of objects that gives us a possibility to create arbitrary multisets of objects. In addition, a few determined constructors of multisets of objects, which allow creating multisets, using strictly defined schemas, also are proposed in the paper. Such constructors are very useful in cases of very big cardinalities of multisets, because they give us an opportunity to calculate a multiplicity of each object and cardinality of multiset before its creation. The proposed constructors of multisets of objects allow us to model in a sense corresponding processes of human thought, that in turn give us an opportunity to develop IIS, using these tools.
Dynamical spectral unmixing of multitemporal hyperspectral images
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we consider the problem of unmixing a time series of hyperspectral images. We propose a dynamical model based on linear mixing processes at each time instant. The spectral signatures and fractional abundances of the pure materials in the scene are seen as latent variables, and assumed to follow a general dynamical structure. Based on a simplified version of this model, we derive an efficient spectral unmixing algorithm to estimate the latent variables by performing alternating minimizations. The performance of the proposed approach is demonstrated on synthetic and real multitemporal hyperspectral images.
A Clock Synchronizer for Repeaterless Low Swing On-Chip Links
Venue: arXiv cs.AR 2015
Year: 2015

A clock synchronizing circuit for repeaterless low swing interconnects is presented in this paper. The circuit uses a delay locked loop (DLL) to generate multiple phases of the clock, of which the one closest to the center of the eye is picked by a phase detector loop. The picked phase is then further fine tuned by an analog voltage controlled delay to position the sampling clock at the center of the eye. A clock domain transfer circuit then transfers the sampled data to the receiver clock domain with a maximum latency of three clock cycles. The proposed synchronizer has been designed and fabricated in 130 nm UMC MM CMOS technology. The circuit consumes 1.4 mW from a 1.2 V supply at a data rate of 1.3 Gbps. Further, the proposed synchronizer has been designed and simulated in TSMC 65 nm CMOS technology. Post layout simulations show that the synchronizer consumes 1.5 mW from a 1 V supply, at a data rate of 4 Gbps in this technology.
Offloading in Software Defined Network at Edge with Information Asymmetry: A Contract Theoretical Approach
Venue: arXiv cs.NI 2015
Year: 2015

The proliferation of highly capable mobile devices such as smartphones and tablets has significantly increased the demand for wireless access. Software defined network (SDN) at edge is viewed as one promising technology to simplify the traffic offloading process for current wireless networks. In this paper, we investigate the incentive problem in SDN-at-edge of how to motivate a third party access points (APs) such as WiFi and smallcells to offload traffic for the central base stations (BSs). The APs will only admit the traffic from the BS under the precondition that their own traffic demand is satisfied. Under the information asymmetry that the APs know more about own traffic demands, the BS needs to distribute the payment in accordance with the APs' idle capacity to maintain a compatible incentive. First, we apply a contract-theoretic approach to model and analyze the service trading between the BS and APs. Furthermore, other two incentive mechanisms: optimal discrimination contract and linear pricing contract are introduced to serve as the comparisons of the anti adverse selection contract. Finally, the simulation results show that the contract can effectively incentivize APs' participation and offload the cellular network traffic. Furthermore, the anti adverse selection contract achieves the optimal outcome under the information asymmetry scenario.
Reimagining Internet Geographies: A User-Centric Ethnological Mapping of the World Wide Web
Venue: arXiv cs.SI 2015
Year: 2015

We propose a new user-centric imagery of the WWW that foregrounds local usage and its shaping forces, in contrast to existing imageries that prioritize Internet infrastructure. We construct ethnological maps of WWW usage through a network analysis of shared global traffic between 1000 most popular websites at three time points and develop granular measures for exploring global participation in online communication. Our results reveal the significant growth and thickening of online regional cultures associated with the global South. We draw attention to how local cultural identity, affirmative state intervention and economic contexts shape regional cultures on the global WWW.
Secure Image Steganography using Cryptography and Image Transposition
Venue: arXiv cs.MM 2015
Year: 2015

Information security is one of the most challenging problems in today's technological world. In order to secure the transmission of secret data over the public network (Internet), various schemes have been presented over the last decade. Steganography combined with cryptography, can be one of the best choices for solving this problem. This paper proposes a new steganographic method based on gray-level modification for true colour images using image transposition, secret key and cryptography. Both the secret key and secret information are initially encrypted using multiple encryption algorithms (bitxor operation, bits shuffling, and stego key-based encryption); these are, subsequently, hidden in the host image pixels. In addition, the input image is transposed before data hiding. Image transposition, bits shuffling, bitxoring, stego key-based encryption, and gray-level modification introduce five different security levels to the proposed scheme, making the data recovery extremely difficult for attackers. The proposed technique is evaluated by objective analysis using various image quality assessment metrics, producing promising results in terms of imperceptibility and security. Moreover, the high quality stego images and its minimal histogram changeability, also validate the effectiveness of the proposed approach.
Narrative Science Systems: A Review
Venue: arXiv cs.AI 2015
Year: 2015

Automatic narration of events and entities is the need of the hour, especially when live reporting is critical and volume of information to be narrated is huge. This paper discusses the challenges in this context, along with the algorithms used to build such systems. From a systematic study, we can infer that most of the work done in this area is related to statistical data. It was also found that subjective evaluation or contribution of experts is also limited for narration context.
A Critical Survey of Deconvolution Methods for Separating cell-types in Complex Tissues
Venue: arXiv cs.CE 2015
Year: 2015

Identifying concentrations of components from an observed mixture is a fundamental problem in signal processing. It has diverse applications in fields ranging from hyperspectral imaging to denoising biomedical sensors. This paper focuses on in-silico deconvolution of signals associated with complex tissues into their constitutive cell-type specific components, along with a quantitative characterization of the cell-types. Deconvolving mixed tissues/cell-types is useful in the removal of contaminants (e.g., surrounding cells) from tumor biopsies, as well as in monitoring changes in the cell population in response to treatment or infection. In these contexts, the observed signal from the mixture of cell-types is assumed to be a linear combination of the expression levels of genes in constitutive cell-types. The goal is to use known signals corresponding to individual cell-types along with a model of the mixing process to cast the deconvolution problem as a suitable optimization problem. In this paper, we present a survey of models, methods, and assumptions underlying deconvolution techniques. We investigate the choice of the different loss functions for evaluating estimation error, constraints on solutions, preprocessing and data filtering, feature selection, and regularization to enhance the quality of solutions, along with the impact of these choices on the performance of regression-based methods for deconvolution. We assess different combinations of these factors and use detailed statistical measures to evaluate their effectiveness. We identify shortcomings of current methods and avenues for further investigation. For many of the identified shortcomings, such as normalization issues and data filtering, we provide new solutions. We summarize our findings in a prescriptive step-by-step process, which can be applied to a wide range of deconvolution problems.
Predictive partitioning for efficient BFS traversal in social networks
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we show how graph structure can be used to drastically reduce the computational bottleneck of the Breadth First Search algorithm (the foundation of many graph traversal techniques). In particular, we address parallel implementations where the bottleneck is the number of messages between processors emitted at the peak iteration. First, we derive an expression for the expected degree distribution of vertices in the frontier of the algorithm which is shown to be highly skewed. Subsequently, we derive an expression for the expected message along an edge in a particular iteration. This skew suggests a weighted, iteration based, partition would be advantageous. Employing the METIS algorithm we then show empirically that such partitions can reduce the message overhead by up to 50% in some particular instances and in the order of 20% on average. These results have implications for graph processing in multiprocessor and distributed computing environments.