OpenRaiser/Intern-Atlas huggingface dataset:
HRank: A Path based Ranking Framework in Heterogeneous Information Network
Venue: arXiv cs.IR 2014
Year: 2014

Recently, there is a surge of interests on heterogeneous information network analysis. As a newly emerging network model, heterogeneous information networks have many unique features (e.g., complex structure and rich semantics) and a number of interesting data mining tasks have been exploited in this kind of networks, such as similarity measure, clustering, and classification. Although evaluating the importance of objects has been well studied in homogeneous networks, it is not yet exploited in heterogeneous networks. In this paper, we study the ranking problem in heterogeneous networks and propose the HRank framework to evaluate the importance of multiple types of objects and meta paths. Since the importance of objects depends upon the meta paths in heterogeneous networks, HRank develops a path based random walk process. Moreover, a constrained meta path is proposed to subtly capture the rich semantics in heterogeneous networks. Furthermore, HRank can simultaneously determine the importance of objects and meta paths through applying the tensor analysis. Extensive experiments on three real datasets show that HRank can effectively evaluate the importance of objects and paths together. Moreover, the constrained meta path shows its potential on mining subtle semantics by obtaining more accurate ranking results.
Exposition: Synthesis via Functional Interpretation
Venue: arXiv cs.LO 2014
Year: 2014

The aim of this short paper is to give a practical introduction to functional interpretation of proofs for computer scientists interested in synthesis.
DDoS Attack and Interception Resistance IP Fast Hopping Based Protocol
Venue: arXiv cs.NI 2014
Year: 2014

Denial-of-Service attacks continue to be a serious problem for the Internet community despite the fact that a large number of defense approaches has been proposed by the research community. In this paper we introduce IP Fast Hopping, easily deployable and effective network-layer architecture against DDoS attacks. Our approach also provides an easy way for clients to hide content and destination server of theirs communication sessions. We describe a method of dynamic server IP address change and all modules necessary to implement the approach.
Difficulty Rating of Sudoku Puzzles: An Overview and Evaluation
Venue: arXiv cs.AI 2014
Year: 2014

How can we predict the difficulty of a Sudoku puzzle? We give an overview of difficulty rating metrics and evaluate them on extensive dataset on human problem solving (more then 1700 Sudoku puzzles, hundreds of solvers). The best results are obtained using a computational model of human solving activity. Using the model we show that there are two sources of the problem difficulty: complexity of individual steps (logic operations) and structure of dependency among steps. We also describe metrics based on analysis of solutions under relaxed constraints -- a novel approach inspired by phase transition phenomenon in the graph coloring problem. In our discussion we focus not just on the performance of individual metrics on the Sudoku puzzle, but also on their generalizability and applicability to other problems.
DimmWitted: A Study of Main-Memory Statistical Analytics
Venue: arXiv cs.DB 2014
Year: 2014

We perform the first study of the tradeoff space of access methods and replication to support statistical analytics using first-order methods executed in the main memory of a Non-Uniform Memory Access (NUMA) machine. Statistical analytics systems differ from conventional SQL-analytics in the amount and types of memory incoherence they can tolerate. Our goal is to understand tradeoffs in accessing the data in row- or column-order and at what granularity one should share the model and data for a statistical task. We study this new tradeoff space, and discover there are tradeoffs between hardware and statistical efficiency. We argue that our tradeoff study may provide valuable information for designers of analytics engines: for each system we consider, our prototype engine can run at least one popular task at least 100x faster. We conduct our study across five architectures using popular models including SVMs, logistic regression, Gibbs sampling, and neural networks.
Building A Large Concept Bank for Representing Events in Video
Venue: arXiv cs.MM 2014
Year: 2014

Concept-based video representation has proven to be effective in complex event detection. However, existing methods either manually design concepts or directly adopt concept libraries not specifically designed for events. In this paper, we propose to build Concept Bank, the largest concept library consisting of 4,876 concepts specifically designed to cover 631 real-world events. To construct the Concept Bank, we first gather a comprehensive event collection from WikiHow, a collaborative writing project that aims to build the world's largest manual for any possible How-To event. For each event, we then search Flickr and discover relevant concepts from the tags of the returned images. We train a Multiple Kernel Linear SVM for each discovered concept as a concept detector in Concept Bank. We organize the concepts into a five-layer tree structure, in which the higher-level nodes correspond to the event categories while the leaf nodes are the event-specific concepts discovered for each event. Based on such tree ontology, we develop a semantic matching method to select relevant concepts for each textual event query, and then apply the corresponding concept detectors to generate concept-based video representations. We use TRECVID Multimedia Event Detection 2013 and Columbia Consumer Video open source event definitions and videos as our test sets and show very promising results on two video event detection tasks: event modeling over concept space and zero-shot event retrieval. To the best of our knowledge, this is the largest concept library covering the largest number of real-world events.
The Call of the Crowd: Event Participation in Location-based Social Services
Venue: arXiv cs.SI 2014
Year: 2014

