OpenRaiser/Intern-Atlas huggingface dataset:
The crossing numbers of $K_m\times P_n$ and $K_m\times C_n$
Venue: arXiv cs.DM 2012
Year: 2012

The {\it crossing number} of a graph $G$ is the minimum number of pairwise intersections of edges in a drawing of $G$. In this paper, we study the crossing numbers of $K_{m}\times P_n$ and $K_{m}\times C_n$.
On Whitespace Identification Using Randomly Deployed Sensors
Venue: arXiv cs.IT 2012
Year: 2012

This work considers the identification of the available whitespace, i.e., the regions that are not covered by any of the existing transmitters, within a given geographical area. To this end, $n$ sensors are deployed at random locations within the area. These sensors detect for the presence of a transmitter within their radio range $r_s$, and their individual decisions are combined to estimate the available whitespace. The limiting behavior of the recovered whitespace as a function of $n$ and $r_s$ is analyzed. It is shown that both the fraction of the available whitespace that the nodes fail to recover as well as their radio range both optimally scale as $\log(n)/n$ as $n$ gets large. The analysis is extended to the case of unreliable sensors, and it is shown that, surprisingly, the optimal scaling is still $\log(n)/n$ even in this case. A related problem of estimating the number of transmitters and their locations is also analyzed, with the sum absolute error in localization as performance metric. The optimal scaling of the radio range and the necessary minimum transmitter separation is determined, that ensure that the sum absolute error in transmitter localization is minimized, with high probability, as $n$ gets large. Finally, the optimal distribution of sensor deployment is determined, given the distribution of the transmitters, and the resulting performance benefit is characterized.
A Brief Review of Data Mining Application Involving Protein Sequence Classification
Venue: arXiv cs.DB 2012
Year: 2012

Data mining techniques have been used by researchers for analyzing protein sequences. In protein analysis, especially in protein sequence classification, selection of feature is most important. Popular protein sequence classification techniques involve extraction of specific features from the sequences. Researchers apply some well-known classification techniques like neural networks, Genetic algorithm, Fuzzy ARTMAP, Rough Set Classifier etc for accurate classification. This paper presents a review is with three different classification models such as neural network model, fuzzy ARTMAP model and Rough set classifier model. A new technique for classifying protein sequences have been proposed in the end. The proposed technique tries to reduce the computational overheads encountered by earlier approaches and increase the accuracy of classification.
Parameterized Uniform Complexity in Numerics: from Smooth to Analytic, from NP-hard to Polytime
Venue: arXiv cs.NA 2012
Year: 2012

