OpenRaiser/Intern-Atlas huggingface dataset:
A Simple Sequential Spectrum Sensing Scheme for Cognitive Radio
Venue: arXiv cs.IT 2009
Year: 2009

Cognitive radio that supports a secondary and opportunistic access to licensed spectrum shows great potential to dramatically improve spectrum utilization. Spectrum sensing performed by secondary users to detect unoccupied spectrum bands, is a key enabling technique for cognitive radio. This paper proposes a truncated sequential spectrum sensing scheme, namely the sequential shifted chi-square test (SSCT). The SSCT has a simple test statistic and does not rely on any deterministic knowledge about primary signals. As figures of merit, the exact false-alarm probability is derived, and the miss-detection probability as well as the average sample number (ASN) are evaluated by using a numerical integration algorithm. Corroborating numerical examples show that, in comparison with fixed-sample size detection schemes such as energy detection, the SSCT delivers considerable reduction on the ASN while maintaining a comparable detection performance.
Divide and Conquer: Partitioning Online Social Networks
Venue: arXiv cs.NI 2009
Year: 2009

Online Social Networks (OSNs) have exploded in terms of scale and scope over the last few years. The unprecedented growth of these networks present challenges in terms of system design and maintenance. One way to cope with this is by partitioning such large networks and assigning these partitions to different machines. However, social networks possess unique properties that make the partitioning problem non-trivial. The main contribution of this paper is to understand different properties of social networks and how these properties can guide the choice of a partitioning algorithm. Using large scale measurements representing real OSNs, we first characterize different properties of social networks, and then we evaluate qualitatively different partitioning methods that cover the design space. We expose different trade-offs involved and understand them in light of properties of social networks. We show that a judicious choice of a partitioning scheme can help improve performance.
The cost of being co-Buchi is nonlinear
Venue: arXiv cs.FL 2009
Year: 2009

It is well known, and easy to see, that not each nondeterministic Buchi automaton on infinite words can be simulated by a nondeterministic co-Buchi automaton. We show that in the cases when such a simulation is possible, the number of states needed for it can grow nonlinearly. More precisely, we show a sequence of - as we believe, simple and elegant - languages which witness the existence of a nondeterministic Buchi automaton with n states, which can be simulated by a nondeterministic co-Buchi automaton, but cannot be simulated by any nondeterministic co-Buchi automaton with less than c*n^{7/6} states for some constant c. This improves on the best previously known lower bound of 3(n-1)/2.
Equations of States in Statistical Learning for a Nonparametrizable and Regular Case
Venue: arXiv cs.LG 2009
Year: 2009

Many learning machines that have hierarchical structure or hidden variables are now being used in information science, artificial intelligence, and bioinformatics. However, several learning machines used in such fields are not regular but singular statistical models, hence their generalization performance is still left unknown. To overcome these problems, in the previous papers, we proved new equations in statistical learning, by which we can estimate the Bayes generalization loss from the Bayes training loss and the functional variance, on the condition that the true distribution is a singularity contained in a learning machine. In this paper, we prove that the same equations hold even if a true distribution is not contained in a parametric model. Also we prove that, the proposed equations in a regular case are asymptotically equivalent to the Takeuchi information criterion. Therefore, the proposed equations are always applicable without any condition on the unknown true distribution.
Solar radiation forecasting using ad-hoc time series preprocessing and neural networks
Venue: arXiv cs.AI 2009
Year: 2009

In this paper, we present an application of neural networks in the renewable energy domain. We have developed a methodology for the daily prediction of global solar radiation on a horizontal surface. We use an ad-hoc time series preprocessing and a Multi-Layer Perceptron (MLP) in order to predict solar radiation at daily horizon. First results are promising with nRMSE < 21% and RMSE < 998 Wh/m2. Our optimized MLP presents prediction similar to or even better than conventional methods such as ARIMA techniques, Bayesian inference, Markov chains and k-Nearest-Neighbors approximators. Moreover we found that our data preprocessing approach can reduce significantly forecasting errors.
Towards a Centralized Scheduling Framework for Communication Flows in Distributed Systems
Venue: arXiv cs.DS 2009
Year: 2009

