OpenRaiser/Intern-Atlas huggingface dataset:
The Scale-free Network of Passwords : Visualization and Estimation of Empirical Passwords
Venue: arXiv cs.CR 2015
Year: 2015

In this paper, we present a novel vision of large scale of empirical password sets available and improve the understanding of passwords by revealing their interconnections and considering the security on a level of the whole password set instead of one single password level. Through the visualization of Yahoo, Phpbb, 12306, etc. we, for the first time, show what the spatial structure of empirical password sets are like and take the community and clustering patterns of the passwords into account to shed lights on the definition of popularity of a password based on their frequency and degree separately. Furthermore, we propose a model of statistical guessing attack from the perspective of the data's topological space, which provide an explanation of the "cracking curve". We also give a lower bound of the minimum size of the dictionary needed to compromise arbitrary ratio of any given password set by proving that it is equivalent to the minimum dominating set problem, which is a NP-complete problem. Hence the minimal dictionary problem is also NP-complete.
A global Constraint for mining Sequential Patterns with GAP constraint
Venue: arXiv cs.AI 2015
Year: 2015

Sequential pattern mining (SPM) under gap constraint is a challenging task. Many efficient specialized methods have been developed but they are all suffering from a lack of genericity. The Constraint Programming (CP) approaches are not so effective because of the size of their encodings. In[7], we have proposed the global constraint Prefix-Projection for SPM which remedies to this drawback. However, this global constraint cannot be directly extended to support gap constraint. In this paper, we propose the global constraint GAP-SEQ enabling to handle SPM with or without gap constraint. GAP-SEQ relies on the principle of right pattern extensions. Experiments show that our approach clearly outperforms both CP approaches and the state-of-the-art cSpade method on large datasets.
Low-Complexity SINR Feasibility Checking and Joint Power and Admission Control in Prioritized Multi-tier Cellular Networks
Venue: arXiv cs.NI 2015
Year: 2015

Next generation cellular networks will consist of multiple tiers of cells and users associated with different network tiers may have different priorities (e.g., macrocell-picocell-femtocell networks with macro tier prioritized over pico tier, which is again prioritized over femto tier). Designing efficient joint power and admission control (JPAC) algorithms for such networks under a co-channel deployment (i.e., underlay) scenario is of significant importance. Feasibility checking of a given target signal-to-noise-plus-interference ratio (SINR) vector is generally the most significant contributor to the complexity of JPAC algorithms in single/multi-tier underlay cellular networks. This is generally accomplished through iterative strategies whose complexity is either unpredictable or of O(M^3), when the well-known relationship between the SINR vector and the power vector is used, where $M$ is the number of users/links. In this paper, we derive a novel relationship between a given SINR vector and its corresponding uplink/downlink power vector based on which the feasibility checking can be performed with a complexity of O(B^3+M B), where B is the number of base stations. This is significantly less compared to O(M^3) in many cellular wireless networks since the number of base stations is generally much lower than the number of users/links in such networks. The developed novel relationship between the SINR and power vector not only substantially reduces the complexity of designing JPAC algorithms, but also provides insights into developing efficient but low-complexity power update strategies for prioritized multi-tier cellular networks. We propose two such algorithms and through simulations, we show that our proposed algorithms outperform the existing ones in prioritized cellular networks.
Distributed Machine Learning via Sufficient Factor Broadcasting
Venue: arXiv cs.LG 2015
Year: 2015

Matrix-parametrized models, including multiclass logistic regression and sparse coding, are used in machine learning (ML) applications ranging from computer vision to computational biology. When these models are applied to large-scale ML problems starting at millions of samples and tens of thousands of classes, their parameter matrix can grow at an unexpected rate, resulting in high parameter synchronization costs that greatly slow down distributed learning. To address this issue, we propose a Sufficient Factor Broadcasting (SFB) computation model for efficient distributed learning of a large family of matrix-parameterized models, which share the following property: the parameter update computed on each data sample is a rank-1 matrix, i.e., the outer product of two "sufficient factors" (SFs). By broadcasting the SFs among worker machines and reconstructing the update matrices locally at each worker, SFB improves communication efficiency --- communication costs are linear in the parameter matrix's dimensions, rather than quadratic --- without affecting computational correctness. We present a theoretical convergence analysis of SFB, and empirically corroborate its efficiency on four different matrix-parametrized ML models.
A Stochastic Process Model of Classical Search
Venue: arXiv cs.AI 2015
Year: 2015

