OpenRaiser/Intern-Atlas huggingface dataset:
An Empirical Study of How Users Adopt Famous Entities
Venue: arXiv cs.SI 2012
Year: 2012

Users of social networking services construct their personal social networks by creating asymmetric and symmetric social links. Users usually follow friends and selected famous entities that include celebrities and news agencies. In this paper, we investigate how users follow famous entities. We statically and dynamically analyze data within a huge social networking service with a manually classified set of famous entities. The results show that the in-degree of famous entities does not fit to power-law distribution. Conversely, the maximum number of famous followees in one category for each user shows power-law property. To our best knowledge, there is no research work on this topic with human-chosen famous entity dataset in real life. These findings might be helpful in microblogging marketing and user classification.
Communicating Processes with Data for Supervisory Coordination
Venue: arXiv cs.SY 2012
Year: 2012

We employ supervisory controllers to safely coordinate high-level discrete(-event) behavior of distributed components of complex systems. Supervisory controllers observe discrete-event system behavior, make a decision on allowed activities, and communicate the control signals to the involved parties. Models of the supervisory controllers can be automatically synthesized based on formal models of the system components and a formalization of the safe coordination (control) requirements. Based on the obtained models, code generation can be used to implement the supervisory controllers in software, on a PLC, or an embedded (micro)processor. In this article, we develop a process theory with data that supports a model-based systems engineering framework for supervisory coordination. We employ communication to distinguish between the different flows of information, i.e., observation and supervision, whereas we employ data to specify the coordination requirements more compactly, and to increase the expressivity of the framework. To illustrate the framework, we remodel an industrial case study involving coordination of maintenance procedures of a printing process of a high-tech Oce printer.
The Meaning of Requirements and Adaptation
Venue: arXiv cs.SE 2012
Year: 2012

The traditional understanding of stakeholders requirements is that they express desirable relationships among phenomena in the relevant environment. Historically, software engineering research has tended to focus more on the problems of modeling requirements and deriving specifications given requirements, and much less on the meaning of a requirement itself. I introduce new concepts that elucidate the meaning of requirements, namely, the designated set and the falsifiability of requirements. By relying on these concepts, I (i) show that the adaptive requirements approaches, which constitute a lively and growing field in RE, are fundamentally flawed, (ii) give a sufficient characterization of vague requirements, and (iii) make the connection between requirements modeling and the Zave and Jackson sense of engineering. I support my claims with examples and an extensive discussion of the related literature. Finally, I show how adaptation can be framed in terms of Zave and Jackson's ontology.
A Comparative Study between Moravec and Harris Corner Detection of Noisy Images Using Adaptive Wavelet Thresholding Technique
Venue: arXiv cs.CV 2012
Year: 2012

In this paper a comparative study between Moravec and Harris Corner Detection has been done for obtaining features required to track and recognize objects within a noisy image. Corner detection of noisy images is a challenging task in image processing. Natural images often get corrupted by noise during acquisition and transmission. As Corner detection of these noisy images does not provide desired results, hence de-noising is required. Adaptive wavelet thresholding approach is applied for the same.
Secure and Privacy-Preserving Authentication Protocols for Wireless Mesh Networks
Venue: arXiv cs.CR 2012
Year: 2012

Wireless mesh networks (WMNs) have emerged as a promising concept to meet the challenges in next-generation wireless networks such as providing flexible, adaptive, and reconfigurable architecture while offering cost-effective solutions to service providers. As WMNs become an increasingly popular replacement technology for last-mile connectivity to the home networking, community and neighborhood networking, it is imperative to design efficient and secure communication protocols for these networks. However, several vulnerabilities exist in currently existing protocols for WMNs. These security loopholes can be exploited by potential attackers to launch attack on WMNs. The absence of a central point of administration makes securing WMNs even more challenging. The broadcast nature of transmission and the dependency on the intermediate nodes for multi-hop communications lead to several security vulnerabilities in WMNs. The attacks can be external as well as internal in nature. External attacks are launched by intruders who are not authorized users of the network. For example, an intruding node may eavesdrop on the packets and replay those packets at a later point of time to gain access to the network resources. On the other hand, the internal attacks are launched by the nodes that are part of the WMN. On example of such attack is an intermediate node dropping packets which it was supposed to forward. This chapter presents a comprehensive discussion on the current authentication and privacy protection schemes for WMN. In addition, it proposes a novel security protocol for node authentication and message confidentiality and an anonymization scheme for privacy protection of users in WMNs.
Progressive Differences Convolutional Low-Density Parity-Check Codes
Venue: arXiv cs.IT 2012
Year: 2012

