Maranello: practical partial packet recovery for 802.11 - Han,Bo; Schulman,Aaron; Gringoli,Francesco; Spring, Neil; Bhattacharjee, Bobby; Nava,Lorenzo; Ji,Lusheng; Lee,Seungjoon; Miller,Robert (Proceedings of the 7th USENIX conference on Networked systems design and implementation, 2010)
Partial packet recovery protocols attempt to repair corrupted packets instead of retransmitting them in their entirety. Recent approaches have used physical layer confidence estimates or additional error detection codes embedded in each transmission to identify corrupt bits, or have applied forward error correction to repair without such explicit knowledge. In contrast to these approaches, our goal is a practical design that simultaneously: (a) requires no extra bits in correct packets, (b) reduces recovery latency, except in rare instances, (c) remains compatible with existing 802.11 devices by obeying timing and backoff standards, and (d) can be incrementally deployed on widely available access points and wireless cards. In this paper, we design, implement, and evaluate Maranello, a novel partial packet recovery mechanism for 802.11. In Maranello, the receiver computes checksums over blocks in corrupt packets and bundles these checksums into a negative acknowledgment sent when the sender expects to receive an acknowledgment. The sender then retransmits only those blocks for which the checksum is incorrect, and repeats this partial retransmission until it receives an acknowledgment. Successful transmissions are not burdened by additional bits and the receiver needs not infer which bits were corrupted. We implemented Maranello using OpenFWWF (open source firmware for Broadcom wireless cards) and deployed it in a small testbed. We compare Maranello to alternative recovery protocols using a trace-driven simulation and to 802.11 using a live implementation under various channel conditions. To our knowledge, Maranello is the first partial packet recovery design to be implemented in commonly available firmware.

Measuring transitivity using untrained annotators - Madnani,Nitin; Jordan Boyd-Graber; Resnik, Philip (Proceedings of the NAACL HLT 2010 Workshop on Creating Speech and Language Data with Amazon's Mechanical Turk, 2010)
Hopper and Thompson (1980) defined a multi-axis theory of transitivity that goes beyond simple syntactic transitivity and captures how much "action" takes place in a sentence. Detecting these features requires a deep understanding of lexical semantics and real-world pragmatics. We propose two general approaches for creating a corpus of sentences labeled with respect to the Hopper-Thompson transitivity schema using Amazon Mechanical Turk. Both approaches assume no existing resources and incorporate all necessary annotation into a single system; this is done to allow for future generalization to other languages. The first task attempts to use language-neutral videos to elicit human-composed sentences with specified transitivity attributes. The second task uses an iterative process to first label the actors and objects in sentences and then annotate the sentences' transitivity. We examine the success of these techniques and perform a preliminary classification of the transitivity of held-out data.

Method for concealing data in curves of an image - M. Wu; Gou,Hongmei (2010)
A method of concealing data in images imperceptibly alters curves therein, such as through adding a value representing the data to be hidden to each of a number of B-spline control points representing the original curve. The altered control points characterize the imperceptibly altered curve, which replaces the original curve in the image. The altered control points may be later extracted from the image and compared with the original control points to determine the hidden value. Prudent selection of the values altering the control points as well as an iterative alignment-minimization algorithm in the detection process provides protection against numerous techniques for preventing the hidden values from being recovered.

Method for fingerprinting multimedia content - He,Shan; M. Wu (2010)
To identify participants in collusion directed to altering a digital fingerprint embedded in multimedia content, an ECC based fingerprinting technique establishes a code symbol for each of a plurality of segments of digital data forming the multimedia content. The code symbols are concatenated to form a fingerprint signal, which is subdivided into a plurality of subsegments for each segment in the digital data. The subsegments are permuted and embedded into the digital data. When a suspicious copy of the multimedia content is discovered, the permuted fingerprint signal is extracted from the content and inversely permuted to form a test fingerprint. The identity of one of the colluders is determined by correlation with characteristics of the codeword originally assigned to the user. The determination of identity may be enhanced by the addition of group data embedded as an additional fingerprint in the digital data. Joint consideration of coding and embedding provide benefits over...

Method for measurement of head related transfer functions - Duraiswami, Ramani; Gumerov, Nail A. (2010)
Head Related Transfer Functions (HRTFs) of an individual are measured in rapid fashion in an arrangement where a sound source is positioned in the individual's ear channel, while microphones are arranged in the microphone array enveloping the individual's head. The pressure waves generated by the sounds emanating from the sound source reach the microphones and are converted into corresponding electrical signals which are further processed in a processing system to extract HRTFs, which may then be used to synthesize a spatial audio scene. The acoustic field generated by the sounds from the sound source can be evaluated at any desired point inside or outside the microphone array.

Modeling and generalization of discrete Morse terrain decompositions - De Floriani, Leila; Magillo,P.; Vitali,M. (Proc. 20th Int. Conf. on Pattern Recognition, ICPR, 2010)
We address the problem of morphological analysis ofreal terrains. We describe a morphological model for a terrain by considering extensions of Morse theory to the discrete case. We propose a two-level model of the morphology of a terrain based on a graph joining the critical points of the terrain through integral lines. We present a new set of generalization operators specific for discrete piece-wise linear terrain models, which are used to reduce noise and the size of the morphological representation. We show results of our approach on real terrains.

Modelling Type 1a Supernova Light Curves - Rust,Bert W.; O'Leary, Dianne P.; Mullen,Katharine M. (Exponential Data Fitting and Its ApplicationsExponential Data Fitting and Its Applications, 2010)

Multiresolution analysis of 3D images based on discrete distortion - Weiss,K.; De Floriani, Leila; Mesmoudi,M. M. (International Conference on Pattern Recognition (ICPR), 2010)
We consider a model of a 3D image obtained bydiscretizing it into a multiresolution tetrahedral mesh known as a hierarchy of diamonds. This model enables us to extract crack-free approximations of the 3D image at any uniform or variable resolution, thus reducing the size of the data set without reducing the accuracy. A 3D intensity image is a scalar field (the intensity field) defined at the vertices of a 3D regular grid and thus the graph of the image is a hypersurface in R4. We measure the discrete distortion, a generalization of the notion of curvature, of the transformation which maps the tetrahedralized 3D grid onto its graph in R4. We evaluate the use of a hierarchy of diamonds to analyze properties of a 3D image, such as its discrete distortion, directly on lower resolution approximations. Our results indicate that distortion-guided extractions focus the resolution of approximated images on the salient features of the intensity image.

Multiresolution morse triangulations - Danovaro,Emanuele; De Floriani, Leila; Magillo,Paola; Vitali,Maria (Proceedings of the 14th ACM Symposium on Solid and Physical Modeling, 2010)
We address the problem of representing the geometry and the morphology of a triangulated surface endowed with a scalar field in a combined geometric and topological multiresolution model. The model, called a Multiresolution Morse Triangulation (MMT), is composed of a multiresolution triangle mesh, and of a multiresolution Morse complex describing the morphology of the field. The MMT is built through a combined morphological and geometrical generalization, and supports queries to extract consistent geometrical and morphological representations of the field at both uniform and variable resolutions.

New Approaches to Robust, Point-Based Image Registration - Mount, Dave; Netanyahu,N. S; Ratanasanya,S. (Image Registration for Remote SensingImage Registration for Remote Sensing, 2010)
We consider various algorithmic solutions to image registration based on thealignment of a set of feature points. We present a number of enhancements to a branch-and-bound algorithm introduced by Mount, Netanyahu, and Le Moigne (Pattern Recognition, Vol. 32, 1999, pp. 17–38), which presented a registration algorithm based on the partial Hausdorff distance. Our enhance- ments include a new distance measure, the discrete Gaussian mismatch, and a number of improvements and extensions to the above search algorithm. Both distance measures are robust to the presence of outliers, that is, data points from either set that do not match any point of the other set. We present experimental studies, which show that the new distance measure considered can provide significant improvements over the partial Hausdorff distance in instances where the number of outliers is not known in advance. These experiments also show that our other algorithmic improvements can offer tangible improvements. We demonstrate the algorithm’s efficacy by considering images involving different sensors and different spectral bands, both in a traditional framework and in a multiresolution framework.

Object Dependent Manifold Priors for Image Deconvolution - Ni,Jie; Turaga,Pavan; M.Patel,Vishal; Chellapa, Rama (Digital Image Processing and Analysis, 2010)
In this paper we propose a manifold based deconvolution algorithm by estimating a manifold from a set of natural images that exploits the availability of the sample class data for regularizing the deblurring problem.
Keywords: Deconvolution; IMAGE PROCESSING; Inverse problems

Optimal Authenticated Data Structures with Multilinear Forms - Charalampos Papamanthou; Tamassia, Roberto; Triandopoulos, Nikos (Pairing-Based Cryptography - Pairing 2010, 2010)
Cloud computing and cloud storage are becoming increasingly prevalent. In this paradigm, clients outsource their data and computations to third-party service providers. Data integrity in the cloud therefore becomes an important factor for the functionality of these web services.Authenticated data structures, implemented with various cryptographic primitives, have been widely studied as a means of providing efficient solutions to data integrity problems (e.g., Merkle trees). In this paper, we introduce a new authenticated dictionary data structure that employs multilinear forms, a cryptographic primitive proposed by Silverberg and Boneh in 2003 [10], the construction of which, however, remains an open problem to date. Our authenticated dictionary is optimal, that is, it does not add any extra asymptotic cost to the plain dictionary data structure, yielding proofs of constant size, i.e., asymptotically equal to the size of the answer, while maintaining other relevant complexities logarithmic. Instead, solutions based on cryptographic hashing (e.g., Merkle trees) require proofs of logarithmic size [40]. Because multilinear forms are not known to exist yet, our result can be viewed from a different angle: if one could prove that optimal authenticated dictionaries cannot exist in the computational model, irrespectively of cryptographic primitives, then our solution would imply that cryptographically interesting multilinear form generators cannot exist as well (i.e., it can be viewed as a reduction). Thus, we provide an alternative avenue towards proving the nonexistence of multilinear form generators in the context of general lower bounds for authenticated data structures [40] and for memory checking [18], a model similar to the authenticated data structures model.
Keywords: Algorithm Analysis and Problem Complexity; authenticated dictionary; Coding and Information Theory; Computer Communication Networks; Data Encryption; Discrete Mathematics in Computer Science; multilinear forms; Systems and Data Security

PADS: A Probabilistic Activity Detection Framework for Video Data - Albanese, M.; Chellapa, Rama; Cuntoor, N.; Moscato, V.; Picariello, A.; V.S. Subrahmanian; Udrea,O. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2010)
There is now a growing need to identify various kinds of activities that occur in videos. In this paper, we first present a logical language called Probabilistic Activity Description Language (PADL) in which users can specify activities of interest. We then develop a probabilistic framework which assigns to any subvideo of a given video sequence a probability that the subvideo contains the given activity, and we finally develop two fast algorithms to detect activities within this framework. OffPad finds all minimal segments of a video that contain a given activity with a probability exceeding a given threshold. In contrast, the OnPad algorithm examines a video during playout (rather than afterwards as OffPad does) and computes the probability that a given activity is occurring (even if the activity is only partially complete). Our prototype Probabilistic Activity Detection System (PADS) implements the framework and the two algorithms, building on top of existing image processing algorithms. We have conducted detailed experiments and compared our approach to four different approaches presented in the literature. We show that-for complex activity definitions-our approach outperforms all the other approaches.
Keywords: Automated; Programming Languages; Video Recording; Computer-Assisted; Models; PADL; PADS; image processing algorithms; offPad algorithm; onPad algorithm; probabilistic activity description language; probabilistic activity detection framework; video data; video sequence; image sequences; object detection; probability; video surveillance; Algorit; Statistical; Movement; Pattern Recognition

Probabilistic similarity logic - Bröcheler,M.; Mihalkova,L.; Getoor, Lise (Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2010)
Many machine learning applications require theability to learn from and reason about noisy multi-relational data. To address this, several ef- fective representations have been developed that provide both a language for expressing the struc- tural regularities of a domain, and principled sup- port for probabilistic inference. In addition to these two aspects, however, many applications also involve a third aspect–the need to reason about similarities–which has not been directly supported in existing frameworks. This paper introduces probabilistic similarity logic (PSL), a general-purpose framework for joint reason- ing about similarity in relational domains that incorporates probabilistic reasoning about sim- ilarities and relational structure in a principled way. PSL can integrate any existing domain- specific similarity measures and also supports reasoning about similarities between sets of en- tities. We provide efficient inference and learn- ing techniques for PSL and demonstrate its ef- fectiveness both in common relational tasks and in settings that require reasoning about similarity.

Pushdown Control-Flow Analysis of Higher-Order Programs - Earl, Christopher; Might, Matthew; David Van Horn (arXiv:1007.4268 [cs], 2010)
Context-free approaches to static analysis gain precision over classical approaches by perfectly matching returns to call sites---a property that eliminates spurious interprocedural paths. Vardoulakis and Shivers's recent formulation of CFA2 showed that it is possible (if expensive) to apply context-free methods to higher-order languages and gain the same boost in precision achieved over first-order programs. To this young body of work on context-free analysis of higher-order programs, we contribute a pushdown control-flow analysis framework, which we derive as an abstract interpretation of a CESK machine with an unbounded stack. One instantiation of this framework marks the first polyvariant pushdown analysis of higher-order programs; another marks the first polynomial-time analysis. In the end, we arrive at a framework for control-flow analysis that can efficiently compute pushdown generalizations of classical control-flow analyses.
Keywords: Computer Science - Programming Languages; F.3.2; F.4.1

Putting the user in the loop: interactive Maximal Marginal Relevance for query-focused summarization - Jimmy Lin; Madnani,Nitin; Dorr, Bonnie J (Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2010)
This work represents an initial attempt to move beyond "single-shot" summarization to interactive summarization. We present an extension to the classic Maximal Marginal Relevance (MMR) algorithm that places a user "in the loop" to assist in candidate selection. Experiments in the complex interactive Question Answering (ciQA) task at TREC 2007 show that interactively-constructed responses are significantly higher in quality than automatically-generated ones. This novel algorithm provides a starting point for future work on interactive summarization.

Ranking under temporal constraints - Wang,Lidan; Metzler,Donald; Jimmy Lin (Proceedings of the 19th ACM international conference on Information and knowledge management, 2010)
This paper introduces the notion of temporally constrained ranked retrieval, which, given a query and a time constraint, produces the best possible ranked list within the specified time limit. Naturally, more time should translate into better results, but the ranking algorithm should always produce some results. This property is desirable from a number of perspectives: to cope with diverse users and information needs, as well as to better manage system load and variance in query execution times. We propose two temporally constrained ranking algorithms based on a class of probabilistic prediction models that can naturally incorporate efficiency constraints: one that makes independent feature selection decisions, and the other that makes joint feature selection decisions. Experiments on three different test collections show that both ranking algorithms are able to satisfy imposed time constraints, although the joint model outperforms the independent model in being able to deliver more effective results, especially under tight time constraints, due to its ability to capture feature dependencies.
Keywords: efficiency; Learning to rank; Linear Models

Realistic Compression of Kinetic Sensor Data - Friedler,Sorelle A.; Mount, Dave (Department of Computer Science, University of Maryland, College Park, 2010)
We introduce a realistic analysis for a framework for storing andprocessing kinetic data observed by sensor networks. The massive data sets generated by these networks motivates a significant need for compression. We are interested in the kinetic data generated by a finite set of objects moving through space. Our previously introduced framework and accompanying compression algorithm assumed a given set of sensors, each of which continuously observes these moving objects in its surrounding region. The model relies purely on sensor observations; it allows points to move freely and requires no advance notification of motion plans. Here, we extend the initial theoretical analysis of this framework and compression scheme to a more realistic setting. We extend the current understanding of empirical entropy to introduce definitions for joint empirical entropy, conditional empirical entropy, and empirical independence. We also introduce a notion of limited independence between the outputs of the sensors in the system. We show that, even with this notion of limited independence and in both the statistical and empirical settings, the previously introduced compression algorithm achieves an encoding size on the order of the optimal.
Keywords: Technical Report

Repairing GUI Test Suites Using a Genetic Algorithm - Huang,Si; Cohen,M. B; Memon, Atif M. (Software Testing, Verification and Validation (ICST), 2010 Third International Conference on, 2010)
Recent advances in automated functional testing of Graphical User Interfaces (GUIs) rely on deriving graph models that approximate all possible sequences of events that may be executed on the GUI, and then use the graphs to generate test cases (event sequences) that achieve a specified coverage goal. However, because these models are only approximations of the actual event flows, the generated test cases may suffer from problems of infeasibility, i.e., some events may not be available for execution causing the test case to terminate prematurely. In this paper we develop a method to automatically repair GUI test suites, generating new test cases that are feasible. We use a genetic algorithm to evolve new test cases that increase our test suite's coverage while avoiding infeasible sequences. We experiment with this algorithm on a set of synthetic programs containing different types of constraints and for test sequences of varying lengths. Our results suggest that we can generate new test cases to cover most of the feasible coverage and that the genetic algorithm outperforms a random algorithm trying to achieve the same goal in almost all cases.
Keywords: automated functional testing; genetic algorithm; Genetic algorithms; graph model; graphical user interface; Graphical user interfaces; GUI test suite; program testing; random algorithm; synthetic program; test case

