OpenRaiser/Intern-Atlas huggingface dataset:
A Program Logic for Verifying Secure Routing Protocols
Venue: arXiv cs.LO 2015
Year: 2015

The Internet, as it stands today, is highly vulnerable to attacks. However, little has been done to understand and verify the formal security guarantees of proposed secure inter-domain routing protocols, such as Secure BGP (S-BGP). In this paper, we develop a sound program logic for SANDLog-a declarative specification language for secure routing protocols for verifying properties of these protocols. We prove invariant properties of SANDLog programs that run in an adversarial environment. As a step towards automated verification, we implement a verification condition generator (VCGen) to automatically extract proof obligations. VCGen is integrated into a compiler for SANDLog that can generate executable protocol implementations; and thus, both verification and empirical evaluation of secure routing protocols can be carried out in this unified framework. To validate our framework, we encoded several proposed secure routing mechanisms in SANDLog, verified variants of path authenticity properties by manually discharging the generated verification conditions in Coq, and generated executable code based on SANDLog specification and ran the code in simulation.
semMatch: Road Semantics-based Accurate Map Matching for Challenging Positioning Data
Venue: arXiv cs.CY 2015
Year: 2015

Map matching has been used to reduce the noisiness of the location estimates by aligning them to the road network on a digital map. A growing number of applications, e.g. energy-efficient localization and cellular provider side localization, depend on the availability of only sparse and coarse-grained positioning data; leading to a challenging map matching process. In this paper, we present semMatch: a system that can provide accurate HMM-based map matching for challenging positioning traces. semMatch leverages the smartphone's inertial sensors to detect different road semantics; such as speed bumps, tunnels, and turns; and uses them in a mathe-matically-principled way as hints to overcome the sparse, noisy, and coarse-grained input positioning data, improving the HMM map matching accuracy and efficiency. To do that, semMatch applies a series of preprocessing modules to handle the noisy locations. The filtered location data is then processed by the core of semMatch system using a novel incremental HMM algorithm that combines a semantics-enriched digital map and the car's ambient road semantics in its estimation process. We have evaluated semMatch using traces collected from different cities covering more than 150km under different harsh scenarios including coarse-grained cellular-based positioning data, sparse GPS traces with extremely low sampling rate, and noisy traces with a large number of back-and-force transitions. The results show that semMatch significantly outperforms traditional map matching algorithms under all scenarios, with an enhancement of at least 416% and 894% in precision and recall respectively in the most difficult cases. This highlights its promise as a next generation map matching algorithm for challenging environments.
Sensitivity Gains by Mismatched Probabilistic Shaping for Optical Communication Systems
Venue: arXiv cs.IT 2015
Year: 2015

Probabilistic shaping of quadrature amplitude modulation (QAM) is used to enhance the sensitivity of an optical communication system. Sensitivity gains of 0.43 dB and 0.8 dB are demonstrated in back-to-back experiments by shaping of 16QAM and 64QAM, respectively. Further, numerical simulations are used to prove the robustness of probabilistic shaping to a mismatch between the constellation used and the signal-to-noise ratio (SNR) of the channel. It is found that, accepting a 0.1 dB SNR penalty, only four shaping distributions are required to support these gains for 64QAM.
On the Complexity of Rainbow Coloring Problems
Venue: arXiv cs.DM 2015
Year: 2015

An edge-colored graph $G$ is said to be rainbow connected if between each pair of vertices there exists a path which uses each color at most once. The rainbow connection number, denoted by $rc(G)$, is the minimum number of colors needed to make $G$ rainbow connected. Along with its variants, which consider vertex colorings and/or so-called strong colorings, the rainbow connection number has been studied from both the algorithmic and graph-theoretic points of view. In this paper we present a range of new results on the computational complexity of computing the four major variants of the rainbow connection number. In particular, we prove that the \textsc{Strong Rainbow Vertex Coloring} problem is $NP$-complete even on graphs of diameter $3$. We show that when the number of colors is fixed, then all of the considered problems can be solved in linear time on graphs of bounded treewidth. Moreover, we provide a linear-time algorithm which decides whether it is possible to obtain a rainbow coloring by saving a fixed number of colors from a trivial upper bound. Finally, we give a linear-time algorithm for computing the exact rainbow connection numbers for three variants of the problem on graphs of bounded vertex cover number.
Choosing the right home location definition method for the given dataset
Venue: arXiv cs.SI 2015
Year: 2015