Understanding the social and behavioral forces behind event participation is not only interesting from the viewpoint of social science, but also has important applications in the design of personalized event recommender systems. This paper takes advantage of data from a widely used location-based social network, Foursquare, to analyze event patterns in three metropolitan cities. We put forward several hypotheses on the motivating factors of user participation and confirm that social aspects play a major role in determining the likelihood of a user to participate in an event. While an explicit social filtering signal accounting for whether friends are attending dominates the factors, the popularity of an event proves to also be a strong attractor. Further, we capture an implicit social signal by performing random walks in a high dimensional graph that encodes the place type preferences of friends and that proves especially suited to identify relevant niche events for users. Our findings on the extent to which the various temporal, spatial and social aspects underlie users' event preferences lead us to further hypothesize that a combination of factors better models users' event interests. We verify this through a supervised learning framework. We show that for one in three users in London and one in five users in New York and Chicago it identifies the exact event the user would attend among the pool of suggestions.
Downlink Analysis for a Heterogeneous Cellular Network
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, a comprehensive study of the the downlink performance in a heterogeneous cellular network (or hetnet) is conducted. A general hetnet model is considered consisting of an arbitrary number of open-access and closed-access tier of base stations (BSs) arranged according to independent homogeneous Poisson point processes. The BSs of each tier have a constant transmission power, random fading coefficient with an arbitrary distribution and arbitrary path-loss exponent of the power-law path-loss model. For such a system, analytical characterizations for the coverage probability and average rate at an arbitrary mobile-station (MS), and average per-tier load are derived for both the max-SINR connectivity and nearest-BS connectivity models. Using stochastic ordering, interesting properties and simplifications for the hetnet downlink performance are derived by relating these two connectivity models to the maximum instantaneous received power (MIRP) connectivity model and the maximum biased received power (MBRP) connectivity models, respectively, providing good insights about the hetnets and the downlink performance in these complex networks. Furthermore, the results also demonstrate the effectiveness and analytical tractability of the stochastic geometric approach to study the hetnet performance.
Asymptotically-Optimal Motion Planning using Lower Bounds on Cost
Venue: arXiv cs.RO 2014
Year: 2014

Many path-finding algorithms on graphs such as A* are sped up by using a heuristic function that gives lower bounds on the cost to reach the goal. Aiming to apply similar techniques to speed up sampling-based motion-planning algorithms, we use effective lower bounds on the cost between configurations to tightly estimate the cost-to-go. We then use these estimates in an anytime asymptotically-optimal algorithm which we call Motion Planning using Lower Bounds (MPLB). MPLB is based on the Fast Marching Trees (FMT*) algorithm recently presented by Janson and Pavone. An advantage of our approach is that in many cases (especially as the number of samples grows) the weight of collision detection in the computation is almost negligible with respect to nearest-neighbor calls. We prove that MPLB performs no more collision-detection calls than an anytime version of FMT*. Additionally, we demonstrate in simulations that for certain scenarios, the algorithmic tools presented here enable efficiently producing low-cost paths while spending only a small fraction of the running time on collision detection.
Irregular Fractional Repetition Code Optimization for Heterogeneous Cloud Storage
Venue: arXiv cs.IT 2014
Year: 2014

This paper presents a flexible irregular model for heterogeneous cloud storage systems and investigates how the cost of repairing failed nodes can be minimized. The fractional repetition code, originally designed for minimizing repair bandwidth for homogeneous storage systems, is generalized to the irregular fractional repetition code, which is adaptable to heterogeneous environments. The code structure and the associated storage allocation can be obtained by solving an integer linear programming problem. For moderate sized networks, a heuristic algorithm is proposed and shown to be near-optimal by computer simulations.
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm
Venue: arXiv cs.CC 2014
Year: 2014