The overall performance of a distributed system is highly dependent on the communication efficiency of the system. Although network resources (links, bandwidth) are becoming increasingly more available, the communication performance of data transfers involving large volumes of data does not necessarily improve at the same rate. This is due to the inefficient usage of the available network resources. A solution to this problem consists of data transfer scheduling techniques, which manage and allocate the network resources in an efficient manner. In this paper we present several online and offline data transfer optimization techniques, in the context of a centrally controlled distributed system.
A Mixed-Fractal Model for Network Traffic
Venue: arXiv cs.NI 2009
Year: 2009

In this short paper, we propose a new multi-fractal flow model, aiming to provide a possible explanation for the crossover phenomena that appear in the estimation of Hurst exponent for network traffic. It is shown that crossover occurs if the network flow consists of several components with different Hurst components. Our results indicate that this model might be useful in network traffic modeling and simulation.
On linear completely regular codes with covering radius $ρ=1$. Construction and classification
Venue: arXiv cs.IT 2009
Year: 2009

Completely regular codes with covering radius $ρ=1$ must have minimum distance $d\leq 3$. For $d=3$, such codes are perfect and their parameters are well known. In this paper, the cases $d=1$ and $d=2$ are studied and completely characterized when the codes are linear. Moreover, it is proven that all these codes are completely transitive.
Size dependent word frequencies and translational invariance of books
Venue: arXiv cs.CL 2009
Year: 2009

It is shown that a real novel shares many characteristic features with a null model in which the words are randomly distributed throughout the text. Such a common feature is a certain translational invariance of the text. Another is that the functional form of the word-frequency distribution of a novel depends on the length of the text in the same way as the null model. This means that an approximate power-law tail ascribed to the data will have an exponent which changes with the size of the text-section which is analyzed. A further consequence is that a novel cannot be described by text-evolution models like the Simon model. The size-transformation of a novel is found to be well described by a specific Random Book Transformation. This size transformation in addition enables a more precise determination of the functional form of the word-frequency distribution. The implications of the results are discussed.
Dynamic Data Flow Analysis via Virtual Code Integration (aka The SpiderPig case)
Venue: arXiv cs.CR 2009
Year: 2009

Paper addresses the process of dynamic data flow analysis using virtual code integration (VCI), often refered to as dynamic binary rewriting. This article will try to demonstrate all of the techniques that were applied in the SpiderPig project. It will also discuss the main differences between the methods that were employed and those used in other available software, as well as introducing other related work. SpiderPig's approach was found to be very fast and was transparent enough for reliable and usable data flow analysis. It was created with the purpose of providing a tool which would aid vulnerability and security researchers with tracing and analyzing any necessary data and its further propagation through a program. At the current state it works on IA-32 platforms with Microsoft Windows systems and it supports FPU, SSE, MMX and all of the IA-32 general instructions. SpiderPig also demonstrates the usage of a virtual code integration (VCI) framework which allows for modifying the target application code at the instruction level. By this I mean that the VCI framework allows for custom code insertion, original code modification and full customization of the original application's code. Instructions can be swapped out, deleted or modified at a whim, without corrupting the surrounding code and side-effects of the modification are resolved.
Spectrum Sensing in Low SNR Regime via Stochastic Resonance
Venue: arXiv cs.IT 2009
Year: 2009

Spectrum sensing is essential in cognitive radio to enable dynamic spectrum access. In many scenarios, primary user signal must be detected reliably in low signal-to-noise ratio (SNR) regime under required sensing time. We propose to use stochastic resonance, a nonlinear filter having certain resonance frequency, to detect primary users when the SNR is very low. Both block and sequential detection schemes are studied. Simulation results show that, under the required false alarm rate, both detection probability and average detection delay can be substantially improved. A few implementation issues are also discussed.
PDF/A standard for long term archiving
Venue: arXiv cs.DL 2009
Year: 2009

