Most cyber security research is focused on detecting network intrusions or anomalies through the use of automated methods, exploratory visual analytics systems, or real-time monitoring using dynamic visual representations. However, there has been minimal investigation of effective decision support systems for cyber analysts. This paper describes the user-centered design and development of a decision support visualization for active network defense. Ocelot helps the cyber analyst assess threats to a network and quarantine affected computers from the healthy parts of a network. The described web-based, functional visualization prototype integrates and visualizes multiple data sources through the use of a hybrid space partitioning tree and node link diagram. We describe our design process for requirements gathering and design feedback which included expert interviews, iterative design, and a user study.

This article describes the resource- and system-building efforts of an 8-week Johns Hopkins University Human Language Technology Center of Excellence Summer Camp for Applied Language Exploration (SCALE-2009) on Semantically Informed Machine Translation (SIMT). We describe a new modality/negation (MN) annotation scheme, the creation of a (publicly available) MN lexicon, and two automated MN taggers that we built using the annotation scheme and lexicon. Our annotation scheme isolates three components of modality and negation: a trigger (a word that conveys modality or negation), a target (an action associated with modality or negation), and a holder (an experiencer of modality). We describe how our MN lexicon was semi-automatically produced and we demonstrate that a structure-based MN tagger results in precision around 86% (depending on genre) for tagging of a standard LDC data set. We apply our MN annotation scheme to statistical machine translation using a syntactic framework that supports the inclusion of semantic annotations. Syntactic tags enriched with semantic annotations are assigned to parse trees in the target-language training texts through a process of tree grafting. Although the focus of our work is modality and negation, the tree grafting procedure is general and supports other types of semantic information. We exploit this capability by including named entities, produced by a pre-existing tagger, in addition to the MN elements produced by the taggers described here. The resulting system significantly outperformed a linguistically naive baseline model (Hiero), and reached the highest scores yet reported on the NIST 2009 Urdu–English test set. This finding supports the hypothesis that both syntactic and semantic information can improve translation quality.

We propose a generic computational framework for maintaining a discrete geometric structure defined by a collection of static and mobile objects. We assume that the mobile objects move incrementally, that is, in discrete time steps. We assume that the structure to be maintained is a function of the current locations of the mobile and static objects (independent of their prior motion). Unlike other models for kinetic computation, we place no restrictions on the motion nor on its predictability. In order to handle unrestricted incremental motion, our framework is based on the coordination of two computational entities. The first is the incremental motion algorithm. It is responsible for maintaining the structure and a set of certificates, or conditions, that prove the structure’s correctness. The other entity, called the motion processor, is responsible for handling all the low-level aspects of motion, including computing and/or tracking the motion of the mobile objects, answering queries about their current positions and velocities, and validating that the object motions satisfy simple motion estimates, which are generated by the incremental motion algorithm. Computational efficiency is measured in terms of the number of interactions between these two entities.

Tagging algorithms have become increasingly important for identifying lexical and semantic features of unstructured text. We describe an approach to lattice-based tagging that estimates joint transition and emission probabilities using support vector machines. The technique offers several advantages over alternative methods, including the ability to accommodate non-local features, support for hundreds of thousands of features, and language-neutrality. We demonstrate the technique on two tagging applications: named entity recognition and part-of-speech tagging.

In k-means clustering we are given a set of n data points in d-dimensional space ℜd and an integer k, and the problem is to determine a set of k points in ℜd, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+ε)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-ε). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.

In k-means clustering, we are given a set of n data points in d-dimensional space R/sup d/ and an integer k and the problem is to determine a set of k points in Rd, called centers, so as to minimize the mean squared distance from each data point to its nearest center. A popular heuristic for k-means clustering is Lloyd's (1982) algorithm. We present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm. This algorithm is easy to implement, requiring a kd-tree as the only major data structure. We establish the practical efficiency of the filtering algorithm in two ways. First, we present a data-sensitive analysis of the algorithm's running time, which shows that the algorithm runs faster as the separation between clusters increases. Second, we present a number of empirical studies both on synthetically generated data and on real data sets from applications in color quantization, data compression, and image segmentation.

Computing discrete two-dimensional (2-D) convolutions is an important problem in image processing. In mathematical morphology, an important variant is that of computing binary convolutions, where the kernel of the convolution is a 0-1 valued function. This operation can be quite costly, especially when large kernels are involved. We present an algorithm for computing convolutions of this form, where the kernel of the binary convolution is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some flexibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satisfies certain reasonable requirements. We say that such a convolution is valid. Given this flexibility we show that it is possible to compute binary convolutions more efficiently than would normally be possible for large kernels. Our main result is an algorithm which, given an m x n image and a k-sided convex polygonal kernel K, computes a valid convolution in O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is independent of the area or perimeter of K, and our techniques do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's (1965) line-drawing algorithm and prefix-sums to update the convolution incrementally as the kernel is moved from one position to another across the image.

means clustering is a very popular clustering technique, which is used in numerous applications.Given a set of n data points in R d and an integer k, the problem is to determine a set of k points R d, called centers, so as to minimize the mean squared distance from each data point to its nearest center.A popular heuristic for k-means clustering is Lloyd's algorithm.In this paper we present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm.This algorithm is very easy to implement.It differs from most other approaches in that it precomputes a kd-tree data structure for the data points rather than the center points.We establish the practical efficiency of the filtering algorithm in two ways.First, we present a data-sensitive analysis of the algorithm's running time.Second, we have implemented the algorithm and performed a number of empirical studies, both on synthetically generated data and on real data from applications in color quantization, compression, and segmentation.

We present a tone reproduction operator that preserves visibility in high dynamic range scenes. Our method introduces a new histogram adjustment technique, based on the population of local adaptation luminances in a scene. To match subjective viewing experience, the method incorporates models for human contrast sensitivity, glare, spatial acuity, and color sensitivity. We compare our results to previous work and present examples of our techniques applied to lighting simulation and electronic photography.

The authors consider the problem of finding a shortest polygonal path from s to t within a simple polygon P, subject to the restriction that the path have at most k links (edges). They give an algorithm to compute a k-link path with length at most (1 + epsilon ) times the length of a shortest k-link path, for any error tolerance epsilon >0. The algorithm runs in time O(n/sup 3/k/sup 3/ log (Hk/ epsilon /sup 1/k/)), where N is the largest integer coordinate among the n vertices of P. They also study the more general problem of approximating shortest k-link paths in polygons with holes. In this case, they give an algorithm that returns a path with at most 2k links and length at most that of a shortest k-link path; the running time is O(kE/sup 2/), where E is the number of edges in the visibility graph. Finally, they study the bicriteria path problem in which the two criteria are link length and 'total turn' (the integral of mod Delta theta mod along a path). They obtain in an exact polynomial-time algorithm for polygons with holes.>