Ever since first mobile phones equipped with GPS came to the market, knowing the exact user location has become a holy grail of almost every service that lives in the digital world. Starting with the idea of location based services, nowadays it is not only important to know where users are in real time, but also to be able predict where they will be in future. Moreover, it is not enough to know user location in form of latitude longitude coordinates provided by GPS devices, but also to give a place its meaning (i.e., semantically label it), in particular detecting the most probable home location for the given user. The aim of this paper is to provide novel insights on differences among the ways how different types of human digital trails represent the actual mobility patterns and therefore the differences between the approaches interpreting those trails for inferring said patterns. Namely, with the emergence of different digital sources that provide information about user mobility, it is of vital importance to fully understand that not all of them capture exactly the same picture. With that being said, in this paper we start from an example showing how human mobility patterns described by means of radius of gyration are different for Flickr social network and dataset of bank card transactions. Rather than capturing human movements closer to their homes, Flickr more often reveals people travel mode. Consequently, home location inferring methods used in both cases cannot be the same. We consider several methods for home location definition known from the literature and demonstrate that although for bank card transactions they provide highly consistent results, home location definition detection methods applied to Flickr dataset happen to be way more sensitive to the method selected, stressing the paramount importance of adjusting the method to the specific dataset being used.
Iterative distributed minimum total-MSE approach for secure communications in MIMO interference channels
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the problem of joint transmit precoding (TPC) matrix and receive filter matrix design subject to both secrecy and per-transmitter power constraints in the MIMO interference channel, where $K$ legitimate transmitter-receiver pairs communicate in the presence of an external eavesdropper. Explicitly, we jointly design the TPC and receive filter matrices based on the minimum total mean-squared error (MT-MSE) criterion under a given and feasible information-theoretic degrees of freedom. More specifically, we formulate this problem by minimizing the total MSEs of the signals communicated between the legitimate transmitter-receiver pairs, whilst ensuring that the MSE of the signals decoded by the eavesdropper remains higher than a certain threshold. We demonstrate that the joint design of the TPC and receive filter matrices subject to both secrecy and transmit power constraints can be accomplished by an efficient iterative distributed algorithm. The convergence of the proposed iterative algorithm is characterized as well. Furthermore, the performance of the proposed algorithm, including both its secrecy rate and MSE, is characterized with the aid of numerical results. We demonstrate that the proposed algorithm outperforms the traditional interference alignment (IA) algorithm in terms of both the achievable secrecy rate and the MSE. As a benefit, secure communications can be guaranteed by the proposed algorithm for the MIMO interference channel even in the presence of a "sophisticated/strong" eavesdropper, whose number of antennas is much higher than that of each legitimate transmitter and receiver.
Exploring Invariants & Patterns in Human Commute time
Venue: arXiv cs.CY 2015
Year: 2015

In everyday life, the process of commuting to work from home happens every now and then. And the research of commute characteristics is useful for urban function planning. For humans, the commute of an individual seems revealing no regular universal patterns, but it is true that people try to find a satisfactory state of life regarding commute issues. Commute time and distance are most important indicators to measure the degree of this satisfaction. Marchetti states a certain regularity in human commute time distribution - specifically, it states that no matter when, where and how far away people live, they always tend to spend approximately the same average time for their daily commute. However, will the rapid development of cities nowadays as well as serious challenges brought by economic development affect this constant? If there are novel characteristics? We revisit these problems using fine grained communication data in two Chinese major cities during recent two years. The results indicate that the commute time has been slightly increased from Marchetti's constant with the development of society. People's overall travel budgets have been increased, more concretely speaking, for medium and long distance commuters, their endurance limit for commute time is enhanced during the passing years, and fluctuates around a constant; for short distance commuters, their commute time increases with the distance. Moreover, the population distribution in every commute distance shows strong cross-city similarity and does not change much over two years.
Radio Resource Management Based on Reused Frequency Allocation for Dynamic Channel Borrowing Scheme in Wireless Networks
Venue: arXiv cs.NI 2015
Year: 2015

In the modern era, cellular communication consumers are exponentially increasing as they find the system more user-friendly. Due to enormous users and their numerous demands, it has become a mandate to make the best use of the limited radio resources that assures the highest standard of Quality of Service (QoS). To reach the guaranteed level of QoS for the maximum number of users, maximum utilization of bandwidth is not only the key issue to be considered, rather some other factors like interference, call blocking probability etc. are also needed to keep under deliberation. The lower performances of these factors may retrograde the overall cellular networks performances. Keeping these difficulties under consideration, we propose an effective dynamic channel borrowing model that safeguards better QoS, other factors as well. The proposed scheme reduces the excessive overall call blocking probability and does interference mitigation without sacrificing bandwidth utilization. The proposed scheme is modeled in such a way that the cells are bifurcated after the channel borrowing process if the borrowed channels have the same type of frequency band (i.e. reused frequency). We also propose that the unoccupied interfering channels of adjacent cells can also be inactivated, instead of cell bifurcation for interference mitigation. The simulation endings show satisfactory performances in terms of overall call blocking probability and bandwidth utilization that are compared to the conventional scheme without channel borrowing. Furthermore, signal to interference plus noise ratio (SINR) level, capacity, and outage probability are compared to the conventional scheme without interference mitigation after channel borrowing that may attract the considerable concentration to the operators.
Better Exploiting OS-CNNs for Better Event Recognition in Images
Venue: arXiv cs.CV 2015
Year: 2015