Among classical search algorithms with the same heuristic information, with sufficient memory A* is essentially as fast as possible in finding a proven optimal solution. However, in many situations optimal solutions are simply infeasible, and thus search algorithms that trade solution quality for speed are desirable. In this paper, we formalize the process of classical search as a metalevel decision problem, the Abstract Search MDP. For any given optimization criterion, this establishes a well-defined notion of the best possible behaviour for a search algorithm and offers a theoretical approach to the design of algorithms for that criterion. We proceed to approximately solve a version of the Abstract Search MDP for anytime algorithms and thus derive a novel search algorithm, Search by Maximizing the Incremental Rate of Improvement (SMIRI). SMIRI is shown to outperform current state-of-the-art anytime search algorithms on a parametrized stochastic tree model for most of the tested parameter values.
Fly-automata for checking MSO 2 graph properties
Venue: arXiv cs.LO 2015
Year: 2015

A more descriptive but too long title would be : Constructing fly-automata to check properties of graphs of bounded tree-width expressed by monadic second-order formulas written with edge quantifications. Such properties are called MSO2 in short. Fly-automata (FA) run bottom-up on terms denoting graphs and compute "on the fly" the necessary states and transitions instead of looking into huge, actually unimplementable tables. In previous works, we have constructed FA that process terms denoting graphs of bounded clique-width, in order to check their monadic second-order (MSO) properties (expressed by formulas without edge quan-tifications). Here, we adapt these FA to incidence graphs, so that they can check MSO2 properties of graphs of bounded tree-width. This is possible because: (1) an MSO2 property of a graph is nothing but an MSO property of its incidence graph and (2) the clique-width of the incidence graph of a graph is linearly bounded in terms of its tree-width. Our constructions are actually implementable and usable. We detail concrete constructions of automata in this perspective.
Category Enhanced Word Embedding
Venue: arXiv cs.CL 2015
Year: 2015

Distributed word representations have been demonstrated to be effective in capturing semantic and syntactic regularities. Unsupervised representation learning from large unlabeled corpora can learn similar representations for those words that present similar co-occurrence statistics. Besides local occurrence statistics, global topical information is also important knowledge that may help discriminate a word from another. In this paper, we incorporate category information of documents in the learning of word representations and to learn the proposed models in a document-wise manner. Our models outperform several state-of-the-art models in word analogy and word similarity tasks. Moreover, we evaluate the learned word vectors on sentiment analysis and text classification tasks, which shows the superiority of our learned word vectors. We also learn high-quality category embeddings that reflect topical meanings.
Provenance Circuits for Trees and Treelike Instances (Extended Version)
Venue: arXiv cs.DB 2015
Year: 2015

Query evaluation in monadic second-order logic (MSO) is tractable on trees and treelike instances, even though it is hard for arbitrary instances. This tractability result has been extended to several tasks related to query evaluation, such as counting query results [3] or performing query evaluation on probabilistic trees [10]. These are two examples of the more general problem of computing augmented query output, that is referred to as provenance. This article presents a provenance framework for trees and treelike instances, by describing a linear-time construction of a circuit provenance representation for MSO queries. We show how this provenance can be connected to the usual definitions of semiring provenance on relational instances [20], even though we compute it in an unusual way, using tree automata; we do so via intrinsic definitions of provenance for general semirings, independent of the operational details of query evaluation. We show applications of this provenance to capture existing counting and probabilistic results on trees and treelike instances, and give novel consequences for probability evaluation.
FixRoute: A Unified Logic and Numerical Tool for Provably Safe Internet Traffic Engineering
Venue: arXiv cs.NI 2015
Year: 2015

The performance of networks that use the Internet Protocol is sensitive to precise configuration of many low-level parameters on each network device. These settings govern the action of dynamic routing protocols, which direct the flow of traffic; in order to ensure that these dynamic protocols all converge to produce some 'optimal' flow, each parameter must be set correctly. Multiple conflicting optimization objectives, nondeterminism, and the need to reason about different failure scenarios make the task particularly complicated. We present a fast and flexible approach for the analysis of a number of such management tasks presented in the context of BGP routing. The idea is to combine {\em logical} satisfiability criteria with traditional {\em numerical} optimization, to reach a desired traffic flow outcome subject to given constraints on the routing process. The method can then be used to probe parameter sensitivity, trade-offs in the selection of optimization goals, resilience to failure, and so forth. The theory is underpinned by a rigorous abstraction of the convergence of distributed asynchronous message-passing protocols, and is therefore generalizable to other scenarios. Our resulting hybrid engine is faster than either purely logical or purely numeric alternatives, making it potentially feasible for interactive production use.
Cloud-based DDoS Attacks and Defenses
Venue: arXiv cs.CR 2015
Year: 2015