We present a new family of low-density parity-check (LDPC) convolutional codes that can be designed using ordered sets of progressive differences. We study their properties and define a subset of codes in this class that have some desirable features, such as fixed minimum distance and Tanner graphs without short cycles. The design approach we propose ensures that these properties are guaranteed independently of the code rate. This makes these codes of interest in many practical applications, particularly when high rate codes are needed for saving bandwidth. We provide some examples of coded transmission schemes exploiting this new class of codes.
A Framework for Concurrent Imperative Programming
Venue: arXiv cs.PL 2012
Year: 2012

The proposed framework provides a general model of concurrent imperative programming. Programs are modeled as formal languages and concurrency as an interleaving (or shuffle) operator. This yields a simple and elegant algebra of programs. The framework supports the views program logic by Dinsdale-Young and others, which generalizes various type systems and separation logic approaches to program correctness. It also validates familiar operational calculi in small-step and big-step flavours. The consistency of the program logic with respect to the operational rules is established directly and does not use induction on derivations. In fact the whole framework uses only straightforward mathematics. Parametric in states, views and basic commands, it can be instantiated to a variety of concrete languages and settings.
A Generalization of the Convex Kakeya Problem
Venue: arXiv cs.CG 2012
Year: 2012

Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be seen as a generalization of Kakeya's problem of finding a convex region of smallest area such that a needle can be rotated through 360 degrees within this region. We show that there is always an optimal region that is a triangle, and we give an optimal Θ(n log n)-time algorithm to compute such a triangle for a given set of n segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then placing the segments with their midpoint at the origin and taking their convex hull results in an optimal solution. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of every rotated copy of G.
Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication
Venue: arXiv cs.DS 2012
Year: 2012

Graph expansion analysis of computational DAGs is useful for obtaining communication cost lower bounds where previous methods, such as geometric embedding, are not applicable. This has recently been demonstrated for Strassen's and Strassen-like fast square matrix multiplication algorithms. Here we extend the expansion analysis approach to fast algorithms for rectangular matrix multiplication, obtaining a new class of communication cost lower bounds. These apply, for example to the algorithms of Bini et al. (1979) and the algorithms of Hopcroft and Kerr (1971). Some of our bounds are proved to be optimal.
Contracts for Interacting Two-Party Systems
Venue: arXiv cs.LO 2012
Year: 2012

This article deals with the interrelation of deontic operators in contracts -- an aspect often neglected when considering only one of the involved parties. On top of an automata-based semantics we formalise the onuses that obligations, permissions and prohibitions on one party impose on the other. Such formalisation allows for a clean notion of contract strictness and a derived notion of contract conflict that is enriched with issues arising from party interdependence.
A History of BlockingQueues
Venue: arXiv cs.LO 2012
Year: 2012

This paper describes a way to formally specify the behaviour of concurrent data structures. When specifying concurrent data structures, the main challenge is to make specifications stable, i.e., to ensure that they cannot be invalidated by other threads. To this end, we propose to use history-based specifications: instead of describing method behaviour in terms of the object's state, we specify it in terms of the object's state history. A history is defined as a list of state updates, which at all points can be related to the actual object's state. We illustrate the approach on the BlockingQueue hierarchy from the java.util.concurrent library. We show how the behaviour of the interface BlockingQueue is specified, leaving a few decisions open to descendant classes. The classes implementing the interface correctly inherit the specifications. As a specification language, we use a combination of JML and permission-based separation logic, including abstract predicates. This results in an abstract, modular and natural way to specify the behaviour of concurrent queues. The specifications can be used to derive high-level properties about queues, for example to show that the order of elements is preserved. Moreover, the approach can be easily adapted to other concurrent data structures.
PCA-Based Relevance Feedback in Document Image Retrieval
Venue: arXiv cs.IR 2012
Year: 2012

Research has been devoted in the past few years to relevance feedback as an effective solution to improve performance of information retrieval systems. Relevance feedback refers to an interactive process that helps to improve the retrieval performance. In this paper we propose the use of relevance feedback to improve document image retrieval System (DIRS) performance. This paper compares a variety of strategies for positive and negative feedback. In addition, feature subspace is extracted and updated during the feedback process using a Principal Component Analysis (PCA) technique and based on user's feedback. That is, in addition to reducing the dimensionality of feature spaces, a proper subspace for each type of features is obtained in the feedback process to further improve the retrieval accuracy. Experiments show that using relevance Feedback in DIR achieves better performance than common DIR.
Quasi-polynomial Hitting-set for Set-depth-Delta Formulas
Venue: arXiv cs.CC 2012
Year: 2012