Event recognition from still images is one of the most important problems for image understanding. However, compared with object recognition and scene recognition, event recognition has received much less research attention in computer vision community. This paper addresses the problem of cultural event recognition in still images and focuses on applying deep learning methods on this problem. In particular, we utilize the successful architecture of Object-Scene Convolutional Neural Networks (OS-CNNs) to perform event recognition. OS-CNNs are composed of object nets and scene nets, which transfer the learned representations from the pre-trained models on large-scale object and scene recognition datasets, respectively. We propose four types of scenarios to explore OS-CNNs for event recognition by treating them as either "end-to-end event predictors" or "generic feature extractors". Our experimental results demonstrate that the global and local representations of OS-CNNs are complementary to each other. Finally, based on our investigation of OS-CNNs, we come up with a solution for the cultural event recognition track at the ICCV ChaLearn Looking at People (LAP) challenge 2015. Our team secures the third place at this challenge and our result is very close to the best performance.
repAIrC: A Tool for Ensuring Data Consistency by Means of Active Integrity Constraints
Venue: arXiv cs.DB 2015
Year: 2015

Consistency of knowledge repositories is of prime importance in organization management. Integrity constraints are a well-known vehicle for specifying data consistency requirements in knowledge bases; in particular, active integrity constraints go one step further, allowing the specification of preferred ways to overcome inconsistent situations in the context of database management. This paper describes a tool to validate an SQL database with respect to a given set of active integrity constraints, proposing possible repairs in case the database is inconsistent. The tool is able to work with the different kinds of repairs proposed in the literature, namely simple, founded, well-founded and justified repairs. It also implements strategies for parallelizing the search for them, allowing the user both to compute partitions of independent or stratified active integrity constraints, and to apply these partitions to find repairs of inconsistent databases efficiently in parallel.
Cut-Set Bound Is Loose for Gaussian Relay Networks
Venue: arXiv cs.IT 2015
Year: 2015

The cut-set bound developed by Cover and El Gamal in 1979 has since remained the best known upper bound on the capacity of the Gaussian relay channel. We develop a new upper bound on the capacity of the Gaussian primitive relay channel which is tighter than the cut-set bound. Our proof is based on typicality arguments and concentration of Gaussian measure. Combined with a simple tensorization argument proposed by Courtade and Ozgur in 2015, our result also implies that the current capacity approximations for Gaussian relay networks, which have linear gap to the cut-set bound in the number of nodes, are order-optimal and leads to a lower bound on the pre-constant.
Reachability problems for PAMs
Venue: arXiv cs.NA 2015
Year: 2015

Piecewise affine maps (PAMs) are frequently used as a reference model to show the openness of the reachability questions in other systems. The reachability problem for one-dimentional PAM is still open even if we define it with only two intervals. As the main contribution of this paper we introduce new techniques for solving reachability problems based on p-adic norms and weights as well as showing decidability for two classes of maps. Then we show the connections between topological properties for PAM's orbits, reachability problems and representation of numbers in a rational base system. Finally we show a particular instance where the uniform distribution of the original orbit may not remain uniform or even dense after making regular shifts and taking a fractional part in that sequence.
Object-Oriented Dynamic Networks
Venue: arXiv cs.AI 2015
Year: 2015

This paper contains description of such knowledge representation model as Object-Oriented Dynamic Network (OODN), which gives us an opportunity to represent knowledge, which can be modified in time, to build new relations between objects and classes of objects and to represent results of their modifications. The model is based on representation of objects via their properties and methods. It gives us a possibility to classify the objects and, in a sense, to build hierarchy of their types. Furthermore, it enables to represent relation of modification between concepts, to build new classes of objects based on existing classes and to create sets and multisets of concepts. OODN can be represented as a connected and directed graph, where nodes are concepts and edges are relations between them. Using such model of knowledge representation, we can consider modifications of knowledge and movement through the graph of network as a process of logical reasoning or finding the right solutions or creativity, etc. The proposed approach gives us an opportunity to model some aspects of human knowledge system and main mechanisms of human thought, in particular getting a new experience and knowledge.
A Privacy Preserving Improvement for SRTA in Telecare Systems
Venue: arXiv cs.CR 2015
Year: 2015