We show that for every positive $ε> 0$, unless NP $\subset$ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than $2^{\log^{1-ε} n}$ by a reduction from the maximum label cover problem. Our result also implies that Approximate Graph Isomorphism is not robust and is in fact, $1 - ε$ vs $ε$ hard assuming the Unique Games Conjecture. Then, we present an $O(\sqrt{n})$-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms.
Optimal Cooperative Cognitive Relaying and Spectrum Access for an Energy Harvesting Cognitive Radio: Reinforcement Learning Approach
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we consider a cognitive setting under the context of cooperative communications, where the cognitive radio (CR) user is assumed to be a self-organized relay for the network. The CR user and the PU are assumed to be energy harvesters. The CR user cooperatively relays some of the undelivered packets of the primary user (PU). Specifically, the CR user stores a fraction of the undelivered primary packets in a relaying queue (buffer). It manages the flow of the undelivered primary packets to its relaying queue using the appropriate actions over time slots. Moreover, it has the decision of choosing the used queue for channel accessing at idle time slots (slots where the PU's queue is empty). It is assumed that one data packet transmission dissipates one energy packet. The optimal policy changes according to the primary and CR users arrival rates to the data and energy queues as well as the channels connectivity. The CR user saves energy for the PU by taking the responsibility of relaying the undelivered primary packets. It optimally organizes its own energy packets to maximize its payoff as time progresses.
Twitter in Academic Conferences: Usage, Networking and Participation over Time
Venue: arXiv cs.SI 2014
Year: 2014

Twitter is often referred to as a backchannel for conferences. While the main conference takes place in a physical setting, attendees and virtual attendees socialize, introduce new ideas or broadcast information by microblogging on Twitter. In this paper we analyze the scholars' Twitter use in 16 Computer Science conferences over a timespan of five years. Our primary finding is that over the years there are increasing differences with respect to conversation use and information use in Twitter. We studied the interaction network between users to understand whether assumptions about the structure of the conversations hold over time and between different types of interactions, such as retweets, replies, and mentions. While `people come and people go', we want to understand what keeps people stay with the conference on Twitter. By casting the problem to a classification task, we find different factors that contribute to the continuing participation of users to the online Twitter conference activity. These results have implications for research communities to implement strategies for continuous and active participation among members.
Capacity Analysis of LTE-Advanced HetNets with Reduced Power Subframes and Range Expansion
Venue: arXiv cs.IT 2014
Year: 2014

The time domain inter-cell interference coordination techniques specified in LTE Rel. 10 standard improves the throughput of picocell-edge users by protecting them from macrocell interference. On the other hand, it also degrades the aggregate capacity in macrocell because the macro base station (MBS) does not transmit data during certain subframes known as almost blank subframes. The MBS data transmission using reduced power subframes was standardized in LTE Rel. 11, which can improve the capacity in macrocell while not causing high interference to the nearby picocells. In order to get maximum benefit from the reduced power subframes, setting the key system parameters, such as the amount of power reduction, carries critical importance. Using stochastic geometry, this paper lays down a theoretical foundation for the performance evaluation of heterogeneous networks with reduced power subframes and range expansion bias. The analytic expressions for average capacity and 5th percentile throughput are derived as a function of transmit powers, node densities, and interference coordination parameters in a heterogeneous network scenario, and are validated through Monte Carlo simulations. Joint optimization of range expansion bias, power reduction factor, scheduling thresholds, and duty cycle of reduced power subframes are performed to study the trade-offs between aggregate capacity of a cell and fairness among the users. To validate our analysis, we also compare the stochastic geometry based theoretical results with the real MBS deployment (in the city of London) and the hexagonal-grid model. Our analysis shows that with optimum parameter settings, the LTE Rel. 11 with reduced power subframes can provide substantially better performance than the LTE Rel. 10 with almost blank subframes, in terms of both aggregate capacity and fairness.
Increasing Opportunistic Gain in Small Cells Through Energy-Aware User Cooperation
Venue: arXiv cs.NI 2014
Year: 2014

To meet the increasing demand for wireless capacity, future networks are likely to consist of dense layouts of small cells. The number of users in each cell is thus reduced which results in diminished gains from opportunistic scheduling, particularly under dynamic traffic loads. We propose an user-initiated base station (BS)-transparent traffic spreading approach that leverages user-user communication to increase BS scheduling flexibility. The proposed scheme can increase opportunistic gain and improve user performance. For a specified tradeoff between performance and power expenditure, we characterize the optimal policy by modeling the system as a Markov decision process and also present a heuristic algorithm that yields significant performance gains. Our simulations show that, in the performance-centric case, average file transfer delays are lowered by up to 20% even in homogeneous scenarios, and up to 50% with heterogeneous users. Further, we show that the bulk of the performance improvement can be achieved with a small increase in power expenditure, e.g., in an energy-sensitive case, up to 78% of the performance improvement can be typically achieved at only 20% of the power expenditure of the performance-centric case.
Multiple-Population Moment Estimation: Exploiting Inter-Population Correlation for Efficient Moment Estimation in Analog/Mixed-Signal Validation
Venue: arXiv cs.OH 2014
Year: 2014

Moment estimation is an important problem during circuit validation, in both pre-Silicon and post-Silicon stages. From the estimated moments, the probability of failure and parametric yield can be estimated at each circuit configuration and corner, and these metrics are used for design optimization and making product qualification decisions. The problem is especially difficult if only a very small sample size is allowed for measurement or simulation, as is the case for complex analog/mixed-signal circuits. In this paper, we propose an efficient moment estimation method, called Multiple-Population Moment Estimation (MPME), that significantly improves estimation accuracy under small sample size. The key idea is to leverage the data collected under different corners/configurations to improve the accuracy of moment estimation at each individual corner/configuration. Mathematically, we employ the hierarchical Bayesian framework to exploit the underlying correlation in the data. We apply the proposed method to several datasets including post-silicon measurements of a commercial high-speed I/O link, and demonstrate an average error reduction of up to 2$\times$, which can be equivalently translated to significant reduction of validation time and cost.
Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
Venue: arXiv cs.IT 2014
Year: 2014

Superposition codes are efficient for the Additive White Gaussian Noise channel. We provide here a replica analysis of the performances of these codes for large signals. We also consider a Bayesian Approximate Message Passing decoder based on a belief-propagation approach, and discuss its performance using the density evolution technic. Our main findings are 1) for the sizes we can access, the message-passing decoder outperforms other decoders studied in the literature 2) its performance is limited by a sharp phase transition and 3) while these codes reach capacity as $B$ (a crucial parameter in the code) increases, the performance of the message passing decoder worsen as the phase transition goes to lower rates.
ImNet: An Imperative Network Programming Language
Venue: arXiv cs.PL 2014
Year: 2014