The synthesis of classical Computational Complexity Theory with Recursive Analysis provides a quantitative foundation to reliable numerics. Here the operators of maximization, integration, and solving ordinary differential equations are known to map (even high-order differentiable) polynomial-time computable functions to instances which are `hard' for classical complexity classes NP, #P, and CH; but, restricted to analytic functions, map polynomial-time computable ones to polynomial-time computable ones -- non-uniformly! We investigate the uniform parameterized complexity of the above operators in the setting of Weihrauch's TTE and its second-order extension due to Kawamura&Cook (2010). That is, we explore which (both continuous and discrete, first and second order) information and parameters on some given f is sufficient to obtain similar data on Max(f) and int(f); and within what running time, in terms of these parameters and the guaranteed output precision 2^(-n). It turns out that Gevrey's hierarchy of functions climbing from analytic to smooth corresponds to the computational complexity of maximization growing from polytime to NP-hard. Proof techniques involve mainly the Theory of (discrete) Computation, Hard Analysis, and Information-Based Complexity.
Temporal Provenance Model (TPM): Model and Query Language
Venue: arXiv cs.DB 2012
Year: 2012

Provenance refers to the documentation of an object's lifecycle. This documentation (often represented as a graph) should include all the information necessary to reproduce a certain piece of data or the process that led to it. In a dynamic world, as data changes, it is important to be able to get a piece of data as it was, and its provenance graph, at a certain point in time. Supporting time-aware provenance querying is challenging and requires: (i) explicitly representing the time information in the provenance graphs, and (ii) providing abstractions and efficient mechanisms for time-aware querying of provenance graphs over an ever growing volume of data. The existing provenance models treat time as a second class citizen (i.e. as an optional annotation). This makes time-aware querying of provenance data inefficient and sometimes inaccessible. We introduce an extended provenance graph model to explicitly represent time as an additional dimension of provenance data. We also provide a query language, novel abstractions and efficient mechanisms to query and analyze timed provenance graphs. The main contributions of the paper include: (i) proposing a Temporal Provenance Model (TPM) as a timed provenance model; and (ii) introducing two concepts of timed folder, as a container of related set of objects and their provenance relationship over time, and timed paths, to represent the evolution of objects tracing information over time, for analyzing and querying TPM graphs. We have implemented the approach on top of FPSPARQL, a query engine for large graphs, and have evaluated for querying TPM models. The evaluation shows the viability and efficiency of our approach.
Faster Random Walks By Rewiring Online Social Networks On-The-Fly
Venue: arXiv cs.SI 2012
Year: 2012

Many online social networks feature restrictive web interfaces which only allow the query of a user's local neighborhood through the interface. To enable analytics over such an online social network through its restrictive web interface, many recent efforts reuse the existing Markov Chain Monte Carlo methods such as random walks to sample the social network and support analytics based on the samples. The problem with such an approach, however, is the large amount of queries often required (i.e., a long "mixing time") for a random walk to reach a desired (stationary) sampling distribution. In this paper, we consider a novel problem of enabling a faster random walk over online social networks by "rewiring" the social network on-the-fly. Specifically, we develop Modified TOpology (MTO)-Sampler which, by using only information exposed by the restrictive web interface, constructs a "virtual" overlay topology of the social network while performing a random walk, and ensures that the random walk follows the modified overlay topology rather than the original one. We show that MTO-Sampler not only provably enhances the efficiency of sampling, but also achieves significant savings on query cost over real-world online social networks such as Google Plus, Epinion etc.
Families of Hadamard Z2Z4Q8-codes
Venue: arXiv cs.IT 2012
Year: 2012

A Z2Z4Q8-code is a non-empty subgroup of a direct product of copies of Z_2, Z_4 and Q_8 (the binary field, the ring of integers modulo 4 and the quaternion group on eight elements, respectively). Such Z2Z4Q8-codes are translation invariant propelinear codes as the well known Z_4-linear or Z_2Z_4-linear codes. In the current paper, we show that there exist "pure" Z2Z4Q8-codes, that is, codes that do not admit any abelian translation invariant propelinear structure. We study the dimension of the kernel and rank of the Z2Z4Q8-codes, and we give upper and lower bounds for these parameters. We give tools to construct a new class of Hadamard codes formed by several families of Z2Z4Q8-codes; we study and show the different shapes of such a codes and we improve the upper and lower bounds for the rank and the dimension of the kernel when the codes are Hadamard.
The Parametric Ordinal-Recursive Complexity of Post Embedding Problems
Venue: arXiv cs.LO 2012
Year: 2012

Post Embedding Problems are a family of decision problems based on the interaction of a rational relation with the subword embedding ordering, and are used in the literature to prove non multiply-recursive complexity lower bounds. We refine the construction of Chambart and Schnoebelen (LICS 2008) and prove parametric lower bounds depending on the size of the alphabet.
NanoInfoBio: A case-study in interdisciplinary research
Venue: arXiv cs.GL 2012
Year: 2012

A significant amount of high-impact contemporary scientific research occurs where biology, computer science, engineering and chemistry converge. Although programmes have been put in place to support such work, the complex dynamics of interdisciplinarity are still poorly understood. In this paper we highlight potential barriers to effective research across disciplines, and suggest, using a case study, possible mechanisms for removing these impediments.
A Composite Design Pattern for Service Injection and Composition of Web Services for Peer-To-Peer Computing with Service Oriented Architecture
Venue: arXiv cs.SE 2012
Year: 2012

In this paper we present a Service Injection and composition Design Pattern for Unstructured Peer-to-Peer networks, which is designed with Aspect-oriented design patterns, and amalgamation of the Strategy, Worker Object, and Check-List Design Patterns used to design the Self-Adaptive Systems. It will apply self reconfiguration planes dynamically without the interruption or intervention of the administrator for handling service failures at the servers. When a client requests for a complex service, Service Composition should be done to fulfil the request. If a service is not available in the memory, it will be injected as Aspectual Feature Module code. We used Service Oriented Architecture (SOA) with Web Services in Java to Implement the composite Design Pattern. As far as we know, there are no studies on composition of design patterns for Peer-to-peer computing domain. The pattern is described using a java-like notation for the classes and interfaces. A simple UML class and Sequence diagrams are depicted.
Trajectory Tracking Control with Flat Inputs and a Dynamic Compensator
Venue: arXiv cs.SY 2012
Year: 2012

This paper proposes a tracking controller based on the concept of flat inputs and a dynamic compensator. Flat inputs represent a dual approach to flat outputs. In contrast to conventional flatness-based control design, the regulated output may be a non-flat output, or the system may be non-flat. The method is applicable to observable systems with stable internal dynamics. The performance of the new design is demonstrated on the variable-length pendulum, a non-flat nonlinear system with a singularity in the relative degree.
An Automatic Algorithm for Object Recognition and Detection Based on ASIFT Keypoints
Venue: arXiv cs.AI 2012
Year: 2012

Object recognition is an important task in image processing and computer vision. This paper presents a perfect method for object recognition with full boundary detection by combining affine scale invariant feature transform (ASIFT) and a region merging algorithm. ASIFT is a fully affine invariant algorithm that means features are invariant to six affine parameters namely translation (2 parameters), zoom, rotation and two camera axis orientations. The features are very reliable and give us strong keypoints that can be used for matching between different images of an object. We trained an object in several images with different aspects for finding best keypoints of it. Then, a robust region merging algorithm is used to recognize and detect the object with full boundary in the other images based on ASIFT keypoints and a similarity measure for merging regions in the image. Experimental results show that the presented method is very efficient and powerful to recognize the object and detect it with high accuracy.
User Scheduling for Coordinated Dual Satellite Systems with Linear Precoding
Venue: arXiv cs.IT 2012
Year: 2012

The constantly increasing demand for interactive broadband satellite communications is driving current research to explore novel system architectures that reuse frequency in a more aggressive manner. To this end, the topic of dual satellite systems, in which satellites share spatial (i.e. same coverage area) and spectral (i.e. full frequency reuse) degrees of freedom is introduced. In each multibeam satellite, multiuser interferences are mitigated by employing zero forcing precoding with realistic per antenna power constraints. However, the two sets of users that the transmitters are separately serving, interfere. The present contribution, proposes the partial cooperation, namely coordination between the two coexisting transmitters in order to reduce interferences and enhance the performance of the whole system, while maintaining moderate system complexity. In this direction, a heuristic, iterative, low complexity algorithm that allocates users in the two interfering sets is proposed. This novel algorithm, improves the performance of each satellite and of the overall system, simultaneously. The first is achieved by maximizing the orthogonality between users allocated in the same set, hence optimizing the zero forcing performance, whilst the second by minimizing the level of interferences between the two sets. Simulation results show that the proposed method, compared to conventional techniques, significantly increases spectral efficiency.
Finding influential users of an online health community: a new metric based on sentiment influence
Venue: arXiv cs.SI 2012
Year: 2012

What characterizes influential users in online health communities (OHCs)? We hypothesize that (1) the emotional support received by OHC members can be assessed from their sentiment ex-pressed in online interactions, and (2) such assessments can help to identify influential OHC members. Through text mining and sentiment analysis of users' online interactions, we propose a novel metric that directly measures a user's ability to affect the sentiment of others. Using dataset from an OHC, we demonstrate that this metric is highly effective in identifying influential users. In addition, combining the metric with other traditional measures further improves the identification of influential users. This study can facilitate online community management and advance our understanding of social influence in OHCs.
A Formal Model of a Virtual Filesystem Switch
Venue: arXiv cs.LO 2012
Year: 2012

This work presents a formal model that is part of our effort to construct a verified file system for Flash memory. To modularize the verification we factor out generic aspects into a common component that is inspired by the Linux Virtual Filesystem Switch (VFS) and provides POSIX compatible operations. It relies on an abstract specification of its internal interface to concrete file system implementations (AFS). We proved that preconditions of AFS are respected and that the state is kept consistent. The model can be made executable and mounted into the Linux directory tree using FUSE.
Distributed Priority Synthesis
Venue: arXiv cs.SY 2012
Year: 2012

Given a set of interacting components with non-deterministic variable update and given safety requirements, the goal of priority synthesis is to restrict, by means of priorities, the set of possible interactions in such a way as to guarantee the given safety conditions for all possible runs. In distributed priority synthesis we are interested in obtaining local sets of priorities, which are deployed in terms of local component controllers sharing intended next moves between components in local neighborhoods only. These possible communication paths between local controllers are specified by means of a communication architecture. We formally define the problem of distributed priority synthesis in terms of a multi-player safety game between players for (angelically) selecting the next transition of the components and an environment for (demonically) updating uncontrollable variables. We analyze the complexity of the problem, and propose several optimizations including a solution-space exploration based on a diagnosis method using a nested extension of the usual attractor computation in games together with a reduction to corresponding SAT problems. When diagnosis fails, the method proposes potential candidates to guide the exploration. These optimized algorithms for solving distributed priority synthesis problems have been integrated into the VissBIP framework. An experimental validation of this implementation is performed using a range of case studies including scheduling in multicore processors and modular robotics.
A Methodology for Studying VANET Performance with Practical Vehicle Distribution in Urban Environment
Venue: arXiv cs.NI 2012
Year: 2012

In a Vehicular Ad-hoc Network (VANET), the amount of interference from neighboring nodes to a communication link is governed by the vehicle density dynamics in vicinity and transmission probabilities of terminals. It is obvious that vehicles are distributed non-homogeneously along a road segment due to traffic controls and speed limits at different portions of the road. The common assumption of homogeneous node distribution in the network in most of the previous work in mobile ad-hoc networks thus appears to be inappropriate in VANETs. In light of the inadequacy, we present in this paper an original methodology to study the performance of VANETs with practical vehicle distribution in urban environment. Specifically, we introduce the stochastic traffic model to characterize the general vehicular traffic flow as well as the randomness of individual vehicles, from which we can acquire the mean dynamics and the probability distribution of vehicular density. As illustrative examples, we demonstrate how the density knowledge from the stochastic traffic model can be utilized to derive the throughput and progress performance of three routing strategies in different channel access protocols. We confirm the accuracy of the analytical results through extensive simulations. Our results demonstrate the applicability of the proposed methodology on modeling protocol performance, and shed insight into the performance analysis of other transmission protocols and network configurations in vehicular networks. Furthermore, we illustrate that the optimal transmission probability for optimized network performance can be obtained as a function of the location space from our results. Such information can be computed by road-side nodes and then broadcasted to road users for optimized multi-hop packet transmission in the communication network.
Increasing the failure recovery probability of atomic replacement approaches
Venue: arXiv cs.SE 2012
Year: 2012

Web processes are made up of services as their units of functionality. The services are represented as a graph and compose a synergy of service. The composite service is prone to failure due to various causes. However, the end-user should receive a smooth and non-interrupted execution. Atomic replacement of a failed Web service to recover the system is a straightforward approach. Nevertheless, finding a similar service is not reliable. In order to increase the probability of the recovery of a failed composite service, a set of services is replaced with another similar set.
TwitterPaul: Extracting and Aggregating Twitter Predictions
Venue: arXiv cs.SI 2012
Year: 2012

This paper introduces TwitterPaul, a system designed to make use of Social Media data to help to predict game outcomes for the 2010 FIFA World Cup tournament. To this end, we extracted over 538K mentions to football games from a large sample of tweets that occurred during the World Cup, and we classified into different types with a precision of up to 88%. The different mentions were aggregated in order to make predictions about the outcomes of the actual games. We attempt to learn which Twitter users are accurate predictors and explore several techniques in order to exploit this information to make more accurate predictions. We compare our results to strong baselines and against the betting line (prediction market) and found that the quality of extractions is more important than the quantity, suggesting that high precision methods working on a medium-sized dataset are preferable over low precision methods that use a larger amount of data. Finally, by aggregating some classes of predictions, the system performance is close to the one of the betting line. Furthermore, we believe that this domain independent framework can help to predict other sports, elections, product release dates and other future events that people talk about in social media.
Using Friends as Sensors to Detect Global-Scale Contagious Outbreaks
Venue: arXiv cs.SI 2012
Year: 2012

Recent research has focused on the monitoring of global-scale online data for improved detection of epidemics, mood patterns, movements in the stock market, political revolutions, box-office revenues, consumer behaviour and many other important phenomena. However, privacy considerations and the sheer scale of data available online are quickly making global monitoring infeasible, and existing methods do not take full advantage of local network structure to identify key nodes for monitoring. Here, we develop a model of the contagious spread of information in a global-scale, publicly-articulated social network and show that a simple method can yield not just early detection, but advance warning of contagious outbreaks. In this method, we randomly choose a small fraction of nodes in the network and then we randomly choose a "friend" of each node to include in a group for local monitoring. Using six months of data from most of the full Twittersphere, we show that this friend group is more central in the network and it helps us to detect viral outbreaks of the use of novel hashtags about 7 days earlier than we could with an equal-sized randomly chosen group. Moreover, the method actually works better than expected due to network structure alone because highly central actors are both more active and exhibit increased diversity in the information they transmit to others. These results suggest that local monitoring is not just more efficient, it is more effective, and it is possible that other contagious processes in global-scale networks may be similarly monitored.
Average sampling of band-limited stochastic processes
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of reconstructing a wide sense stationary band-limited process from its local averages taken either at the Nyquist rate or above. As a result, we obtain a sufficient condition under which average sampling expansions hold in mean square and for almost all sample functions. Truncation and aliasing errors of the expansion are also discussed.