OpenRaiser/Intern-Atlas huggingface dataset:
Similarity Analysis and Modeling in Mobile Societies: The Missing Link
Venue: arXiv cs.NI 2010
Year: 2010

A new generation of "behavior-aware" delay tolerant networks is emerging in what may define future mobile social networks. With the introduction of novel behavior-aware protocols, services and architectures, there is a pressing need to understand and realistically model mobile users behavioral characteristics, their similarity and clustering. Such models are essential for the analysis, performance evaluation, and simulation of future DTNs. This paper addresses issues related to mobile user similarity, its definition, analysis and modeling. To define similarity, we adopt a behavioral-profile based on users location preferences using their on-line association matrix and its SVD, then calculate the behavioral distance to capture user similarity. This measures the difference of the major spatio-temporal behavioral trends and can be used to cluster users into similarity groups or communities. We then analyze and contrast similarity distributions of mobile user populations in two settings: (i) based on real measurements from four major campuses with over ten thousand users for a month, and (ii) based on existing mobility models, including random direction and time-varying community models. Our results show a rich set of similar communities in real mobile societies with distinct behavioral clusters of users. This is true for all the traces studied, with the trend being consistent over time. Surprisingly, however, we find that the existing mobility models do not explicitly capture similarity and result in homogeneous users that are all similar to each other. Thus the richness and diversity of user behavioral patterns is not captured to any degree in the existing models. These findings strongly suggest that similarity should be explicitly captured in future mobility models, which motivates the need to re-visit mobility modeling in the future.
Gang FTP scheduling of periodic and parallel rigid real-time tasks
Venue: arXiv cs.OS 2010
Year: 2010

In this paper we consider the scheduling of periodic and parallel rigid tasks. We provide (and prove correct) an exact schedulability test for Fixed Task Priority (FTP) Gang scheduler sub-classes: Parallelism Monotonic, Idling, Limited Gang, and Limited Slack Reclaiming. Additionally, we study the predictability of our schedulers: we show that Gang FJP schedulers are not predictable and we identify several sub-classes which are actually predictable. Moreover, we extend the definition of rigid, moldable and malleable jobs to recurrent tasks.
Monotonic Mappings Invariant Linearisation of Finite Posets
Venue: arXiv cs.DM 2010
Year: 2010

In this paper we describe a novel a procedure to build a linear order from an arbitrary poset which (i) preserves the original ordering and (ii) allows to extend monotonic and antitonic mappings defined over the original poset to monotonic and antitonic mappings over the new linear poset.
The Study State Analysis of Tandem Queue with Blocking and Feedback
Venue: arXiv cs.NI 2010
Year: 2010

Computer system models provide detailed answer to system performance.In this paper a two stage tandem network system with Blocking and Feedback is considered and it performance has been analyzed by spectral expansion method.The study state system with balance equations has been discussed.
Image Segmentation Using Weak Shape Priors
Venue: arXiv cs.CV 2010
Year: 2010

The problem of image segmentation is known to become particularly challenging in the case of partial occlusion of the object(s) of interest, background clutter, and the presence of strong noise. To overcome this problem, the present paper introduces a novel approach segmentation through the use of "weak" shape priors. Specifically, in the proposed method, an segmenting active contour is constrained to converge to a configuration at which its geometric parameters attain their empirical probability densities closely matching the corresponding model densities that are learned based on training samples. It is shown through numerical experiments that the proposed shape modeling can be regarded as "weak" in the sense that it minimally influences the segmentation, which is allowed to be dominated by data-related forces. On the other hand, the priors provide sufficient constraints to regularize the convergence of segmentation, while requiring substantially smaller training sets to yield less biased results as compared to the case of PCA-based regularization methods. The main advantages of the proposed technique over some existing alternatives is demonstrated in a series of experiments.
Penalized K-Nearest-Neighbor-Graph Based Metrics for Clustering
Venue: arXiv cs.CV 2010
Year: 2010

A difficult problem in clustering is how to handle data with a manifold structure, i.e. data that is not shaped in the form of compact clouds of points, forming arbitrary shapes or paths embedded in a high-dimensional space. In this work we introduce the Penalized k-Nearest-Neighbor-Graph (PKNNG) based metric, a new tool for evaluating distances in such cases. The new metric can be used in combination with most clustering algorithms. The PKNNG metric is based on a two-step procedure: first it constructs the k-Nearest-Neighbor-Graph of the dataset of interest using a low k-value and then it adds edges with an exponentially penalized weight for connecting the sub-graphs produced by the first step. We discuss several possible schemes for connecting the different sub-graphs. We use three artificial datasets in four different embedding situations to evaluate the behavior of the new metric, including a comparison among different clustering methods. We also evaluate the new metric in a real world application, clustering the MNIST digits dataset. In all cases the PKNNG metric shows promising clustering results.
Global Optimization for Value Function Approximation
Venue: arXiv cs.AI 2010
Year: 2010