Safety and reliability are important in the cloud computing environment. This is especially true today as distributed denial-of-service (DDoS) attacks constitute one of the largest threats faced by Internet users and cloud computing services. DDoS attacks target the resources of these services, lowering their ability to provide optimum usage of the network infrastructure. Due to the nature of cloud computing, the methodologies for preventing or stopping DDoS attacks are quite different compared to those used in traditional networks. In this paper, we investigate the effect of DDoS attacks on cloud resources and recommend practical defense mechanisms against different types of DDoS attacks in the cloud environment.
Applying CMM Towards an m-Learning Context
Venue: arXiv cs.CY 2015
Year: 2015

In the era of m-Learning, it is found that educational institutions have onus of incorporating the latest technological innovations that can be accepted and understood widely. While investigating the important theme of fast-paced development of emerging technologies in mobile communications, it is important to recognize the extent influence of these innovations using which society can communicate, learn, access information, and, additionally, interact. In addition, the usage of mobile technology in higher education needs not only the pervasive nature of the technology but also its disruptive nature that offers several challenges while incorporation in the area of teaching and learning. Therefore, recently, higher education institutions are looking at various ways of implementing m-Learning strategies, in order to offer solutions, which, in turn, can standardize the process of education and, additionally, replace those traditional didactic courses, focusing on m-Learning endless benefits. Some of the benefits are: the process of learning itself could be self-paced, whereas information could be easier accessed, adding to independent, discovery-oriented learning that becomes more engaging. Applying CMM successfully to design effective incorporation strategies of m-Learning, this research targets formulation of such a maturity model by which the process of m-Learning can be more effective and efficient.
Steganography: A Secure way for Transmission in Wireless Sensor Networks
Venue: arXiv cs.MM 2015
Year: 2015

Addressing the security concerns in wireless sensor networks (WSN) is a challenging task, which has attracted the attention of many researchers from the last few decades. Researchers have presented various schemes in WSN, addressing the problems of processing, bandwidth, load balancing, and efficient routing. However, little work has been done on security aspects of WSN. In a typical WSN network, the tiny nodes installed on different locations sense the surrounding environment, send the collected data to their neighbors, which in turn is forwarded to a sink node. The sink node aggregate the data received from different sensors and send it to the base station for further processing and necessary actions. In highly critical sensor networks such as military and law enforcement agencies networks, the transmission of such aggregated data via the public network Internet is very sensitive and vulnerable to various attacks and risks. Therefore, this paper provides a solution for addressing these security issues based on steganography, where the aggregated data can be embedded as a secret message inside an innocent-looking cover image. The stego image containing the embedded data can be then sent to fusion center using Internet. At the fusion center, the hidden data is extracted from the image, the required processing is performed and decision is taken accordingly. Experimentally, the proposed method is evaluated by objective analysis using peak signal-to-noise ratio (PSNR), mean square error (MSE), normalized cross correlation (NCC), and structural similarity index metric (SSIM), providing promising results in terms of security and image quality, thus validating its superiority.
Entity Suggestion by Example using a Conceptual Taxonomy
Venue: arXiv cs.IR 2015
Year: 2015

Entity suggestion by example (ESbE) refers to a type of entity acquisition query in which a user provides a set of example entities as the query and obtains in return some entities that best complete the concept underlying the given query. Such entity acquisition queries can be useful in many applications such as related-entity recommendation and query expansion. A number of ESbE query processing solutions exist in the literature. However, they mostly build only on the idea of entity co-occurrences either in text or web lists, without taking advantage of the existence of many web-scale conceptual taxonomies that consist of hierarchical isA relationships between entity-concept pairs. This paper provides a query processing method based on the relevance models between entity sets and concepts. These relevance models can be used to obtain the fine-grained concepts implied by the query entity set, and the entities that belong to a given concept, thereby providing the entity suggestions. Extensive evaluations with real data sets show that the accuracy of the queries processed with this new method is significantly higher than that of existing solutions.
Partial-Diffusion Least Mean-Square Estimation Over Networks Under Noisy Information Exchange
Venue: arXiv cs.SY 2015
Year: 2015

Partial diffusion scheme is an effective method for reducing computational load and power consumption in adaptive network implementation. The Information is exchanged among the nodes, usually over noisy links. In this paper, we consider a general version of partial-diffusion least-mean-square (PDLMS) algorithm in the presence of various sources of imperfect information exchanges. Like the established PDLMS, we consider two different schemes to select the entries, sequential and stochastic, for transmission at each iteration. Our objective is to analyze the aggregate effect of these perturbations on general PDLMS strategies. Simulation results demonstrate that considering noisy link assumption adds a new complexity to the related optimization problem and the trade-off between communication cost and estimation performance in comparison to ideal case becomes unbalanced.
Recognizing Temporal Linguistic Expression Pattern of Individual with Suicide Risk on Social Media
Venue: arXiv cs.SI 2015
Year: 2015

