Cost analysis of object-oriented bytecode programs

Cost analysis statically approximates the cost of programs in terms of their input data size. This paper presents, to the best of our knowledge, the first approach to the automatic cost analysis of object-oriented bytecode programs. In languages such as Java and C#, analyzing bytecode has a much wider application area than analyzing source code since the latter is often not available. Cost analysis in this context has to consider, among others, dynamic dispatch, jumps, the operand stack, and the heap. Our method takes a bytecode program and a cost model specifying the resource of interest, and generates cost relations which approximate the execution cost of the program with respect to such resource. We report on COSTA, an implementation for Java bytecode which can obtain upper bounds on cost for a large class of programs and complexity classes. Our basic techniques can be directly applied to infer cost relations for other object-oriented imperative languages, not necessarily in bytecode form.     

Network intrusion detection: Evaluating cluster, discriminant, and logit analysis

This paper evaluates the statistical methodologies of cluster analysis, discriminant analysis, and Logit analysis used in the examination of intrusion detection data. The research is based on a sample of 1200 random observations for 42 variables of the KDD-99 database, that contains ‘normal’ and ‘bad’ connections. The results indicate that Logit analysis is more effective than cluster or discriminant analysis in intrusion detection. Specifically, according to the Kappa statistic that makes full use of all the information contained in a confusion matrix, Logit analysis (K = 0.629) has been ranked first, with second discriminant analysis (K = 0.583), and third cluster analysis (K = 0.460).     

Interactive minimax optimisation for integrated performance analysis and resource planning

Analysing performances for future improvement and resource planning is a key management function. Data Envelopment Analysis (DEA) provides an analytical mean for performance modelling without assuming parametric functions. Multiple Objective Optimisation (MOO) is well-suited for resource planning. This paper reports an investigation in exploring relationships between DEA and MOO models for equivalent efficiency analysis in a MOO process. It is shown that under certain conditions minimax reference point models are identical to input-oriented dual DEA models for performance assessment. The former can thus be used for Hybrid Efficiency and Trade-off Analyses (HETA). In this paper, these conditions are first established and the equivalent models are explored both analytically and graphically to better understand HETA. Further investigation in the equivalence models leads to the modification of efficiency measures and the development of a minimax reference point approach for supporting integrated performance analysis and resource planning, with the Decision Maker’s (DM) preferences taken into account in an interactive fashion. Both numerical and case studies are conducted to demonstrate the proposed approach and its potential applications.     

A method for the transformation of factors in factor analysis

A method is proposed for obtaining combinations of factors derived from a factor analysis characterized by a large number of near-zero loadings relative to the original variables. It differs from rotation of factors, which replaces r factors by an equal number, r, of differently oriented factors, in that each solution consists of a single direction in F variable space.     

SqFreeEVAL: An (almost) optimal real-root isolation algorithm