Existing value function approximation methods have been successfully used in many applications, but they often lack useful a priori error bounds. We propose a new approximate bilinear programming formulation of value function approximation, which employs global optimization. The formulation provides strong a priori guarantees on both robust and expected policy loss by minimizing specific norms of the Bellman residual. Solving a bilinear program optimally is NP-hard, but this is unavoidable because the Bellman-residual minimization itself is NP-hard. We describe and analyze both optimal and approximate algorithms for solving bilinear programs. The analysis shows that this algorithm offers a convergent generalization of approximate policy iteration. We also briefly analyze the behavior of bilinear programming algorithms under incomplete samples. Finally, we demonstrate that the proposed approach can consistently minimize the Bellman residual on simple benchmark problems.
A Metaheuristic Approach for IT Projects Portfolio Optimization
Venue: arXiv cs.CE 2010
Year: 2010

Optimal selection of interdependent IT Projects for implementation in multi periods has been challenging in the framework of real option valuation. This paper presents a mathematical optimization model for multi-stage portfolio of IT projects. The model optimizes the value of the portfolio within a given budgetary and sequencing constraints for each period. These sequencing constraints are due to time wise interdependencies among projects. A Metaheuristic approach is well suited for solving this kind of a problem definition and in this paper a genetic algorithm model has been proposed for the solution. This optimization model and solution approach can help IT managers taking optimal funding decision for projects prioritization in multiple sequential periods. The model also gives flexibility to the managers to generate alternative portfolio by changing the maximum and minimum number of projects to be implemented in each sequential period.
A Parallel Encryption Algorithm for Block Ciphers Based on Reversible Programmable Cellular Automata
Venue: arXiv cs.CR 2010
Year: 2010

A Cellular Automata (CA) is a computing model of complex System using simple rule. In CA the problem space into number of cell and each cell can be one or several final state. Cells are affected by neighbours' to the simple rule. Cellular Automata are highly parallel and discrete dynamical systems, whose behaviour is completely specified in terms of a local relation. This paper deals with the Cellular Automata (CA) in cryptography for a class of Block Ciphers through a new block encryption algorithm based on Reversible Programmable Cellular Automata Theory. The proposed algorithm belongs to the class of symmetric key systems.
A Complexity measure based on Requirement Engineering Document
Venue: arXiv cs.SE 2010
Year: 2010

Research shows, that the major issue in development of quality software is precise estimation. Further this estimation depends upon the degree of intricacy inherent in the software i.e. complexity. This paper attempts to empirically demonstrate the proposed complexity which is based on IEEE Requirement Engineering document. It is said that a high quality SRS is pre requisite for high quality software. Requirement Engineering document (SRS) is a specification for a particular software product, program or set of program that performs some certain functions for a specific environment. The various complexity measure given so far are based on Code and Cognitive metrics value of software, which are code based. So these metrics provide no leverage to the developer of the code. Considering the shortcoming of code based approaches, the proposed approach identifies complexity of software immediately after freezing the requirement in SDLC process. The proposed complexity measure compares well with established complexity measures. Finally the trend can be validated with the result of proposed measure. Ultimately, Requirement based complexity measure can be used to understand the complexity of proposed software much before the actual implementation of design thus saving on cost and manpower wastage.
Normalization at the field level: fractional counting of citations
Venue: arXiv cs.DL 2010
Year: 2010

Van Raan et al. (2010; arXiv:1003.2113) have proposed a new indicator (MNCS) for field normalization. Since field normalization is also used in the Leiden Rankings of universities, we elaborate our critique of journal normalization in Opthof & Leydesdorff (2010; arXiv:1002.2769) in this rejoinder concerning field normalization. Fractional citation counting thoroughly solves the issue of normalization for differences in citation behavior among fields. This indicator can also be used to obtain a normalized impact factor.
Instantiation of SMT problems modulo Integers
Venue: arXiv cs.LO 2010
Year: 2010

Many decision procedures for SMT problems rely more or less implicitly on an instantiation of the axioms of the theories under consideration, and differ by making use of the additional properties of each theory, in order to increase efficiency. We present a new technique for devising complete instantiation schemes on SMT problems over a combination of linear arithmetic with another theory T. The method consists in first instantiating the arithmetic part of the formula, and then getting rid of the remaining variables in the problem by using an instantiation strategy which is complete for T. We provide examples evidencing that not only is this technique generic (in the sense that it applies to a wide range of theories) but it is also efficient, even compared to state-of-the-art instantiation schemes for specific theories.
Identifying Shapes Using Self-Assembly (extended abstract)
Venue: arXiv cs.CC 2010
Year: 2010