PDF/A is defined by ISO 19005-1 as a file format based on PDF format. The standard provides a mechanism for representing electronic documents in a way that preserves their visual appearance over time, independent of the tools and systems used for creating or storing the files.
Fast Weak Learner Based on Genetic Algorithm
Venue: arXiv cs.LG 2009
Year: 2009

An approach to the acceleration of parametric weak classifier boosting is proposed. Weak classifier is called parametric if it has fixed number of parameters and, so, can be represented as a point into multidimensional space. Genetic algorithm is used instead of exhaustive search to learn parameters of such classifier. Proposed approach also takes cases when effective algorithm for learning some of the classifier parameters exists into account. Experiments confirm that such an approach can dramatically decrease classifier training time while keeping both training and test errors small.
On a Generalized Foster-Lyapunov Type Criterion for the Stability of Multidimensional Markov chains with Applications to the Slotted-Aloha Protocol with Finite Number of Queues
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we generalize a positive recurrence criterion for multidimensional discrete-time Markov chains over countable state spaces due to Rosberg (JAP, Vol. 17, No. 3, 1980). We revisit the stability analysis of well known slotted-Aloha protocol with finite number of queues. Under standard modeling assumptions, we derive a sufficient condition for the stability by applying our positive recurrence criterion. Our sufficiency condition for stability is linear in arrival rates and does not require knowledge of the stationary joint statistics of queue lengths. We believe that the technique reported here could be useful in analyzing other stability problems in countable space Markovian settings. Toward the end, we derive some sufficient conditions for instability of the protocol.
On Sparse Channel Estimation
Venue: arXiv cs.IT 2009
Year: 2009

Channel Estimation is an essential component in applications such as radar and data communication. In multi path time varying environments, it is necessary to estimate time-shifts, scale-shifts (the wideband equivalent of Doppler-shifts), and the gains/phases of each of the multiple paths. With recent advances in sparse estimation (or "compressive sensing"), new estimation techniques have emerged which yield more accurate estimates of these channel parameters than traditional strategies. These estimation strategies, however, restrict potential estimates of time-shifts and scale-shifts to a finite set of values separated by a choice of grid spacing. A small grid spacing increases the number of potential estimates, thus lowering the quantization error, but also increases complexity and estimation time. Conversely, a large grid spacing lowers the number of potential estimates, thus lowering the complexity and estimation time, but increases the quantization error. In this thesis, we derive an expression which relates the choice of grid spacing to the mean-squared quantization error. Furthermore, we consider the case when scale-shifts are approximated by Doppler-shifts, and derive a similar expression relating the choice of the grid spacing and the quantization error. Using insights gained from these expressions, we further explore the effects of the choice and grid spacing, and examine when a wideband model can be well approximated by a narrowband model.
On the Complexity of Smooth Spline Surfaces from Quad Meshes
Venue: arXiv cs.GR 2009
Year: 2009

This paper derives strong relations that boundary curves of a smooth complex of patches have to obey when the patches are computed by local averaging. These relations restrict the choice of reparameterizations for geometric continuity. In particular, when one bicubic tensor-product B-spline patch is associated with each facet of a quadrilateral mesh with n-valent vertices and we do not want segments of the boundary curves forced to be linear, then the relations dictate the minimal number and multiplicity of knots: For general data, the tensor-product spline patches must have at least two internal double knots per edge to be able to model a G^1-conneced complex of C^1 splines. This lower bound on the complexity of any construction is proven to be sharp by suitably interpreting an existing surface construction. That is, we have a tight bound on the complexity of smoothing quad meshes with bicubic tensor-product B-spline patches.
Generalised Pinsker Inequalities
Venue: arXiv cs.IT 2009
Year: 2009