Let f be a univariate polynomial with real coefficients, f∈R[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the real roots of f in a given interval. In this paper, we consider a simple subdivision algorithm whose primitives are purely numerical (e.g., function evaluation). The complexity of this algorithm is adaptive because the algorithm makes decisions based on local data. The complexity analysis of adaptive algorithms (and this algorithm in particular) is a new challenge for computer science. In this paper, we compute the size of the subdivision tree for the SqFreeEVAL algorithm.The SqFreeEVAL algorithm is an evaluation-based numerical algorithm which is well-known in several communities. The algorithm itself is simple, but prior attempts to compute its complexity have proven to be quite technical and have yielded sub-optimal results. Our main result is a simple O(d(L+lnd)) bound on the size of the subdivision tree for the SqFreeEVAL algorithm on the benchmark problem of isolating all real roots of an integer polynomial f of degree d and whose coefficients can be written with at most L bits.Our proof uses two amortization-based techniques: first, we use the algebraic amortization technique of the standard Mahler-Davenport root bounds to interpret the integral in terms of d and L. Second, we use a continuous amortization technique based on an integral to bound the size of the subdivision tree. This paper is the first to use the novel analysis technique of continuous amortization to derive state of the art complexity bounds.     

VIRTUE: A visual tool for information retrieval performance evaluation and failure analysis

Objective: Information Retrieval (IR) is strongly rooted in experimentation where new and better ways to measure and interpret the behavior of a system are key to scientific advancement. This paper presents an innovative visualization environment: Visual Information Retrieval Tool for Upfront Evaluation (VIRTUE), which eases and makes more effective the experimental evaluation process.Methods: VIRTUE supports and improves performance analysis and failure analysis.Performance analysis: VIRTUE offers interactive visualizations based on well-known IR metrics allowing us to explore system performances and to easily grasp the main problems of the system.Failure analysis: VIRTUE develops visual features and interaction, allowing researchers and developers to easily spot critical regions of a ranking and grasp possible causes of a failure.Results: VIRTUE was validated through a user study involving IR experts. The study reports on (a) the scientific relevance and innovation and (b) the comprehensibility and efficacy of the visualizations.Conclusion: VIRTUE eases the interaction with experimental results, supports users in the evaluation process and reduces the user effort.Practice: VIRTUE will be used by IR analysts to analyze and understand experimental results.Implications: VIRTUE improves the state-of-the-art in the evaluation practice and integrates visualization and IR research fields in an innovative way.     

Approximate levels of significance for the cos θ coefficient

A table has been derived for the probability P(θ, n) of observing an angle θ between two unit vectors distributed at random in n-space (n > 2). This may be used to obtain approximate levels of significance for the pairwise values in a cos θ similarity matrix. An example is given of its application.     

New lower bounds for online k-server routing problems

In a k-server routing problem k?1 servers move in a metric space in order to visit specified points or carry objects from sources to destinations. In the online version requests arrive online while the servers are traveling. Two classical objective functions are to minimize the makespan, i.e., the time when the last server has completed its tour (k-Traveling Salesman Problem or k-tsp) and to minimize the sum of completion times (k-Traveling Repairman Problem or k-trp). Both problems, the k-tsp and the k-trp have been studied from a competitive analysis point of view, where the cost of an online algorithm is compared to that of an optimal offline algorithm. However, the gap between the obtained competitive ratios and the corresponding lower bounds have mostly been quite large for k>1, in particular for randomized algorithms against an oblivious adversary.We reduce a number of gaps by providing new lower bounds for randomized algorithms. The most dramatic improvement is in the lower bound for the k-Dial-a-Ride-Problem (the k-trp when objects need to be carried) from to 3 which is currently also the best lower bound for deterministic algorithms.     

Runtime analysis of a binary particle swarm optimizer

We investigate the runtime of a binary Particle Swarm Optimizer (PSO) for optimizing pseudo-Boolean functions f:{0,1}ⁿ→R. The binary PSO maintains a swarm of particles searching for good solutions. Each particle consists of a current position from {0,1}ⁿ, its own best position and a velocity vector used in a probabilistic process to update its current position. The velocities for a particle are then updated in the direction of its own best position and the position of the best particle in the swarm.We present a lower bound for the time needed to optimize any pseudo-Boolean function with a unique optimum. To prove upper bounds we transfer a fitness-level argument that is well-established for evolutionary algorithms (EAs) to PSO. This method is applied to estimate the expected runtime for the class of unimodal functions. A simple variant of the binary PSO is considered in more detail for the test function OneMax, showing that there the binary PSO is competitive to EAs. An additional experimental comparison reveals further insights.     

A faster solution to the horizon problem

An algorithm is developed for calculating the horizons for each point in a digital terrain grid in order N iterations, whereas all previous methods seem to be of O(N²) time complexity. The new method makes horizon computations reasonable, and ought to improve the accuracy of surface climate models in rugged terrain.     

Computing the subset partial order for dense families of sets

We give an algorithm to compute the subset partial order (called the subset graph) for a family F of sets containing k sets with N elements in total and domain size n. Our algorithm requires O(nk²/logk) time and space on a Pointer Machine. When F is dense, i.e. N=Θ(nk), the algorithm requires O(N²/log²N) time and space. We give a construction for a dense family whose subset graph is of size Θ(N²/log²N), indicating the optimality of our algorithm for dense families. The subset graph can be dynamically maintained when F undergoes set insertions and deletions in O(nk/logk) time per update (that is sub-linear in N for the case of dense families). If we assume words of b?k bits, allow bits to be packed in words, and use bitwise operations, the above running time and space requirements can be reduced by a factor of blog(k/b+1)/logk and b²log(k/b+1)/logk respectively.     

Speech-acts based analysis for requirements discovery from online discussions

Online discussions about software applications and services that take place on web-based communication platforms represent an invaluable knowledge source for diverse software engineering tasks, including requirements elicitation. The amount of research work on developing effective tool-supported analysis methods is rapidly increasing, as part of the so called software analytics. Textual messages in App store reviews, tweets, online discussions taking place in mailing lists and user forums, are processed by combining natural language techniques to filter out irrelevant data; text mining and machine learning algorithms to classify messages into different categories, such as bug report and feature request.Our research objective is to exploit a linguistic technique based on speech-acts for the analysis of online discussions with the ultimate goal of discovering requirements-relevant information. In this paper, we present a revised and extended version of the speech-acts based analysis technique, which we previously presented at CAiSE 2017, together with a detailed experimental characterisation of its properties. Datasets used in the experimental evaluation are taken from a widely used open source software project (161120 textual comments), as well as from an industrial project in the home energy management domain. We make them available for experiment replication purposes. On these datasets, our approach is able to successfully classify messages into Feature/Enhancement and Other, with F-measure of 0.81 and 0.84 respectively. We also found evidence that there is an association between types of speech-acts and categories of issues, and that there is correlation between some of the speech-acts and issue priority, thus motivating further research on the exploitation of our speech-acts based analysis technique in semi-automated multi-criteria requirements prioritisation.     

On guaranteed parameter estimation of a multiparameter linear regression process

This paper presents a sequential estimation procedure for the unknown parameters of a continuous-time stochastic linear regression process. As an example, the sequential estimation problem of two dynamic parameters in stochastic linear systems with memory and in autoregressive processes is solved. The estimation procedure is based on the least squares method with weights and yields estimators with guaranteed accuracy in the sense of the L_q-norm for fixed q≥2.The proposed procedure works in the mentioned examples for all possible values of unknown dynamic parameters on the plane R² for the autoregressive processes and on the plane R² with the exception of some lines for the linear stochastic delay equations. The asymptotic behaviour of the duration of observations is determined.The general estimation procedure is designed for two or more parametric models. It is shown that the proposed procedure can be applied to the sequential parameter estimation problem of affine stochastic delay differential equations and autoregressive processes of an arbitrary order.     

Inapproximability of maximal strip recovery

In comparative genomics, the first step of sequence analysis is usually to decompose two or more genomes into syntenic blocks that are segments of homologous chromosomes. For the reliable recovery of syntenic blocks, noise and ambiguities in the genomic maps need to be removed first. Maximal Strip Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff for reliably recovering syntenic blocks from genomic maps in the midst of noise and ambiguities. Given d genomic maps as sequences of gene markers, the objective of MSR-d is to find d subsequences, one subsequence of each genomic map, such that the total length of syntenic blocks in these subsequences is maximized. For any constant d≥2, a polynomial-time 2d-approximation for MSR-d was previously known. In this paper, we show that for any d≥2, MSR-d is APX-hard, even for the most basic version of the problem in which all gene markers are distinct and appear in positive orientation in each genomic map. Moreover, we provide the first explicit lower bounds on approximating MSR-d for all d≥2. In particular, we show that MSR-d is NP-hard to approximate within Ω(d/logd). From the other direction, we show that the previous 2d-approximation for MSR-d can be optimized into a polynomial-time algorithm even if d is not a constant but is part of the input. We then extend our inapproximability results to several related problems including CMSR-d, δ-gap-MSR-d, and δ-gap-CMSR-d.     

Process pattern construction and multi-mode monitoring

A novel framework for process pattern construction and multi-mode monitoring is proposed. To identify process patterns, the framework utilizes a clustering method that consists of an ensemble moving window strategy along with an ensemble clustering solutions strategy. A new k-independent component analysis-principal component analysis (k-ICA-PCA) modeling method captures the relevant process patterns in corresponding clusters and facilitates the validation of ensemble solutions. Following pattern construction, the proposed framework offers an adjoined multi-ICA-PCA model for detection of faults under multiple operating modes. The Tennessee Eastman (TE) benchmark process is used as a case study to demonstrate the salient features of the method. Specifically, the proposed method is shown to have superior performance compared to the previously reported k-PCA models clustering approach.     

Variability and classification of remote sensing reflectance spectra in the eastern English Channel and southern North Sea

During spring and summer 2004, intensive field bio-optical campaigns were conducted in the eastern English Channel and southern North Sea to assess the mechanisms regulating the ocean color variability in a complex coastal environment. The bio-optical properties of the sampled waters span a wide range of variability, due to the various biogeochemical and physical processes occurring in this area. In-water hyperspectral remote sensing reflectances (R_rs) were acquired simultaneously with measurements of optically significant parameters at 93 stations. An empirical orthogonal function (EOF) analysis indicates that 74% of the total variance of R_rs is partly explained by particulate backscattering (b_bp), while particulate and dissolved absorption only explain 15% of the ocean color variability. These results confirm, for the first time from in situ backscattering measurements, previous studies performed in other coastal environments. Whereas the amplitude factors of the first EOF mode are well correlated (r = 0.75) with the particulate backscattering coefficient (b_bp), the highest correlation (r = 0.83) is found with the particulate backscattering ratio (b_bp/b_p). This result highlights the fundamental role of the nature of the bulk particulate assemblage in the ocean color variability.An unsupervised hierarchical cluster analysis applied to our data set of normalized R_rs spectra, leads to five spectrally distinct classes. We show that the class-specific mean R_rs spectra significantly differ from one another by their bio-optical properties. Three classes particularly stand out: one class corresponds to a Phaeocystis globosa bloom situation, whereas the two others are associated with water masses dominated by mineral and non-living particles, respectively. Among the different bio-optical parameters, the particulate backscattering ratio, the chlorophyll concentration, and the particulate organic carbon to chlorophyll ratio, are the most class-specific ones. These different results are very encouraging for the inversion of bio-optical parameters from class-specific algorithms.     

Worst-case properties of the uniform distribution and randomized algorithms for robustness analysis

In this paper we study aprobabilistic approach which is an alternative to the classical worst-case algorithms for robustness analysis and design of uncertain control systems. That is, we aim to estimate the probability that a control system with uncertain parametersq restricted to a boxQ attains a given level of performance γ. Since this probability depends on the underlying distribution, we address the following question: What is a “reasonable” distribution so that the estimated probability makes sense? To answer this question, we define two worstcase criteria and prove that the uniform distribution is optimal in both cases. In the second part of the paper we turn our attention to a subsequent problem. That is, we estimate the sizes of both the so-called “good” and “bad” sets via sampling. Roughly speaking, the good set contains the parametersq∈Q with a performance level better than or equal to γ while the bad set is the set of parametersq∈Q with a performance level worse than γ. We give bounds on the minimum sample size to attain a good estimate of these sets in a certain probabilistic sense.     

A test for multidimensional clustering tendency

This paper examines a d-dimensional extension of the Cox-Lewis statistic and investigates its power as a function of dimensionality in discriminating among random, aggregated and regular arrangements of points in d-dimensions. It was motivated by the Clustering Tendency problem which attempts to prevent the inappropriate application of clustering algorithms and other exploratory procedures. After reviewing the literature, the d-dimensional Cox-Lewis statistic is defined and its distribution under a randomness hypothesis of a Poisson spatial point process is given. Analytical expressions for the densities of the Cox-Lewis statistic under lattice regularity and under extreme clustering are also provided. The powers of Neyman-Pearson tests of hypotheses based on the Cox-Lewis statistic are derived and compared. Power is a unimodal function of dimensionality in the test of lattice regularity, with the minimum occurring at 12 dimensions.The power of the Cox-Lewis statistic is also examined under hard-core regularity and under Neyman-Scott clustering with Monte Carlo simulations. The Cox-Lewis statistic leads to one-sided tests for regularity having reasonable power and provides a sharper discrimination between random and clustered data than other statistics. The choice of sampling window is a critical factor. The Cox-Lewis statistic shows great promise for assessing the gross structure of data.