OpenRaiser/Intern-Atlas huggingface dataset:
Stability and Instability Conditions for Slotted Aloha with Exponential Backoff
Venue: arXiv cs.IT 2017
Year: 2017

This paper provides stability and instability conditions for slotted Aloha under the exponential backoff (EB) model with geometric law $i\mapsto b^{-i-i_0}$, when transmission buffers are in saturation, i.e., always full. In particular, we prove that for any number of users and for $b>1$ the system is: (i) ergodic for $i_0 >1$, (ii) null recurrent for $0<i_0\le 1$, and (iii) transient for $i_0=0$. Furthermore, when referring to a system with queues and Poisson arrivals, the system is shown to be stable whenever EB in saturation is stable with throughput $λ_0$ and the system input rate is upper-bounded as $λ<λ_0$.
Emergence of Distributed Coordination in the Kolkata Paise Restaurant Problem with Finite Information
Venue: arXiv cs.GT 2017
Year: 2017

In this paper, we study a large-scale distributed coordination problem and propose efficient adaptive strategies to solve the problem. The basic problem is to allocate finite number of resources to individual agents such that there is as little congestion as possible and the fraction of unutilized resources is reduced as far as possible. In the absence of a central planner and global information, agents can employ adaptive strategies that uses only finite knowledge about the competitors. In this paper, we show that a combination of finite information sets and reinforcement learning can increase the utilization rate of resources substantially.
On Robustness in Multilayer Interdependent Network
Venue: arXiv cs.NI 2017
Year: 2017

Critical Infrastructures like power and communication networks are highly interdependent on each other for their full functionality. Many significant research have been pursued to model the interdependency and failure analysis of these interdependent networks. However, most of these models fail to capture the complex interdependencies that might actually exist between the infrastructures. The \emph{Implicative Interdependency Model} that utilizes Boolean Logic to capture complex interdependencies was recently proposed which overcome the limitations of the existing models. A number of problems were studies based on this model. In this paper we study the \textit{Robustness} problem in Interdependent Power and Communication Network. The robustness is defined with respect to two parameters $K \in I^{+} \cup \{0\}$ and $ρ\in (0,1]$. We utilized the \emph{Implicative Interdependency Model} model to capture the complex interdependency between the two networks. The model classifies the interdependency relations into four cases. Computational complexity of the problem is analyzed for each of these cases. A polynomial time algorithm is designed for the first case that outputs the optimal solution. All the other cases are proved to be NP-complete. An in-approximability bound is provided for the third case. For the general case we formulate an Integer Linear Program to get the optimal solution and a polynomial time heuristic. The applicability of the heuristic is evaluated using power and communication network data of Maricopa County, Arizona. The experimental results showed that the heuristic almost always produced near optimal value of parameter $K$ for $ρ< 0.42$.
Tempas: Temporal Archive Search Based on Tags
Venue: arXiv cs.IR 2017
Year: 2017

Limited search and access patterns over Web archives have been well documented. One of the key reasons is the lack of understanding of the user access patterns over such collections, which in turn is attributed to the lack of effective search interfaces. Current search interfaces for Web archives are (a) either purely navigational or (b) have sub-optimal search experience due to ineffective retrieval models or query modeling. We identify that external longitudinal resources, such as social bookmarking data, are crucial sources to identify important and popular websites in the past. To this extent we present Tempas, a tag-based temporal search engine for Web archives. Websites are posted at specific times of interest on several external platforms, such as bookmarking sites like Delicious. Attached tags not only act as relevant descriptors useful for retrieval, but also encode the time of relevance. With Tempas we tackle the challenge of temporally searching a Web archive by indexing tags and time. We allow temporal selections for search terms, rank documents based on their popularity and also provide meaningful query recommendations by exploiting tag-tag and tag-document co-occurrence statistics in arbitrary time windows. Finally, Tempas operates as a fairly non-invasive indexing framework. By not dealing with contents from the actual Web archive it constitutes an attractive and low-overhead approach for quick access into Web archives.
Anyone Can Become a Troll: Causes of Trolling Behavior in Online Discussions
Venue: arXiv cs.SI 2017
Year: 2017

In online communities, antisocial behavior such as trolling disrupts constructive discussion. While prior work suggests that trolling behavior is confined to a vocal and antisocial minority, we demonstrate that ordinary people can engage in such behavior as well. We propose two primary trigger mechanisms: the individual's mood, and the surrounding context of a discussion (e.g., exposure to prior trolling behavior). Through an experiment simulating an online discussion, we find that both negative mood and seeing troll posts by others significantly increases the probability of a user trolling, and together double this probability. To support and extend these results, we study how these same mechanisms play out in the wild via a data-driven, longitudinal analysis of a large online news discussion community. This analysis reveals temporal mood effects, and explores long range patterns of repeated exposure to trolling. A predictive model of trolling behavior shows that mood and discussion context together can explain trolling behavior better than an individual's history of trolling. These results combine to suggest that ordinary people can, under the right circumstances, behave like trolls.
Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks
Venue: arXiv cs.AI 2017
Year: 2017