In this paper, we introduce the following problem in the theory of algorithmic self-assembly: given an input shape as the seed of a tile-based self-assembly system, design a finite tile set that can, in some sense, uniquely identify whether or not the given input shape--drawn from a very general class of shapes--matches a particular target shape. We first study the complexity of correctly identifying squares. Then we investigate the complexity associated with the identification of a considerably more general class of non-square, hole-free shapes.
Sequences, Bent Functions and Jacobsthal sums
Venue: arXiv cs.DM 2010
Year: 2010

The $p$-ary function $f(x)$ mapping $\mathrm{GF}(p^{4k})$ to $\mathrm{GF}(p)$ and given by $f(x)={\rm Tr}_{4k}\big(ax^d+bx^2\big)$ with $a,b\in\mathrm{GF}(p^{4k})$ and $d=p^{3k}+p^{2k}-p^k+1$ is studied with the respect to its exponential sum. In the case when either $a^{p^k(p^k+1)}\neq b^{p^k+1}$ or $a^2=b^d$ with $b\neq 0$, this sum is shown to be three-valued and the values are determined. For the remaining cases, the value of the exponential sum is expressed using Jacobsthal sums of order $p^k+1$. Finding the values and the distribution of those sums is a long-lasting open problem.
MIMO Detection Algorithms for High Data Rate Wireless Transmission
Venue: arXiv cs.OH 2010
Year: 2010

Motivated by MIMO broad-band fading channel model, in this section a comparative study is presented regarding various uncoded adaptive and non-adaptive MIMO detection algorithms with respect to BER/PER performance, and hardware complexity. All the simulations are conducted within MIMO-OFDM framework and with a packet structure similar to that of IEEE 802.11a/g standard. As the comparison results show, the RLS algorithm appears to be an affordable solution for wideband MIMO system targeting at Giga-bit wireless transmission. So MIMO can overcome huge processing power required for MIMO detection by using optimizing channel coding and MIMO detection.
Normalized Information Distance is Not Semicomputable
Venue: arXiv cs.CC 2010
Year: 2010

Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of the file involved, using a real-world compression program. This practical application is called 'normalized compression distance' and it is trivially computable. It is a parameter-free similarity measure based on compression, and is used in pattern recognition, data mining, phylogeny, clustering, and classification. The complexity properties of its theoretical precursor, the NID, have been open. We show that the NID is neither upper semicomputable nor lower semicomputable.
New modelling technique for aperiodic-sampling linear systems
Venue: arXiv cs.DM 2010
Year: 2010

A general input-output modelling technique for aperiodic-sampling linear systems has been developed. The procedure describes the dynamics of the system and includes the sequence of sampling periods among the variables to be handled. Some restrictive conditions on the sampling sequence are imposed in order to guarantee the validity of the model. The particularization to the periodic case represents an alternative to the classic methods of discretization of continuous systems without using the Z-transform. This kind of representation can be used largely for identification and control purposes.
An upper bound on the number of states for a strongly universal hyperbolic cellular automaton on the pentagrid
Venue: arXiv cs.FL 2010
Year: 2010

In this paper, following the way opened by a previous paper deposited on arXiv, we give an upper bound to the number of states for a hyperbolic cellular automaton in the pentagrid. Indeed, we prove that there is a hyperbolic cellular automaton which is rotation invariant and whose halting problem is undecidable and which has 9~states.
Hosting Byzantine Fault Tolerant Services on a Chord Ring
Venue: arXiv cs.DC 2010
Year: 2010

In this paper we demonstrate how stateful Byzantine Fault Tolerant services may be hosted on a Chord ring. The strategy presented is fourfold: firstly a replication scheme that dissociates the maintenance of replicated service state from ring recovery is developed. Secondly, clients of the ring based services are made replication aware. Thirdly, a consensus protocol is introduced that supports the serialization of updates. Finally Byzantine fault tolerant replication protocols are developed that ensure the integrity of service data hosted on the ring.
Action Recognition in Videos: from Motion Capture Labs to the Web
Venue: arXiv cs.CV 2010
Year: 2010

This paper presents a survey of human action recognition approaches based on visual data recorded from a single video camera. We propose an organizing framework which puts in evidence the evolution of the area, with techniques moving from heavily constrained motion capture scenarios towards more challenging, realistic, "in the wild" videos. The proposed organization is based on the representation used as input for the recognition task, emphasizing the hypothesis assumed and thus, the constraints imposed on the type of video that each technique is able to address. Expliciting the hypothesis and constraints makes the framework particularly useful to select a method, given an application. Another advantage of the proposed organization is that it allows categorizing newest approaches seamlessly with traditional ones, while providing an insightful perspective of the evolution of the action recognition task up to now. That perspective is the basis for the discussion in the end of the paper, where we also present the main open issues in the area.
A Derandomized Sparse Johnson-Lindenstrauss Transform
Venue: arXiv cs.DS 2010
Year: 2010