We generalise the classical Pinsker inequality which relates variational divergence to Kullback-Liebler divergence in two ways: we consider arbitrary f-divergences in place of KL divergence, and we assume knowledge of a sequence of values of generalised variational divergences. We then develop a best possible inequality for this doubly generalised situation. Specialising our result to the classical case provides a new and tight explicit bound relating KL to variational divergence (solving a problem posed by Vajda some 40 years ago). The solution relies on exploiting a connection between divergences and the Bayes risk of a learning problem via an integral representation.
Algebraic methods for counting Euclidean embeddings of rigid graphs
Venue: arXiv cs.CG 2009
Year: 2009

The study of (minimally) rigid graphs is motivated by numerous applications, mostly in robotics and bioinformatics. A major open problem concerns the number of embeddings of such graphs, up to rigid motions, in Euclidean space. We capture embeddability by polynomial systems with suitable structure, so that their mixed volume, which bounds the number of common roots, to yield interesting upper bounds on the number of embeddings. We focus on $\RR^2$ and $\RR^3$, where Laman graphs and 1-skeleta of convex simplicial polyhedra, respectively, admit inductive Henneberg constructions. We establish the first lower bound in $\RR^3$ of about $2.52^n$, where $n$ denotes the number of vertices. Moreover, our implementation yields upper bounds for $n \le 10$ in $\RR^2$ and $\RR^3$, which reduce the existing gaps, and tight bounds up to $n=7$ in $\RR^3$.
The Complexity of Satisfiability for Fragments of Hybrid Logic -- Part I
Venue: arXiv cs.LO 2009
Year: 2009

The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this paper, we investigate the effect of restricting the propositional part of the language on decidability and on the complexity of the satisfiability problem over arbitrary, transitive, total frames, and frames based on equivalence relations. We also consider different sets of modal and hybrid operators. We trace the border of decidability and give the precise complexity of most fragments, in particular for all fragments including negation. For the monotone fragments, we are able to distinguish the easy from the hard cases, depending on the allowed set of operators.
On Defining 'I' "I logy"
Venue: arXiv cs.AI 2009
Year: 2009

Could we define I? Throughout this article we give a negative answer to this question. More exactly, we show that there is no definition for I in a certain way. But this negative answer depends on our definition of definability. Here, we try to consider sufficient generalized definition of definability. In the middle of paper a paradox will arise which makes us to modify the way we use the concept of property and definability.
On the Statistics of Cognitive Radio Capacity in Shadowing and Fast Fading Environments (Journal Version)
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we consider the capacity of the cognitive radio channel in different fading environments under a low interference regime. First we derive the probability that the low interference regime holds under shadow fading as well as Rayleigh and Rician fast fading conditions. We demonstrate that this is the dominant case, especially in practical cognitive radio deployment scenarios. The capacity of the cognitive radio channel depends critically on a power loss parameter, $α$, which governs how much transmit power the cognitive radio dedicates to relaying the primary message. We derive a simple, accurate approximation to $α$ in Rayleigh and Rician fading environments which gives considerable insight into system capacity. We also investigate the effects of system parameters and propagation environment on $α$ and the cognitive radio capacity. In all cases, the use of the approximation is shown to be extremely accurate.
Scheduling with Outliers
Venue: arXiv cs.DS 2009
Year: 2009