We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition (X_1,...,X_d) of the variable indices [n] that the top product layer respects, i.e. C(x) = \sum_{i=1}^k \prod_{j=1}^{d} f_{i,j}(x_{X_j}), where f_{i,j} is a sparse polynomial in F[x_{X_j}]. Extending this definition to any depth - we call a depth-Delta formula C (consisting of alternating layers of Sigma and Pi gates, with a Sigma-gate on top) a set-depth-Delta formula if every Pi-layer in C respects a (unknown) partition on the variables; if Delta is even then the product gates of the bottom-most Pi-layer are allowed to compute arbitrary monomials. In this work, we give a hitting-set generator for set-depth-Delta formulas (over any field) with running time polynomial in exp(({Delta}^2 log s)^{Delta - 1}), where s is the size bound on the input set-depth-Delta formula. In other words, we give a quasi-polynomial time blackbox polynomial identity test for such constant-depth formulas. Previously, the very special case of Delta=3 (also known as set-multilinear depth-3 circuits) had no known sub-exponential time hitting-set generator. This was declared as an open problem by Shpilka & Yehudayoff (FnT-TCS 2010); the model being first studied by Nisan & Wigderson (FOCS 1995). Our work settles this question, not only for depth-3 but, up to depth epsilon.log s / loglog s, for a fixed constant epsilon < 1. The technique is to investigate depth-Delta formulas via depth-(Delta-1) formulas over a Hadamard algebra, after applying a `shift' on the variables. We propose a new algebraic conjecture about the low-support rank-concentration in the latter formulas, and manage to prove it in the case of set-depth-Delta formulas.
Acquisition probability of multi-user UWB systems in the presence of a novel synchronization approach
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, to synchronize Ultra Wideband (UWB) systems in ad-hoc multi-user environments, we propose a new timing acquisition approach for achieving a good performance despite the difficulties to get there. Synchronization constraints are caused by the ultra-short emitted waveforms nature of UWB signals. Used in [1, 2] for single-user environments, our timing acquisition approach is based on two successive stages or floors. Extended for multi-user environments, the used algorithm is a combination between coarse synchronization based on timing with dirty templates (TDT) acquisition scheme and a new fine synchronization scheme developed in [3-6] which conduct to an improved estimate of timing offset. In this work, we develop and test this method in both data-aided (DA) and non-data-aided (NDA) modes. Simulation results and comparisons are also given to confirm performance improvement of our approach (in terms of mean square error and acquisition probability) compared to the original TDT algorithm in multi-user environments, especially in the NDA mode.
Maximum Weight Independent Sets in Odd-Hole-Free Graphs Without Dart or Without Bull
Venue: arXiv cs.DM 2012
Year: 2012

The Maximum Weight Independent Set (MWIS) Problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most important problems on graphs, it is well known to be NP-complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying clique separator decomposition as well as modular decomposition, we obtain polynomial time solutions of MWIS for odd-hole- and dart-free graphs as well as for odd-hole- and bull-free graphs (dart and bull have five vertices, say $a,b,c,d,e$, and dart has edges $ab,ac,ad,bd,cd,de$, while bull has edges $ab,bc,cd,be,ce$). If the graphs are hole-free instead of odd-hole-free then stronger structural results and better time bounds are obtained.
Joint Detection/Decoding Algorithms for Nonbinary LDPC Codes over ISI Channels
Venue: arXiv cs.IT 2012
Year: 2012

This paper is concerned with the application of nonbinary low-density parity-check (NB-LDPC) codes to binary input inter-symbol interference (ISI) channels. Two low-complexity joint detection/decoding algorithms are proposed. One is referred to as max-log-MAP/X-EMS algorithm, which is implemented by exchanging soft messages between the max-log-MAP detector and the extended min-sum (EMS) decoder. The max-log-MAP/X-EMS algorithm is applicable to general NB-LDPC codes. The other one, referred to as Viterbi/GMLGD algorithm, is designed in particular for majority-logic decodable NB-LDPC codes. The Viterbi/GMLGD algorithm works in an iterative manner by exchanging hard-decisions between the Viterbi detector and the generalized majority-logic decoder(GMLGD). As a by-product, a variant of the original EMS algorithm is proposed, which is referred to as μ-EMS algorithm. In the μ-EMS algorithm, the messages are truncated according to an adaptive threshold, resulting in a more efficient algorithm. Simulations results show that the max-log-MAP/X-EMS algorithm performs as well as the traditional iterative detection/decoding algorithm based on the BCJR algorithm and the QSPA, but with lower complexity. The complexity can be further reduced for majority-logic decodable NB-LDPC codes by executing the Viterbi/GMLGD algorithm with a performance degradation within one dB. Simulation results also confirm that the μ-EMS algorithm requires lower computational loads than the EMS algorithm with a fixed threshold. These algorithms provide good candidates for trade-offs between performance and complexity.
Training a Feed-forward Neural Network with Artificial Bee Colony Based Backpropagation Method
Venue: arXiv cs.NE 2012
Year: 2012

Back-propagation algorithm is one of the most widely used and popular techniques to optimize the feed forward neural network training. Nature inspired meta-heuristic algorithms also provide derivative-free solution to optimize complex problem. Artificial bee colony algorithm is a nature inspired meta-heuristic algorithm, mimicking the foraging or food source searching behaviour of bees in a bee colony and this algorithm is implemented in several applications for an improved optimized outcome. The proposed method in this paper includes an improved artificial bee colony algorithm based back-propagation neural network training method for fast and improved convergence rate of the hybrid neural network learning method. The result is analysed with the genetic algorithm based back-propagation method, and it is another hybridized procedure of its kind. Analysis is performed over standard data sets, reflecting the light of efficiency of proposed method in terms of convergence speed and rate.
Hybrid Message-Embedded Cipher Using Logistic Map
Venue: arXiv cs.CR 2012
Year: 2012

The proposed hybrid message embedded scheme consists of hill cipher combined with message embedded chaotic scheme. Message-embedded scheme using non-linear feedback shift register as non-linear function and 1-D logistic map as chaotic map is modified, analyzed and tested for avalanche property and strength against known plaintext attack and brute-force attack. Parameter of logistic map acts as a secret key. As we know that the minimum key space to resist brute-force attack is 2100, and it is observed from analysis that key space of the discussed method is lesser than 2100. But the identifiability test concludes that the scheme consists of identifiable keys which are sufficient condition to resist brute-force attack for chaotic ciphers. A complete file can be encrypted and decrypted successfully by the method that assures security against brute force attack. It is also concluded that the scheme has an average key sensitivity.
A threshold secure data sharing scheme for federated clouds
Venue: arXiv cs.DC 2012
Year: 2012

Cloud computing allows users to view computing in a new direction, as it uses the existing technologies to provide better IT services at low-cost. To offer high QOS to customers according SLA, cloud services broker or cloud service provider uses individual cloud providers that work collaboratively to form a federation of clouds. It is required in applications like Real-time online interactive applications, weather research and forecasting etc., in which the data and applications are complex and distributed. In these applications secret data should be shared, so secure data sharing mechanism is required in Federated clouds to reduce the risk of data intrusion, the loss of service availability and to ensure data integrity. So In this paper we have proposed zero knowledge data sharing scheme where Trusted Cloud Authority (TCA) will control federated clouds for data sharing where the secret to be exchanged for computation is encrypted and retrieved by individual cloud at the end. Our scheme is based on the difficulty of solving the Discrete Logarithm problem (DLOG) in a finite abelian group of large prime order which is NP-Hard. So our proposed scheme provides data integrity in transit, data availability when one of host providers are not available during the computation.
Rewriting and narrowing for constructor systems with call-time choice semantics
Venue: arXiv cs.PL 2012
Year: 2012

Non-confluent and non-terminating constructor-based term rewrite systems are useful for the purpose of specification and programming. In particular, existing functional logic languages use such kind of rewrite systems to define possibly non-strict non-deterministic functions. The semantics adopted for non-determinism is call-time choice, whose combination with non-strictness is a non trivial issue, addressed years ago from a semantic point of view with the Constructor-based Rewriting Logic (CRWL), a well-known semantic framework commonly accepted as suitable semantic basis of modern functional logic languages. A drawback of CRWL is that it does not come with a proper notion of one-step reduction, which would be very useful to understand and reason about how computations proceed. In this paper we develop thoroughly the theory for the first order version of let-rewriting, a simple reduction notion close to that of classical term rewriting, but extended with a let-binding construction to adequately express the combination of call-time choice with non-strict semantics. Let-rewriting can be seen as a particular textual presentation of term graph rewriting. We investigate the properties of let-rewriting, most remarkably their equivalence with respect to a conservative extension of the CRWL-semantics coping with let-bindings, and we show by some case studies that having two interchangeable formal views (reduction/semantics) of the same language is a powerful reasoning tool. After that, we provide a notion of let-narrowing which is adequate for call-time choice as proved by soundness and completeness results of let-narrowing with respect to let-rewriting. Moreover, we relate those let-rewriting and let-narrowing relations (and hence CRWL) with ordinary term rewriting and narrowing (..) To appear in Theory and Practice of Logic Programming (TPLP).
Visual Tracking with Similarity Matching Ratio
Venue: arXiv cs.CV 2012
Year: 2012

This paper presents a novel approach to visual tracking: Similarity Matching Ratio (SMR). The traditional approach of tracking is minimizing some measures of the difference between the template and a patch from the frame. This approach is vulnerable to outliers and drastic appearance changes and an extensive study is focusing on making the approach more tolerant to them. However, this often results in longer, corrective algo- rithms which do not solve the original problem. This paper proposes a novel approach to the definition of the tracking problems, SMR, which turns the differences into a probability measure. Only pixel differences below a threshold count towards deciding the match, the rest are ignored. This approach makes the SMR tracker robust to outliers and points that dramaticaly change appearance. The SMR tracker is tested on challenging video sequences and achieved state-of-the-art performance.