Deep neural networks have emerged as a widely used and effective means for tackling complex, real-world problems. However, a major obstacle in applying them to safety-critical systems is the great difficulty in providing formal guarantees about their behavior. We present a novel, scalable, and efficient technique for verifying properties of deep neural networks (or providing counter-examples). The technique is based on the simplex method, extended to handle the non-convex Rectified Linear Unit (ReLU) activation function, which is a crucial ingredient in many modern neural networks. The verification procedure tackles neural networks as a whole, without making any simplifying assumptions. We evaluated our technique on a prototype deep neural network implementation of the next-generation airborne collision avoidance system for unmanned aircraft (ACAS Xu). Results show that our technique can successfully prove properties of networks that are an order of magnitude larger than the largest networks verified using existing methods.
The Dawn of Today's Popular Domains: A Study of the Archived German Web over 18 Years
Venue: arXiv cs.DL 2017
Year: 2017

The Web has been around and maturing for 25 years. The popular websites of today have undergone vast changes during this period, with a few being there almost since the beginning and many new ones becoming popular over the years. This makes it worthwhile to take a look at how these sites have evolved and what they might tell us about the future of the Web. We therefore embarked on a longitudinal study spanning almost the whole period of the Web, based on data collected by the Internet Archive starting in 1996, to retrospectively analyze how the popular Web as of now has evolved over the past 18 years. For our study we focused on the German Web, specifically on the top 100 most popular websites in 17 categories. This paper presents a selection of the most interesting findings in terms of volume, size as well as age of the Web. While related work in the field of Web Dynamics has mainly focused on change rates and analyzed datasets spanning less than a year, we looked at the evolution of websites over 18 years. We found that around 70% of the pages we investigated are younger than a year, with an observed exponential growth in age as well as in size up to now. If this growth rate continues, the number of pages from the popular domains will almost double in the next two years. In addition, we give insights into our data set, provided by the Internet Archive, which hosts the largest and most complete Web archive as of today.
On the Applicability of Delicious for Temporal Search on Web Archives
Venue: arXiv cs.IR 2017
Year: 2017

Web archives are large longitudinal collections that store webpages from the past, which might be missing on the current live Web. Consequently, temporal search over such collections is essential for finding prominent missing webpages and tasks like historical analysis. However, this has been challenging due to the lack of popularity information and proper ground truth to evaluate temporal retrieval models. In this paper we investigate the applicability of external longitudinal resources to identify important and popular websites in the past and analyze the social bookmarking service Delicious for this purpose. The timestamped bookmarks on Delicious provide explicit cues about popular time periods in the past along with relevant descriptors. These are valuable to identify important documents in the past for a given temporal query. Focusing purely on recall, we analyzed more than 12,000 queries and find that using Delicious yields average recall values from 46% up to 100%, when limiting ourselves to the best represented queries in the considered dataset. This constitutes an attractive and low-overhead approach for quick access into Web archives by not dealing with the actual contents.
Mitigation of Phase Noise in Massive MIMO Systems: A Rate-Splitting Approach
Venue: arXiv cs.IT 2017
Year: 2017

This work encompasses Rate-Splitting (RS), providing significant benefits in multi-user settings in the context of huge degrees of freedom promised by massive Multiple-Input Multiple-Output (MIMO). However, the requirement of massive MIMO for cost-efficient implementation makes them more prone to hardware imperfections such as phase noise (PN). As a result, we focus on a realistic broadcast channel with a large number of antennas and hampered by the unavoidable PN. Moreover, we employ the RS transmission strategy, and we show its robustness against PN, since the sum-rate does not saturate at high signal-to-noise ratio (SNR). Although, the analytical results are obtained by means of the deterministic equivalent analysis, they coincide with simulation results even for finite system dimensions.
Insights into Entity Name Evolution on Wikipedia
Venue: arXiv cs.CL 2017
Year: 2017

Working with Web archives raises a number of issues caused by their temporal characteristics. Depending on the age of the content, additional knowledge might be needed to find and understand older texts. Especially facts about entities are subject to change. Most severe in terms of information retrieval are name changes. In order to find entities that have changed their name over time, search engines need to be aware of this evolution. We tackle this problem by analyzing Wikipedia in terms of entity evolutions mentioned in articles regardless the structural elements. We gathered statistics and automatically extracted minimum excerpts covering name changes by incorporating lists dedicated to that subject. In future work, these excerpts are going to be used to discover patterns and detect changes in other sources. In this work we investigate whether or not Wikipedia is a suitable source for extracting the required knowledge.
Towards Better Analysis of Machine Learning Models: A Visual Analytics Perspective
Venue: arXiv cs.LG 2017
Year: 2017