In classical scheduling problems, we are given jobs and machines, and have to schedule all the jobs to minimize some objective function. What if each job has a specified profit, and we are no longer required to process all jobs -- we can schedule any subset of jobs whose total profit is at least a (hard) target profit requirement, while still approximately minimizing the objective function? We refer to this class of problems as scheduling with outliers. This model was initiated by Charikar and Khuller (SODA'06) on the minimum max-response time in broadcast scheduling. We consider three other well-studied scheduling objectives: the generalized assignment problem, average weighted completion time, and average flow time, and provide LP-based approximation algorithms for them. For the minimum average flow time problem on identical machines, we give a logarithmic approximation algorithm for the case of unit profits based on rounding an LP relaxation; we also show a matching integrality gap. For the average weighted completion time problem on unrelated machines, we give a constant factor approximation. The algorithm is based on randomized rounding of the time-indexed LP relaxation strengthened by the knapsack-cover inequalities. For the generalized assignment problem with outliers, we give a simple reduction to GAP without outliers to obtain an algorithm whose makespan is within 3 times the optimum makespan, and whose cost is at most (1 + ε) times the optimal cost.
Adding eScience Assets to the Data Web
Venue: arXiv cs.DL 2009
Year: 2009

Aggregations of Web resources are increasingly important in scholarship as it adopts new methods that are data-centric, collaborative, and networked-based. The same notion of aggregations of resources is common to the mashed-up, socially networked information environment of Web 2.0. We present a mechanism to identify and describe aggregations of Web resources that has resulted from the Open Archives Initiative - Object Reuse and Exchange (OAI-ORE) project. The OAI-ORE specifications are based on the principles of the Architecture of the World Wide Web, the Semantic Web, and the Linked Data effort. Therefore, their incorporation into the cyberinfrastructure that supports eScholarship will ensure the integration of the products of scholarly research into the Data Web.
Structure of Heterogeneous Networks
Venue: arXiv cs.CY 2009
Year: 2009

Heterogeneous networks play a key role in the evolution of communities and the decisions individuals make. These networks link different types of entities, for example, people and the events they attend. Network analysis algorithms usually project such networks unto simple graphs composed of entities of a single type. In the process, they conflate relations between entities of different types and loose important structural information. We develop a mathematical framework that can be used to compactly represent and analyze heterogeneous networks that combine multiple entity and link types. We generalize Bonacich centrality, which measures connectivity between nodes by the number of paths between them, to heterogeneous networks and use this measure to study network structure. Specifically, we extend the popular modularity-maximization method for community detection to use this centrality metric. We also rank nodes based on their connectivity to other nodes. One advantage of this centrality metric is that it has a tunable parameter we can use to set the length scale of interactions. By studying how rankings change with this parameter allows us to identify important nodes in the network. We apply the proposed method to analyze the structure of several heterogeneous networks. We show that exploiting additional sources of evidence corresponding to links between, as well as among, different entity types yields new insights into network structure.
Shopping Uncertainties in a Mobile and Social Context
Venue: arXiv cs.HC 2009
Year: 2009

We conducted a qualitative user study with 77 consumers to investigate what social aspects are relevant when supporting customers during their shopping activities and particularly in situations when they are undecided. Twenty-five respondents (32%) reported seeking extra information on web pages and forums, in addition to asking their peers for advice (related to the nature of the item to be bought). Moreover, from the remaining 52 subjects, only 6 (8%) were confident enough to make prompt comparisons between items and an immediate purchasing choice, while 17 respondents (22%) expressed the need for being away from persuasive elements. The remaining 29 respondents (38%) reported having a suboptimal strategy for making their shopping decisions (i.e. buying all items, not buying, or choosing randomly). Therefore, the majority of our participants (70% = 32% + 38%) had social and information needs when making purchasing decisions. This result motivates the development of applications that would allow consumers to ask shopping questions to their social network while on-the-go.
Symbolic Script Programming for Java
Venue: arXiv cs.SC 2009
Year: 2009

Computer algebra in Java is a promising field of development. It has not yet reached an industrial strength, in part because of a lack of good user interfaces. Using a general purpose scripting language can bring a natural mathematical notation, akin to the one of specialized interfaces included in most computer algebra systems. We present such an interface for Java computer algebra libraries, using scripts available in the JSR 223 framework. We introduce the concept of `symbolic programming' and show its usefulness by prototypes of symbolic polynomials and polynomial rings.