Radio Frequency Identification (RFID) is a modern communication technology, which provides authentication and identification through a nonphysical contact. Recently, the use of this technology is almost developed in healthcare environments. Although RFID technology can prepare sagacity in systems, privacy and security issues ought to be considered before. Recently, in 2015, Li et al. proposed SRTA, a hash-based RFID authentication protocol in medication verification for healthcare. In this paper, we study this protocol and show that SRTA protocol is vulnerable to traceability, impersonation and Dos attacks. So it does not provide the privacy and security of RFID end users. Therefore, we propose an improved secure and efficient RFID authentication protocol to enhance the performance of Li et al. method. Our analyze show that the existing weaknesses of SRTA protocol are eliminated in our proposed protocol.
Reducing one-to-many problem in Voice Conversion by equalizing the formant locations using dynamic frequency warping
Venue: arXiv cs.SD 2015
Year: 2015

In this study, we investigate a solution to reduce the effect of one-to-many problem in voice conversion. One-to-many problem in VC happens when two very similar speech segments in source speaker have corresponding speech segments in target speaker that are not similar to each other. As a result, the mapper function usually over-smoothes the generated features in order to be similar to both target speech segments. In this study, we propose to equalize the formant location of source-target frame pairs using dynamic frequency warping in order to reduce the complexity. After the conversion, another dynamic frequency warping is further applied to reverse the effect of formant location equalization during the training. The subjective experiments showed that the proposed approach improves the speech quality significantly.
Inheritance in Object-Oriented Knowledge Representation
Venue: arXiv cs.AI 2015
Year: 2015

This paper contains the consideration of inheritance mechanism in such knowledge representation models as object-oriented programming, frames and object-oriented dynamic networks. In addition, inheritance within representation of vague and imprecise knowledge are also discussed. New types of inheritance, general classification of all known inheritance types and approach, which allows avoiding in many cases problems with exceptions, redundancy and ambiguity within object-oriented dynamic networks and their fuzzy extension, are introduced in the paper. The proposed approach bases on conception of homogeneous and inhomogeneous or heterogeneous class of objects, which allow building of inheritance hierarchy more flexibly and efficiently.
PRIMAL: PRofIt Maximization Avatar pLacement for Mobile Edge Computing
Venue: arXiv cs.NI 2015
Year: 2015

We propose a cloudlet network architecture to bring the computing resources from the centralized cloud to the edge. Thus, each User Equipment (UE) can communicate with its Avatar, a software clone located in a cloudlet, with lower end-to-end (E2E) delay. However, UEs are moving over time, and so the low E2E delay may not be maintained if UEs' Avatars stay in their original cloudlets. Thus, live Avatar migration (i.e., migrating a UE's Avatar to a suitable cloudlet based on the UE's location) is enabled to maintain low E2E delay between each UE and its Avatar. On the other hand, the migration itself incurs extra overheads in terms of resources of the Avatar, which compromise the performance of applications running in the Avatar. By considering the gain (i.e., the E2E delay reduction) and the cost (i.e., the migration overheads) of the live Avatar migration, we propose a PRofIt Maximization Avatar pLacement (PRIMAL) strategy for the cloudlet network in order to optimize the tradeoff between the migration gain and the migration cost by selectively migrating the Avatars to their optimal locations. Simulation results demonstrate that as compared to the other two strategies (i.e., Follow Me Avatar and Static), PRIMAL maximizes the profit in terms of maintaining the low average E2E delay between UEs and their Avatars and minimizing the migration cost simultaneously.
Filtrated Spectral Algebraic Subspace Clustering
Venue: arXiv cs.CV 2015
Year: 2015

Algebraic Subspace Clustering (ASC) is a simple and elegant method based on polynomial fitting and differentiation for clustering noiseless data drawn from an arbitrary union of subspaces. In practice, however, ASC is limited to equi-dimensional subspaces because the estimation of the subspace dimension via algebraic methods is sensitive to noise. This paper proposes a new ASC algorithm that can handle noisy data drawn from subspaces of arbitrary dimensions. The key ideas are (1) to construct, at each point, a decreasing sequence of subspaces containing the subspace passing through that point; (2) to use the distances from any other point to each subspace in the sequence to construct a subspace clustering affinity, which is superior to alternative affinities both in theory and in practice. Experiments on the Hopkins 155 dataset demonstrate the superiority of the proposed method with respect to sparse and low rank subspace clustering methods.
A Potential Approach to Overcome Data Limitation in Scientific Publication Recommendation
Venue: arXiv cs.DL 2015
Year: 2015

Data are essential for the experiments of relevant scientific publication recommendation methods but it is difficult to build ground truth data. A naturally promising solution is using publications that are referenced by researchers to build their ground truth data. Unfortunately, this approach has not been explored in the literature, so its applicability is still a gap in our knowledge. In this research, we systematically study this approach by theoretical and empirical analyses. In general, the results show that this approach is reasonable and has many advantages. However, the empirical analysis shows both positive and negative results. We conclude that, in some situations, this is a useful alternative approach toward overcoming data limitation. Based on this approach, we build and publish a dataset in computer science domain to help advancing other researches.