Suicide is a global public health problem. Early detection of individual suicide risk plays a key role in suicide prevention. In this paper, we propose to look into individual suicide risk through time series analysis of personal linguistic expression on social media (Weibo). We examined temporal patterns of the linguistic expression of individuals on Chinese social media (Weibo). Then, we used such temporal patterns as predictor variables to build classification models for estimating levels of individual suicide risk. Characteristics of time sequence curves to linguistic features including parentheses, auxiliary verbs, personal pronouns and body words are reported to affect performance of suicide most, and the predicting model has a accuracy higher than 0.60, shown by the results. This paper confirms the efficiency of the social media data in detecting individual suicide risk. Results of this study may be insightful for improving the performance of suicide prevention programs.
Algorithms as Mechanisms: The Price of Anarchy of Relax-and-Round
Venue: arXiv cs.GT 2015
Year: 2015

Many algorithms that are originally designed without explicitly considering incentive properties are later combined with simple pricing rules and used as mechanisms. The resulting mechanisms are often natural and simple to understand. But how good are these algorithms as mechanisms? Truthful reporting of valuations is typically not a dominant strategy (certainly not with a pay-your-bid, first-price rule, but it is likely not a good strategy even with a critical value, or second-price style rule either). Our goal is to show that a wide class of approximation algorithms yields this way mechanisms with low Price of Anarchy. The seminal result of Lucier and Borodin [SODA 2010] shows that combining a greedy algorithm that is an $α$-approximation algorithm with a pay-your-bid payment rule yields a mechanism whose Price of Anarchy is $O(α)$. In this paper we significantly extend the class of algorithms for which such a result is available by showing that this close connection between approximation ratio on the one hand and Price of Anarchy on the other also holds for the design principle of relaxation and rounding provided that the relaxation is smooth and the rounding is oblivious. We demonstrate the far-reaching consequences of our result by showing its implications for sparse packing integer programs, such as multi-unit auctions and generalized matching, for the maximum traveling salesman problem, for combinatorial auctions, and for single source unsplittable flow problems. In all these problems our approach leads to novel simple, near-optimal mechanisms whose Price of Anarchy either matches or beats the performance guarantees of known mechanisms.
A Type Theory for Probabilistic and Bayesian Reasoning
Venue: arXiv cs.LO 2015
Year: 2015

This paper introduces a novel type theory and logic for probabilistic reasoning. Its logic is quantitative, with fuzzy predicates. It includes normalisation and conditioning of states. This conditioning uses a key aspect that distinguishes our probabilistic type theory from quantum type theory, namely the bijective correspondence between predicates and side-effect free actions (called instrument, or assert, maps). The paper shows how suitable computation rules can be derived from this predicate-action correspondence, and uses these rules for calculating conditional probabilities in two well-known examples of Bayesian reasoning in (graphical) models. Our type theory may thus form the basis for a mechanisation of Bayesian inference.
Hardware-In-the-Loop Measurements of the Multi-Carrier Compressed Sensing Multi-User Detection (MCSM) System
Venue: arXiv cs.IT 2015
Year: 2015

MCSM is a recently proposed novel system concept to solve the massive access problem envisioned in future communication systems like 5G and industry 4.0 systems. This work focuses on the practical verification of the theoretical gains that MCSM provides using a Hardware-In-the-Loop (HIL) measurement setup. We present results in two different scenarios: (i) a LoS lab setup and (ii) a non-LoS machine hall. In both scenarios MCSM shows promising performance in terms of the number of supported users and the achieved reliability.
"Piaf" vs "Adele": classifying encyclopedic queries using automatically labeled training data
Venue: arXiv cs.IR 2015
Year: 2015

Encyclopedic queries express the intent of obtaining information typically available in encyclopedias, such as biographical, geographical or historical facts. In this paper, we train a classifier for detecting the encyclopedic intent of web queries. For training such a classifier, we automatically label training data from raw query logs. We use click-through data to select positive examples of encyclopedic queries as those queries that mostly lead to Wikipedia articles. We investigated a large set of features that can be generated to describe the input query. These features include both term-specific patterns as well as query projections on knowledge bases items (e.g. Freebase). Results show that using these feature sets it is possible to achieve an F1 score above 87%, competing with a Google-based baseline, which uses a much wider set of signals to boost the ranking of Wikipedia for potential encyclopedic queries. The results also show that both query projections on Wikipedia article titles and Freebase entity match represent the most relevant groups of features. When the training set contains frequent positive examples (i.e rare queries are excluded) results tend to improve.