Interactive model analysis, the process of understanding, diagnosing, and refining a machine learning model with the help of interactive visualization, is very important for users to efficiently solve real-world artificial intelligence and data mining problems. Dramatic advances in big data analytics has led to a wide variety of interactive model analysis tasks. In this paper, we present a comprehensive analysis and interpretation of this rapidly developing area. Specifically, we classify the relevant work into three categories: understanding, diagnosis, and refinement. Each category is exemplified by recent influential work. Possible future research opportunities are also explored and discussed.
Simple to Complex Cross-modal Learning to Rank
Venue: arXiv cs.LG 2017
Year: 2017

The heterogeneity-gap between different modalities brings a significant challenge to multimedia information retrieval. Some studies formalize the cross-modal retrieval tasks as a ranking problem and learn a shared multi-modal embedding space to measure the cross-modality similarity. However, previous methods often establish the shared embedding space based on linear mapping functions which might not be sophisticated enough to reveal more complicated inter-modal correspondences. Additionally, current studies assume that the rankings are of equal importance, and thus all rankings are used simultaneously, or a small number of rankings are selected randomly to train the embedding space at each iteration. Such strategies, however, always suffer from outliers as well as reduced generalization capability due to their lack of insightful understanding of procedure of human cognition. In this paper, we involve the self-paced learning theory with diversity into the cross-modal learning to rank and learn an optimal multi-modal embedding space based on non-linear mapping functions. This strategy enhances the model's robustness to outliers and achieves better generalization via training the model gradually from easy rankings by diverse queries to more complex ones. An efficient alternative algorithm is exploited to solve the proposed challenging problem with fast convergence in practice. Extensive experimental results on several benchmark datasets indicate that the proposed method achieves significant improvements over the state-of-the-arts in this literature.
2-subcoloring is NP-complete for planar comparability graphs
Venue: arXiv cs.DM 2017
Year: 2017

A $k$-subcoloring of a graph is a partition of the vertex set into at most $k$ cluster graphs, that is, graphs with no induced $P_3$. 2-subcoloring is known to be NP-complete for comparability graphs and three subclasses of planar graphs, namely triangle-free planar graphs with maximum degree 4, planar perfect graphs with maximum degree 4, and planar graphs with girth 5. We show that 2-subcoloring is also NP-complete for planar comparability graphs with maximum degree 4.
New cardinality estimation algorithms for HyperLogLog sketches
Venue: arXiv cs.DS 2017
Year: 2017

This paper presents new methods to estimate the cardinalities of data sets recorded by HyperLogLog sketches. A theoretically motivated extension to the original estimator is presented that eliminates the bias for small and large cardinalities. Based on the maximum likelihood principle a second unbiased method is derived together with a robust and efficient numerical algorithm to calculate the estimate. The maximum likelihood approach can also be applied to more than a single HyperLogLog sketch. In particular, it is shown that it gives more precise cardinality estimates for union, intersection, or relative complements of two sets that are both represented by HyperLogLog sketches compared to the conventional technique using the inclusion-exclusion principle. All the new methods are demonstrated and verified by extensive simulations.
Bounds and Constructions of Codes with All-Symbol Locality and Availability
Venue: arXiv cs.IT 2017
Year: 2017

We investigate the distance properties of linear locally recoverable codes (LRC codes) with all-symbol locality and availability. New upper and lower bounds on the minimum distance of such codes are derived. The upper bound is based on the shortening method and improves existing shortening bounds. To reduce the gap in between upper and lower bounds we do not restrict the alphabet size and propose explicit constructions of codes with locality and availability via rank-metric codes. The first construction relies on expander graphs and is better in low rate region, the second construction utilizes LRC codes developed by Wang et al. as inner codes and better in high rate region.
An Experimental Study of Deep Convolutional Features For Iris Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Iris is one of the popular biometrics that is widely used for identity authentication. Different features have been used to perform iris recognition in the past. Most of them are based on hand-crafted features designed by biometrics experts. Due to tremendous success of deep learning in computer vision problems, there has been a lot of interest in applying features learned by convolutional neural networks on general image recognition to other tasks such as segmentation, face recognition, and object detection. In this paper, we have investigated the application of deep features extracted from VGG-Net for iris recognition. The proposed scheme has been tested on two well-known iris databases, and has shown promising results with the best accuracy rate of 99.4\%, which outperforms the previous best result.
Undecidability and Finite Automata
Venue: arXiv cs.FL 2017
Year: 2017