Recent work of [Dasgupta-Kumar-Sarlos, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in our proof is improved. The main ingredient in our proof is a spectral moment bound for quadratic forms that was recently used in [Diakonikolas-Kane-Nelson, FOCS 2010].
Segmentation of Natural Images by Texture and Boundary Compression
Venue: arXiv cs.CV 2010
Year: 2010

We present a novel algorithm for segmentation of natural images that harnesses the principle of minimum description length (MDL). Our method is based on observations that a homogeneously textured region of a natural image can be well modeled by a Gaussian distribution and the region boundary can be effectively coded by an adaptive chain code. The optimal segmentation of an image is the one that gives the shortest coding length for encoding all textures and boundaries in the image, and is obtained via an agglomerative clustering process applied to a hierarchy of decreasing window sizes as multi-scale texture features. The optimal segmentation also provides an accurate estimate of the overall coding length and hence the true entropy of the image. We test our algorithm on the publicly available Berkeley Segmentation Dataset. It achieves state-of-the-art segmentation results compared to other existing methods.
Promoting Component Reuse by Separating Transmission Policy from Implementation
Venue: arXiv cs.DC 2010
Year: 2010

In this paper we present a methodology and set of tools which assist the construction of applications from components, by separating the issues of transmission policy from component definition and implementation. This promotes a greater degree of software reuse than is possible using traditional middleware environments. Whilst component technologies are usually presented as a mechanism for promoting reuse, reuse is often limited due to design choices that permeate component implementation. The programmer has no direct control over inter-address-space parameter passing semantics: it is fixed by the distributed application's structure, based on the remote accessibility of the components. Using traditional middleware tools and environments, the application designer may be forced to use an unnatural encoding of application level semantics since application parameter passing semantics are tightly coupled with the component deployment topology. This paper describes how inter-address-space parameter passing semantics may be decided independently of component implementation. Transmission policy may be dynamically defined on a per-class, per-method or per-parameter basis.
RAFDA: Middleware Supporting the Separation of Application Logic from Distribution Policy
Venue: arXiv cs.DC 2010
Year: 2010

Middleware technologies often limit the way in which object classes may be used in distributed applications due to the fixed distribution policies imposed by the Middleware system. These policies permeate the applications developed using them and force an unnatural encoding of application level semantics. For example, the application programmer has no direct control over inter-address-space parameter passing semantics since it is fixed by the application's distribution topology which is dictated early in the design cycle by the Middleware. This creates applications that are brittle with respect to changes in the way in which the applications are distributed. This paper explores technology permitting arbitrary objects in an application to be dynamically exposed for remote access. Using this, the application can be written without concern for its distribution with object placement and distribution boundaries decided late in the design cycle and even dynamically. Inter-address-space parameter passing semantics may also be decided independently of object implementation and at varying times in the design cycle, again, possibly as late as run-time. Furthermore, transmission policy may be defined on a per-class, per-method or per-parameter basis maximizing plasticity. This flexibility is of utility in the development of new distributed applications and the creation of management and monitoring infrastructures for existing applications.
A Study of Non-Neutral Networks with Usage-based Prices
Venue: arXiv cs.NI 2010
Year: 2010

Hahn and Wallsten wrote that network neutrality "usually means that broadband service providers charge consumers only once for Internet access, do not favor one content provider over another, and do not charge content providers for sending information over broadband lines to end users." In this paper we study the implications of non-neutral behaviors under a simple model of linear demand-response to usage-based prices. We take into account advertising revenues and consider both cooperative and non-cooperative scenarios. In particular, we model the impact of side-payments between service and content providers. We also consider the effect of service discrimination by access providers, as well as an extension of our model to non-monopolistic content providers.
Increasing the Reliability of Adaptive Quadrature Using Explicit Interpolants
Venue: arXiv cs.NA 2010
Year: 2010

We present two new adaptive quadrature routines. Both routines differ from previously published algorithms in many aspects, most significantly in how they represent the integrand, how they treat non-numerical values of the integrand, how they deal with improper divergent integrals and how they estimate the integration error. The main focus of these improvements is to increase the reliability of the algorithms without significantly impacting their efficiency. Both algorithms are implemented in Matlab and tested using both the "families" suggested by Lyness and Kaganove and the battery test used by Gander and Gautschi and Kahaner. They are shown to be more reliable, albeit in some cases less efficient, than other commonly-used adaptive integrators.