One of the most recent architectures of networks is Software-Defined Networks (SDNs) using a con- troller appliance to control the set of switches on the network. The controlling process includes installing or uninstalling packet-processing rules on flow tables of switches. This paper presents a high-level imperative network programming language, called ImNet, to facilitate writing efficient, yet simple, programs executed by controller to manage switches. ImNet is simply-structured, expressive, compositional, and imperative. This paper also introduces an operational semantics to ImNet. Detailed examples of programs (with their operational semantics) constructed in ImNet are illustrated in the paper as well.
Covering nearly surface-embedded graphs with a fixed number of balls
Venue: arXiv cs.CG 2014
Year: 2014

A recent result of Chepoi, Estellon and Vaxes [DCG '07] states that any planar graph of diameter at most 2R can be covered by a constant number of balls of size R; put another way, there are a constant-sized subset of vertices within which every other vertex is distance half the diameter. We generalize this result to graphs embedded on surfaces of fixed genus with a fixed number of apices, making progress toward the conjecture that graphs excluding a fixed minor can also be covered by a constant number of balls. To do so, we develop two tools which may be of independent interest. The first gives a bound on the density of graphs drawn on a surface of genus $g$ having a limit on the number of pairwise-crossing edges. The second bounds the size of a non-contractible cycle in terms of the Euclidean norm of the degree sequence of a graph embedded on surface.
Flux-Limited Diffusion for Multiple Scattering in Participating Media
Venue: arXiv cs.GR 2014
Year: 2014

For the rendering of multiple scattering effects in participating media, methods based on the diffusion approximation are an extremely efficient alternative to Monte Carlo path tracing. However, in sufficiently transparent regions, classical diffusion approximation suffers from non-physical radiative fluxes which leads to a poor match to correct light transport. In particular, this prevents the application of classical diffusion approximation to heterogeneous media, where opaque material is embedded within transparent regions. To address this limitation, we introduce flux-limited diffusion, a technique from the astrophysics domain. This method provides a better approximation to light transport than classical diffusion approximation, particularly when applied to heterogeneous media, and hence broadens the applicability of diffusion-based techniques. We provide an algorithm for flux-limited diffusion, which is validated using the transport theory for a point light source in an infinite homogeneous medium. We further demonstrate that our implementation of flux-limited diffusion produces more accurate renderings of multiple scattering in various heterogeneous datasets than classical diffusion approximation, by comparing both methods to ground truth renderings obtained via volumetric path tracing.
On the Incremental Asymmetric Signatures
Venue: arXiv cs.CR 2014
Year: 2014

The purpose of incremental cryptography is to allow the updating of cryptographic forms of documents undergoing modifications, more efficiently than if we had to recompute them from scratch. This paper defines a framework for using securely a variant of the incremental hash function designed by Bok-Min Goi et al. The condition of use of their hash function is somehow impractical since they assume that the blocks of the message are all distinct. In this paper we show how we can discard this strong assumption so as to construct the first practical incremental asymmetric signature scheme that keeps efficient update operations. Finally, as the proposed scheme has the defect to severely expand the signature size, we propose a solution which drastically reduces this drawback.
EPICS process variables in different subnetworks and different IOCs without the use of the CaGateway
Venue: arXiv cs.NI 2014
Year: 2014

This technical document describes the comparison of the EPICS PV gateway and a new solution based on relay of UDP packets using the UDP-HELPER switch feature, iptables and a C program. The solution can be applied on environments that contain multiple sub-networks and a number of IOCs on the same host or multiple IOCs on the same sub-network.