Using a novel rewriting problem, we show that several natural decision problems about finite automata are undecidable (i.e., recursively unsolvable). In contrast, we also prove three related problems are decidable. We apply one result to prove the undecidability of a related problem about k-automatic sets of rational numbers.
Enhancing Elasticity of SaaS Applications using Queuing Theory
Venue: arXiv cs.DC 2017
Year: 2017

Elasticity is one of key features of cloud computing. Elasticity allows Software as a Service (SaaS) applications' provider to reduce cost of running applications. In large SaaS applications that are developed using service-oriented architecture model, each service is deployed in a separated virtual machine and may use one or more services to complete its task. Although, scaling service independently from its required services propagates scaling problem to other services, most of current elasticity approaches do not consider functional dependencies between services, which increases the probability of violating service level agreement. In this paper, architecture of SaaS application is modeled as multi-class M/M/m processor sharing queuing model with deadline to take into account functional dependencies between services during estimating required scaling resources. Experimental results show effectiveness of the proposed model in estimating required resources during scaling virtual resources.
Printed Arabic Text Recognition using Linear and Nonlinear Regression
Venue: arXiv cs.CV 2017
Year: 2017

Arabic language is one of the most popular languages in the world. Hundreds of millions of people in many countries around the world speak Arabic as their native speaking. However, due to complexity of Arabic language, recognition of printed and handwritten Arabic text remained untouched for a very long time compared with English and Chinese. Although, in the last few years, significant number of researches has been done in recognizing printed and handwritten Arabic text, it stills an open research field due to cursive nature of Arabic script. This paper proposes automatic printed Arabic text recognition technique based on linear and ellipse regression techniques. After collecting all possible forms of each character, unique code is generated to represent each character form. Each code contains a sequence of lines and ellipses. To recognize fonts, a unique list of codes is identified to be used as a fingerprint of font. The proposed technique has been evaluated using over 14000 different Arabic words with different fonts and experimental results show that average recognition rate of the proposed technique is 86%.
Survey of modern Fault Diagnosis methods in networks
Venue: arXiv cs.AI 2017
Year: 2017

With the advent of modern computer networks, fault diagnosis has been a focus of research activity. This paper reviews the history of fault diagnosis in networks and discusses the main methods in information gathering section, information analyzing section and diagnosing and revolving section of fault diagnosis in networks. Emphasis will be placed upon knowledge-based methods with discussing the advantages and shortcomings of the different methods. The survey is concluded with a description of some open problems.
Real-Time Influence Maximization on Dynamic Social Streams
Venue: arXiv cs.SI 2017
Year: 2017

Influence maximization (IM), which selects a set of $k$ users (called seeds) to maximize the influence spread over a social network, is a fundamental problem in a wide range of applications such as viral marketing and network monitoring. Existing IM solutions fail to consider the highly dynamic nature of social influence, which results in either poor seed qualities or long processing time when the network evolves. To address this problem, we define a novel IM query named Stream Influence Maximization (SIM) on social streams. Technically, SIM adopts the sliding window model and maintains a set of $k$ seeds with the largest influence value over the most recent social actions. Next, we propose the Influential Checkpoints (IC) framework to facilitate continuous SIM query processing. The IC framework creates a checkpoint for each window slide and ensures an $\varepsilon$-approximate solution. To improve its efficiency, we further devise a Sparse Influential Checkpoints (SIC) framework which selectively keeps $O(\frac{\log{N}}β)$ checkpoints for a sliding window of size $N$ and maintains an $\frac{\varepsilon(1-β)}{2}$-approximate solution. Experimental results on both real-world and synthetic datasets confirm the effectiveness and efficiency of our proposed frameworks against the state-of-the-art IM approaches.
Position and Orientation Estimation through Millimeter Wave MIMO in 5G Systems
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter wave signals and large antenna arrays are considered enabling technologies for future 5G networks. While their benefits for achieving high-data rate communications are well-known, their potential advantages for accurate positioning are largely undiscovered. We derive the Cramér-Rao bound (CRB) on position and rotation angle estimation uncertainty from millimeter wave signals from a single transmitter, in the presence of scatterers. We also present a novel two-stage algorithm for position and rotation angle estimation that attains the CRB for average to high signal-to-noise ratio. The algorithm is based on multiple measurement vectors matching pursuit for coarse estimation, followed by a refinement stage based on the space-alternating generalized expectation maximization algorithm. We find that accurate position and rotation angle estimation is possible using signals from a single transmitter, in either line-of- sight, non-line-of-sight, or obstructed-line-of-sight conditions.