Resolving and Exploiting the k-CFA Paradox: Illuminating Functional vs. Object-oriented Program Analysis - Might, Matthew; Smaragdakis, Yannis; David Van Horn (PLDI '10 Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2010)
Low-level program analysis is a fundamental problem, taking the shape of "flow analysis" in functional languages and "points-to" analysis in imperative and object-oriented languages. Despite the similarities, the vocabulary and results in the two communities remain largely distinct, with limited cross-understanding. One of the few links is Shivers's k-CFA work, which has advanced the concept of "context-sensitive analysis" and is widely known in both communities. Recent results indicate that the relationship between the functional and object-oriented incarnations of k-CFA is not as well understood as thought. Van Horn and Mairson proved k-CFA for k ≥ 1 to be EXPTIME-complete; hence, no polynomial-time algorithm can exist. Yet, there are several polynomial-time formulations of context-sensitive points-to analyses in object-oriented languages. Thus, it seems that functional k-CFA may actually be a profoundly different analysis from object-oriented k-CFA. We resolve this paradox by showing that the exact same specification of k-CFA is polynomial-time for object-oriented languages yet exponential-time for functional ones: objects and closures are subtly different, in a way that interacts crucially with context-sensitivity and complexity. This illumination leads to an immediate payoff: by projecting the object-oriented treatment of objects onto closures, we derive a polynomial-time hierarchy of context-sensitive CFAs for functional programs.
Keywords: control-flow analysis; functional; k-cfa; m-cfa; object-oriented; pointer analysis; static analysis

Robust regression using sparse learning for high dimensional parameter estimation problems - Mitra, K.; Veeraraghavan,A.; Chellapa, Rama (Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on, 2010)
Algorithms such as Least Median of Squares (LMedS) and Random Sample Consensus (RANSAC) have been very successful for low-dimensional robust regression problems. However, the combinatorial nature of these algorithms makes them practically unusable for high-dimensional applications. In this paper, we introduce algorithms that have cubic time complexity in the dimension of the problem, which make them computationally efficient for high-dimensional problems. We formulate the robust regression problem by projecting the dependent variable onto the null space of the independent variables which receives significant contributions only from the outliers. We then identify the outliers using sparse representation/learning based algorithms. Under certain conditions, that follow from the theory of sparse representation, these polynomial algorithms can accurately solve the robust regression problem which is, in general, a combinatorial problem. We present experimental results that demonstrate the efficacy of the proposed algorithms. We also analyze the intrinsic parameter space of robust regression and identify an efficient and accurate class of algorithms for different operating conditions. An application to facial age estimation is presented.
Keywords: algorithm; random; analysis; combinatorial; complexity; least; complexity; parameter; consensus; robust; Estimation; estimation; polynomials; regression; learning; sparse; median; of; problem; cubic; problem; polynomial; problem; sparse; regression; representation; computational; sample; squares; parameter; TIME

Robust RVM regression using sparse outlier model - Mitra, K.; Veeraraghavan,A.; Chellapa, Rama (Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, 2010)
Kernel regression techniques such as Relevance Vector Machine (RVM) regression, Support Vector Regression and Gaussian processes are widely used for solving many computer vision problems such as age, head pose, 3D human pose and lighting estimation. However, the presence of outliers in the training dataset makes the estimates from these regression techniques unreliable. In this paper, we propose robust versions of the RVM regression that can handle outliers in the training dataset. We decompose the noise term in the RVM formulation into a (sparse) outlier noise term and a Gaussian noise term. We then estimate the outlier noise along with the model parameters. We present two approaches for solving this estimation problem: (1) a Bayesian approach, which essentially follows the RVM framework and (2) an optimization approach based on Basis Pursuit Denoising. In the Bayesian approach, the robust RVM problem essentially becomes a bigger RVM problem with the advantage that it can be solved efficiently by a fast algorithm. Empirical evaluations, and real experiments on image de-noising and age estimation demonstrate the better performance of the robust RVM algorithms over that of the RVM reg ression.
Keywords: 3D; analysis; approach; Gaussian; denoising; computer; denoising; lighting; denoising; regression; estimation; relevance; human; machine; robust; model; Gaussian; noise; basis; noise; computer; outlier; pose; Bayesian; pursuit; regression; sparse; RVM; vector; vision; image

Secure text processing with applications to private DNA matching - Katz, Jonathan; Malka,Lior (Proceedings of the 17th ACM conference on Computer and communications security, 2010)
Motivated by the problem of private DNA matching, we consider the design of efficient protocols for secure text processing. Here, informally, a party P1 holds a text T and a party P2 holds a pattern p and some additional information y, and P2 wants to learn {f(T,j,y)} for all locations j where p is found as a substring in T. (In particular, this generalizes the basic pattern matching problem.) We aim for protocols with full security against a malicious P2 that also preserve privacy against a malicious P1 (i.e., one-sided security). We show how to modify Yao's garbled circuit approach to obtain a protocol where the size of the garbled circuit is linear in the number of occurrences of p in T (rather than linear in $|T|$). Along the way we show a new keyword search protocol that may be of independent interest.
Keywords: COMPUTATION; secure

Self-assembly of neural networks viewed as swarm intelligence - Martin,C. E; Reggia, James A. (Swarm Intelligence, 2010)

Serializing C intermediate representations for efficient and portable parsing - Meister,Jeffrey A; Foster, Jeffrey S.; Hicks, Michael W. (Software: Practice and Experience, 2010)
C static analysis tools often use intermediate representations (IRs) that organize program data in a simple, well-structured manner. However, the C parsers that create IRs are slow, and because they are difficult to write, only a few implementations exist, limiting the languages in which a C static analysis can be written. To solve these problems, we investigate two language-independent, on-disk representations of C IRs: one using XML and the other using an Internet standard binary encoding called eXternal Data Representation (XDR). We benchmark the parsing speeds of both options, finding the XML to be about a factor of 2 slower than parsing C and the XDR over 6 times faster. Furthermore, we show that the XML files are far too large at 19 times the size of C source code, whereas XDR is only 2.2 times the C size. We also demonstrate the portability of our XDR system by presenting a C source code querying tool in Ruby. Our solution and the insights we gained from building it will be useful to analysis authors and other clients of C IRs. We have made our software freely available for download at http://www.cs.umd.edu/projects/PL/scil/. Copyright © 2010 John Wiley&Sons, Ltd.
Keywords: C; intermediate representations; parsing; static analysis; XDR; XML

Spatial indexing on tetrahedral meshes - De Floriani, Leila; Fellegara,Riccardo; Magillo,Paola (Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2010)
We address the problem of performing spatial queries on tetrahedral meshes. These latter arise in several application domains including 3D GIS, scientific visualization, finite element analysis. We have defined and implemented a family of spatial indexes, that we call tetrahedral trees. Tetrahedral trees subdivide a cubic domain containing the mesh in an octree or 3D kd-tree fashion, with three different subdivision criteria. Here, we present and compare such indexes, their memory usage, and spatial queries on them.
Keywords: kd-trees; octrees; spatial indexes; tetrahedral meshes

Spatio-temporal range searching over compressed kinetic sensor data - Friedler,S.; Mount, Dave (Algorithms–ESA 2010, 2010)
As sensor networks increase in size and number, efficient techniques are required to process the very large data sets that they generate. Frequently, sensor networks monitor objects in motion within their vicinity; the data associated with the movement of these objects are known as kinetic data. In an earlier paper we introduced an algorithm which, given a set of sensor observations, losslessly compresses this data to a size that is within a constant factor of the asymptotically optimal joint entropy bound. In this paper we present an efficient algorithm for answering spatio-temporal range queries. Our algorithm operates on a compressed representation of the data, without the need to decompress it. We analyze the efficiency of our algorithm in terms of a natural measure of information content, the joint entropy of the sensor outputs. We show that with space roughly equal to entropy, queries can be answered in time that is roughly logarithmic in entropy. In addition, we show experimentally that on real-world data our range searching structures use less space and have faster query times than the naive versions. These results represent the first solutions to range searching problems over compressed kinetic sensor data.

SPECIAL SECTION ON SHAPE ANALYSIS AND ITS APPLICATIONS IN IMAGE UNDERSTANDING - Srivastava, A.; Damon,J.N.; Dryden,I.L.; Jermyn,I.H.; Das,S.; Vaswani, N.; Huckemann,S.; Hotz,T.; Munk,A.; Lin,Z.; others (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010)

On Stability of Magnetization Dynamics in Nanoparticles - Mayergoyz, Issak D; Serpico,C.; Bertotti,G. (Magnetics, IEEE Transactions on, 2010)
It is rigorously demonstrated that spatially uniform magnetization oscillations in sufficiently small ellipsoidal nanoparticles can be unconditionally stable with respect to spatially nonuniform perturbations. The proof reveals the dominant stabilizing effect of exchange field which is mathematically manifested through the Poincare inequality.
Keywords: (electron); magnetic; DYNAMICS; ellipsoidal; field; magnetization; inequality; exchange; INTERACTIONS; magnetization; nanoparticles; spatially; nonuniform; oscillations; spin-wave; particles; magnetisation; nanoparticles; spin; perturbations; exchange; perturbations; spatially; Poincare; stability; small; uniform; waves

The state of visual analytics: Views on what visual analytics is and where it is going - May,R.; Hanrahan,P.; Keim,D. A; Shneiderman, Ben; Card,S. (2010 IEEE Symposium on Visual Analytics Science and Technology (VAST), 2010)
In the 2005 publication "Illuminating the Path" visual analytics was defined as "the science of analytical reasoning facilitated by interactive visual interfaces." A lot of work has been done in visual analytics over the intervening five years. While visual analytics started in the United States with a focus on security, it is now a worldwide research agenda with a broad range of application domains. This is evidenced by efforts like the European VisMaster program and the upcoming Visual Analytics and Knowledge Discovery (VAKD) workshop, just to name two.There are still questions concerning where and how visual analytics fits in the large body of research and applications represented by the VisWeek community. This panel will present distinct viewpoints on what visual analytics is and its role in understanding complex information in a complex world. The goal of this panel is to engender discussion from the audience on the emergence and continued advancement of visual analytics and its role relative to fields of related research. Four distinguished panelists will provide their perspective on visual analytics focusing on what it is, what it should be, and thoughts about a development path between these two states. The purpose of the presentations is not to give a critical review of the literature but rather to give a review on the field and to provide a contextual perspective based on the panelists' years of experience and accumulated knowledge.
Keywords: analytical reasoning; Data analysis; data mining; data visualisation; European VisMaster program; interactive visual interfaces; knowledge discovery; United States; visual analytics; VisWeek community

SwitchBlade: a platform for rapid deployment of network protocols on programmable hardware - Anwer,Muhammad Bilal; Motiwala,Murtaza; Bin Tariq,Mukarram; Feamster, Nick (SIGCOMM Comput. Commun. Rev., 2010)
We present SwitchBlade, a platform for rapidly deploying custom protocols on programmable hardware. SwitchBlade uses a pipeline-based design that allows individual hardware modules to be enabled or disabled on the fly, integrates software exception handling, and provides support for forwarding based on custom header fields. SwitchBlade's ease of programmability and wire-speed performance enables rapid prototyping of custom data-plane functions that can be directly deployed in a production network. SwitchBlade integrates common packet-processing functions as hardware modules, enabling different protocols to use these functions without having to resynthesize hardware. SwitchBlade's customizable forwarding engine supports both longest-prefix matching in the packet header and exact matching on a hash value. SwitchBlade's software exceptions can be invoked based on either packet or flow-based rules and updated quickly at runtime, thus making it easy to integrate more flexible forwarding function into the pipeline. SwitchBlade also allows multiple custom data planes to operate in parallel on the same physical hardware, while providing complete isolation for protocols running in parallel. We implemented SwitchBlade using NetFPGA board, but SwitchBlade can be implemented with any FPGA. To demonstrate SwitchBlade's flexibility, we use SwitchBlade to implement and evaluate a variety of custom network protocols: we present instances of IPv4, IPv6, Path Splicing, and an OpenFlow switch, all running in parallel while forwarding packets at line rate.
Keywords: netfpga; network virtualization

System and Method for Confidentiality-Preserving Rank-Ordered Search - Swaminathan,Ashwin; Mao,Yinian; Su,Guan-Ming; Gou,Hongmei; Varna,Avinash L.; He,Shan; M. Wu; Oard, Douglas (2010)
A confidentiality preserving system and method for performing a rank-ordered search and retrieval of contents of a data collection. The system includes at least one computer system including a search and retrieval algorithm using term frequency and/or similar features for rank-ordering selective contents of the data collection, and enabling secure retrieval of the selective contents based on the rank-order. The search and retrieval algorithm includes a baseline algorithm, a partially server oriented algorithm, and/or a fully server oriented algorithm. The partially and/or fully server oriented algorithms use homomorphic and/or order preserving encryption for enabling search capability from a user other than an owner of the contents of the data collection. The confidentiality preserving method includes using term frequency for rank-ordering selective contents of the data collection, and retrieving the selective contents based on the rank-order.

Tight lower bounds for halfspace range searching - Arya,Sunil; Mount, Dave; Xia,Jian (Proceedings of the 2010 annual symposium on Computational geometry, 2010)
We establish two new lower bounds for the halfspace range searching problem: Given a set of n points in ℜd, where each point is associated with a weight from a commutative semigroup, compute the semigroup sum of the weights of the points lying within any query halfspace. Letting $m$ denote the space requirements, we prove a lower bound for general semigroups of Ω(n1-1/(d+1)/m1/(d+1)) and for integral semigroups of Ω(n/m1/d). Our lower bounds are proved in the semigroup arithmetic model. Neglecting logarithmic factors, our result for integral semigroups matches the best known upper bound due to Matoušek. Our result for general semigroups improves upon the best known lower bound due to Brönnimann, Chazelle, and Pach. Moreover, Fonseca and Mount have recently shown that, given uniformly distributed points, halfspace range queries over idempotent semigroups can be answered in O(n1-1/(d+1)/m1/(d+1)) time in the semigroup arithmetic model. As our lower bounds are established for uniformly distributed point sets, it follows that they also resolve the computational complexity of halfspace range searching over idempotent semigroups in this important special case.
Keywords: Idempotence; lower bounds; Range searching

A unified approach to approximate proximity searching - Arya,S.; da Fonseca,G.; Mount, Dave (Algorithms–ESA 2010, 2010)

Using methods & measures from network analysis for gui testing - Elsaka,E.; Moustafa,W. E; Nguyen,Bao; Memon, Atif M. (Software Testing, Verification, and Validation Workshops (ICSTW), 2010 Third International Conference on, 2010)
Graphical user interfaces (GUIs) for today's applications are extremely large. Moreover, they provide many degrees of freedom to the end-user, thus allowing the user to perform a very large number of event sequences on the GUI. The large sizes and degrees of freedom create severe problems for GUI quality assurance, including GUI testing. In this paper, we leverage methods and measures from network analysis to analyze and study GUIs, with the goal of aiding GUI testing activities. We apply these methods and measures on the event-flow graph model of GUIs. Results of a case study show that "network centrality measures" are able to identify the most important events in the GUI as well as the most important sequences of events. These events and sequences are good candidates for test prioritization. In addition, the "betweenness clustering" method is able to partition the GUI into regions that can be tested separately.
Keywords: betweenness clustering method; event sequences; event-flow graph model; Graphical user interfaces; GUI quality assurance; GUI testing; network analysis; network centrality measures; program testing; Software quality

Using symbolic evaluation to understand behavior in configurable software systems - Reisner,E.; Song,C.; Ma,K.K.; Foster, Jeffrey S.; Porter, Adam (Software Engineering, 2010 ACM/IEEE 32nd International Conference on, 2010)

VizWiz: nearly real-time answers to visual questions - Bigham,Jeffrey P.; Jayant,Chandrika; Ji,Hanjie; Little,Greg; Miller,Andrew; Miller,Robert C.; Miller,Robin; Tatarowicz,Aubrey; White,Brandyn; White,Samual; Tom Yeh (Proceedings of the 23nd annual ACM symposium on User interface software and technology, 2010)
The lack of access to visual information like text labels, icons, and colors can cause frustration and decrease independence for blind people. Current access technology uses automatic approaches to address some problems in this space, but the technology is error-prone, limited in scope, and quite expensive. In this paper, we introduce VizWiz, a talking application for mobile phones that offers a new alternative to answering visual questions in nearly real-time - asking multiple people on the web. To support answering questions quickly, we introduce a general approach for intelligently recruiting human workers in advance called quikTurkit so that workers are available when new questions arrive. A field deployment with 11 blind participants illustrates that blind people can effectively use VizWiz to cheaply answer questions in their everyday lives, highlighting issues that automatic approaches will need to address to be useful. Finally, we illustrate the potential of using VizWiz as part of the participatory design of advanced tools by using it to build and evaluate VizWiz::LocateIt, an interactive mobile tool that helps blind people solve general visual search problems.
Keywords: blind users; non-visual interfaces; real-time human computation

VizWiz::LocateIt - enabling blind people to locate objects in their environment - Bigham,Jeffrey P.; Jayant,Chandrika; Miller,Andrew; White,Brandyn; Tom Yeh (Computer Vision and Pattern Recognition Workshops (CVPRW), 2010 IEEE Computer Society Conference on, 2010)
Blind people face a number of challenges when interacting with their environments because so much information is encoded visually. Text is pervasively used to label objects, colors carry special significance, and items can easily become lost in surroundings that cannot be quickly scanned. Many tools seek to help blind people solve these problems by enabling them to query for additional information, such as color or text shown on the object. In this paper we argue that many useful problems may be better solved by directly modeling them as search problems, and present a solution called VizWiz::LocateIt that directly supports this type of interaction. VizWiz::LocateIt enables blind people to take a picture and ask for assistance in finding a specific object. The request is first forwarded to remote workers who outline the object, enabling efficient and accurate automatic computer vision to guide users interactively from their existing cellphones. A two-stage algorithm is presented that uses this information to guide users to the appropriate object interactively from their phone.

Why Did the Person Cross the Road (There)? Scene Understanding Using Probabilistic Logic Models and Common Sense Reasoning - Kembhavi,Aniruddha; Tom Yeh; Davis, Larry S. (Computer Vision – ECCV 2010, 2010)
We develop a video understanding system for scene elements, such as bus stops, crosswalks, and intersections, that are characterized more by qualitative activities and geometry than by intrinsic appearance. The domain models for scene elements are not learned from a corpus of video, but instead, naturally elicited by humans, and represented as probabilistic logic rules within a Markov Logic Network framework. Human elicited models, however, represent object interactions as they occur in the 3D world rather than describing their appearance projection in some specific 2D image plane. We bridge this gap by recovering qualitative scene geometry to analyze object interactions in the 3D world and then reasoning about scene geometry, occlusions and common sense domain knowledge using a set of meta-rules. The effectiveness of this approach is demonstrated on a set of videos of public spaces.

Workshop on experimental evaluation of software and systems in computer science (Evaluate 2010) - Blackburn,Steven M.; Diwan,Amer; Hauswirth,Matthias; Memon, Atif M.; Sweeney,Peter F. (Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion, 2010)
We call ourselves 'computer scientists', but are we scientists? If we are scientists, then we must practice the scientific method. This includes a solid experimental evaluation. In our experience, our experimental methodology is ad hoc at best, and nonexistent at worst. This workshop brings together experts from different areas of computer science to discuss, explore, and attempt to identify the principles of sound experimental evaluation
Keywords: Evaluation; METHODOLOGY

Active segmentation for robotics - Mishra,A.; Aloimonos, J.; Fermüller, Cornelia (IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009. IROS 2009, 2009)
The semantic robots of the immediate future are robots that will be able to find and recognize objects in any environment. They need the capability of segmenting objects in their visual field. In this paper, we propose a novel approach to segmentation based on the operation of fixation by an active observer. Our approach is different from current approaches: while existing works attempt to segment the whole scene at once into many areas, we segment only one image region, specifically the one containing the fixation point. Furthermore, our solution integrates monocular cues (color, texture) with binocular cues (stereo disparities and optical flow). Experiments with real imagery collected by our active robot and from the known databases demonstrate the promise of the approach.
Keywords: binocular cues; image colour analysis; Image segmentation; Image texture; Intelligent robots; Layout; Machine vision; monocular cues; Navigation; optical flow; Orbital robotics; Robot sensing systems; robot vision; Robot vision systems; robotics active segmentation; Robotics and automation; semantic robot; Simultaneous localization and mapping; stereo disparity; stereo image processing

Advances in Web Testing - Eaton,Cyntrica; Memon, Atif M. (Computer Performance IssuesComputer Performance Issues, 2009)
AbstractDemand for high‐quality Web applications continues to escalate as reliance on Web‐based software increases and Web systems become increasingly complex. Given the importance of quality and its impact on the user experience, a significant research effort has been invested in developing tools and methodologies that facilitate effective quality assurance for Web applications. Testing, in particular, provides a critical inroad toward meeting the quality demand by enabling developers to discover failures and anomalies in applications before they are released. In this survey, we discuss advances in Web testing and begin by exploring the peculiarities of Web applications that makes evaluating their correctness a challenge and the direct translation of conventional software engineering principles impractical in some cases. We then provide an overview of research contributions in three critical aspects of Web testing: deriving adequate Web application models, defining appropriate Web testing strategies, and conducting Web portability analysis. In short, models are used to capture Web application components, their attributes, and interconnections; testing strategies use the models to generate test cases; and portability analysis enables Web developers to ensure that their applications remain correct as they are launched in highly diverse configurations.

Aggregate Query Answering under Uncertain Schema Mappings - Gal,A.; Martinez,M. V; Simari,G. I; V.S. Subrahmanian (Data Engineering, 2009. ICDE '09. IEEE 25th International Conference on, 2009)
Recent interest in managing uncertainty in data integration has led to the introduction of probabilistic schema mappings and the use of probabilistic methods to answer queries across multiple databases using two semantics: by-table and by-tuple. In this paper, we develop three possible semantics for aggregate queries: the range, distribution, and expected value semantics, and show that these three semantics combine with the by-table and by-tuple semantics in six ways. We present algorithms to process COUNT, AVG, SUM, MIN, and MAX queries under all six semantics and develop results on the complexity of processing such queries under all six semantics. We show that computing COUNT is in PTIME for all six semantics and computing SUM is in PTIME for all but the by-tuple/distribution semantics. Finally, we show that AVG, MIN, and MAX are PTIME computable for all by-table semantics and for the by-tuple/range semantics.We developed a prototype implementation and experimented with both real-world traces and simulated data. We show that, as expected, naive processing of aggregates does not scale beyond small databases with a small number of mappings. The results also show that the polynomial time algorithms are scalable up to several million tuples as well as with a large number of mappings.
Keywords: aggregate; algorithm; probabilistic; answering; by-table; complexity; data; complexity; distributed; database; polynomial; databases; databases; probability; query; integration; distribution; mapping; computational; mapping; query; processing; range; processing; statistical; query; schema; semantics; by-tuple; semantics; computational; semantics; expected; semantics; multiple; semantics; uncertain; TIME; value

All Bits Are Not Equal - A Study of IEEE 802.11 Communication Bit Errors - Han,Bo; Ji,Lusheng; Lee,Seungjoon; Bhattacharjee, Bobby; Miller,R.R. (INFOCOM 2009, IEEE, 2009)
In IEEE 802.11 Wireless LAN (WLAN) systems, techniques such as acknowledgement, retransmission, and transmission rate adaptation, are frame-level mechanisms designed for combating transmission errors. Recently sub-frame level mechanisms such as frame combining have been proposed by the research community. In this paper, we present results obtained from our bit error study for identifying sub-frame error patterns because we believe that identifiable bit error patterns can potentially introduce new opportunities in channel coding, network coding, forward error correction (FEC), and frame combining mechanisms. We have constructed a number of IEEE 802.11 wireless LAN testbeds and conducted extensive experiments to study the characteristics of bit errors and their location distribution. Conventional wisdom dictates that bit error probability is the result of channel condition and ought to follow corresponding distribution. However our measurement results identify three repeatable bit error patterns that are not induced by channel conditions. We have verified that such error patterns are present in WLAN transmissions in different physical environments and across different wireless LAN hardware platforms. We also discuss our current hypotheses for the reasons behind these bit error probability patterns and how identifying these patterns may help improving WLAN transmission robustness.
Keywords: 802.11; bit; coding; error; coding; forward; coding; subframe; combining; Communication; correction; frame; correction; wireless; error; errors; channel; errors; wireless; IEEE; LAN; LAN; channel; mechanisms; network; patterns; transmission; statistics; forward

Analysis of clonally related environmental Vibrio cholerae O1 El Tor isolated before 1992 from Varanasi, India reveals origin of SXT‐ICEs belonging to O139 and O1 serogroups - Mohapatra,Saswat S.; Mantri,Chinmay K.; Mohapatra,Harapriya; Rita R Colwell; Singh,Durg V. (Environmental Microbiology Reports, 2009)
In this study, we report the presence of SXT in environmental Vibrio cholerae O1 El Tor strains isolated before 1992 from Varanasi, India. All isolates, except one, were resistant to Tm, and/or Sul, Sm, Fr, Na and Am. None contained plasmids. PCR and DNA sequencing revealed the presence of SXT containing dfrA1 and/or sulII, strAB in six isolates and dfr18, sulII and strAB in five isolates. Three clinical V. cholerae O1 isolated during 1992 contained the antibiotic resistance gene cassette aadA1 in the class 1 integron. Conjugation experiments, followed by PCR analysis of transconjugants, provided evidence of the transferable nature of SXT and associated antibiotic resistance genes, and its integration into the prfC site. Results of phylogenetic analysis of the intSXT gene of clonally similar V. cholerae showed a clear difference between dfr18+ and dfrA1+V. cholerae O1 isolates. This is the first report of the occurrence of SXT harbouring sulII, strAB, dfr18 and/or dfrA1 genes in environmental V. cholerae O1 isolated prior to 1992 from Varanasi, India, and suggests emergence of SXT+ antibiotic-resistant V. cholerae O139 and O1 from an environmental V. cholerae progenitor by acquisition of SXT and antibiotic-resistant gene clusters.

Analytical Description of Quasi-Random Magnetization Relaxation to Equilibrium - Serpico,C.; d'Aquino,M.; Bertotti,G.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 2009)
The Landau-Lifshitz (LL) dynamics of a uniformly magnetized particle is considered. The LL equation is written in the form of a Hamiltonian perturbed dynamical system. By using suitable averaging technique, the equation for the slow dynamics of the energy is derived. The averaging technique breaks up in the case of separatrix crossing. It is shown that, in the limit of small damping, the separatrix crossing can be described by using a probabilistic approach.
Keywords: approach; quasirandom; crossing; uniformly; dynamical; dynamics; averaging; Hamiltonian; magnetization; magnetized; particle; magnetic; particles; magnetic; perturbed; relaxation; magnetisation; probability; relaxation; separatrix; system; Landau-Lifshitz; technique; damping; probabilistic

Analyzing (social media) networks with NodeXL - Smith,Marc A.; Shneiderman, Ben; Milic-Frayling,Natasa; Mendes Rodrigues,Eduarda; Barash,Vladimir; Dunne,Cody; Capone,Tony; Perer,Adam; Gleave,Eric (Proceedings of the fourth international conference on Communities and technologies, 2009)
We present NodeXL, an extendible toolkit for network overview, discovery and exploration implemented as an add-in to the Microsoft Excel 2007 spreadsheet software. We demonstrate NodeXL data analysis and visualization features with a social media data sample drawn from an enterprise intranet social network. A sequence of NodeXL operations from data import to computation of network statistics and refinement of network visualization through sorting, filtering, and clustering functions is described. These operations reveal sociologically relevant differences in the patterns of interconnection among employee participants in the social media space. The tool and method can be broadly applied.
Keywords: excel; network analysis; social media; social network; spreadsheet; Visualization

CAPE: Automatically Predicting Changes in Group Behavior - Sliva,A.; V.S. Subrahmanian; Martinez,V.; Simari,G. (Mathematical Methods in Counterterrorism, 2009)
There is now intense interest in the problem of forecasting what a group will do in the future. Past work [1, 2, 3] has built complex models of a group’s behavior and used this to predict what the group might do in the future. However, almost all past work assumes that the group will not change its past behavior. Whether the group is a group of investors, or a political party, or a terror group, there is much interest in when and how the group will change its behavior. In this paper, we develop an architecture and algorithms called CAPE to forecast the conditions under which a group will change its behavior. We have tested CAPE on social science data about the behaviors of seven terrorist groups and show that CAPE is highly accurate in its predictions—at least in this limited setting.

Channel Access Throttling for Improving WLAN QoS - Han,Bo; Ji,Lusheng; Lee,Seungjoon; Miller,R.R.; Bhattacharjee, Bobby (Sensor, Mesh and Ad Hoc Communications and Networks, 2009. SECON '09. 6th Annual IEEE Communications Society Conference on, 2009)
The de facto QoS channel access method for the IEEE 802.11 Wireless LANs is the Enhanced Distributed Channel Access (EDCA) mechanism, which differentiates transmission treatments for data frames belonging to different traffic categories with four different levels of channel access priority. In this paper, we propose extending EDCA with Channel Access Throttling (CAT) for more flexible and efficient QoS support. By assigning different member stations different channel access parameters, CAT differentiates channel access priorities not between traffic categories but between member stations. Then by dynamically changing the channel access parameters of each member station based on a pre-computed schedule, CAT enables EDCA WLANs the benefits of scheduled access QoS. We also present evaluation results of CAT obtained from both simulations and experiments conducted using off-the-shelf WLAN hardware and open-source device driver. Our results show that CAT can proportionally partition channel capacity, significantly improve performance of multimedia applications, effectively achieve performance protection for admitted flows, and increase per cell VoIP call capacity by up to 41%.
Keywords: 802.11; access; area; call; capacity; data; capacity; quality; capacity; WLAN; categories; transmission; channel; device; distributed; driver; quality; facto; frames; de; IEEE; LAN; LAN; VoIP; local; mechanism; member; method; enhanced; multimedia; network; wireless; networks; channel; of; parameters; channel; priority; channel; QoS; QoS; channel; service; telecommunication; service; traffic; standards; telecommunication; stations; open-source; throttling; channel; traffic; wireless; treatments; wireless; wireless

Channel Access Throttling for Overlapping BSS Management - Han,Bo; Ji,Lusheng; Lee,Seungjoon; Miller,R.R.; Bhattacharjee, Bobby (Communications, 2009. ICC '09. IEEE International Conference on, 2009)
Multiple co-channel WLAN BSSes (i.e., WLAN cells) overlapping in coverage are generally considered undesirable because members of the OBSSes compete for channel access, which typically increases the contention level of wireless medium access and reduces overall system performance. In this paper, we propose to use channel access throttling (CAT) for managing Wireless LAN radio resources for overlapping BSSes (OBSSes). CAT provides an access point (AP) of each BSS with a mechanism to control channel access parameters of its member stations on the fly. By coordinating the CAT operations of the OBSS APs, we can enable privileged channel access to an individual BSS at a particular time, for example, by assigning high priority access parameters to member stations associated with the BSS. By controlling how much each BSS may be given the privileged channel access, we can also achieve a proportional partitioning of channel capacity among OBSSes. We present evaluation results obtained from both simulations and experiments using testbed built with commercial off-the-shelf (COTS) WLAN hardware and open-source device driver. Our results show that with CAT, not only can we proportionally partition channel capacity among the OBSSes, but also improve channel utilization efficiency and increase overall capacity.
Keywords: access; access; cellular; allocation; channel; BSS; capacity; computer; capacity; proportional; cell; open-source; channel; channels; co-channel; device; driver; overlapping; efficiency; high-priority; LAN; wireless; management; partition; management; wireless; medium; network; parameters; multiple; partitioning; radio; radio; channel; resources; wireless; throttling; channel; utilization; WLAN

Characterizing VLAN-induced sharing in a campus network - Bin Tariq,Mukarram; Mansy,Ahmed; Feamster, Nick; Ammar,Mostafa (Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference, 2009)
Many enterprise, campus, and data-center networks have complex layer-2 virtual LANs ("VLANs") below the IP layer. The interaction between layer-2 and IP topologies in these VLANs introduces hidden dependencies between IP level network and the physical infrastructure that has implications for network management tasks such as planning for capacity or reliability, and for fault diagnosis. This paper characterizes the extent and effect of these dependencies in a large campus network. We first present the design and implementation of EtherTrace, a tool that we make publicly available, which infers the layer-2 topology using data passively collected from Ethernet switches. Using this tool, we infer the layer-2 topology for a large campus network and compare it with the IP topology. We find that almost 70% of layer-2 edges are shared by 10 or more IP edges, and a single layer-2 edge may be shared by as many as 34 different IP edges. This sharing of layer-2 edges and switches among IP paths commonly results from trunking multiple VLANs to the same access router, or from colocation of academic departments that share layer-2 infrastructure, but have logically separate IP subnet and routers. We examine how this sharing affects the accuracy and specificity of fault diagnosis. For example, applying network tomography to the IP topology to diagnose failures caused by layer-2 devices results in only 54% accuracy, compared to 100% accuracy when our tomography algorithm takes input across layers.
Keywords: network diagnosis; network virtualization; VLAN; vlan-induced dependency

Common effect of antipsychotics on the biosynthesis and regulation of fatty acids and cholesterol supports a key role of lipid homeostasis in schizophrenia - Polymeropoulos,Mihael H.; Licamele,Louis; Volpi,Simona; Mack,Kendra; Mitkus,Shruti N.; Carstea,Eugene D.; Getoor, Lise; Thompson,Andrew; Lavedan,Christian (Schizophrenia Research, 2009)
For decades, the dopamine hypothesis has gained the most attention in an attempt to explain the origin and the symptoms of schizophrenia. While this hypothesis offers an explanation for the relationship between psychotic symptoms and dopamine kinetics, it does not provide a direct explanation of the etiology of schizophrenia which remains poorly understood. Consequently, current antipsychotics that target neurotransmitter receptors, have limited and inconsistent efficacy. To gain insights into the mechanism of action of these drugs, we studied the expression profile of 12,490 human genes in a cell line treated with 18 antipsychotics, and compared it to that of a library of 448 other compounds used in a variety of disorders. Analysis reveals a common effect of antipsychotics on the biosynthesis and regulation of fatty acids and cholesterol, which is discussed in the context of a lipid hypothesis where alterations in lipid homeostasis might underlie the pathogenesis of schizophrenia. This finding may help research aimed at the development of novel treatments for this devastating disease.
Keywords: Antipsychotic action; Gene expression; Lipid homeostasis; Pathogenesis

Compressing kinetic data from sensor networks - Friedler,S.; Mount, Dave (Algorithmic Aspects of Wireless Sensor Networks, 2009)
We introduce a framework for storing and processing kinetic data observed by sensor networks. These sensor networks generate vast quantities of data, which motivates a significant need for data compression. We are given a set of sensors, each of which continuously monitors some region of space. We are interested in the kinetic data generated by a finite set of objects moving through space, as observed by these sensors. Our model relies purely on sensor observations; it allows points to move freely and requires no advance notification of motion plans. Sensor outputs are represented as random processes, where nearby sensors may be statistically dependent. We model the local nature of sensor networks by assuming that two sensor outputs are statistically dependent only if the two sensors are among the k nearest neighbors of each other. We present an algorithm for the lossless compression of the data produced by the network. We show that, under the statistical dependence and locality assumptions of our framework, asymptotically this compression algorithm encodes the data to within a constant factor of the information-theoretic lower bound optimum dictated by the joint entropy of the system.

Computer Help at Home: Methods and Motivations for Informal Technical Support - Poole, Erika Shehan; Marshini Chetty; Morgan, Tom; Grinter, Rebecca E.; Edwards, W. Keith (SIGCHI '09, 2009)
Prior research suggests that people may ask their family and friends for computer help. But what influences whether and how a "helper" will provide help? To answer this question, we conducted a qualitative investigation of people who participated in computer support activities with family and friends in the past year. We describe how factors including maintenance of one's personal identity as a computer expert and accountability to one's social network determine who receives help and the quality of help provided. We also discuss the complex, fractured relationship between the numerous stakeholders involved in the upkeep of home computing infrastructures. Based on our findings, we provide implications for the design of systems to support informal help-giving in residential settings.
Keywords: help-giving; help-seeking; Home computing; identity management; social networks

Controlling data in the cloud: outsourcing computation without outsourcing control - Chow, Richard; Golle, Philippe; Jakobsson, Markus; Elaine Shi; Staddon, Jessica; Masuoka, Ryusuke; Molina,Jesus (ACM, 2009)
Cloud computing is clearly one of today's most enticing technology areas due, at least in part, to its cost-efficiency and flexibility. However, despite the surge in activity and interest, there are significant, persistent concerns about cloud computing that are impeding momentum and will eventually compromise the vision of cloud computing as a new IT procurement model. In this paper, we characterize the problems and their impact on adoption. In addition, and equally importantly, we describe how the combination of existing research thrusts has the potential to alleviate many of the concerns impeding adoption. In particular, we argue that with continued research advances in trusted computing and computation-supporting encryption, life in the cloud can be advantageous from a business intelligence standpoint over the isolated alternative that is more common today.
Keywords: Cloud computing; privacy; Security

A cost-effective lexical acquisition process for large-scale thesaurus translation - Jimmy Lin; Murray,G. C; Dorr, Bonnie J; Hajič,J.; Pecina,P. (Language resources and evaluation, 2009)
Thesauri and controlled vocabularies facilitate access to digital collections by explicitly representing the underlying principles of organization. Translation of such resources into multiple languages is an important component for providing multilingual access. However, the specificity of vocabulary terms in most thesauri precludes fully-automatic translation using general-domain lexical resources. In this paper, we present an efficient process for leveraging human translations to construct domain-specific lexical resources. This process is illustrated on a thesaurus of 56,000 concepts used to catalog a large archive of oral histories. We elicited human translations on a small subset of concepts, induced a probabilistic phrase dictionary from these translations, and used the resulting resource to automatically translate the rest of the thesaurus. Two separate evaluations demonstrate the acceptability of the automatic translations and the cost-effectiveness of our approach.

Creativity challenges and opportunities in social computing - Fischer,Gerhard; Jennings,Pamela; Maher,Mary Lou; Resnick,Mitchel; Shneiderman, Ben (Proceedings of the 27th international conference extended abstracts on Human factors in computing systems, 2009)
There is a convergence in recent theories of creativity that go beyond characteristics and cognitive processes of individuals to recognize the importance of the social construction of creativity. In parallel, there has been a rise in social computing supporting the collaborative construction of knowledge. The panel will discuss the challenges and opportunities from the confluence of these two developments by bringing together the contrasting and controversial perspective of the individual panel members. It will synthesize from different perspectives an analytic framework to understand these new developments, and how to promote rigorous research methods and how to identify the unique challenges in developing evaluation and assessment methods for creativity research.
Keywords: creativity; social computing

Cross-document coreference resolution: A key technology for learning by reading - Mayfield,J.; Alexander,D.; Dorr, Bonnie J; Eisner,J.; Elsayed,T.; Finin,T.; Fink,C.; Freedman,M.; Garera,N.; McNamee,P.; others (AAAI Spring Symposium on Learning by Reading and Learning to Read, 2009)

Detecting network neutrality violations with causal inference - Bin Tariq,Mukarram; Motiwala,Murtaza; Feamster, Nick; Ammar,Mostafa (Proceedings of the 5th international conference on Emerging networking experiments and technologies, 2009)
We present NANO, a system that detects when ISPs apply policies that discriminate against specific classes of applications, users, or destinations. Existing systems for detecting discrimination are typically specific to an application or to a particular discrimination mechanism and rely on active measurement tests. Unfortunately, ISPs can change discrimination policies and mechanisms, and they can evade these tests by giving probe traffic higher priority. NANO detects ISP discrimination by passively collecting performance data from clients. To distinguish discrimination from other causes of degradation (e.g., overload, misconfiguration, failure), NANO establishes a causal relationship between an ISP and observed performance by adjusting for confounding factors. NANO agents deployed at participating clients across the Internet collect performance data for selected services and report this information to centralized servers, which analyze the measurements to establish causal relationship between an ISP and performance degradations. We have implemented NANO and deployed clients in a controlled environment on Emulab. We run a combination of controlled experiments on Emulab and wide-area experiments on PlanetLab that show that NANO can determine the extent and criteria for discrimination for a variety of discrimination policies and applications.
Keywords: causal inference; network neutrality

Determination of relationships among non-toxigenic Vibrio cholerae O1 biotype El Tor strains from housekeeping gene sequences and ribotype patterns - Mohapatra,Saswat S.; Ramachandran,Dhanya; Mantri,Chinmay K.; Rita R Colwell; Singh,Durg V. (Research in Microbiology, 2009)
Sequencing of three housekeeping genes, mdh, dnaE and recA, and ribotyping for seven non-toxigenic Vibrio cholerae O1 strains isolated from different geographic sources indicate a phylogenetic relationship among the strains. Results of MLST and ribotyping indicate a clear difference between three toxigenic strains (N16961, O395, and 569B) and three non-toxigenic strains from India (GS1, GS2, and GW87) and one Guam strain (X392), the latter of which were similar in both MLST and ribotyping, while two other non-toxigenic strains from the USA and India (2740-80 and OR69) appeared to be more closely related to toxigenic strains than to non-toxigenic strains, although this was not supported by ribotyping. These results provide clues to the emergence of toxigenic strains from a non-toxigenic progenitor by acquisition of virulence gene clusters. Results of split decomposition analysis suggest that widespread recombination occurs among the three housekeeping genes and that recombination plays an important role in the emergence of toxigenic strains of V. cholerae O1.
Keywords: Housekeeping genes; Ribotyping; sequencing; Vibrio cholerae

Determining the causes of intradomain routing changes - Medem,A.; Teixeira,R.; Feamster, Nick; Meulle,M. (University Pierre and Marie Curie, 2009)
This paper studies how intradomain routinginstability relates to events in network trouble tickets for two networks: a VPN provider and the Internet2 backbone network. Our goal in performing this joint analysis of routing and trouble tickets is to better understand the likely underlying causes of intradomain routing instability. We develop a method to correlate trouble tickets with instability events and find that, although unplanned events last longer than scheduled maintenance, there is no single underlying cause for most instability, and that these causes differ across networks. In comparison to a similar study from Labovitz et al. from ten years ago, we find that, while certain causes of instability such as maintenance and circuit problems remain significant, power issues have become much less prevalent, and software-related problems have become more common.

Digital forensics [From the Guest Editors] - Delp,E.; Memon, N.; Wu,M. (Signal Processing Magazine, IEEE, 2009)
This special issue provides a comprehensive overview of recent developments and open problems in digital forensics that are amenable to signal processing techniques.

A dimension-independent library for building and manipulating multiresolution triangulations - De Floriani, Leila; Magillo,P.; Puppo,E. (Department of Computer Science and Information Science, University of Genoa, 2009)
A Multi-Triangulation (MT) is a general multiresolution model for representing k-dimensional geometricobjects through simplicial complexes. An MT integrates several alternative representations of an object, and provides simple methods for handling representations at variable resolution efficiently , thus offering a basis for the development of applications that need to manage the level-of-detail of complex objects. In this paper, we present an object-oriented library that provides an open-ended tool for building and manipulating object representations based on the MT.

Discrete distortion for surface meshes - Mesmoudi,M.; De Floriani, Leila; Magillo,P. (Image Analysis and Processing–ICIAP 2009, 2009)
Discrete distortion for two- and three-dimensional combinatorial manifolds is a discrete alternative to Ricci curvature known for differentiable manifolds. Here, we show that distortion can be successfully used to estimate mean curvature at any point of a surface. We compare our approach with the continuous case and with a common discrete approximation of mean curvature, which depends on the area of the star of each vertex in the triangulated surface. This provides a new, area-independent, tool for curvature estimation and for morphological shape analysis. We illustrate our approach through experimental results showing the behavior of discrete distortion.

Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks - Han,Bo; Kumar,V. S.A; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind (IEEE INFOCOM 2009, 2009)
Equipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple non-overlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in software-defined radio (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters' decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductive-scheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.
Keywords: access hash function; Channel allocation; channel assignment algorithm; channel capacity; collision avoidance; Computer science; cryptography; distributed algorithm; distributed algorithms; Educational institutions; inductive-scheduling technique; Interference; interference set; packet scheduling algorithm; Peer to peer computing; Radio network; radio networks; radiofrequency interference; random oracle methodology; scheduling; Scheduling algorithm; simultaneous channel allocation; software radio; software-defined radio wireless network capacity; telecommunication congestion control; telecommunication security; Throughput; wireless channels; Wireless networks

Do you know the way to SNA?: A process model for analyzing and visualizing social media data - Hansen,D. L; Rotman,D.; Bonsignore,E.; Milic-Frayling,N.; Rodrigues,E.M.; Smith,M.; Shneiderman, Ben (University of Maryland Tech Report: HCIL-2009-17, 2009)
Traces of activity left by social media users can shed lighton individual behavior, social relationships, and community efficacy. Tools and processes to analyze social traces are essential for enabling practitioners to study and nurture meaningful and sustainable social interaction. Yet such tools and processes remain in their infancy. We conducted a study of 15 graduate students who were learning to apply Social Network Analysis (SNA) to data from online communities. Based on close observations of their emergent practices, we derived the Network Analysis and Visualization (NAV) process model and identified stages where intervention from peers, experts, and an SNA tool were most useful. We show how the NAV model informs the design of SNA tools and services, education practices, and support for social media practitioners.

Dynamic software updates: a VM-centric approach - Subramanian,Suriya; Hicks, Michael W.; McKinley,Kathryn S. (Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, 2009)
Software evolves to fix bugs and add features. Stopping and restarting programs to apply changes is inconvenient and often costly. Dynamic software updating (DSU) addresses this problem by updating programs while they execute, but existing DSU systems for managed languages do not support many updates that occur in practice and are inefficient. This paper presents the design and implementation of Jvolve, a DSU-enhanced Java VM. Updated programs may add, delete, and replace fields and methods anywhere within the class hierarchy. Jvolve implements these updates by adding to and coordinating VM classloading, just-in-time compilation, scheduling, return barriers, on-stack replacement, and garbage collection. Jvolve, is safe: its use of bytecode verification and VM thread synchronization ensures that an update will always produce type-correct executions. Jvolve is flexible: it can support 20 of 22 updates to three open-source programs--Jetty web server, JavaEmailServer, and CrossFTP server--based on actual releases occurring over 1 to 2 years. Jvolve is efficient: performance experiments show that incurs no overhead during steady-state execution. These results demonstrate that this work is a significant step towards practical support for dynamic updates in virtual machines for managed languages.
Keywords: dynamic software updating; garbage collection; virtual machine technology

Dynamic software updates for Java: A VM-centric approach - Subramanian,S.; Hicks, Michael W.; McKinley,K.S. (Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI), 2009)
Software evolves to fix bugs and add features, but stopping andrestarting existing programs to take advantage of these changes can be inconvenient and costly. Dynamic software updating (DSU) addresses these problems by updating programs while they run. The challenge is to develop DSU infrastructure that is flexible, safe, and efficient—DSU should enable updates that are likely to occur in practice, and updated programs should be as reliable and as efficient as those started from scratch. This paper presents the design and implementation of a JVM we call JVOLVE that is enhanced with DSU support. The pa- per’s key insight is that flexible, safe, and efficient DSU can be supported by naturally extending existing VM services. By piggybacking on classloading and garbage collection, JVOLVE can flexibly support additions and replacements of fields and methods anywhere within the class hierarchy, and in a manner that may alter class signatures. By utilizing bytecode verifi- cation and thread synchronization support, JVOLVE can ensure that an applied update will never violate type-safety. Finally, by employing JIT compilation, all DSU-related overhead be- fore or after an update can be effectively eliminated. Using JVOLVE, we successfully applied dynamic continuous updates corresponding to 20 of the 22 releases that occurred over nearly two years’ time, one update per release, for three open-source programs, Jetty web server, JavaEmailServer, and CrossFTP server. Our results indicate that the VM is well-suited to sup- port practical DSU services.

The Dynamics of Actor Loyalty to Groups in Affiliation Networks - Sharara,H.; Singh,L.; Getoor, Lise; Mann,J. (Social Network Analysis and Mining, 2009. ASONAM '09. International Conference on Advances in, 2009)
In this paper, we introduce a method for analyzing the temporal dynamics of affiliation networks. We define affiliation groups which describe temporally related subsets of actors and describe an approach for exploring changing memberships in these affiliation groups over time. To model the dynamic behavior in these networks, we consider the concept of loyalty and introduce a measure that captures an actorpsilas loyalty to an affiliation group as the degree of dasiacommitmentpsila an actor shows to the group over time. We evaluate our measure using two real world affiliation networks: a senate bill co-sponsorship network and a dolphin network. The results show how the behavior of actors in different affiliation groups change dynamically over time, reinforcing the utility of our measure for understanding the loyalty of actors to time-varying affiliation groups.
Keywords: actor; bill; co-sponsorship; dynamics; social; groups; affiliation; loyalty; affiliation; network; senate; network; temporal; networks; dolphin; sciences

The effect of corners on the complexity of approximate range searching - Arya,S.; Malamatos,T.; Mount, Dave (Discrete & Computational Geometry, 2009)
Given an n-element point set in ℝ d , the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam(η) of η’s boundary.In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup (S,+) is idempotent if x+x=x for all x∈S, and it is integral if for all k≥2, the k-fold sum x+⋅⋅⋅+x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least \varOmega(1/{ε }^{d-2\sqrt{d}}) . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ε d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ε)(d−1)/2log (1/ε)) time using O(n/ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ε)(d−1)/2). This bound is in the decision-tree model and holds irrespective of space.

Efficient Robust Private Set Intersection - Dana Dachman-Soled; Malkin, Tal; Raykova, Mariana; Yung, Moti (Applied Cryptography and Network Security, 2009)
Computing Set Intersection privately and efficiently between two mutually mistrusting parties is an important basic procedure in the area of private data mining. Assuring robustness, namely, coping with potentially arbitrarily misbehaving (i.e., malicious) parties, while retaining protocol efficiency (rather than employing costly generic techniques) is an open problem. In this work the first solution to this problem is presented.
Keywords: Coding and Information Theory; Computer Communication Networks; Cryptographic protocols; Data Encryption; Data Structures, Cryptology and Information Theory; Information Systems Applications (incl.Internet); Privacy Preserving Data Mining; Secure Two-party Computation; Set Intersection; Systems and Data Security

Electromagnetic Analysis of Plasmon-Resonance Based All-Optical Magnetic Recording - Mayergoyz, Issak D; Zhang,Zhenyu; McAvoy,P.; Bowen,D.; Krafft,C. (Magnetics, IEEE Transactions on, 2009)
The electromagnetic analysis of plasmon-resonance-based all-optical magnetic recording is performed. This analysis is based on the treatment of plasmon resonances as an eigenvalue problem for specific boundary integral equations. The plasmon modes which can be excited in circular nanoholes and cylindrical nanoshells by circularly polarized light are theoretically and numerically studied. Dramatic enhancement of circularly polarized light intensity on the nanoscale through the excitation of specific plasmon modes in uniaxial nanostructures is demonstrated.
Keywords: Ag; boundary; all-optical; analysis; magnetization; and; based; effects; nanoparticles; silver; surface; eigenfunctions; magnetic; equations; circular; equations; eigenvalues; integral; intensity; cylindrical; light; magnetic; modes; plasmon-resonance; nanoholes; circularly; nanoshells; eigenvalue; nanostructures; boundary; plasmon; polarized; problem; electromagnetic; recording; magnetisation; recording; silver; uniaxial; resonance; reversal; magneto-optical; reversals; nanoparticle; plasmon

Enhancing Testing Technologies for Globalization of Software Engineering and Productivity - Khan,A.H.; Memon, Atif M. (Handbook of Research on Software Engineering and Productivity Technologies: Implications of GlobalizationHandbook of Research on Software Engineering and Productivity Technologies: Implications of Globalization, 2009)

Estimating semantic distance using soft semantic constraints in knowledge-source-corpus hybrid models - Marton,Y.; Mohammad,S.; Resnik, Philip (Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 2-Volume 2, 2009)

Evaluating Attack Resiliency for Host Intrusion Detection Systems - Molina,J.; Michel Cukier (Journal of Information Assurance and Security, 2009)
Host intrusion detection systems (HIDSs) areimportant tools used to provide security to computer systems. Many HIDSs exist and security practitioners need a way to determine the optimal security solution for their environment. Current evaluations of HIDSs focus on detection accuracy and typically do not account for the possibility that an adversary may subvert the HIDS and modify the outcome. As some elements from the HIDS need to reside within the system under supervi- sion, evaluating the strength against HIDS subversion is critical. This paper defines HIDS subversion and presents HIDS resiliency as a metric of HIDS strength in the event of an attack against the system being supervised. To estimate HIDS resiliency, we evaluated the inde- pendency between the system being supervised and the HIDS. Then we integrated resiliency into current frame- works to evaluate detection accuracy.

Evaluating Files to Audit for Detecting Intrusions in FileSystem Data - Molina,J.; Michel Cukier (2009)
Monitoring filesystem data is a common method used to detect intrusions. Once a computer is compromised, an attacker may alter files, add new files or delete existing files. The changes that attackers make may target any part of the filesystem, including metadata along with files (e.g., permissions, ownerships and inodes). The accuracy of detecting an intrusion depends on the data audited: if an intrusion does not manifest in the data, the intrusion will not be detected. Moreover, not all files, which contain filesystem activity, are suitable to detect intrusions, as some may fail to provide useful information. In this paper, we describe an empirical study that focused on filesystem attack activity after a SSH compromise. Three types of attacker action are considered: reconnaissance, password modification, and malware download. For each type of action, we evaluated the files to audit using metrics derived from the field of information theory and estimated with the empirical SSH compromise data.
Keywords: authorisation; Bayes methods; Bayesian metric; data auditing; empirical SSH compromise data; Entropy; entropy-based metric; file evaluation; file organisation; filesystem attack activity; filesystem data monitoring; honeypot; information theory; intrusion detection system; invasive software; malware download; meta data; optimisation; optimization problem; password modification; probability; reconnaissance action; unauthorized user

Evidence for Coregulation of Myocardial Gene Expression by MEF2 and NFAT in Human Heart Failure / CLINICAL PERSPECTIVE - Putt,Mary E.; Hannenhalli, Sridhar; Lu,Yun; Haines,Philip; Chandrupatla,Hareesh R.; Morrisey,Edward E.; Margulies,Kenneth B.; Cappola,Thomas P. (Circulation: Cardiovascular Genetics, 2009)
Background— Pathological stresses induce heart failure in animal models through activation of multiple cardiac transcription factors (TFs) working cooperatively. However, interactions among TFs in human heart failure are less understood. Here, we use genomic data to examine the evidence that 5 candidate TF families coregulate gene expression in human heart failure.Methods and Results— RNA isolates from failing (n=86) and nonfailing (n=16) human hearts were hybridized with Affymetrix HU133A arrays. For each gene on the array, we determined conserved MEF2, NFAT, NKX , GATA , and FOX binding motifs within the −1-kb promoter region using human-murine sequence alignments and the TRANSFAC database. Across 9076 genes expressed in the heart, TF-binding motifs tended to cluster together in nonrandom patterns within promoters of specific genes (P values ranging from 10−2 to 10−21), suggesting coregulation. We then modeled differential expression as a function of TF combinations present in promoter regions. Several combinations predicted increased odds of differential expression in the failing heart, with the highest odds ratios noted for genes containing both MEF2 and NFAT binding motifs together in the same promoter region (peak odds ratio, 3.47; P=0.005).Conclusions— These findings provide genomic evidence for coregulation of myocardial gene expression by MEF2 and NFAT in human heart failure. In doing so, they extend the paradigm of combinatorial regulation of gene expression to the human heart and identify new target genes for mechanistic study. More broadly, we demonstrate how integrating diverse sources of genomic data yields novel insight into human cardiovascular disorders.

An Extensible Heuristic-Based Framework for GUI Test Case Maintenance - McMaster,S.; Memon, Atif M. (Software Testing, Verification and Validation Workshops, 2009. ICSTW '09. International Conference on, 2009)
Graphical user interfaces (GUIs) make up a large portion of the code comprising many modern software applications. However, GUI testing differs significantly from testing of traditional software. One respect in which this is true is test case maintenance. Due to the way that GUI test cases are often implemented, relatively minor changes to the construction of the GUI can cause a large number of test case executions to malfunction, often because GUI elements referred to by the test cases have been renamed, moved, or otherwise altered. We posit that a general solution to the problem of GUI test case maintenance must be based on heuristics that attempt to match an applicationpsilas GUI elements across versions. We demonstrate the use of some heuristics with framework support. Our tool support is general in that it may be used with other heuristics if needed in the future.
Keywords: extensible heuristic-based framework; graphical user interface; Graphical user interfaces; GUI code; GUI test case maintenance; program testing; Software maintenance

Fighting Spam with the NeighborhoodWatch DHT - Bender,A.; Sherwood,R.; Monner,D.; Goergen,N.; Spring, Neil; Bhattacharjee, Bobby (IEEE INFOCOM 2009, 2009)
In this paper, we present DHTBL, an anti-spam blacklist built upon a novel secure distributed hash table (DHT). We show how DHTBL can be used to replace existing DNS-based blacklists (DNSBLs) of IP addresses of mail relays that forward spam. Implementing a blacklist on a DHT improves resilience to DoS attacks and secures message delivery, when compared to DNSBLs. However, due to the sensitive nature of the blacklist, storing the data in a peer-to-peer DHT would invite attackers to infiltrate the system. Typical DHTs can withstand fail-stop failures, but malicious nodes may provide incorrect routing information, refuse to return published items, or simply ignore certain queries. The neighborhoodwatch DHT is resilient to malicious nodes and maintains the O(logiV) bounds on routing table size and expected lookup time. NeighborhoodWatch depends on two assumptions in order to make these guarantees: (1) the existence of an on-line trusted authority that periodically contacts and issues signed certificates to each node, and (2) for every sequence of k + 1 consecutive nodes in the ID space, at least one is alive and non-malicious. We show how NeighborhoodWatch maintains many of its security properties even when the second assumption is violated. Honest nodes in NeighborhoodWatch can detect malicious behavior and expel the responsible nodes from the DHT.
Keywords: Communications Society; computer crime; cryptography; Databases; IP addresses; IP networks; on-line trusted authority; Peer to peer computing; peer-to-peer computing; peer-to-peer distributed hash table; Postal services; Relays; Resilience; Routing; Security; table size routing; Unsolicited electronic mail

Fluency, adequacy, or HTER?: exploring different human judgments with a tunable MT metric - Snover,Matthew; Madnani,Nitin; Dorr, Bonnie J; Schwartz,Richard (Proceedings of the Fourth Workshop on Statistical Machine Translation, 2009)
Automatic Machine Translation (MT) evaluation metrics have traditionally been evaluated by the correlation of the scores they assign to MT output with human judgments of translation performance. Different types of human judgments, such as Fluency, Adequacy, and HTER, measure varying aspects of MT performance that can be captured by automatic MT metrics. We explore these differences through the use of a new tunable MT metric: TER-Plus, which extends the Translation Edit Rate evaluation metric with tunable parameters and the incorporation of morphology, synonymy and paraphrases. TER-Plus was shown to be one of the top metrics in NIST's Metrics MATR 2008 Challenge, having the highest average rank in terms of Pearson and Spearman correlation. Optimizing TER-Plus to different types of human judgments yields significantly improved correlations and meaningful changes in the weight of different types of edits, demonstrating significant differences between the types of human judgments.

Gene Profiling of Human Adipose Tissue During Evoked Inflammation In Vivo - Shah,Rachana; Lu,Yun; Hinkle,Christine C; McGillicuddy,Fiona C; Kim,Roy; Hannenhalli, Sridhar; Cappola,Thomas P.; Heffron,Sean; Wang,XingMei; Mehta,Nehal N; Putt,Mary; Reilly,Muredach P (DiabetesDiabetes, 2009)
OBJECTIVE Adipose inflammation plays a central role in obesity-related metabolic and cardiovascular complications. However, few human adipose-secreted proteins are known to mediate these processes. We hypothesized that microarray mRNA profiling of human adipose during evoked inflammation could identify novel adipocytokines.RESEARCH DESIGN AND METHODS Healthy human volunteers (n = 14) were treated with intravenous endotoxin (3 ng/kg lipopolysaccharide [LPS]) and underwent subcutaneous adipose biopsies before and after LPS. On Affymetrix U133Plus 2.0 arrays, adipose mRNAs modulated >1.5-fold (with P < 0.00001) were selected. SignalP 3.0 and SecretomeP 2.0 identified genes predicted to encode secreted proteins. Of these, 86 candidates were chosen for validation in adipose from an independent human endotoxemia protocol (N = 7, with 0.6 ng/kg LPS) and for exploration of cellular origin in primary human adipocytes and macrophages in vitro. RESULTS Microarray identified 776 adipose genes modulated by LPS; 298 were predicted to be secreted. Of detectable prioritized genes, 82 of 85 (96% [95% CI 90–99]) were upregulated (fold changes >1.0) during the lower-dose (LPS 0.6 ng/kg) validation study and 51 of 85 (59% [49–70]) were induced greater than 1.5-fold. Treatment of primary adipocytes with LPS and macrophage polarization to M1 proinflammatory phenotype increased expression by 1.5-fold for 58 and 73% of detectable genes, respectively. CONCLUSIONS We demonstrate that evoked inflammation of human adipose in vivo modulated expression of multiple genes likely secreted by adipocytes and monocytes. These included established adipocytokines and chemokines implicated in recruitment and activation of lymphocytes, adhesion molecules, antioxidants, and several novel genes with unknown function. Such candidates may represent biomarkers and therapeutic targets for obesity-related complications.

Generating high-coverage semantic orientation lexicons from overtly marked words and a thesaurus - Mohammad,Saif; Dunne,Cody; Dorr, Bonnie J (Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 2 - Volume 2, 2009)
Sentiment analysis often relies on a semantic orientation lexicon of positive and negative words. A number of approaches have been proposed for creating such lexicons, but they tend to be computationally expensive, and usually rely on significant manual annotation and large corpora. Most of these methods use WordNet. In contrast, we propose a simple approach to generate a high-coverage semantic orientation lexicon, which includes both individual words and multi-word expressions, using only a Roget-like thesaurus and a handful of affixes. Further, the lexicon has properties that support the Polyanna Hypothesis. Using the General Inquirer as gold standard, we show that our lexicon has 14 percentage points more correct entries than the leading WordNet-based high-coverage lexicon (SentiWordNet). In an extrinsic evaluation, we obtain significantly higher performance in determining phrase polarity using our thesaurus-based lexicon than with any other. Additionally, we explore the use of visualization techniques to gain insight into the our algorithm beyond the evaluations mentioned above.

Generating surveys of scientific paradigms - Mohammad,S.; Dorr, Bonnie J; Egan,M.; Hassan,A.; Muthukrishan,P.; Qazvinian,V.; Radev,D.; Zajic, David (Proceedings of HLT-NAACL, 2009)
The number of research publications in var-ious disciplines is growing exponentially. Researchers and scientists are increasingly finding themselves in the position of having to quickly understand large amounts of tech- nical material. In this paper we present the first steps in producing an automatically gen- erated, readily consumable, technical survey. Specifically we explore the combination of citation information and summarization tech- niques. Even though prior work (Teufel et al., 2006) argues that citation text is unsuitable for summarization, we show that in the frame- work of multi-document survey creation, cita- tion texts can play a crucial role.

Genome assortment, not serogroup, defines Vibrio cholerae pandemic strains - Brettin,Thomas S[Los Alamos National Laboratory; Bruce,David C[Los Alamos National Laboratory; Challacombe,Jean F[Los Alamos National Laboratory; Detter,John C[Los Alamos National Laboratory; Han,Cliff S[Los Alamos National Laboratory; Munik,A. C[Los Alamos National Laboratory; Chertkov,Olga[Los Alamos National Laboratory; Meincke,Linda[Los Alamos National Laboratory; Saunders,Elizabeth[Los Alamos National Laboratory; Choi,Seon Y[SEOUL NATL UNIV; Haley,Bradd J[U MARYLAND; Taviani,Elisa[U MARYLAND; et al. (Nature, 2009)
Vibrio cholerae, the causative agent of cholera, is a bacterium autochthonous to the aquatic environment, and a serious public health threat. V. cholerae serogroup O1 is responsible for the previous two cholera pandemics, in which classical and El Tor biotypes were dominant in the 6th and the current 7th pandemics, respectively. Cholera researchers continually face newly emerging and re-emerging pathogenic clones carrying combinations of new serogroups as well as of phenotypic and genotypic properties. These genotype and phenotype changes have hampered control of the disease. Here we compare the complete genome sequences of 23 strains of V. cholerae isolated from a variety of sources and geographical locations over the past 98 years in an effort to elucidate the evolutionary mechanisms governing genetic diversity and genesis of new pathogenic clones. The genome-based phylogeny revealed 12 distinct V. cholerae phyletic lineages, of which one, designated the V. cholerae core genome (CG), comprises both O1 classical and EI Tor biotypes. All 7th pandemic clones share nearly identical gene content, i.e., the same genome backbone. The transition from 6th to 7th pandemic strains is defined here as a 'shift' between pathogenic clones belonging to the same O1 serogroup, but from significantly different phyletic lineages within the CG clade. In contrast, transition among clones during the present 7th pandemic period can be characterized as a 'drift' between clones, differentiated mainly by varying composition of laterally transferred genomic islands, resulting in emergence of variants, exemplified by V.cholerae serogroup O139 and V.cholerae O1 El Tor hybrid clones that produce cholera toxin of classical biotype. Based on the comprehensive comparative genomics presented in this study it is concluded that V. cholerae undergoes extensive genetic recombination via lateral gene transfer, and, therefore, genome assortment, not serogroup, should be used to define pathogenic V. cholerae clones.
Keywords: 59; CHOLERA; GENES; GENETICS; GENOTYPE; ISLANDS; ORIGIN; PHENOTYPE; PUBLIC HEALTH; RECOMBINATION; STRAINS; TOXINS

HEALTH AND WELLBEING - Gillam,M.; Feied,C.; MOODY,E.; Shneiderman, Ben; Smith,M.; DICKASON,J. (The fourth paradigm: data-intensive scientific discovery, 2009)

Improved Non-committing Encryption with Applications to Adaptively Secure Protocols - Choi, Seung Geol; Dana Dachman-Soled; Malkin, Tal; Wee, Hoeteck (Advances in Cryptology – ASIACRYPT 2009, 2009)
We present a new construction of non-committing encryption schemes. Unlike the previous constructions of Canetti et al. (STOC ’96) and of Damgård and Nielsen (Crypto ’00), our construction achieves all of the following properties: Optimal round complexity. Our encryption scheme is a 2-round protocol, matching the round complexity of Canetti et al. and improving upon that in Damgård and Nielsen. Weaker assumptions. Our construction is based on trapdoor simulatable cryptosystems, a new primitive that we introduce as a relaxation of those used in previous works. We also show how to realize this primitive based on hardness of factoring. Improved efficiency. The amortized complexity of encrypting a single bit is O(1) public key operations on a constant-sized plaintext in the underlying cryptosystem. As a result, we obtain the first non-committing public-key encryption schemes under hardness of factoring and worst-case lattice assumptions; previously, such schemes were only known under the CDH and RSA assumptions. Combined with existing work on secure multi-party computation, we obtain protocols for multi-party computation secure against a malicious adversary that may adaptively corrupt an arbitrary number of parties under weaker assumptions than were previously known. Specifically, we obtain the first adaptively secure multi-party protocols based on hardness of factoring in both the stand-alone setting and the UC setting with a common reference string.
Keywords: adaptive corruption; Algorithm Analysis and Problem Complexity; Applications of Mathematics; Data Encryption; Data Structures, Cryptology and Information Theory; Discrete Mathematics in Computer Science; non-committing encryption; public-key encryption; secure multi-party computation; Systems and Data Security

Improved statistical machine translation using monolingually-derived paraphrases - Marton,Y.; Callison-Burch,C.; Resnik, Philip (Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1-Volume 1, 2009)

Incremental Multiple Kernel Learning for object recognition - Kembhavi,Aniruddha; Siddiquie,Behjat; Miezianko,Roland; McCloskey,Scott; Davis, Larry S. (Computer Vision, 2009 IEEE 12th International Conference on, 2009)
A good training dataset, representative of the test images expected in a given application, is critical for ensuring good performance of a visual categorization system. Obtaining task specific datasets of visual categories is, however, far more tedious than obtaining a generic dataset of the same classes. We propose an Incremental Multiple Kernel Learning (IMKL) approach to object recognition that initializes on a generic training database and then tunes itself to the classification task at hand. Our system simultaneously updates the training dataset as well as the weights used to combine multiple information sources. We demonstrate our system on a vehicle classification problem in a video stream overlooking a traffic intersection. Our system updates itself with images of vehicles in poses more commonly observed in the scene, as well as with image patches of the background, leading to an increase in performance. A considerable change in the kernel combination weights is observed as the system gathers scene specific training data over time. The system is also seen to adapt itself to the illumination change in the scene as day transitions to night.

An Initial Characterization of Industrial Graphical User Interface Systems - Brooks,P.A.; Robinson,B.P.; Memon, Atif M. (Software Testing Verification and Validation, 2009. ICST '09. International Conference on, 2009)
To date we have developed and applied numerous model-based GUI testing techniques; however, we are unable to provide definitive improvement schemes to real-world GUI test planners, as our data was derived from open source applications, small compared to industrial systems. This paper presents a study of three industrial GUI-based software systems developed at ABB, including data on classified defects detected during late-phase testing and customer usage, test suites, and source code change metrics. The results show that (1) 50% of the defects found through the GUI are categorized as data access and handling, control flow and sequencing, correctness, and processing defects, (2) system crashes exposed defects 12-19% of the time, and (3) GUI and non-GUI components are constructed differently, in terms of source code metrics.
Keywords: Graphical user interfaces; GUI-based software systems; industrial graphical user interface systems; model-based GUI testing techniques; program testing; software metrics; source code change metrics

Integrated product and process design for a flapping wing drive mechanism - Bejgerowski,W.; Ananthanarayanan,A.; Mueller,D.; Gupta,S.K. (Journal of Mechanical Design, 2009)

Interacting with eHealth: towards grand challenges for HCI - André,P.; White,R.; Tan,D.; Berners-Lee,T.; Consolvo,S.; Jacobs,R.; Kohane,I.; Le Dantec,C.A.; Mamykina,L.; Marsden,G. (Proceedings of the 27th international conference extended abstracts on Human factors in computing systems, 2009)
While health records are increasingly stored electronically, we, as citizens, have little access to this data about ourselves. We are not used to thinking of these official records either as ours or as useful to us. We increasingly turn to the Web, however, to query any ache, pain or health goal we may have before consulting with health care professionals. Likewise, for proactive health care such as nutrition or fitness, or to find fellow-sufferers for post diagnosis support, we turn to online resources. There is a potential disconnect between points at which professional and lay eHealth data and resources intersect for preventative or proactive health care. Such gaps in information sharing may have direct impact on practices we decide to take up, the care we seek, or the support professionals offer. In this panel, we consider several places within proactive, preventative health care in particular HCI has a role towards enhancing health knowledge discovery and health support interaction. Our goal is to demonstrate how now is the time for eHealth to come to the forefront of the HCI research agenda.

Interlingual annotation of multilingual text corpora and FrameNet - Farwell,David; Dorr, Bonnie J; Habash,Nizar; Helmreich,Stephen; Hovy,Eduard; Green,Rebecca; Levin,Lori; Miller,Keith; Mitamura,Teruko; Rambow,Owen; Reeder,Flo; Siddharthan,Advaith (Multilingual FrameNets in Computational LexicographyMultilingual FrameNets in Computational Lexicography, 2009)

Introducing a test suite similarity metric for event sequence-based test cases - Brooks,P.A.; Memon, Atif M. (Software Maintenance, 2009. ICSM 2009. IEEE International Conference on, 2009)
Most of today's event driven software (EDS) systems are tested using test cases that are carefully constructed as sequences of events; they test the execution of an event in the context of its preceding events. Because sizes of these test suites can be extremely large, researchers have developed techniques, such as reduction and minimization, to obtain test suites that are ldquosimilarrdquo to the original test suite, but smaller. Existing similarity metrics mostly use code coverage; they do not consider the contextual relationships between events. Consequently, reduction based on such metrics may eliminate desirable test cases. In this paper, we present a new parameterized metric, CONTeSSi(n) which uses the context of n preceding events in test cases to develop a new context-aware notion of test suite similarity for EDS. This metric is defined and evaluated by comparing four test suites for each of four open source applications. Our results show that CONT eSSi(n) is a better indicator of the similarity of EDS test suites than existing metrics.
Keywords: event driven software systems; event sequence-based test cases; open source systems; program testing; public domain software; software metrics; Software testing; test suite similarity metric

It's Not Easy Being Green: Understanding Home Computer Power Management - Marshini Chetty; Brush, A.J. Bernheim; Meyers, Brian R.; Johns, Paul (SIGCHI '09, 2009)
Although domestic computer use is increasing, most efforts to reduce energy use through improved power management have focused on computers in the workplace. We studied 20 households to understand how people use power management strategies on their home computers. We saw computers in the home, particularly desktop computers, are left on much more than they are actively used suggesting opportunities for economic and energy savings. However, for most of our participants, the economic incentives were too minor to motivate them to turn off devices when not in use, especially given other frustrations such as long boot up times. We suggest research directions for home computer power management that could help users be more green without having to dramatically change their home computing habits.
Keywords: home computer use; power management; Sustainability

Maintaining nets and net trees under incremental motion - Cho,M.; Mount, Dave; Park,E. (Algorithms and Computation, 2009)
The problem of maintaining geometric structures for points in motion has been well studied over the years. Much theoretical work to date has been based on the assumption that point motion is continuous and predictable, but in practice, motion is typically presented incrementally in discrete time steps and may not be predictable. We consider the problem of maintaining a data structure for a set of points undergoing such incremental motion. We present a simple online model in which two agents cooperate to maintain the structure. One defines the data structure and provides a collection of certificates, which guarantee the structure’s correctness. The other checks that the motion over time satisfies these certificates and notifies the first agent of any violations.We present efficient online algorithms for maintaining both nets and net trees for a point set undergoing incremental motion in a space of constant dimension. We analyze our algorithms’ efficiencies by bounding their competitive ratios relative to an optimal algorithm. We prove a constant factor competitive ratio for maintaining a slack form of nets, and our competitive ratio for net trees is proportional to the square of the tree’s height.

Measuring vlan-induced dependencies on a campus network - Mansy,A.; Tariq,M.B.; Feamster, Nick; Ammar,M. (Proceedings of the ACM SIGCOMM Internet measurement conference, 2009)
Many enterprise, campus, and data-center networks have complexlayer-2 virtual LANs (“VLANs”) underlying the layer-3 network. The interac- tion between layer-2 and layer-3 topologies can introduce dependencies that are not visible when analyzed solely from layer 3; this paper studies the extent and impact of these dependencies. We first present EtherTrace, a tool that infers the layer-2 topology using data passively collected from Ethernet switches. Using this tool, we infer the layer-2 topology for a large campus network and compare the two topologies. Our comparison yields some striking initial findings: almost 70% of layer-2 edges are shared by 10 or more IP edges, and a single layer-2 edge may be shared by as many as 34 different IP edges. This sharing has significant implications for both robustness and for network tomography. Applying network tomography to the IP topology to diagnose failures caused by layer-2 devices results in only 54% accuracy, compared to 100% accuracy when tomography is performed at layer 2.

Method and system for optimal data diagnosis - V.S. Subrahmanian; Ernst,Jason (2009)
In the method and system for automated data diagnosis, a relational data base is formed of attributes characterizing an entity. The framework computes optimal diagnosis for a diagnostic inference problem which separates the desirable attributes from the undesirable attributes. The user of the system is permitted to specify certain parameters based on which the system computes a set of optimal or near optimal association rules between the attributes of a specific process, product, or other entity. The system and method of the present invention considers the simplicity of conditions in addition to support and confidence when ordering them, contributes the notion of tight conditions and semi-equivalence to remove redundant rules, uses the concept of the top fringes which allows near optimal conditions to be found, in addition to optimal conditions. Numeric as well as non-numeric attributes can be analyzed.

Modeling and Testing of Ethernet Transformers - Bowen,D.; Mayergoyz, Issak D; Zhang,Zhenyu; McAvoy,P.; Krafft,C.; Kroop,D. (Magnetics, IEEE Transactions on, 2009)
In this paper, novel techniques for the testing and identification of lumped parameters of equivalent circuits for Ethernet transformers are presented. It is demonstrated experimentally and theoretically that resonance phenomena may occur in the loop formed by leakage inductances and cross-winding capacitance. This resonance may corrupt the pass band of the transformers transfer characteristic for differential-mode signals.
Keywords: area; capacitance; differential-mode; characteristic; local; Ethernet; identification; lumped; inductances; lumped; networks; transformers; PARAMETERS; phenomena; transformers; signals; leakage; testing; resonance; transfer; transformers; cross-winding

Morphology analysis of 3D scalar fields based on morse theory and discrete distortion - Mesmoudi,Mohammed Mostefa; De Floriani, Leila; Magillo,Paola (Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2009)
We investigate a morphological approach to the analysis and understanding of 3D scalar fields defined by volume data sets. We consider a discrete model of the 3D field obtained by discretizing its domain into a tetrahedral mesh. We use Morse theory as the basic mathematical tool which provides a segmentation of the graph of the scalar field based on relevant morphological features (such as critical points). Since the graph of a discrete 3D field is a tetrahedral hypersurface in 4D space, we measure the distortion of the transformation which maps the tetrahedral decomposition of the domain of the scalar field into the tetrahedral mesh representing its graph in R4, and we call it discrete distortion. We develop a segmentation algorithm to produce a Morse decompositions associated with the scalar field and its discrete distortion. We use a merging procedure to control the number of 3D regions in the segmentation output. Experimental results show the validity of our approach.
Keywords: curvature; morphological analysis; Morse theory; segmentation

A Narrow Waist for Multipath Routing - Motiwala,M.; bin Tariq,M.; Anwer,B.; Andersen,D.; Feamster, Nick (School of Computer Science, Georgia Tech, 2009)
Many applications can use multipath routing to improvereliability or throughput, and many multipath routing pro- tocols exist. Despite this diversity of mechanisms and applications, no common interface exists to allow an ap- plication to select these paths. This paper presents a de- sign for such a common interface, called path bits. Path bits are a small string of opaque, semantic-free bits in a packet header; these bits have a simple property: changing a packet’s path bits should, with high probability, result in the packet taking a different path to the destination. This paper presents the design of path bits and demonstrates that they are simple enough to be easily implemented in both hardware and software and expressive enough to sup- port a variety of applications that can benefit from mul- tipath routing. We present both hardware and software implementations of multipath routing protocols that im- plement the path bits abstraction, as well as implementa- tions of applications that can use this abstraction with only small modifications.

Nonlinear Resonant and Chaotic Dynamics in Microwave Assisted Magnetization Switching - d'Aquino,M.; Serpico,C.; Bertotti,G.; Mayergoyz, Issak D; Bonin,R. (Magnetics, IEEE Transactions on, 2009)
The switching process of a uniformly magnetized magnetic nanoparticle is considered. The particle is subject to applied fields having both dc and linearly-polarized radio-frequency (RF) components. The possibility of using the RF power to obtain a reduced coercivity of the particle is related to the onset of chaotic magnetization dynamics for moderately low values of the RF field amplitude. Perturbation technique for the evaluation of the reduced coercive field is developed and applied to the microwave assisted switching of the particle. Numerical simulations confirm the predictions of the theory.
Keywords: amplitude; chaotic; components; magnetic; dynamical; dynamics; coercive; dynamics; numerical; field; field; coercivity; linearly-polarized; force; magnetic; magnetization; nanoparticle; microwave-assisted; particles; magnetic; radiofrequency; resonant; RF; simulations; perturbation; switching; nanoparticles; nonlinear; switching; nonlinear; systems; perturbation; technique; chaos; coercive; theory

Online allocation of display advertisements subject to advanced sales contracts - Alaei,Saeed; Arcaute,Esteban; Khuller, Samir; Ma,Wenjing; Malekian,Azarakhsh; Tomlin,John (Proceedings of the Third International Workshop on Data Mining and Audience Intelligence for Advertising, 2009)
In this paper we propose a utility model that accounts for both sales and branding advertisers. We first study the computational complexity of optimization problems related to both online and offline allocation of display advertisements. Next, we focus on a particular instance of the online allocation problem, and design a simple online algorithm with provable approximation guarantees. Our algorithm is near optimal as is shown by a matching lower bound. Finally, we report on experiments to establish actual case behavior on some real datasets, with encouraging results.
Keywords: display advertising; modeling; online algorithms; OPTIMIZATION; simulation

An OpenFlow switch element for Click - Mundada,Y.; Sherwood,R.; Feamster, Nick (Symposium on Click Modular Router, 2009)

Optical interconnect structure in a computer system and method of transporting data between processing elements and memory through the optical interconnect structure - Vishkin, Uzi (2009)
A multi-chip processor/memory arrangement replacing a large computer chip, includes a number of modules each including processing elements, registers, and/or memories interconnected by an optical interconnection fabric providing an all-to-all interconnection between the chips, so that the memory cells on each chip represent a portion of shared memory. The optical interconnect fabric is responsible for transporting data between the chips while processing elements on each chip dominate processing. Each chip is manufactured in mass production so that the entire processor/memory arrangement is fabricated in an inexpensive and simplified technology process. The optical communication fabric is based on waveguide technology and includes a number of waveguides, the layout of which follows certain constraints. The waveguides can intersect each other in the single plane, or alternatively, a double layer of waveguide structures and bent over approach may be used. Specific layout patterns of...

Passive aggressive measurement with MGRP - Papageorge,Pavlos; McCann,Justin; Hicks, Michael W. (SIGCOMM Comput. Commun. Rev., 2009)
We present the Measurement Manager Protocol (MGRP), an in-kernel service that schedules and transmits probes on behalf of active measurement tools. Unlike prior measurement services, MGRP transparently piggybacks application packets inside the often significant amounts of empty padding contained in typical probes. Using MGRP thus combines the modularity, flexibility, and accuracy of standalone active measurement tools with the lower overhead of passive measurement techniques. Microbenchmark experiments show that the resulting bandwidth savings makes it possible to measure the network accurately, but faster and more aggressively than without piggybacking, and with few ill effects to piggybacked application or competing traffic. When using MGRP to schedule measurements on behalf of MediaNet, an overlay service that adaptively schedules media streams, we show MediaNet can achieve significantly higher streaming rates under the same network conditions.
Keywords: active; available bandwidth; kernel module; passive; piggybacking; probing; streaming; transport protocol

Predicting and Controlling System-Level Parameters of Multi-Agent Systems - Miner,Don; desJardins, Marie (2009 AAAI Fall Symposium Series, 2009)
Boid flocking is a system in which several individual agents follow three simple rules to generate swarm-level flocking behavior. To control this system, the user must adjust the agent program parameters, which indirectly modifies the flocking behavior. This is unintuitive because the properties of the flocking behavior are non-explicit in the agent program. In this paper, we discuss a domain-independent approach for detecting and controlling two emergent properties of boids: density and a qualitative threshold effect of swarming vs. flocking. Also, we discuss the possibility of applying this approach to detecting and controlling traffic jams in traffic simulations.
Keywords: Complex Adaptive Systems; System-level behavior

Predicting the distribution of Vibrio spp. in the Chesapeake Bay: a Vibrio cholerae case study - Constantin de Magny,G.; Long,W.; Brown,C. W.; Hood,R. R.; Huq,A.; Murtugudde,R.; Rita R Colwell (EcoHealth, 2009)
Vibrio cholerae, the causative agent of cholera, is a naturally occurring inhabitant of the Chesapeake Bay and serves as a predictor for other clinically important vibrios, including Vibrio parahaemolyticus and Vibrio vulnificus. A system was constructed to predict the likelihood of the presence of V. cholerae in surface waters of the Chesapeake Bay, with the goal to provide forecasts of the occurrence of this and related pathogenic Vibrio spp. Prediction was achieved by driving an available multivariate empirical habitat model estimating the probability of V. cholerae within a range of temperatures and salinities in the Bay, with hydrodynamically generated predictions of ambient temperature and salinity. The experimental predictions provided both an improved understanding of the in situ variability of V. cholerae, including identification of potential hotspots of occurrence, and usefulness as an early warning system. With further development of the system, prediction of the probability of the occurrence of related pathogenic vibrios in the Chesapeake Bay, notably V. parahaemolyticus and V. vulnificus, will be possible, as well as its transport to any geographical location where sufficient relevant data are available.

Prioritizing component compatibility tests via user preferences - Yoon,Il-Chul; Sussman, Alan; Memon, Atif M.; Porter, Adam (Software Maintenance, 2009. ICSM 2009. IEEE International Conference on, 2009)
Many software systems rely on third-party components during their build process. Because the components are constantly evolving, quality assurance demands that developers perform compatibility testing to ensure that their software systems build correctly over all deployable combinations of component versions, also called configurations. However, large software systems can have many configurations, and compatibility testing is often time and resource constrained. We present a prioritization mechanism that enhances compatibility testing by examining the ldquomost importantrdquo configurations first, while distributing the work over a cluster of computers. We evaluate our new approach on two large scientific middleware systems and examine tradeoffs between the new prioritization approach and a previously developed lowest-cost-configuration-first approach.
Keywords: compatibility testing prioritization; component configurations; computer clusters; Middleware; Middleware systems; object-oriented programming; program testing; software engineering; Software systems; third-party components; user preferences

On random sampling auctions for digital goods - Alaei,Saeed; Malekian,Azarakhsh; Srinivasan, Aravind (Proceedings of the 10th ACM conference on Electronic commerce, 2009)
In the context of auctions for digital goods, an interesting Random Sampling Optimal Price auction (RSOP) has been proposed by Goldberg, Hartline and Wright; this leads to a truthful mechanism. Since random sampling is a popular approach for auctions that aims to maximize the seller's revenue, this method has been analyzed further by Feige, Flaxman, Hartline and Kleinberg, who have shown that it is 15-competitive in the worst case -- which is substantially better than the previously proved bounds but still far from the conjectured competitive ratio of 4. In this paper, we prove that RSOP is indeed 4-competitive for a large class of instances in which the number λ of bidders receiving the item at the optimal uniform price, is at least 6. We also show that it is 4.68 competitive for the small class of remaining instances thus leaving a negligible gap between the lower and upper bound. Furthermore, we develop a robust version of RSOP -- one in which the seller's revenue is, with high probability, not much below its mean -- when the above parameter λ grows large. We employ a mix of probabilistic techniques and dynamic programming to compute these bounds.
Keywords: auction; mechanism design; random sampling

Reducing complexity assumptions for statistically-hiding commitment - Haitner,I.; Horvitz,O.; Katz, Jonathan; Koo,C. Y; Morselli,R.; Shaltiel,R. (Journal of cryptology, 2009)
We revisit the following question: what are the minimal assumptions needed to construct statistically-hiding commitment schemes? Naor et al. show how to construct such schemes based on any one-way permutation. We improve upon this by showing a construction based on any approximable preimage-size one-way function. These are one-way functions for which it is possible to efficiently approximate the number of pre-images of a given output. A special case is the class of regular one-way functions where all points in the image of the function have the same (known) number of pre-images.We also prove two additional results related to statistically-hiding commitment. First, we prove a (folklore) parallel composition theorem showing, roughly speaking, that the statistical hiding property of any such commitment scheme is amplified exponentially when multiple independent parallel executions of the scheme are carried out. Second, we show a compiler which transforms any commitment scheme which is statistically hiding against an honest-but-curious receiver into one which is statistically hiding even against a malicious receiver.

Resistin gene variation is associated with systemic inflammation but not plasma adipokine levels, metabolic syndrome or coronary atherosclerosis in nondiabetic Caucasians - Qasim,Atif N; Metkus,Thomas S; Tadesse,Mahlet; Lehrke,Michael; Restine,Stephanie; Wolfe,Megan L; Hannenhalli, Sridhar; Cappola,Thomas; Rader,Daniel J; Reilly,Muredach P (Clinical Endocrinology, 2009)
Objective  Resistin causes insulin resistance and diabetes in mice whereas in humans it is linked to inflammation and atherosclerosis. Few human genetic studies of resistin in inflammation and atherosclerosis have been performed. We hypothesized that the –420C>G putative gain-of-function resistin variant would be associated with inflammatory markers and atherosclerosis but not with metabolic syndrome or adipokines in humans.Design and methods  We examined the association of three resistin polymorphisms, –852A>G, –420C>G and +157C>T, and related haplotypes with plasma resistin, cytokines, C-reactive protein (CRP), adipokines, plasma lipoproteins, metabolic syndrome and coronary artery calcification (CAC) in nondiabetic Caucasians (n = 851). Results  Resistin levels were higher, dose-dependently, with the –420G allele (CC 5·9 ± 2·7 ng/ml, GC 6·5 ± 4·0 ng/ml and GG 7·2 ± 4·8 ng/ml, trend P = 0·04) after age and gender adjustment [fold higher for GC + GG vs. CC; 1·07 (1·00–1·15), P < 0·05)]. The –852A>G single nucleotide polymorphism (SNP) was associated with higher soluble tumour necrosis factor-receptor 2 (sol-TNFR2) levels in fully adjusted models [1·06 (95% CI 1·01–1·11), P = 0·01)]. The estimated resistin haplotype (GGT) was associated with sol-TNFR2 (P = 0·04) and the AGT haplotype was related to CRP (P = 0·04) in the fully adjusted models. Resistin SNPs and haplotypes were not associated with body mass index (BMI), fasting glucose, insulin resistance, metabolic syndrome, adipokines or CAC scores. Conclusions  Despite modest associations with plasma resistin and inflammatory biomarkers, resistin 5′ variants were not associated with metabolic parameters or coronary calcification. This suggests that resistin is an inflammatory cytokine in humans but has little influence on adiposity, metabolic syndrome or atherosclerosis.

Ring signatures: Stronger definitions, and constructions without random oracles - Bender,A.; Katz, Jonathan; Morselli,R. (Journal of Cryptology, 2009)
Ring signatures, first introduced by Rivest, Shamir, and Tauman, enable a user to sign a message so that a ring of possible signers (of which the user is a member) is identified, without revealing exactly which member of that ring actually generated the signature. In contrast to group signatures, ring signatures are completely “ad-hoc” and do not require any central authority or coordination among the various users (indeed, users do not even need to be aware of each other); furthermore, ring signature schemes grant users fine-grained control over the level of anonymity associated with any particular signature.This paper has two main areas of focus. First, we examine previous definitions of security for ring signature schemes and suggest that most of these prior definitions are too weak, in the sense that they do not take into account certain realistic attacks. We propose new definitions of anonymity and unforgeability which address these threats, and give separation results proving that our new notions are strictly stronger than previous ones. Second, we show the first constructions of ring signature schemes in the standard model. One scheme is based on generic assumptions and satisfies our strongest definitions of security. Two additional schemes are more efficient, but achieve weaker security guarantees and more limited functionality.

RNA Colony Blot Hybridization Method for Enumeration of Culturable Vibrio Cholerae and Vibrio Mimicus Bacteria - Grim,Christopher J.; Zo,Young-Gun; Hasan,Nur A.; Ali,Afsar; Chowdhury,Wasimul B.; Islam,Atiqul; Rashid,Mohammed H.; Alam,Munirul; Morris,J. Glenn; Huq,Anwar; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2009)
A species-specific RNA colony blot hybridization protocol was developed for enumeration of culturable Vibrio cholerae and Vibrio mimicus bacteria in environmental water samples. Bacterial colonies on selective or nonselective plates were lysed by sodium dodecyl sulfate, and the lysates were immobilized on nylon membranes. A fluorescently labeled oligonucleotide probe targeting a phylogenetic signature sequence of 16S rRNA of V. cholerae and V. mimicus was hybridized to rRNA molecules immobilized on the nylon colony lift blots. The protocol produced strong positive signals for all colonies of the 15 diverse V. cholerae-V. mimicus strains tested, indicating 100% sensitivity of the probe for the targeted species. For visible colonies of 10 nontarget species, the specificity of the probe was calculated to be 90% because of a weak positive signal produced by Grimontia (Vibrio) hollisae, a marine bacterium. When both the sensitivity and specificity of the assay were evaluated using lake water samples amended with a bioluminescent V. cholerae strain, no false-negative or false-positive results were found, indicating 100% sensitivity and specificity for culturable bacterial populations in freshwater samples when G. hollisae was not present. When the protocol was applied to laboratory microcosms containing V. cholerae attached to live copepods, copepods were found to carry approximately 10,000 to 50,000 CFU of V. cholerae per copepod. The protocol was also used to analyze pond water samples collected in an area of cholera endemicity in Bangladesh over a 9-month period. Water samples collected from six ponds demonstrated a peak in abundance of total culturable V. cholerae bacteria 1 to 2 months prior to observed increases in pathogenic V. cholerae and in clinical cases recorded by the area health clinic. The method provides a highly specific and sensitive tool for monitoring the dynamics of V. cholerae in the environment. The RNA blot hybridization protocol can also be applied to detection of other gram-negative bacteria for taxon-specific enumeration.

Scene it or not? incremental multiple kernel learning for object detection - Kembhavi,A.; Siddiquie,B.; Miezianko,R.; McCloskey,S.; Davis, Larry S.; Schwartz, W.R.; Harwood,D.; Gupta,A.; Farrell,R.; Luo,Y.; others (Proceedings of the International Conference on Computer Vision, 2009)

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints - Anil Kumar,V.; Marathe,Madhav; Parthasarathy,Srinivasan; Srinivasan, Aravind (Algorithmica, 2009)
We present polylogarithmic approximations for the R | prec | C max and R | prec |∑ j w j C j problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind . We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment—this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion + dilation”, as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–632, 1994 ). The first step in our algorithm for the R | prec | C max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function.

Sikuli: using GUI screenshots for search and automation - Tom Yeh; Chang,Tsung-Hsiang; Miller,Robert C. (Proceedings of the 22nd annual ACM symposium on User interface software and technology, 2009)
We present Sikuli, a visual approach to search and automation of graphical user interfaces using screenshots. Sikuli allows users to take a screenshot of a GUI element (such as a toolbar button, icon, or dialog box) and query a help system using the screenshot instead of the element's name. Sikuli also provides a visual scripting API for automating GUI interactions, using screenshot patterns to direct mouse and keyboard events. We report a web-based user study showing that searching by screenshot is easy to learn and faster to specify than keywords. We also demonstrate several automation tasks suitable for visual scripting, such as map navigation and bus tracking, and show how visual scripting can improve interactive help systems previously proposed in the literature.
Keywords: Automation; image search; online help

Simple, Black-Box Constructions of Adaptively Secure Protocols - Choi, Seung Geol; Dana Dachman-Soled; Malkin, Tal; Wee, Hoeteck (Theory of Cryptography, 2009)
We present a compiler for transforming an oblivious transfer (OT) protocol secure against an adaptive semi-honest adversary into one that is secure against an adaptive malicious adversary. Our compiler achieves security in the universal composability framework, assuming access to an ideal commitment functionality, and improves over previous work achieving the same security guarantee in two ways: it uses black-box access to the underlying protocol and achieves a constant multiplicative overhead in the round complexity. As a corollary, we obtain the first constructions of adaptively secure protocols in the stand-alone model using black-box access to a low-level primitive.
Keywords: Algorithm Analysis and Problem Complexity; computers and society; Data Encryption; Discrete Mathematics in Computer Science; Management of Computing and Information Systems; Systems and Data Security

Space-time tradeoffs for approximate nearest neighbor searching - Arya,Sunil; Malamatos,Theocharis; Mount, Dave (Journal of the ACM (JACM), 2009)
Nearest neighbor searching is the problem of preprocessing a set of n point points in d-dimensional space so that, given any query point q, it is possible to report the closest point to q rapidly. In approximate nearest neighbor searching, a parameter ϵ > 0 is given, and a multiplicative error of (1 + ϵ) is allowed. We assume that the dimension d is a constant and treat n and ϵ as asymptotic quantities. Numerous solutions have been proposed, ranging from low-space solutions having space O(n) and query time O(log n + 1/ϵd−1) to high-space solutions having space roughly O((n log n)/ϵd) and query time O(log (n/ϵ)). We show that there is a single approach to this fundamental problem, which both improves upon existing results and spans the spectrum of space-time tradeoffs. Given a tradeoff parameter γ, where 2 ≤ γ ≤ 1/ϵ, we show that there exists a data structure of space O(nγd−1 log(1/ϵ)) that can answer queries in time O(log(nγ) + 1/(ϵγ)(d−1)/2. When γ = 2, this yields a data structure of space O(n log (1/ϵ)) that can answer queries in time O(log n + 1/ϵ(d−1)/2). When γ = 1/ϵ, it provides a data structure of space O((n/ϵd−1)log(1/ϵ)) that can answer queries in time O(log(n/ϵ)). Our results are based on a data structure called a (t,ϵ)-AVD, which is a hierarchical quadtree-based subdivision of space into cells. Each cell stores up to t representative points of the set, such that for any query point q in the cell at least one of these points is an approximate nearest neighbor of q. We provide new algorithms for constructing AVDs and tools for analyzing their total space requirements. We also establish lower bounds on the space complexity of AVDs, and show that, up to a factor of O(log (1/ϵ)), our space bounds are asymptotically tight in the two extremes, γ = 2 and γ = 1/ϵ.
Keywords: nearest neighbor searching; space-time tradeoffs

Sparse representation of cast shadows via ℓ1-regularized least squares - Mei,Xue; Ling,Haibin; Jacobs, David W. (Computer Vision, 2009 IEEE 12th International Conference on, 2009)
Scenes with cast shadows can produce complex sets of images. These images cannot be well approximated by low-dimensional linear subspaces. However, in this paper we show that the set of images produced by a Lambertian scene with cast shadows can be efficiently represented by a sparse set of images generated by directional light sources. We first model an image with cast shadows as composed of a diffusive part (without cast shadows) and a residual part that captures cast shadows. Then, we express the problem in an #x2113;1-regularized least squares formulation, with nonnegativity constraints. This sparse representation enjoys an effective and fast solution, thanks to recent advances in compressive sensing. In experiments on both synthetic and real data, our approach performs favorably in comparison to several previously proposed methods.
Keywords: #x2113; 1-regularized; approximations; lighting; formulation; Lambertian; least; representation; image; representation; least; scene; cast; sensing; sparse; shadows; compressive; squares

Speaking through pictures: images vs. icons - Ma,Xiaojuan; Jordan Boyd-Graber; Nikolova,Sonya; Cook,Perry R. (Proceedings of the 11th international ACM SIGACCESS conference on Computers and accessibility, 2009)
People with aphasia, a condition that impairs the ability to understand or generate written or spoken language, are aided by assistive technology that helps them communicate through a vocabulary of icons. These systems are akin to language translation systems, translating icon arrangements into spoken or written language and vice versa. However, these icon-based systems have little vocabulary breadth or depth, making it difficult for people with aphasia to apply their usage to multiple real world situations. Pictures from the web are numerous, varied, and easily accessible and thus, could potentially address the small size issues of icon-based systems. We present results from two studies that investigate this potential and demonstrate that images can be as effective as icons when used as a replacement for English language communication. The first study uses elderly subjects to investigate the efficacy of images vs. icons in conveying word meaning; the second study examines the retention of word-level meaning by both images and icons with a population of aphasics. We conclude that images collected from the web are as functional as icons in conveying information and thus, are feasible to use in assistive technology that supports people with aphasia.
Keywords: aphasia; computerized visual communication (C-VIC); visual communication (VIC)

Symbolic-to-statistical hybridization: extending generation-heavy machine translation - Habash,Nizar; Dorr, Bonnie J; Monz,Christof (Machine Translation, 2009)
The last few years have witnessed an increasing interest in hybridizing surface-based statistical approaches and rule-based symbolic approaches to machine translation (MT). Much of that work is focused on extending statistical MT systems with symbolic knowledge and components. In the brand of hybridization discussed here, we go in the opposite direction: adding statistical bilingual components to a symbolic system. Our base system is Generation-heavy machine translation (GHMT), a primarily symbolic asymmetrical approach that addresses the issue of Interlingual MT resource poverty in source-poor/target-rich language pairs by exploiting symbolic and statistical target-language resources. GHMT’s statistical components are limited to target-language models, which arguably makes it a simple form of a hybrid system . We extend the hybrid nature of GHMT by adding statistical bilingual components. We also describe the details of retargeting it to Arabic–English MT. The morphological richness of Arabic brings several challenges to the hybridization task. We conduct an extensive evaluation of multiple system variants. Our evaluation shows that this new variant of GHMT—a primarily symbolic system extended with monolingual and bilingual statistical components—has a higher degree of grammaticality than a phrase-based statistical MT system, where grammaticality is measured in terms of correct verb-argument realization and long-distance dependency translation.

A synthesis for exactly 3-edge-connected graphs - Kingsford, Carl; Marçais,G. (Arxiv preprint arXiv:0905.1053, 2009)

System and method for fast illumination-invariant background subtraction ... - Lim,Ser-Nam; Mittal,Anurag; Davis, Larry S. (2009)
A method for eliminating errors in foreground object detection in digitized images comprises providing a reference camera and a secondary camera, vertically aligning each said camera with a baseline that is approximately perpendicular to a ground plane, wherein said reference camera is placed lower than said secondary camera, selecting a foreground pixel in a reference view of a first point in a foreground object, finding a conjugate pixel of the foreground pixel in a secondary view, using the foreground and conjugate pixels to determine an image base pixel of a base point in the reference view, wherein said base point is a point on the ground plane below the first point, and using the foreground and image base pixels to find a location where the ground plane is first visible.

System and Method for Spatio-Temporal-Context Aware Interaction of Users ... - Agrawala, Ashok K.; Varshney, Amitabh; Almazan,Christian B. (2009)
A multifunctional interaction system which is capable of spatio-temporal context localization of users and of communication of audio/video streams to an entity of interest defined by the user, includes a communication domain supporting a predefined localization service, a server associated with the communication domain, client devices, and a dynamically changing context database which is customized in accord with the dynamics of interaction sessions of client devices with the server. The client communicates with the system to either request services therefrom or to send a message to the entity of interest. The system is provided with a panic alert mechanism which, upon actuation, transmits an audio/video data stream along with the client location tag, time stamp, and client ID, to a police precinct for prompt action.

Temporal Summaries: Supporting Temporal Categorical Searching, Aggregation and Comparison - Wang,T. D; Plaisant, Catherine; Shneiderman, Ben; Spring, Neil; Roseman,D.; Marchand,G.; Mukherjee,V.; Smith,M. (Visualization and Computer Graphics, IEEE Transactions on, 2009)
When analyzing thousands of event histories, analysts often want to see the events as an aggregate to detect insights and generate new hypotheses about the data. An analysis tool must emphasize both the prevalence and the temporal ordering of these events. Additionally, the analysis tool must also support flexible comparisons to allow analysts to gather visual evidence. In a previous work, we introduced align, rank, and filter (ARF) to accentuate temporal ordering. In this paper, we present temporal summaries, an interactive visualization technique that highlights the prevalence of event occurrences. Temporal summaries dynamically aggregate events in multiple granularities (year, month, week, day, hour, etc.) for the purpose of spotting trends over time and comparing several groups of records. They provide affordances for analysts to perform temporal range filters. We demonstrate the applicability of this approach in two extensive case studies with analysts who applied temporal summaries to search, filter, and look for patterns in electronic health records and academic records.
Keywords: Automated; Thrombocytopenia; Time Factors; Computerized; Pattern Recognition; Factual; Heparin; Humans; Medical Records Systems; interactive visualization technique; temporal categorical searching; temporal ordering; temporal summaries; data visualisation; human computer interaction; Computational Biology; Computer Graphics; Databases

Temporal Summaries: Supporting Temporal Categorical Searching, Aggregation and Comparison - Wang,T. D; Plaisant, Catherine; Shneiderman, Ben; Spring, Neil; Roseman,D.; Marchand,G.; Mukherjee,V.; Smith,M. (IEEE Transactions on Visualization and Computer Graphics, 2009)
When analyzing thousands of event histories, analysts often want to see the events as an aggregate to detect insights and generate new hypotheses about the data. An analysis tool must emphasize both the prevalence and the temporal ordering of these events. Additionally, the analysis tool must also support flexible comparisons to allow analysts to gather visual evidence. In a previous work, we introduced align, rank, and filter (ARF) to accentuate temporal ordering. In this paper, we present temporal summaries, an interactive visualization technique that highlights the prevalence of event occurrences. Temporal summaries dynamically aggregate events in multiple granularities (year, month, week, day, hour, etc.) for the purpose of spotting trends over time and comparing several groups of records. They provide affordances for analysts to perform temporal range filters. We demonstrate the applicability of this approach in two extensive case studies with analysts who applied temporal summaries to search, filter, and look for patterns in electronic health records and academic records.
Keywords: Aggregates; Collaborative work; Computational Biology; Computer Graphics; Data analysis; data visualisation; Data visualization; Databases, Factual; Displays; Event detection; Filters; Heparin; History; Human computer interaction; Human-computer interaction; HUMANS; Information Visualization; Interaction design; interactive visualization technique; Medical Records Systems, Computerized; Pattern Recognition, Automated; Performance analysis; Springs; temporal categorical data visualization; temporal categorical searching; temporal ordering; temporal summaries; Thrombocytopenia; Time factors

TER-Plus: paraphrase, semantic, and alignment enhancements to Translation Edit Rate - Snover,Matthew; Madnani,Nitin; Dorr, Bonnie J; Schwartz,Richard (Machine Translation, 2009)
This paper describes a new evaluation metric, TER-Plus (TERp) for automatic evaluation of machine translation (MT). TERp is an extension of Translation Edit Rate (TER). It builds on the success of TER as an evaluation metric and alignment tool and addresses several of its weaknesses through the use of paraphrases, stemming, synonyms, as well as edit costs that can be automatically optimized to correlate better with various types of human judgments. We present a correlation study comparing TERp to BLEU, METEOR and TER, and illustrate that TERp can better evaluate translation adequacy.

TESTING EVENT-DRIVEN SOFTWARE–THE NEXT QA CHALLENGE? - Memon, Atif M. (Software Engineering and DevelopmentSoftware Engineering and Development, 2009)
A particular class of software that is fast becoming ubiquitous is event-driven software(EDS). All EDS share a common event-driven model–they take sequences of events (eg, messages, mouse-clicks) as input, change their state, and (sometimes) output an event sequence. Examples include web applications, graphical user interfaces (GUIs), network protocols, device drivers, and embedded software. Quality assurance tasks such as testing have become important for EDS since they are being used in critical applications. Numerous researchers have shown that existing testing techniques do not apply directly to EDS because of the new challenges that EDS offer. This column lists some of these challenges and emphasizes on the need to develop new techniques (or enhance existing ones) to test EDS.

Testing graphical user interfaces - Strecker,J.; Memon, Atif M. (Encyclopedia of Information Science and Technology, 2009)

Three genomes from the phylum Acidobacteria provide insight into the lifestyles of these microorganisms in soils. - Ward, Naomi L; Challacombe, Jean F; Janssen, Peter H; Henrissat, Bernard; Coutinho, Pedro M; Wu, Martin; Xie, Gary; Haft, Daniel H; Sait, Michelle; Badger, Jonathan; Barabote, Ravi D; Bradley, Brent; et al. (Appl Environ Microbiol, 2009)
The complete genomes of three strains from the phylum Acidobacteria were compared. Phylogenetic analysis placed them as a unique phylum. They share genomic traits with members of the Proteobacteria, the Cyanobacteria, and the Fungi. The three strains appear to be versatile heterotrophs. Genomic and culture traits indicate the use of carbon sources that span simple sugars to more complex substrates such as hemicellulose, cellulose, and chitin. The genomes encode low-specificity major facilitator superfamily transporters and high-affinity ABC transporters for sugars, suggesting that they are best suited to low-nutrient conditions. They appear capable of nitrate and nitrite reduction but not N(2) fixation or denitrification. The genomes contained numerous genes that encode siderophore receptors, but no evidence of siderophore production was found, suggesting that they may obtain iron via interaction with other microorganisms. The presence of cellulose synthesis genes and a large class of novel high-molecular-weight excreted proteins suggests potential traits for desiccation resistance, biofilm formation, and/or contribution to soil structure. Polyketide synthase and macrolide glycosylation genes suggest the production of novel antimicrobial compounds. Genes that encode a variety of novel proteins were also identified. The abundance of acidobacteria in soils worldwide and the breadth of potential carbon use by the sequenced strains suggest significant and previously unrecognized contributions to the terrestrial carbon cycle. Combining our genomic evidence with available culture traits, we postulate that cells of these isolates are long-lived, divide slowly, exhibit slow metabolic rates under low-nutrient conditions, and are well equipped to tolerate fluctuations in soil hydration.
Keywords: Anti-Bacterial Agents; bacteria; Biological Transport; Carbohydrate Metabolism; Cyanobacteria; DNA, Bacterial; Fungi; Genome, Bacterial; Macrolides; Molecular Sequence Data; Nitrogen; Phylogeny; Proteobacteria; Sequence Analysis, DNA; sequence homology; Soil Microbiology

Together, Rpn10 and Dsk2 Can Serve as a Polyubiquitin Chain-Length Sensor - Zhang,Daoning; Chen,Tony; Ziv,Inbal; Rosenzweig,Rina; Matiuhin,Yulia; Bronner,Vered; Glickman,Michael H.; Fushman, David (Molecular Cell, 2009)
SummaryAs a signal for substrate targeting, polyubiquitin meets various layers of receptors upstream to the 26S proteasome. We obtained structural information on two receptors, Rpn10 and Dsk2, alone and in complex with (poly)ubiquitin or with each other. A hierarchy of affinities emerges with Dsk2 binding monoubiquitin tighter than Rpn10 does, whereas Rpn10 prefers the ubiquitin-like domain of Dsk2 to monoubiquitin, with increasing affinities for longer polyubiquitin chains. We demonstrated the formation of ternary complexes of both receptors simultaneously with (poly)ubiquitin and found that, depending on the ubiquitin chain length, the orientation of the resulting complex is entirely different, providing for alternate signals. Dynamic rearrangement provides a chain-length sensor, possibly explaining how accessibility of Dsk2 to the proteasome is limited unless it carries a properly tagged cargo. We propose a mechanism for a malleable ubiquitin signal that depends both on chain length and combination of receptors to produce tetraubiquitin as an efficient signal threshold.
Keywords: Proteins; signaling

Toward reconstructing the evolution of advanced moths and butterflies (Lepidoptera: Ditrysia): an initial molecular study - Regier,J. C; Zwick,A.; Cummings, Michael P.; Kawahara,A. Y; Cho,S.; Weller,S.; Roe,A.; Baixeras,J.; Brown,J. W; Parr,C.; Davis,DR; Epstein,M; et al. (BMC Evol Biol, 2009)
BACKGROUND: In the mega-diverse insect order Lepidoptera (butterflies and moths; 165,000 described species), deeper relationships are little understood within the clade Ditrysia, to which 98% of the species belong. To begin addressing this problem, we tested the ability of five protein-coding nuclear genes (6.7 kb total), and character subsets therein, to resolve relationships among 123 species representing 27 (of 33) superfamilies and 55 (of 100) families of Ditrysia under maximum likelihood analysis. RESULTS: Our trees show broad concordance with previous morphological hypotheses of ditrysian phylogeny, although most relationships among superfamilies are weakly supported. There are also notable surprises, such as a consistently closer relationship of Pyraloidea than of butterflies to most Macrolepidoptera. Monophyly is significantly rejected by one or more character sets for the putative clades Macrolepidoptera as currently defined (P < 0.05) and Macrolepidoptera excluding Noctuoidea and Bombycoidea sensu lato (P < or = 0.005), and nearly so for the superfamily Drepanoidea as currently defined (P < 0.08). Superfamilies are typically recovered or nearly so, but usually without strong support. Relationships within superfamilies and families, however, are often robustly resolved. We provide some of the first strong molecular evidence on deeper splits within Pyraloidea, Tortricoidea, Geometroidea, Noctuoidea and others.Separate analyses of mostly synonymous versus non-synonymous character sets revealed notable differences (though not strong conflict), including a marked influence of compositional heterogeneity on apparent signal in the third codon position (nt3). As available model partitioning methods cannot correct for this variation, we assessed overall phylogeny resolution through separate examination of trees from each character set. Exploration of "tree space" with GARLI, using grid computing, showed that hundreds of searches are typically needed to find the best-feasible phylogeny estimate for these data. CONCLUSION: Our results (a) corroborate the broad outlines of the current working phylogenetic hypothesis for Ditrysia, (b) demonstrate that some prominent features of that hypothesis, including the position of the butterflies, need revision, and (c) resolve the majority of family and subfamily relationships within superfamilies as thus far sampled. Much further gene and taxon sampling will be needed, however, to strongly resolve individual deeper nodes.

Towards Dynamic Adaptive Automated Test Generation for Graphical User Interfaces - Xun Yuan; Cohen,M. B; Memon, Atif M. (Software Testing, Verification and Validation Workshops, 2009. ICSTW '09. International Conference on, 2009)
Graphical user interfaces (GUIs) present an enormous number of potential event sequences to users. During testing it is necessary to cover this space, however the complexity of modern GUIs has made this an increasingly difficult task. Our past work has demonstrated that it is important to incorporate "context” into GUI test cases, in terms of event combinations, event sequence length, and by considering all possible starting and ending positions for each event. Despite the use of our most refined modeling techniques, many of the generated test cases remain unexecutable. In this paper, we posit that due to the dynamic state-based nature of GUIs, it is important to incorporate feedback from the execution of tests into test case generation algorithms. We propose the use of an evolutionary algorithm to generate test suites with fewer unexecutable test cases and higher event interaction coverage.
Keywords: adaptive automated test generation; computational complexity; event sequence length; evolutionary algorithm; evolutionary computation; graphical user interface; Graphical user interfaces; GUI test case; program testing

Triangle Inequality and Routing Policy Violations in the Internet - Lumezanu,Cristian; Baden,Randy; Spring, Neil; Bhattacharjee, Bobby (Passive and Active Network MeasurementPassive and Active Network Measurement, 2009)
Triangle inequality violations (TIVs) are the effect of packets between two nodes being routed on the longer direct path between them when a shorter detour path through an intermediary is available. TIVs are a natural, widespread and persistent consequence of Internet routing policies. By exposing opportunities to improve the delay between two nodes, TIVs can help myriad applications that seek to minimize end-to-end latency. However, sending traffic along the detour paths revealed by TIVs may influence Internet routing negatively. In this paper we study the interaction between triangle inequality violations and policy routing in the Internet. We use measured and predicted AS paths between Internet nodes to show that 25% of the detour paths exposed by TIVs are in fact available to BGP but are simply deemed “less efficient”. We also compare the AS paths of detours and direct paths and find that detours use AS edges that are rarely followed by default Internet paths, while avoiding others that BGP seems to prefer. Our study is important both for understanding the various interactions that occur at the routing layer as well as their effects on applications that seek to use TIVs to minimize latency.
Keywords: Computer; Science

Two Alternatively Spliced Isoforms of the Arabidopsis SR45 Protein Have Distinct Roles during Normal Plant Development - Zhang,Xiao-Ning; Mount, Stephen M. (Plant PhysiologyPlant Physiol., 2009)
The serine-arginine-rich (SR) proteins constitute a conserved family of pre-mRNA splicing factors. In Arabidopsis (Arabidopsis thaliana), they are encoded by 19 genes, most of which are themselves alternatively spliced. In the case of SR45, the use of alternative 3′ splice sites 21 nucleotides apart generates two alternatively spliced isoforms. Isoform 1 (SR45.1) has an insertion relative to isoform 2 (SR45.2) that replaces a single arginine with eight amino acids (TSPQRKTG). The biological implications of SR45 alternative splicing have been unclear. A previously described loss-of-function mutant affecting both isoforms, sr45-1, shows several developmental defects, including defects in petal development and root growth. We found that the SR45 promoter is highly active in regions with actively growing and dividing cells. We also tested the ability of each SR45 isoform to complement the sr45-1 mutant by overexpression of isoform-specific green fluorescent protein (GFP) fusion proteins. As expected, transgenic plants overexpressing either isoform displayed both nuclear speckles and GFP fluorescence throughout the nucleoplasm. We found that SR45.1-GFP complements the flower petal phenotype, but not the root growth phenotype. Conversely, SR45.2-GFP complements root growth but not floral morphology. Mutation of a predicted phosphorylation site within the alternatively spliced segment, SR45.1-S219A-GFP, does not affect complementation. However, a double mutation affecting both serine-219 and the adjacent threonine-218 (SR45.1-T218A + S219A-GFP) behaves like isoform 2, complementing the root but not the floral phenotype. In conclusion, our study provides evidence that the two alternatively spliced isoforms of SR45 have distinct biological functions.

UbiGreen: investigating a mobile tool for tracking and supporting green transportation habits - Jon Froehlich; Dillahunt,Tawanna; Klasnja,Predrag; Mankoff,Jennifer; Consolvo,Sunny; Harrison,Beverly; Landay,James A. (Proceedings of the 27th international conference on Human factors in computing systems, 2009)
Keywords: ambient displays; mobile phones; sensing; Sustainability; transportation; ubicomp

A unified approach to scheduling on unrelated parallel machines - Kumar,V. S. Anil; Marathe,Madhav V.; Parthasarathy,Srinivasan; Srinivasan, Aravind (J. ACM, 2009)
We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. This algorithm leads to the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria; (ii) better-than-two approximation guarantees for scheduling to minimize the Lp norm of the vector of machine-loads, for all 1 < p < ∞; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and any given collection of integer Lp norms. Our algorithm has a natural interpretation as a melding of linear-algebraic and probabilistic approaches. Via this view, it yields a common generalization of rounding theorems due to Karp et al. [1987] and Shmoys & Tardos [1993], and leads to improved approximation algorithms for the problem of scheduling with resource-dependent processing times introduced by Grigoriev et al. [2007].
Keywords: Approximation algorithms; Randomized rounding; scheduling under multiple criteria

The University of Maryland statistical machine translation system for the Fourth Workshop on Machine Translation - Dyer,C.; Setiawan,H.; Marton,Y.; Resnik, Philip (Proceedings of the Fourth Workshop on Statistical Machine Translation, 2009)

An unsupervised learning method for representing simple sentences - Monner,D.; Reggia, James A. (Neural Networks, 2009. IJCNN 2009. International Joint Conference on, 2009)

Using citations to generate surveys of scientific paradigms - Mohammad,Saif; Dorr, Bonnie J; Egan,Melissa; Hassan,Ahmed; Muthukrishan,Pradeep; Qazvinian,Vahed; Radev,Dragomir; Zajic, David (Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2009)
The number of research publications in various disciplines is growing exponentially. Researchers and scientists are increasingly finding themselves in the position of having to quickly understand large amounts of technical material. In this paper we present the first steps in producing an automatically generated, readily consumable, technical survey. Specifically we explore the combination of citation information and summarization techniques. Even though prior work (Teufel et al., 2006) argues that citation text is unsuitable for summarization, we show that in the framework of multi-document survey creation, citation texts can play a crucial role.

Using GUI Run-Time State as Feedback for Test Automation - Xun Yuan; Memon, Atif M. (Computer Science Research Works, University of Maryland, College Park, 2009)
Graphical user interfaces (GUIs) are the sole mode of interactionbetween end-users and back-end code for almost all of today's software applications. Because of this strategic role of GUIs, their quality has become important. During GUI testing, test cases---modeled as sequences of user events---sample the vast input space of all possible sequences with the goal of detecting faults; for effective testing, it is important to sample this space carefully. Existing techniques either sample manually or employ manually constructed abstract models---the abstraction and/or subsequent test-case generation algorithms enable sampling. This report presents an alternative approach to GUI testing -- it's focus is on developing a fully automatic model-driven technique to generate GUI test cases. The technique is novel in that it uses feedback from the execution of a ``seed test suite'' on a GUI. The seed suite is generated automatically using an existing structural event-interaction graph (EIG) model of the GUI. During its execution, the run-time effect of each GUI event on all other events pinpoints new important event-semantic interaction (ESI) relationships between them, which are used to automatically create an ESI graph (ESIG) model and generate new test cases. Together with a reverse-engineering algorithm used to obtain the EIG, seed suite, ESIG, and new test cases, the feedback-based technique yields a fully automatic, end-to-end GUI testing process.
Keywords: GUI testing; Software testing; test automation; test-case generation

Using reverse engineering for automated usability evaluation of GUI-based applications - Memon, Atif M. (Human-Centered Software Engineering, 2009)
Graphical user interfaces (GUIs) are important parts of today’s software and their usability ensures the usefulness of the overall software. A popular technique to check the usability of GUIs is by performing usability evaluations either manually or automatically using tools. While manual evaluation is resource intensive, performing automatic usability evaluation usually involves the creation of a model of the GUI, a significant resource-intensive step that intimidates many practitioners and prevents the application of the automated techniques. This chapter presents “GUI ripping,” a new process that automatically recovers models of the GUI by dynamically “traversing” all its windows and extracting all the widgets, properties, and values. The usefulness of this process is demonstrated by recovering a structural model called a GUI forest and dynamic models called event-flow graphs and integration trees. Results of case studies show that GUI ripping is effective and requires very little human intervention.

Using Satellite Images of Environmental Changes to Predict Infectious Disease Outbreaks - Ford,Timothy E.; Rita R Colwell; Rose,Joan B.; Morse,Stephen S.; Rogers,David J.; Yates,Terry L. (Emerging Infectious DiseasesEmerg Infect Dis, 2009)
A strong global satellite imaging system is essential for predicting outbreaks., Recent events clearly illustrate a continued vulnerability of large populations to infectious diseases, which is related to our changing human-constructed and natural environments. A single person with multidrug-resistant tuberculosis in 2007 provided a wake-up call to the United States and global public health infrastructure, as the health professionals and the public realized that today’s ease of airline travel can potentially expose hundreds of persons to an untreatable disease associated with an infectious agent. Ease of travel, population increase, population displacement, pollution, agricultural activity, changing socioeconomic structures, and international conflicts worldwide have each contributed to infectious disease events. Today, however, nothing is larger in scale, has more potential for long-term effects, and is more uncertain than the effects of climate change on infectious disease outbreaks, epidemics, and pandemics. We discuss advances in our ability to predict these events and, in particular, the critical role that satellite imaging could play in mounting an effective response.

Validating Automotive Control Software Using Instrumentation-Based Verification - Ray,Arnab; Morschhaeuser,Iris; Ackermann,Chris; Cleaveland, Rance; Shelton,Charles; Martin,Chris (Automated Software Engineering, International Conference on, 2009)
This paper discusses the results of an application of a formally based verification technique, called Instrumentation-Based Verification (IBV), to a production automotive lighting controller. The goal of the study is to assess, from both a tools as well as a methodological perspective, the performance of IBV in an industrial setting. The insights obtained as a result of the project include a refinement of a previously developed architecture for requirements specifications; observations about changes to model-based design workflows; insights into the role of requirements during development; and the capability of automated verification to detect inconsistencies among requirements as well as between requirements and design models.

Vehicle Speed Estimation Using Acoustic Wave Patterns - Cevher, V.; Chellapa, Rama; McClellan, J.H. (Signal Processing, IEEE Transactions on, 2009)
We estimate a vehicle's speed, its wheelbase length, and tire track length by jointly estimating its acoustic wave pattern with a single passive acoustic sensor that records the vehicle's drive-by noise. The acoustic wave pattern is determined using the vehicle's speed, the Doppler shift factor, the sensor's distance to the vehicle's closest-point-of-approach, and three envelope shape (ES) components, which approximate the shape variations of the received signal's power envelope. We incorporate the parameters of the ES components along with estimates of the vehicle engine RPM, the number of cylinders, and the vehicle's initial bearing, loudness and speed to form a vehicle profile vector. This vector provides a fingerprint that can be used for vehicle identification and classification. We also provide possible reasons why some of the existing methods are unable to provide unbiased vehicle speed estimates using the same framework. The approach is illustrated using vehicle speed estimation and classification results obtained with field data.
Keywords: acoustic; Doppler; estimation; passive; estimation; road; estimation; wheelbase; factor; acoustic; identification; vehicle; length; Doppler; length; vehicle; likelihood; patterns; envelope; processing; maximum; profile; sensor; tire; shape; maximum; shift; shift; acoustic; signal; speed; track; vector; vehicle; vehicles; wave

3D shape-encoded particle filter for object tracking and its application to human body tracking - Moon, H.; Chellapa, Rama (J. Image Video Process., 2008)
We present a nonlinear state estimation approach using particle filters, for tracking objects whose approximate 3D shapes are known. The unnormalized conditional density for the solution to the nonlinear filtering problem leads to the Zakai equation, and is realized by the weights of the particles. The weight of a particle represents its geometric and temporal fit, which is computed bottom-up from the raw image using a shape-encoded filter. The main contribution of the paper is the design of smoothing filters for feature extraction combined with the adoption of unnormalized conditional density weights. The "shape filter" has the overall form of the predicted 2D projection of the 3D model, while the cross-section of the filter is designed to collect the gradient responses along the shape. The 3D-model-based representation is designed to emphasize the changes in 2D object shape due to motion, while de-emphasizing the variations due to lighting and other imaging conditions. We have found that the set of sparse measurements using a relatively small number of particles is able to approximate the high-dimensional state distribution very effectively. As a measure to stabilize the tracking, the amount of random diffusion is effectively adjusted using a Kalman updating of the covariance matrix. For a complex problem of human body tracking, we have successfully employed constraints derived from joint angles and walking motion.

Accountable internet protocol (aip) - Andersen,David G.; Balakrishnan,Hari; Feamster, Nick; Koponen,Teemu; Moon,Daekyeong; Shenker,Scott (SIGCOMM Comput. Commun. Rev., 2008)
This paper presents AIP (Accountable Internet Protocol), a network architecture that provides accountability as a first-order property. AIP uses a hierarchy of self-certifying addresses, in which each component is derived from the public key of the corresponding entity. We discuss how AIP enables simple solutions to source spoofing, denial-of-service, route hijacking, and route forgery. We also discuss how AIP's design meets the challenges of scaling, key management, and traffic engineering.
Keywords: accountability; address; internet architecture; scalability; Security

Activity sensing in the wild: a field trial of ubifit garden - Consolvo,S.; McDonald,D.W.; Toscos,T.; Chen,M.Y.; Jon Froehlich; Harrison,B.; Klasnja,P.; LaMarca,A.; LeGrand,L.; Libby,R.; others (Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, 2008)

Advances in multilingual and multimodal information retrieval - Peters,C.; Jijkoun,V.; Mandl,T.; Müller,H.; Oard, Douglas; Peñas,A.; Santos,D. (Lecture Notes in Computer Science, 2008)

Aligning temporal data by sentinel events: discovering patterns in electronic health records - Wang,Taowei David; Plaisant, Catherine; Quinn,Alexander J.; Stanchak,Roman; Murphy,Shawn; Shneiderman, Ben (Proceedings of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, 2008)
Electronic Health Records (EHRs) and other temporal databases contain hidden patterns that reveal important cause-and-effect phenomena. Finding these patterns is a challenge when using traditional query languages and tabular displays. We present an interactive visual tool that complements query formulation by providing operations to align, rank and filter the results, and to visualize estimates of the intervals of validity of the data. Display of patient histories aligned on sentinel events (such as a first heart attack) enables users to spot precursor, co-occurring, and aftereffect events. A controlled study demonstrates the benefits of providing alignment (with a 61% speed improvement for complex tasks). A qualitative study and interviews with medical professionals demonstrates that the interface can be learned quickly and seems to address their needs.
Keywords: electronic health record; Evaluation; Information Visualization; search; temporal data; Uncertainty

Alternating GUI Test Generation and Execution - Xun Yuan; Memon, Atif M. (Practice and Research Techniques, 2008. TAIC PART '08. Testing: Academic Industrial Conference, 2008)
Users of today's software perform tasks by interacting with a graphical user interface (GUI) front-end via sequences of input events. Due to the flexibility offered by most GUIs, the number of event sequences grows exponentially with length. One ubiquitous challenge of GUI testing is to selectively generate those sequences that lead to potentially problematic states. This paper presents ALT, a new technique that generates GUI test cases in batches, by leveraging GUI run-time information from a previously run batch to obtain the next batch. Each successive batch consists of "longer" test cases that expand the state space to be explored, yet prune the "unimportant" states. The "alternating" nature of ALT allows it to enhance the next batch by leveraging certain relationships between GUI events (e.g., one enables the other, one alters the other's execution) that are revealed only at run-time and non-trivial to infer statically. An empirical study on four fielded GUI-based applications demonstrates that ALT is successful at identifying complex failure-causing interactions between GUI events.
Keywords: ALT; complex failure-causing interactions; event sequences; graphical user interface; Graphical user interfaces; GUI test generation; Testing

Applying automatically generated semantic knowledge: A case study in machine translation - Madnani,N.; Resnik, Philip; Dorr, Bonnie J; Schwartz,R. (NSF Symposium on Semantic Knowledge Discovery, Organization and Use, 2008)
In this paper, we discuss how we apply automatically generated semantic knowledge to benefit statisticalmachine translation (SMT). Currently, almost all statistical machine translation systems rely heavily on memorizing translations of phrases. Some systems attempt to go further and generalize these learned phrase translations into templates using empirically derived information about word alignments and a small amount of syntactic information, if at all. There are several issues in a SMT pipeline that could be addressed by the application of semantic knowledge, if such knowledge were easily available. One such issue, an important one, is that of reference sparsity. The fundamental problem that translation systems have to face is that there is no such thing as the correct translation for any sentence. In fact, any given source sentence can often be translated into the target language in many valid ways. Since there can be many “correct answers,” almost all models employed by SMT systems require, in addition to a large bitext, a held-out development set comprised of multiple high-quality, human-authored reference translations in the target language in order to tune their parameters relative to a translation quality metric.1 There are several reasons that this requirement is not an easy one to satisfy. First, with a few exceptions—notably NIST’s annual MT evaluations—most new MT research data sets are provided with only a single reference translation. Second, obtaining multiple reference translations in rapid development, low-density source language scenarios (e.g. (Oard, 2003)) is likely to be severely limited (or made entirely impractical) by limitations of time, cost, and ready availability of qualified translators.

Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints - Chafekar,D.; Kumart,V. S.A; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind (IEEE INFOCOM 2008. The 27th Conference on Computer Communications, 2008)
A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting.
Keywords: Algorithm design and analysis; approximation algorithm; Approximation algorithms; approximation theory; Computer networks; Computer science; graph theory; graph-based model; Interference constraints; polynomial time algorithm; Propagation losses; Protocols; radio networks; radiofrequency interference; signal to interference plus noise ratio; Signal to noise ratio; Throughput; wireless interference; wireless network; Wireless networks

Are multiple reference translations necessary? investigating the value of paraphrased reference translations in parameter optimization - Madnani,N.; Resnik, Philip; Dorr, Bonnie J; Schwartz,R. (Proceedings of the Eighth Conference of the Association for Machine Translation in the Americas, October, 2008)
Most state-of-the-art statistical machine trans-lation systems use log-linear models, which are defined in terms of hypothesis features and weights for those features. It is standard to tune the feature weights in order to maxi- mize a translation quality metric, using held- out test sentences and their corresponding ref- erence translations. However, obtaining refer- ence translations is expensive. In our earlier work (Madnani et al., 2007), we introduced a new full-sentence paraphrase technique, based on English-to-English decoding with an MT system, and demonstrated that the resulting paraphrases can be used to cut the number of human reference translations needed in half. In this paper, we take the idea a step further, asking how far it is possible to get with just a single good reference translation for each item in the development set. Our analysis suggests that it is necessary to invest in four or more hu- man translations in order to significantly im- prove on a single translation augmented by monolingual paraphrases.

Automatic online tuning for fast Gaussian summation - Morariu,V.; Srinivasan,B.V.; Raykar,V.C.; Duraiswami, Ramani; Davis, Larry S. (Advances in Neural Information Processing Systems, 2008)
Many machine learning algorithms require the summation of Gaussian kernelfunctions, an expensive operation if implemented straightforwardly. Several meth- ods have been proposed to reduce the computational complexity of evaluating such sums, including tree and analysis based methods. These achieve varying speedups depending on the bandwidth, dimension, and prescribed error, making the choice between methods difficult for machine learning tasks. We provide an algorithm that combines tree methods with the Improved Fast Gauss Transform (IFGT). As originally proposed the IFGT suffers from two problems: (1) the Taylor series expansion does not perform well for very low bandwidths, and (2) parameter se- lection is not trivial and can drastically affect performance and ease of use. We address the first problem by employing a tree data structure, resulting in four eval- uation methods whose performance varies based on the distribution of sources and targets and input parameters such as desired accuracy and bandwidth. To solve the second problem, we present an online tuning approach that results in a black box method that automatically chooses the evaluation method and its parameters to yield the best performance for the input data, desired accuracy, and bandwidth. In addition, the new IFGT parameter selection approach allows for tighter error bounds. Our approach chooses the fastest method at negligible additional cost, and has superior performance in comparisons with previous approaches.

Automatically repairing event sequence-based GUI test suites for regression testing - Memon, Atif M. (ACM Transactions on Software Engineering and Methodology (TOSEM), 2008)
Although graphical user interfaces (GUIs) constitute a large part of the software being developed today and are typically created using rapid prototyping, there are no effective regression testing techniques for GUIs. The needs of GUI regression testing differ from those of traditional software. When the structure of a GUI is modified, test cases from the original GUI's suite are either reusable or unusable on the modified GUI. Because GUI test case generation is expensive, our goal is to make the unusable test cases usable, thereby helping to retain the suite's event coverage. The idea of reusing these unusable (obsolete) test cases has not been explored before. This article shows that a large number of test cases become unusable for GUIs. It presents a new GUI regression testing technique that first automatically determines the usable and unusable test cases from a test suite after a GUI modification, then determines the unusable test cases that can be repaired so that they can execute on the modified GUI, and finally uses repairing transformations to repair the test cases. This regression testing technique along with four repairing transformations has been implemented. An empirical study for four open-source applications demonstrates that (1) this approach is effective in that many of the test cases can be repaired, and is practical in terms of its time performance, (2) certain types of test cases are more prone to becoming unusable, and (3) certain types of “dominator” events, when modified, make a large number of test cases unusable.
Keywords: Graphical user interfaces; regression testing; repairing test cases; test case management; test maintenance

Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One - Choi, Seung Geol; Dana Dachman-Soled; Malkin, Tal; Wee, Hoeteck (Theory of Cryptography, 2008)
We show how to transform any semantically secure encryption scheme into a non-malleable one, with a black-box construction that achieves a quasi-linear blow-up in the size of the ciphertext. This improves upon the previous non-black-box construction of Pass, Shelat and Vaikuntanathan (Crypto ’06). Our construction also extends readily to guarantee non-malleability under a bounded-CCA2 attack, thereby simultaneously improving on both results in the work of Cramer et al. (Asiacrypt ’07). Our construction departs from the oft-used paradigm of re-encrypting the same message with different keys and then proving consistency of encryptions; instead, we encrypt an encoding of the message with certain locally testable and self-correcting properties. We exploit the fact that low-degree polynomials are simultaneously good error-correcting codes and a secret-sharing scheme.
Keywords: Algorithm Analysis and Problem Complexity; black-box constructions; computers and society; Data Encryption; Discrete Mathematics in Computer Science; Management of Computing and Information Systems; non-malleability; public-key encryption; semantic security; Systems and Data Security

Call-Stack Coverage for GUI Test Suite Reduction - McMaster,S.; Memon, Atif M. (Software Engineering, IEEE Transactions on, 2008)
Graphical user interfaces (GUIs) are used as front ends to most of today's software applications. The event-driven nature of GUIs presents new challenges for testing. One important challenge is test suite reduction. Conventional reduction techniques/tools based on static analysis are not easily applicable due to the increased use of multilanguage GUI implementations, callbacks for event handlers, virtual function calls, reflection, and multithreading. Moreover, many existing techniques ignore code in libraries and fail to consider the context in which event handlers execute. Consequently, they yield GUI test suites with seriously impaired fault-detection abilities. This paper presents a reduction technique based on the call-stack coverage criterion. Call stacks may be collected for any executing program with very little overhead. Empirical studies in this paper compare reduction based on call-stack coverage to reduction based on line, method, and event coverage, including variations that control for the size and optional consideration of library methods. These studies show that call-stack-based reduction provides unique trade-offs between the reduction in test suite size and the loss of fault detection effectiveness, which may be valuable in practice. Additionally, an analysis of the relationship between coverage requirements and fault-revealing test cases is presented.
Keywords: call-stack coverage criterion; computer testing; Graphical user interfaces; test suite reduction

Capacity of Asynchronous Random-Access Scheduling in Wireless Networks - Chafekar,D.; Levin,D.; Kumar,V. S.A; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind (IEEE INFOCOM 2008. The 27th Conference on Computer Communications, 2008)
We study the throughput capacity of wireless networks which employ (asynchronous) random-access scheduling as opposed to deterministic scheduling. The central question we answer is: how should we set the channel-access probability for each link in the network so that the network operates close to its optimal throughput capacity? We design simple and distributed channel-access strategies for random-access networks which are provably competitive with respect to the optimal scheduling strategy, which is deterministic, centralized, and computationally infeasible. We show that the competitiveness of our strategies are nearly the best achievable via random-access scheduling, thus establishing fundamental limits on the performance of random- access. A notable outcome of our work is that random access compares well with deterministic scheduling when link transmission durations differ by small factors, and much worse otherwise. The distinguishing aspects of our work include modeling and rigorous analysis of asynchronous communication, asymmetry in link transmission durations, and hidden terminals under arbitrary link-conflict based wireless interference models.
Keywords: asynchronous random-access scheduling; channel access probability; Computer networks; Computer science; Educational institutions; Interference; Optimal scheduling; Peer to peer computing; probability; Processor scheduling; radio link; radio links; radio networks; Routing; scheduling; Throughput; throughput capacity; wireless channels; Wireless networks

On classification, ranking, and probability estimation - Flach,P.; Matsubara,E.T.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Kersting,K.; Muggleton,S. H (Internationales Begegnungs- und Forschungszentrum fur Informatik (IBFI), Schloss Dagstuhl, Germany, 2008)
Given a binary classification task, a ranker is an algorithm that can sort a set of instances from highest to lowest expectation that the instance is positive. In contrast to a classifier, a ranker does not output class predictions – although it can be turned into a classifier with help of an additional procedure to split the ranked list into two. A straightforward way to compute rankings is to train a scoring classifier to assign numerical scores to instances, for example the predicted odds that an instance is positive. However, rankings can be computed without scores, as we demonstrate in this paper. We propose a lexicographic ranker, LexRank , whose rankings are derived not from scores, but from a simple ranking of attribute values obtained from the training data. Although various metrics can be used, we show that by using the odds ratio to rank the attribute values we obtain a ranker that is conceptually close to the naive Bayes classifier, in the sense that for every instance of LexRank there exists an instance of naive Bayes that achieves the same ranking. However, the reverse is not true, which means that LexRank is more biased than naive Bayes. We systematically develop the relationships and differences between classification, ranking, and probability estimation, which leads to a novel connection between the Brier score and ROC curves. Combining LexRank with isotonic regression, which derives probability estimates from the ROC convex hull, results in the lexicographic probability estimator LexProb.

Combining Classifiers with Informational Confidence - Jaeger,Stefan; Ma,Huanfeng; David Doermann (Studies in Computational Intelligence: Machine Learning in Document Analysis and RecognitionStudies in Computational Intelligence: Machine Learning in Document Analysis and Recognition, 2008)
We propose a new statistical method for learning normalized confidence values in multiple classifier systems. Our main idea is to adjust confidence values so that their nominal values equal the information actually conveyed. In order to do so, we assume that information depends on the actual performance of each confidence value on an evaluation set. As information measure, we use Shannon's well-known logarithmic notion of information. With the confidence values matching their informational content, the classifier combination scheme reduces to the simple sum-rule, theoretically justifying this elementary combination scheme. In experimental evaluations for script identification, and both handwritten and printed character recognition, we achieve a consistent improvement on the best single recognition rate. We cherish the hope that our information-theoretical framework helps fill the theoretical gap we still experience in classifier combination, and puts the excellent practical performance of multiple classifier systems on a more solid basis.

Combining open-source with research to re-engineer a hands-on introductory NLP course - Madnani,Nitin; Dorr, Bonnie J (Proceedings of the Third Workshop on Issues in Teaching Computational Linguistics, 2008)
We describe our first attempts to re-engineer the curriculum of our introductory NLP course by using two important building blocks: (1) Access to an easy-to-learn programming language and framework to build hands-on programming assignments with real-world data and corpora and, (2) Incorporation of interesting ideas from recent NLP research publications into assignment and examination problems. We believe that these are extremely important components of a curriculum aimed at a diverse audience consisting primarily of first-year graduate students from both linguistics and computer science. Based on overwhelmingly positive student feedback, we find that our attempts were hugely successful.

Compressive wireless arrays for bearing estimation - Cevher, V.; Gurbuz, A.C.; McClellan, J.H.; Chellapa, Rama (Acoustics, Speech and Signal Processing, 2008. ICASSP 2008. IEEE International Conference on, 2008)
Joint processing of sensor array outputs improves the performance of parameter estimation and hypothesis testing problems beyond the sum of the individual sensor processing results. When the sensors have high data sampling rates, arrays are tethered, creating a disadvantage for their deployment and also limiting their aperture size. In this paper, we develop the signal processing algorithms for randomly deployable wireless sensor arrays that are severely constrained in communication bandwidth. We focus on the acoustic bearing estimation problem and show that when the target bearings are modeled as a sparse vector in the angle space, low dimensional random projections of the microphone signals can be used to determine multiple source bearings by solving an l 1-norm minimization problem. Field data results are shown where only 10 bits of information is passed from each microphone to estimate multiple target bearings.
Keywords: acoustic; algorithms; sparse; arrays; acoustic; arrays; hypothesis; bandwidth; compressive; bearing; Estimation; estimation; signal; estimation; sparse; matrices; vectors; wireless; minimization; networks; problem; communication; problem; microphone; problems; joint; PROCESSING; processing; array; processing; direction-of-arrival; processing; l1-norm; sensor; signal; signals; parameter; Testing; vector; wireless; wireless

Computational cultural dynamics - Martinez,V.; Simari,G. I; Sliva,A.; V.S. Subrahmanian (IEEE intelligent systems, 2008)

Computing word-pair antonymy - Mohammad,Saif; Dorr, Bonnie J; Hirst,Graeme (Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2008)
Knowing the degree of antonymy between words has widespread applications in natural language processing. Manually-created lexicons have limited coverage and do not include most semantically contrasting word pairs. We present a new automatic and empirical measure of antonymy that combines corpus statistics with the structure of a published thesaurus. The approach is evaluated on a set of closest-opposite questions, obtaining a precision of over 80%. Along the way, we discuss what humans consider antonymous and how antonymy manifests itself in utterances.

A Constrained Probabilistic Petri Net Framework for Human Activity Detection in Video - Albanese, M.; Chellapa, Rama; Moscato, V.; Picariello, A.; V.S. Subrahmanian; Turaga,P.; Udrea,O. (Multimedia, IEEE Transactions on, 2008)
Recognition of human activities in restricted settings such as airports, parking lots and banks is of significant interest in security and automated surveillance systems. In such settings, data is usually in the form of surveillance videos with wide variation in quality and granularity. Interpretation and identification of human activities requires an activity model that a) is rich enough to handle complex multi-agent interactions, b) is robust to uncertainty in low-level processing and c) can handle ambiguities in the unfolding of activities. We present a computational framework for human activity representation based on Petri nets. We propose an extension-Probabilistic Petri Nets (PPN)-and show how this model is well suited to address each of the above requirements in a wide variety of settings. We then focus on answering two types of questions: (i) what are the minimal sub-videos in which a given activity is identified with a probability above a certain threshold and (ii) for a given video, which activity from a given set occurred with the highest probability? We provide the PPN-MPS algorithm for the first problem, as well as two different algorithms (naive PPN-MPA and PPN-MPA) to solve the second. Our experimental results on a dataset consisting of bank surveillance videos and an unconstrained TSA tarmac surveillance dataset show that our algorithms are both fast and provide high quality results.
Keywords: activity; dataset; automated; detection; human; interactions; security; net; human; nets; image; Petri; probabilistic; processing; multiagent; processing; video; representation; low-level; representation; video; signal; Surveillance; surveillance; systems; constrained; systems; surveillance; tarmac; TSA; videos; Petri

Constraint Integration for Efficient Multiview Pose Estimation with Self-Occlusions - Gupta,A.; Mittal,A.; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2008)
Automatic initialization and tracking of human pose is an important task in visual surveillance. We present a part-based approach that incorporates a variety of constraints in a unified framework. These constraints include the kinematic constraints between parts that are physically connected to each other, the occlusion of one part by another, and the high correlation between the appearance of certain parts, such as the arms. The location probability distribution of each part is determined by evaluating appropriate likelihood measures. The graphical (nontree) structure representing the interdependencies between parts is utilized to "connect" such part distributions via nonparametric belief propagation. Methods are also developed to perform this optimization efficiently in the large space of pose configurations.
Keywords: Automated; Posture; Reproducibility of Results; Sensitivity and Specificity; Video Recording; Whole Body Imaging; automatic initialization; constraint integration; graphical structure; human pose tracking; kinematic constraint; likelihood measure; location probability distribution; multiview pose estimation; nonparametric belief propagation; optimization; pose configuration; se; Computer-Assisted; Imaging; Three-Dimensional; Pattern Recognition

CONVEX: Similarity-Based Algorithms for Forecasting Group Behavior - Martinez,V.; Simari,G. I; Sliva,A.; V.S. Subrahmanian (Intelligent Systems, IEEE, 2008)
A proposed framework for predicting a group's behavior associates two vectors with that group. The context vector tracks aspects of the environment in which the group functions; the action vector tracks the group's previous actions. Given a set of past behaviors consisting of a pair of these vectors and given a query context vector, the goal is to predict the associated action vector. To achieve this goal, two families of algorithms employ vector similarity. CONVEXk _NN algorithms use k-nearest neighbors in high-dimensional metric spaces; CONVEXMerge algorithms look at linear combinations of distances of the query vector from context vectors. Compared to past prediction algorithms, these algorithms are extremely fast. Moreover, experiments on real-world data sets show that the algorithms are highly accurate, predicting actions with well over 95-percent accuracy.
Keywords: (artificial; algorithm; action; algorithm; behavioural; algorithm; CONVEXk-NN; BEHAVIOR; computing; ontologies; CONVEXMerge; forecasting; high-dimensional; intelligence); metric; sciences; space; ontology; similarity-based; vector; context; vector; group

CrossTalk: The Journal of Defense Software Engineering. Volume 21, Number 10, October 2008 - Basili, Victor R.; Dangle,K.; Esker,L.; Marotta,F.; Rus,I.; Brosgol,B. M; Jamin,S.; Arthur,J. D; Ravichandar,R.; Wisnosky,D. E (DTIC Document, 2008)

Deciding kCFA is Complete for EXPTIME - David Van Horn; Mairson, Harry G. (ICFP '08 Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming, 2008)
We give an exact characterization of the computational complexity of the kCFA hierarchy. For any k > 0, we prove that the control flow decision problem is complete for deterministic exponential time. This theorem validates empirical observations that such control flow analysis is intractable. It also provides more general insight into the complexity of abstract interpretation.
Keywords: complexity; flow analysis

Development of a multi-piece multi-gate mold for manufacturing a flapping wing drive-mechanism - Ananthanarayanan,A.; Bejgerowski,W.; Mueller,D.; Gupta,S.K. (Transactions of North American Manufacturing Research Institution of SME, 2008)
Successful realization a flapping wing microair vehicle (MAV) requires development of a light weight drive-mechanism that can convert the continuous rotary motion to oscillatory flapping motion. Molded compliant drive-mechanisms are an attractive design option because of manufacturing scalability and reduction in the number of parts. The unique characteristics of this mechanism require development of a complex multi-piece multi-gate mold design. This paper describes a systematic approach for determining the part shape and size, optimizing the mold pieces, and placing the gates on the multi-piece mold. The novel aspects of this work include (1) selecting non-critical shape features to optimize the mold design and (2) the use of sacrificial structural elements to reduce the impact of the weld lines on the structural performance. The mold developed using our approach was utilized to realize a working flapping wing MAV.

Discrete Distortion in Triangulated 3‐Manifolds - Mesmoudi,Mohammed Mostefa; De Floriani, Leila; Port,Umberto (Computer Graphics Forum, 2008)
We introduce a novel notion, that we call discrete distortion, for a triangulated 3-manifold. Discrete distortion naturally generalizes the notion of concentrated curvature defined for triangulated surfaces and provides a powerful tool to understand the local geometry and topology of 3-manifolds. Discrete distortion can be viewed as a discrete approach to Ricci curvature for singular flat manifolds. We distinguish between two kinds of distortion, namely, vertex distortion, which is associated with the vertices of the tetrahedral mesh decomposing the 3-manifold, and bond distortion, which is associated with the edges of the tetrahedral mesh. We investigate properties of vertex and bond distortions. As an example, we visualize vertex distortion on manifold hypersurfaces in R4 defined by a scalar field on a 3D mesh. distance fields.
Keywords: I.3.3 [Computer Graphics]; I.3.5 [Computational Geometry and Object Modeling]

Distortion lower bounds for line embeddings - Mathieu, Claire; Charalampos Papamanthou (Information Processing Letters, 2008)
In this paper, we show how we can derive lower bounds and also compute the exact distortion for the line embeddings of some special metrics, especially trees and graphs with certain structure. Using linear programming to formulate a simpler version of the problem gives an interesting intuition and direction concerning the computation of general lower bounds for distortion into the line. We also show that our lower bounds on special cases of metrics are a lot better than previous lower bounds.
Keywords: combinatorial problems; Theory of computation

The draft genome of the transgenic tropical fruit tree papaya (Carica papaya Linnaeus) - Ming,R.; Hou,S.; Feng,Y.; Yu,Q.; Dionne-Laporte,A.; Saw,J.H.; Senin,P.; Wang,W.; Ly,B.V.; Lewis,K.L.T.; others (Nature, 2008)
Papaya, a fruit crop cultivated in tropical and subtropical regions, is known for its nutritional benefits and medicinal applications. Here we report a 3 draft genome sequence of 'SunUp' papaya, the first commercial virus-resistant transgenic fruit tree to be sequenced. The papaya genome is three times the size of the Arabidopsis genome, but contains fewer genes, including significantly fewer disease-resistance gene analogues. Comparison of the five sequenced genomes suggests a minimal angiosperm gene set of 13,311. A lack of recent genome duplication, atypical of other angiosperm genomes sequenced so far, may account for the smaller papaya gene number in most functional groups. Nonetheless, striking amplifications in gene number within particular functional groups suggest roles in the evolution of tree-like habit, deposition and remobilization of starch reserves, attraction of seed dispersal agents, and adaptation to tropical daylengths. Transgenesis at three locations is closely associated with chloroplast insertions into the nuclear genome, and with topoisomerase I recognition sites. Papaya offers numerous advantages as a system for fruit-tree functional genomics, and this draft genome sequence provides the foundation for revealing the basis of Carica's distinguishing morpho-physiological, medicinal and nutritional properties.

Effective and scalable software compatibility testing - Yoon,Il-Chul; Sussman, Alan; Memon, Atif M.; Porter, Adam (Proceedings of the 2008 international symposium on Software testing and analysis, 2008)
Today's software systems are typically composed of multiple components, each with different versions. Software compatibility testing is a quality assurance task aimed at ensuring that multi-component based systems build and/or execute correctly across all their versions' combinations, or configurations. Because there are complex and changing interdependencies between components and their versions, and because there are such a large number of configurations, it is generally infeasible to test all potential configurations. Consequently, in practice, compatibility testing examines only a handful of default or popular configurations to detect problems; as a result costly errors can and do escape to the field. This paper presents a new approach to compatibility testing, called Rachet. We formally model the entire configuration space for software systems and use the model to generate test plans to sample a portion of the space. In this paper, we test all direct dependencies between components and execute the test plan efficiently in parallel. We present empirical results obtained by applying our approach to two large-scale scientific middleware systems. The results show that for these systems Rachet scaled well and discovered incompatibilities between components, and that testing only direct dependences did not compromise test quality.
Keywords: component-based software system; software compatibility testing

Effective Visualization of File System Access-Control - Heitzmann, Alexander; Palazzi, Bernardo; Charalampos Papamanthou; Tamassia, Roberto (Visualization for Computer Security, 2008)
In this paper, we present a visual representation of access control permissions in a standard hierarchical file system. Our visualization of file permissions leverages treemaps, a popular graphical representation of hierarchical data. In particular, we present a visualization of access control for the NTFS file system that can help a non-expert user understand and manipulate file system permissions in a simple and effective way. While our examples are based on NTFS, our approach can be used for many other hierarchical file systems as well.
Keywords: Computer Communication Networks; Computer Imaging, Vision, Pattern Recognition and Graphics; data mining and knowledge discovery; Data Structures, Cryptology and Information Theory; Visualization

Efficient Kriging via Fast Matrix-Vector Products - Memarsadeghi,N.; Raykar,V.C.; Duraiswami, Ramani; Mount, Dave (Aerospace Conference, 2008 IEEE, 2008)
Interpolating scattered data points is a problem of wide ranging interest. Ordinary kriging is an optimal scattered data estimator, widely used in geosciences and remote sensing. A generalized version of this technique, called cokriging, can be used for image fusion of remotely sensed data. However, it is computationally very expensive for large data sets. We demonstrate the time efficiency and accuracy of approximating ordinary kriging through the use of fast matrix-vector products combined with iterative methods. We used methods based on the fast Multipole methods and nearest neighbor searching techniques for implementations of the fast matrix-vector products.
Keywords: cokriging technique; fast matrix-vector products; fast multipole methods; geophysical techniques; image fusion; Interpolation; iterative methods; nearest neighbor searching; optimal scattered data estimator; Remote sensing; remotely sensed data; scattered data points; sensor fusion; time efficiency

Efficient Kriging via Fast Matrix-Vector Products - Memarsadeghi,N.; Raykar,V.C.; Duraiswami, Ramani; Mount, Dave (Aerospace Conference, 2008 IEEE, 2008)
Interpolating scattered data points is a problem of wide ranging interest. Ordinary kriging is an optimal scattered data estimator, widely used in geosciences and remote sensing. A generalized version of this technique, called cokriging, can be used for image fusion of remotely sensed data. However, it is computationally very expensive for large data sets. We demonstrate the time efficiency and accuracy of approximating ordinary kriging through the use of fast matrix-vector products combined with iterative methods. We used methods based on the fast Multipole methods and nearest neighbor searching techniques for implementations of the fast matrix-vector products.
Keywords: cokriging; data; data; scattered; efficiency; geophysical; estimator; remotely; fusion; fusion; interpolation; iterative; matrix-vector; methods; image; methods; nearest; methods; remote; multipole; neighbor; points; time; products; fast; scattered; searching; optimal; sensed; sensing; sensor; technique; fast; techniques; iterative

Embedding and similarity search for point sets under translation - Cho,Minkyoung; Mount, Dave (Proceedings of the twenty-fourth annual symposium on Computational geometry, 2008)
Pattern matching in point sets is a well studied problem with numerous applications. We assume that the point sets may contain outliers (missing or spurious points) and are subject to an unknown translation. We define the distance between any two point sets to be the minimum size of their symmetric difference over all translations of one set relative to the other. We consider the problem in the context of similarity search. We assume that a large database of point sets is to be preprocessed so that given any query point set, the closest matches in the database can be computed efficiently. Our approach is based on showing that there is a randomized algorithm that computes a translation-invariant embedding of any point set of size at most n into the L_1 metric, so that with high probability, distances are subject to a distortion that is O(log2 n).
Keywords: EMBEDDING; point pattern matching; randomized algorithms; Similarity Search

Energy Efficient Monitoring in Sensor Networks - Deshpande, Amol; Khuller, Samir; Malekian,Azarakhsh; Toossi,Mohammed (LATIN 2008: Theoretical InformaticsLATIN 2008: Theoretical Informatics, 2008)
In this paper we study a set of problems related to efficient energy management for monitoring applications in wireless sensor networks. We study several generalizations of a basic problem called Set k -Cover, which can be described as follows: we are given a set of sensors, and a set of regions to be monitored. Each region can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots) and activate each partition in a different time-slot. The goal is to find the partitioning that maximizes the coverage of the regions. This problem is known to be NP -hard. We first develop improved approximation algorithms for this problem based on its similarities to the max k -cut problem. We then consider a variation, called Set ( k , α )-cover, where each sensor is allowed to be active in α different time-slots. We develop a randomized routing algorithm for this problem. We then consider extensions where each sensor can monitor only a bounded number of regions in any time-slot. We develop the first approximation algorithms for this problem. An experimental evaluation of the algorithms we propose can be found in the full version of the paper.

Enhancements in robust feature matching - Ratanasanya,S.; Mount, Dave; Netanyahu,N. S; Achalakul,T. (Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology, 2008. ECTI-CON 2008. 5th International Conference on, 2008)
We present in this paper a number of new enhancements to a branch-and-bound algorithm given by Mount, Netanyahu, and Le Moigne [8] for feature matching. We introduce a new distance measure, which is more robust to the presence of outliers than the previously used measure, as well as a new variant of the search algorithm and a new search strategy. We also present experimental results, which show that these enhancements offer significant tangible improvements in performance.
Keywords: branch-and-bound algorithm; distance measure; Image Enhancement; Image matching; robust feature matching; tree searching

Environmental signatures associated with cholera epidemics - Constantin de Magny,G.; Murtugudde,R.; Sapiano,M. R. P.; Nizam,A.; Brown,C. W.; Busalacchi,A. J.; Yunus,M.; Nair,G. B.; Gil,A. I.; Lanata,C. F.; Rita R Colwell (Proceedings of the National Academy of Sciences, 2008)
The causative agent of cholera, Vibrio cholerae, has been shown to be autochthonous to riverine, estuarine, and coastal waters along with its host, the copepod, a significant member of the zooplankton community. Temperature, salinity, rainfall and plankton have proven to be important factors in the ecology of V. cholerae, influencing the transmission of the disease in those regions of the world where the human population relies on untreated water as a source of drinking water. In this study, the pattern of cholera outbreaks during 1998–2006 in Kolkata, India, and Matlab, Bangladesh, and the earth observation data were analyzed with the objective of developing a prediction model for cholera. Satellite sensors were used to measure chlorophyll a concentration (CHL) and sea surface temperature (SST). In addition, rainfall data were obtained from both satellite and in situ gauge measurements. From the analyses, a statistically significant relationship between the time series for cholera in Kolkata, India, and CHL and rainfall anomalies was determined. A statistically significant one month lag was observed between CHL anomaly and number of cholera cases in Matlab, Bangladesh. From the results of the study, it is concluded that ocean and climate patterns are useful predictors of cholera epidemics, with the dynamics of endemic cholera being related to climate and/or changes in the aquatic ecosystem. When the ecology of V. cholerae is considered in predictive models, a robust early warning system for cholera in endemic regions of the world can be developed for public health planning and decision making.ecology epidemiology microbiology remote sensing

Expanding the reach of Grid computing: combining Globus- and BOINC-based systems - Myers,D. S; Bazinet,A. L; Cummings, Michael P. (Grids for Bioinformatics and Computational BiologyGrids for Bioinformatics and Computational Biology, 2008)

Exploiting Prior Knowledge in Intelligent Assistants: Combining Relational Models with Hierarchies - Natarajan,S.; Tadepalli,P.; Fern,A.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Kersting,K.; Muggleton,S. H (Probabilistic, Logical and Relational Learning - A Further Synthesis, 2008)
Statitsical relational models have been successfully used to model static probabilistic relationships between the entities of the domain. In this talk, we illustrate their use in a dynamic decison-theoretic setting where the task is to assist a user by inferring his intentional structure and taking appropriate assistive actions. We show that the statistical relational models can be used to succintly express the system's prior knowledge about the user's goal-subgoal structure and tune it with experience. As the system is better able to predict the user's goals, it improves the effectiveness of its assistance. We show through experiments that both the hierarchical structure of the goals and the parameter sharing facilitated by relational models significantly improve the learning speed.

Fast, easy, and cheap: Construction of statistical machine translation models with MapReduce - Dyer,C.; Cordova,A.; Mont,A.; Jimmy Lin (Proceedings of the Third Workshop on Statistical Machine Translation, 2008)
In recent years, the quantity of parallel train-ing data available for statistical machine trans- lation has increased far more rapidly than the performance of individual computers, re- sulting in a potentially serious impediment to progress. Parallelization of the model- building algorithms that process this data on computer clusters is fraught with challenges such as synchronization, data exchange, and fault tolerance. However, the MapReduce programming paradigm has recently emerged as one solution to these issues: a powerful functional abstraction hides system-level de- tails from the researcher, allowing programs to be transparently distributed across potentially very large clusters of commodity hardware. We describe MapReduce implementations of two algorithms used to estimate the parame- ters for two word alignment models and one phrase-based translation model, all of which rely on maximum likelihood probability esti- mates. On a 20-machine cluster, experimental results show that our solutions exhibit good scaling characteristics compared to a hypo- thetical, optimally-parallelized version of cur- rent state-of-the-art single-core tools.

Flow Analysis, Linearity, and PTIME - David Van Horn; Mairson, Harry G. (Static Analysis, 2008)
Flow analysis is a ubiquitous and much-studied component of compiler technology—and its variations abound. Amongst the most well known is Shivers’ 0CFA; however, the best known algorithm for 0CFA requires time cubic in the size of the analyzed program and is unlikely to be improved. Consequently, several analyses have been designed to approximate 0CFA by trading precision for faster computation. Henglein’s simple closure analysis, for example, forfeits the notion of directionality in flows and enjoys an “almost linear” time algorithm. But in making trade-offs between precision and complexity, what has been given up and what has been gained? Where do these analyses differ and where do they coincide? We identify a core language—the linear λ-calculus—where 0CFA, simple closure analysis, and many other known approximations or restrictions to 0CFA are rendered identical. Moreover, for this core language, analysis corresponds with (instrumented) evaluation. Because analysis faithfully captures evaluation, and because the linear λ-calculus is complete for ptime, we derive ptime-completeness results for all of these analyses.
Keywords: Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Programming Languages, Compilers, Interpreters; Programming Techniques; software engineering

Flowers or a robot army?: encouraging awareness & activity with personal, mobile displays - Consolvo,Sunny; Klasnja,Predrag; McDonald,David W.; Avrahami,Daniel; Jon Froehlich; LeGrand,Louis; Libby,Ryan; Mosher,Keith; Landay,James A. (Proceedings of the 10th international conference on Ubiquitous computing, 2008)
Personal, mobile displays, such as those on mobile phones, are ubiquitous, yet for the most part, underutilized. We present results from a field experiment that investigated the effectiveness of these displays as a means for improving awareness of daily life (in our case, self-monitoring of physical activity). Twenty-eight participants in three experimental conditions used our UbiFit system for a period of three months in their day-to-day lives over the winter holiday season. Our results show, for example, that participants who had an awareness display were able to maintain their physical activity level (even during the holidays), while the level of physical activity for participants who did not have an awareness display dropped significantly. We discuss our results and their general implications for the use of everyday mobile devices as awareness displays.
Keywords: ambient display; awareness; calm technology; field experiment; fitness; glanceable display; mobile phone; personal mobile display; persuasive technology; physical activity

Formalizing Soundness of Contextual Effects - Pratikakis,Polyvios; Foster, Jeffrey S.; Hicks, Michael W.; Neamtiu,Iulian (Theorem Proving in Higher Order LogicsTheorem Proving in Higher Order Logics, 2008)
A contextual effect system generalizes standard type and effect systems: where a standard effect system computes the effect of an expression e , a contextual effect system additionally computes the prior and future effect of e , which characterize the behavior of computation prior to and following, respectively, the evaluation of e . This paper describes the formalization and proof of soundness of contextual effects, which we mechanized using the Coq proof assistant. Contextual effect soundness is an unusual property because the prior and future effect of a term e depends not on e itself (or its evaluation), but rather on the evaluation of the context in which e appears. Therefore, to state and prove soundness we must “match up” a subterm in the original typing derivation with the possibly-many evaluations of that subterm during the evaluation of the program, in a way that is robust under substitution. We do this using a novel typed operational semantics. We conjecture that our approach could prove useful for reasoning about other properties of derivations that rely on the context in which that derivation appears.

A Framework for Software Engineering Experimental Replications - Mendonca,M.G.; Maldonado,J.C.; de Oliveira,M.C.F.; Carver, J.; Fabbri,C.P.F.; Shull, F.; Travassos,G.H.; Hohn,E.N.; Basili, Victor R. (Engineering of Complex Computer Systems, 2008. ICECCS 2008. 13th IEEE International Conference on, 2008)
Experimental replications are very important to the advancement of empirical software engineering. Replications are one of the key mechanisms to confirm previous experimental findings. They are also used to transfer experimental knowledge, to train people, and to expand a base of experimental evidence. Unfortunately, experimental replications are difficult endeavors. It is not easy to transfer experimental know-how and experimental findings. Based on our experience, this paper discusses this problem and proposes a Framework for Improving the Replication of Experiments (FIRE). The FIRE addresses knowledge sharing issues both at the intra-group (internal replications) and inter-group (external replications) levels. It encourages coordination of replications in order to facilitate knowledge transfer for lower cost, higher quality replications and more generalizable results.
Keywords: engineering; engineering; evidence; experimental; experimental; Experiments; experimental; for; Framework; Improving; knowledge; of; replication; replication; software; sharing; software; the; transfer; knowledge

A general method for sensor planning in multi-sensor systems: Extension to random occlusion - Mittal,A.; Davis, Larry S. (International Journal of Computer Vision, 2008)
ystems utilizing multiple sensors are required in many domains. In this paper, we specifically concern ourselves with applications where dynamic objects appear randomly and the system is employed to obtain some user-specified characteristics of such objects. For such systems, we deal with the tasks of determining measures for evaluating their performance and of determining good sensor configurations that would maximize such measures for better system performance.We introduce a constraint in sensor planning that has not been addressed earlier: visibility in the presence of random occluding objects. occlusion causes random loss of object capture from certain necessitates the use of other sensors that have visibility of this object. Two techniques are developed to analyze such visibility constraints: a probabilistic approach to determine “average” visibility rates and a deterministic approach to address worst-case scenarios. Apart from this constraint, other important constraints to be considered include image resolution, field of view, capture orientation, and algorithmic constraints such as stereo matching and background appearance. Integration of such constraints is performed via the development of a probabilistic framework that allows one to reason about different occlusion events and integrates different multi-view capture and visibility constraints in a natural way. Integration of the thus obtained capture quality measure across the region of interest yields a measure for the effectiveness of a sensor configuration and maximization of such measure yields sensor configurations that are best suited for a given scenario. The approach can be customized for use in many multi-sensor applications and our contribution is especially significant for those that involve randomly occurring objects capable of occluding each other. These include security systems for surveillance in public places, industrial automation and traffic monitoring. Several examples illustrate such versatility by application of our approach to a diverse set of different and sometimes multiple system objectives.

Generalizing Word Lattice Translation - Dyer,Christopher; Muresan,Smaranda; Resnik, Philip (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2008)
Word lattice decoding has proven useful in spoken language translation; we argue that it provides a compelling model for translation of text genres, as well. We extend lattice decoding to hierarchical phrase-based models, providing a unified treatment with phrase-based decoding by treating lattices as a case of weighted finite-state automata. In the process, we resolve a significant complication that lattice representations introduce in reordering models. Our experiments evaluating the approach demonstrate substantial gains for Chinese-English and Arabic-English translation.
Keywords: *MACHINE TRANSLATION; *STATISTICAL MACHINE TRANSLATION; *WORD LATTICE TRANSLATION; grammars; HIERARCHICAL PHRASE-BASED MODELS; linguistics; MODELS; STATISTICAL PROCESSES

Genome-Wide Analysis of Repetitive Elements in Papaya - Nagarajan,Niranjan; Navajas-Pérez,Rafael; Pop, Mihai; Alam,Maqsudul; Ming,Ray; Paterson,Andrew; Salzberg,Steven (Tropical Plant Biology, 2008)
Papaya ( Carica papaya L.) is an important fruit crop cultivated in tropical and subtropical regions worldwide. A first draft of its genome sequence has been recently released. Together with Arabidopsis , rice, poplar, grapevine and other genomes in the pipeline, it represents a good opportunity to gain insight into the organization of plant genomes. Here we report a detailed analysis of repetitive elements in the papaya genome, including transposable elements (TEs), tandemly-arrayed sequences, and high copy number genes. These repetitive sequences account for ∼56% of the papaya genome with TEs being the most abundant at 52%, tandem repeats at 1.3% and high copy number genes at 3%. Most common types of TEs are represented in the papaya genome with retrotransposons being the dominant class, accounting for 40% of the genome. The most prevalent retrotransposons are Ty3-gypsy (27.8%) and Ty1-copia (5.5%). Among the tandem repeats, microsatellites are the most abundant in number, but represent only 0.19% of the genome. Minisatellites and satellites are less abundant, but represent 0.68% and 0.43% of the genome, respectively, due to greater repeat length. Despite an overall smaller gene repertoire in papaya than many other angiosperms, a significant fraction of genes (>2%) are present in large gene families with copy number greater than 20. This repeat database clarified a major part of the papaya genome organization and partly explained the lower gene repertoire in papaya than in Arabidopsis .

Growth of the flickr social network - Mislove,Alan; Koppula,Hema Swetha; Gummadi,Krishna P.; Druschel,Peter; Bhattacharjee, Bobby (Proceedings of the first workshop on Online social networks, 2008)
Online social networking sites like MySpace, Orkut, and Flickr are among the most popular sites on the Web and continue to experience dramatic growth in their user population. The popularity of these sites offers a unique opportunity to study the dynamics of social networks at scale. Having a proper understanding of how online social networks grow can provide insights into the network structure, allow predictions of future growth, and enable simulation of systems on networks of arbitrary size. However, to date, most empirical studies have focused on static network snapshots rather than growth dynamics. In this paper, we collect and examine detailed growth data from the Flickr online social network, focusing on the ways in which new links are formed. Our study makes two contributions. First, we collect detailed data covering three months of growth, encompassing 950,143 new users and over 9.7 million new links, and we make this data available to the research community. Second, we use a first-principles approach to investigate the link formation process. In short, we find that links tend to be created by users who already have many links, that users tend to respond to incoming links by creating links back to the source, and that users link to other users who are already close in the network.
Keywords: growth; measurement; social networks

Hci for community and international development - Thomas, John; Dearden, Andy; Dray, Susan; Light, Ann; Best, Michael; Arkin, Nuray; Maunder, Andrew; Kam, Mathew; Marshini Chetty; Sambasivan, Nithya; Buckhalter, Celeste; Krishnan, Gaurishankar (SIGCHI EA '08, 2008)
This workshop explores the challenges in applying, extending and inventing appropriate methods and contributions of Human Computer Interaction (HCI) to International economic and community Development. We address interaction design for parts of the world that are often marginalized by the Global North as well as people in the Global North who are themselves similarly marginalized by poverty or other barriers. We hope to extend the boundaries of the field of Human Computer Interaction by spurring a discussion on how existing methods and practices can be adapted and modified, and how new practices can be developed, to deal with the unique challenges posed by these contexts.
Keywords: community design; ict4d; information and communication technology; international development; participatory design; ucd4id; User centered design

A hierarchical spatial index for triangulated surfaces - De Floriani, Leila; Facinoli,M.; Magillo,P.; Dimitri,D. (Int. Conf. on Computer Graphics Theory and Applications (GRAPP), 2008)
We present the PM2-Triangle quadtree (PM2T-quadtree), a new hierarchical spatial index for triangle mesheswhich has been designed for performing spatial queries on triangle-based terrain models. The PM2T-quadtree is based on a recursive space decomposition into square blocks. Here, we propose a highly compact data structure encoding a PM2T-quadtree, which decouples the spatial indexing structure from the combinatorial description of the mesh. We compare the PM2T-quadtree against other spatial indexes by considering the structure of the underlying domain subdivision, the storage costs of their data structures and the performance in geometric queries.

Hosting virtual networks on commodity hardware - Bhatia,S.; Motiwala,M.; Muhlbauer,W.; Valancius,V.; Bavier,A.; Feamster, Nick; Peterson,L.; Rexford,J. (Georgia Institute of Technology, 2008)
This paper describes Trellis, a software platform for hostingmultiple virtual networks on shared commodity hardware. Trellis allows each virtual network to define its own topol- ogy, control protocols, and forwarding tables, which low- ers the barrier for deploying custom services on an isolated, reconfigurable, and programmable network, while amor- tizing costs by sharing the physical infrastructure. Trellis synthesizes two container-based virtualization technologies, VServer and NetNS, as well as a new tunneling mechanism, EGRE, into a coherent platform that enables high-speed vir- tual networks. We describe the design and implementation, of Trellis, including kernel-level performance optimizations, and evaluate its supported packet-forwarding rates against other virtualization technologies. We are in the process of upgrading the VINI facility to use Trellis. We also plan to release Trellis as part of MyVINI, a standalone software dis- tribution that allows researchers and application developers to deploy their own virtual network hosting platforms.

Image acquisition forensics: Forensic analysis to identify imaging source - McKay,C.; Swaminathan,A.; Gou,Hongmei; M. Wu (Acoustics, Speech and Signal Processing, 2008. ICASSP 2008. IEEE International Conference on, 2008)
With widespread availability of digital images and easy-to-use image editing softwares, the origin and integrity of digital images has become a serious concern. This paper introduces the problem of image acquisition forensics and proposes a fusion of a set of signal processing features to identify the source of digital images. Our results show that the devices' color interpolation coefficients and noise statistics can jointly serve as good forensic features to help accurately trace the origin of the input image to its production process and to differentiate between images produced by cameras, cell phone cameras, scanners, and computer graphics. Further, the proposed features can also be extended to determining the brand and model of the device. Thus, the techniques introduced in this work provide a unified framework for image acquisition forensics.
Keywords: ACQUISITION; acquisition; image; analysis; analysis; image; analysis; interpolation; statistical; cameras; color; cell; coefficients; computer; colour; editing; forensics; image; graphics; digital; identification; noise; images; forensic; Interpolation; phone; processing; data; softwares; imaging; source; statistics; scanners; signal

Immunity-Based Epidemic Routing in Intermittent Networks - Mundur, Padma; Seligman,M.; Jin Na Lee (5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, 2008. SECON '08, 2008)
In this research, we propose to modify and extend epidemic routing used in intermittent networks. In particular, we propose to include immunity-based information disseminated in the reverse once messages get delivered to their destination. The goal is to design a more efficient routing protocol in terms of resource utilization. The idea is to analyze and evaluate the network performance using an immunity scheme in the context of epidemic routing and its variants. The reverse dissemination of such information requires minimal resources and the tradeoff in timely purging of delivered messages can be significant. We are using ns2 to implement a detailed simulation of the proposed immunity-based epidemic routing.
Keywords: Analytical models; Delay; delivered messages; Disruption tolerant networking; Educational institutions; immunity-based epidemic routing; information dissemination; intermittent networks; Mobile ad hoc networks; Network topology; Performance analysis; Resource management; resource utilization; routing protocol; routing protocols; telecommunication network topology

Improved approximation bounds for planar point pattern matching - Cho,M.; Mount, Dave (Algorithmica, 2008)
We analyze the performance of simple algorithms for matching two planar point sets under rigid transformations so as to minimize the directed Hausdorff distance between the sets. This is a well studied problem in computational geometry. Goodrich, Mitchell, and Orletsky presented a very simple approximation algorithm for this problem, which computes transformations based on aligning pairs of points. They showed that their algorithm achieves an approximation ratio of 4. We introduce a modification to their algorithm, which is based on aligning midpoints rather than endpoints. This modification has the same simplicity and running time as theirs, and we show that it achieves a better approximation ratio of roughly 3.14. We also analyze the approximation ratio in terms of a instance-specific parameter that is based on the ratio between diameter of the pattern set to the optimum Hausdorff distance. We show that as this ratio increases (as is common in practical applications) the approximation ratio approaches 3 in the limit. We also investigate the performance of the algorithm by Goodrich et al. as a function of this ratio, and present nearly matching lower bounds on the approximation ratios of both algorithms.

Inconsistency management policies - Martinez,M. V; Parisi,F.; Pugliese, A.; Simari,G. I; V.S. Subrahmanian (Proc. 2008 Intl. Conference on Knowledge Representation and Reasoning (KR 2008), 2008)
Though there is much work on how inconsistency indatabases should be managed, there is good reason to believe that end users will want to bring their domain expertise and needs to bear in how to deal with inconsistencies. In this paper, we propose the concept of inconsistency management policies (IMPs). We show that IMPs are rich enough to spec- ify many types of inconsistency management methods pro- posed previously, but provide end users with tools that allow them to use the policies that they want. Our policies are also capable of allowing inconsistency to persist in the database or of eliminating more than a minimal subset of tuples involved in the inconsistency. We present a formal axiomatic definition of IMPs and present appropriate complexity results, together with results linking different IMPs together. We extend the relational algebra (RA) to incorporate IMPs and present the- oretical results showing how IMPs and classical RA operators interact.