VAST 2008 Challenge: Introducing mini-challenges - Grinstein,G.; Plaisant, Catherine; Laskowski,S.; O'Connell,T.; Scholtz,J.; Whiting,M. (Visual Analytics Science and Technology, 2008. VAST '08. IEEE Symposium on, 2008)
Visual analytics experts realize that one effective way to push the field forward and to develop metrics for measuring the performance of various visual analytics components is to hold an annual competition. The VAST 2008 Challenge is the third year that such a competition was held in conjunction with the IEEE Visual Analytics Science and Technology (VAST) symposium. The authors restructured the contest format used in 2006 and 2007 to reduce the barriers to participation and offered four mini-challenges and a Grand Challenge. Mini Challenge participants were to use visual analytic tools to explore one of four heterogeneous data collections to analyze specific activities of a fictitious, controversial movement. Questions asked in the Grand Challenge required the participants to synthesize data from all four data sets. In this paper we give a brief overview of the data sets, the tasks, the participation, the judging, and the results.
Keywords: 2008; analytics; data; Challenge; heterogeneous; collections; visual; data; VAST; visualisation

Visualizing Functional Data with an Application to eBay’s Online Auctions - Chen,Chun-houh; Härdle,Wolfgang; Unwin,Antony; Jank,Wolfgang; Shmueli,Galit; Plaisant, Catherine; Shneiderman, Ben (Handbook of Data VisualizationHandbook of Data Visualization, 2008)
Technological advances in the measurement, collection, and storage of data have led tomore andmore complex data structures. Examples of such structures include measurements of the behavior of individuals over time, digitized two- or three-dimensional images of the brain, and recordings of three- or even four-dimensional movements of objects traveling through space and time. Such data, although recorded in a discrete fashion, are usually thought of as continuous objects that are represented by functional relationships. This gave rise to functional data analysis (FDA), which was made popular by the monographs of Ramsay and Silverman (1997, 2002), where the center of interest is a set of curves, shapes, objects, or, more generally, a set of functional observations , in contrast to classical statistics where interest centers on a set of data vectors. In that sense, functional data is not only different from the data structure studied in classical statistics, but it actually generalizes it. Many of these new data structures require new statistical methods to unveil the information that they carry.

Why Do Hubs in the Yeast Protein Interaction Network Tend To Be Essential: Reexamining the Connection between the Network Topology and Essentiality - Zotenko,Elena; Mestre,Julian; O'Leary, Dianne P.; Przytycka,Teresa M. (PLoS Comput BiolPLoS Comput Biol, 2008)
Analysis of protein interaction networks in the budding yeast Saccharomyces cerevisiae has revealed that a small number of proteins, the so-called hubs, interact with a disproportionately large number of other proteins. Furthermore, many hub proteins have been shown to be essential for survival of the cell—that is, in optimal conditions, yeast cannot grow and multiply without them. This relation between essentiality and the number of neighbors in the protein–protein interaction network has been termed the centrality-lethality rule. However, why are such hubs essential? Jeong and colleagues [1] suggested that overrepresentation of essential proteins among high-degree nodes can be attributed to the central role that hubs play in mediating interactions among numerous, less connected proteins. Another view, proposed by He and Zhang, suggested that that the majority of proteins are essential due to their involvement in one or more essential protein–protein interactions that are distributed uniformly at random along the network edges [2]. We find that none of the above reasons determines essentiality. Instead, the majority of hubs are essential due to their involvement in Essential Complex Biological Modules, a group of densely connected proteins with shared biological function that are enriched in essential proteins. This study sheds new light on the topological complexity of protein interaction networks.

Worst case examples of an exterior point algorithm for the assignment problem - Charalampos Papamanthou; Paparrizos, Konstantinos; Samaras, Nikolaos; Stergiou, Konstantinos (Discrete Optimization, 2008)
An efficient exterior point simplex type algorithm for the assignment problem has been developed by Paparrizos [K. Paparrizos, An infeasible (exterior point) simplex algorithm for assignment problems, Math. Program. 51 (1991) 45–54]. This algorithm belongs to the category of forest algorithms and solves an n × n assignment problem in at most n ( n − 1 ) 2 iterations and in at most O ( n 3 ) time. In this paper worst case examples are presented. Specifically, a systematic procedure to construct worst case assignment problems is presented for the exterior point algorithm. The algorithm applied to these examples executes exactly n ( n − 1 ) 2 iterations. This result verifies that the bound O ( n 3 ) is the best possible for the above-mentioned algorithm.
Keywords: Assignment problem; Exterior point algorithm; Worst case examples

911. gov - Shneiderman, Ben; Preece,J. (Science(Washington), 2007)

Aggregates in Generalized Temporally Indeterminate Databases - Udrea,Octavian; Majkić,Zoran; Subrahmanian,V. (Scalable Uncertainty ManagementScalable Uncertainty Management, 2007)
Dyreson and Snodgrass as well as Dekhtyar et. al. have provided a probabilistic model (as well as compelling example applications) for why there may be temporal indeterminacy in databases. In this paper, we first propose a formal model for aggregate computation in such databases when there is uncertainty not just in the temporal attribute, but also in the ordinary (non-temporal) attributes. We identify two types of aggregates: event correlated aggregates, and non event correlated aggregations, and provide efficient algorithms for both of them. We prove that our algorithms are correct, and we present experimental results showing that the algorithms work well in practice.
Keywords: Computer; Science

Algorithms for on-line monitoring of micro spheres in an optical tweezers-based assembly cell - Peng,T.; Balijepalli,A.; Gupta,S.K.; LeBrun,T. (Journal of Computing and Information Science in Engineering, 2007)
Optical tweezers have emerged as a powerful tool for microand nanomanipulation. Using optical tweezers to perform auto- mated assembly requires on-line monitoring of components in the assembly workspace. This paper presents algorithms for estimat- ing positions and orientations of microscale and nanoscale com- ponents in the 3-Dimensional assembly workspace. Algorithms presented in this paper use images obtained by optical section microscopy. The images are first segmented to locate areas of in- terest and then image gradient information from the areas of in- terest is used to generate probable locations and orientations of components in the XY-plane. Finally, signature curves are com- puted and utilized to obtain component locations and orienta- tions in 3-D space. We have tested these algorithms with silica micro-spheres as well as metallic nanowires. We believe that the algorithms described in this paper will provide the foundation for realizing automated assembly operations in optical tweezers- based assembly cells.

Application of MCL in a dialog agent - Josyula,D. P; Fults,S.; Anderson,M. L; Wilson,S.; Perlis, Don (Third Language and Technology Conference, 2007)

Automated detection of persistent kernel control-flow attacks - Petroni,Jr.,Nick L.; Hicks, Michael W. (Proceedings of the 14th ACM conference on Computer and communications security, 2007)
This paper presents a new approach to dynamically monitoring operating system kernel integrity, based on a property called state-based control-flow integrity (SBCFI). Violations of SBCFI signal a persistent, unexpected modification of the kernel's control-flow graph. We performed a thorough analysis of 25 Linux rootkits and found that 24 (96%) employ persistent control-flow modifications; an informal study of Windows rootkits yielded similar results. We have implemented SBCFI enforcement as part of the Xen and VMware virtual machine monitors. Our implementation detected all the control-flow modifying rootkits we could install, while imposing unnoticeable overhead for both a typical web server workload and CPU-intensive workloads when operating at 10 second intervals.
Keywords: CFI; integrity; Kernel; rootkit; virtualization

BELIV'06: beyond time and errors: novel evaluation methods for information visualization - Bertini,Enrico; Plaisant, Catherine; Santucci,Giuseppe (interactions, 2007)

Characterization of Ehp, a Secreted Complement Inhibitory Protein from Staphylococcus aureus - Hammel,Michal; Sfyroera,Georgia; Pyrpassopoulos,Serapion; Ricklin,Daniel; Ramyar,Kasra X.; Pop, Mihai; Jin,Zhongmin; Lambris,John D.; Geisbrecht,Brian V. (Journal of Biological Chemistry, 2007)
We report here the discovery and characterization of Ehp, a new secreted Staphylococcus aureus protein that potently inhibits the alternative complement activation pathway. Ehp was identified through a genomic scan as an uncharacterized secreted protein from S. aureus, and immunoblotting of conditioned S. aureus culture medium revealed that the Ehp protein was secreted at the highest levels during log-phase bacterial growth. The mature Ehp polypeptide is composed of 80 residues and is 44% identical to the complement inhibitory domain of S. aureus Efb (extracellular fibrinogen-binding protein). We observed preferential binding by Ehp to native and hydrolyzed C3 relative to fully active C3b and found that Ehp formed a subnanomolar affinity complex with these various forms of C3 by binding to its thioester-containing C3d domain. Site-directed mutagenesis demonstrated that Arg75 and Asn82 are important in forming the Ehp·C3d complex, but loss of these side chains did not completely disrupt Ehp/C3d binding. This suggested the presence of a second C3d-binding site in Ehp, which was mapped to the proximity of Ehp Asn63. Further molecular level details of the Ehp/C3d interaction were revealed by solving the 2.7-Å crystal structure of an Ehp·C3d complex in which the low affinity site had been mutationally inactivated. Ehp potently inhibited C3b deposition onto sensitized surfaces by the alternative complement activation pathway. This inhibition was directly related to Ehp/C3d binding and was more potent than that seen for Efb-C. An altered conformation in Ehp-bound C3 was detected by monoclonal antibody C3-9, which is specific for a neoantigen exposed in activated forms of C3. Our results suggest that increased inhibitory potency of Ehp relative to Efb-C is derived from the second C3-binding site in this new protein.

Classifying Computer Generated Charts - Prasad,V. S.N; Siddiquie,B.; Golbeck,J.; Davis, Larry S. (Content-Based Multimedia Indexing, 2007. CBMI '07. International Workshop on, 2007)
We present an approach for classifying images of charts based on the shape and spatial relationships of their primitives. Five categories are considered: bar-charts, curve-plots, pie-charts, scatter-plots and surface-plots. We introduce two novel features to represent the structural information based on (a) region segmentation and (b) curve saliency. The local shape is characterized using the Histograms of Oriented Gradients (HOG) and the Scale Invariant Feature Transform (SIFT) descriptors. Each image is represented by sets of feature vectors of each modality. The similarity between two images is measured by the overlap in the distribution of the features -measured using the Pyramid Match algorithm. A test image is classified based on its similarity with training images from the categories. The approach is tested with a database of images collected from the Internet.
Keywords: algorithm; scale; analysis; visual; classification; image; database; image; databases; feature; Internet; bar-chart; curve-plot; image; invariant; match; matching; image; relationship; surface-plot; Internet; image; representation; image; segmentation; pie-chart; pyramid; segmentation; statistical; transform; scatter-plot; spatial

Community response grids: E-government, social networks, and effective emergency management - Jaeger,Paul T.; Shneiderman, Ben; Fleischmann,Kenneth R.; Preece,Jennifer; Qu,Yan; Fei Wu,Philip (Telecommunications Policy, 2007)
This paper explores the concept of developing community response grids (CRGs) for community emergency response and the policy implications of such a system. CRGs make use of the Internet and mobile communication devices, allowing residents and responders to share information, communicate, and coordinate activities in response to a major disaster. This paper explores the viability of using mobile communication technologies and the Web, including e-government, to develop response systems that would aid communities before, during, and after a major disaster, providing channels for contacting residents and responders, uploading information, distributing information, coordinating the responses of social networks, and facilitating resident-to-resident assistance. Drawing upon research from computer science, information studies, public policy, emergency management, and several other disciplines, the paper elaborates on the concept of and need for CRGs, examines related current efforts that can inform the development of CRGs, discusses how research about community networks can be used to instill trust and social capital in CRGs, and examines the issues of public policy, telecommunications, and e-government related to such a system.
Keywords: Community response grid; E-government; Emergency response; Mobile communications; Public policy; social networks

Community response grids for older adults: Motivations, usability, and sociability - Wu,P.F.; Preece,J.; Shneiderman, Ben; Jaeger,P. T; Qu,Y. (Proceedings of the 13th Americas Conference on Information Systems, 2007)
This paper discusses the motivation for a Community Response Grid (CRG) to helpolder adults improve their capability for coping with emergency situations. We define and discuss the concept of a CRG, briefly review the limits of current emergency response systems, and identify usability and sociability guidelines for CRGs for older adults based on existing research. The paper ends with a call to action and suggestions for future research directions.

Community Response Grids: Using Information Technology to Help Communities Respond to Bioterror Emergencies - Jaeger,Paul T.; Fleischmann,Kenneth R.; Preece,Jennifer; Shneiderman, Ben; Fei Wu,Philip; Qu,Yan (Biosecurity and Bioterrorism: Biodefense Strategy, Practice, and Science, 2007)
Access to accurate and trusted information is vital in preparing for, responding to, and recovering from an mergency. To facilitate response in large-scale emergency situations, Community Response Grids (CRGs) integrate Internet and mobile technologies to enable residents to report information, professional emergency responders to disseminate instructions, and residents to assist one another. CRGs use technology to help residents and professional emergency responders to work together in community response to emergencies, including bioterrorism events. In a time of increased danger from bioterrorist threats, the application of advanced information and communication technologies to community response is vital in confronting such threats. This article describes CRGs, their underlying concepts, development efforts, their relevance to biosecurity and bioterrorism, and future research issues in the use of technology to facilitate community response.

A Comparison between Internal and External Malicious Traffic - Michel Cukier; Panjwani,S. (2007)
This paper empirically compares malicious traffic originating inside an organization (i.e., internal traffic) with malicious traffic originating outside an organization (i.e., external traffic). Two honeypot target computers were deployed to collect malicious traffic data over a period of fifteen weeks. In the first study we showed that there was a weak correlation between internal and external traffic based on the number of malicious connections. Since the type of malicious activity is linked to the port that was targeted, we focused on the most frequently targeted ports. We observed that internal malicious traffic often contained different malicious content compared to that of external traffic. In the third study, we discovered that the volume of malicious traffic was linked to the day of the week. We showed that internal and external malicious activities differ: where the external malicious activity is quite stable over the week, the internal traffic varied as a function of the users' activity profile.
Keywords: Computer networks; Data analysis; external traffic; honeypot target computers; internal traffic; malicious traffic data; security of data; user activity profile

A computational survey of candidate exonic splicing enhancer motifs in the model plant Arabidopsis thaliana - Pertea,Mihaela; Mount, Stephen M.; Salzberg,Steven L. (BMC Bioinformatics, 2007)
Algorithmic approaches to splice site prediction have relied mainly on the consensus patterns found at the boundaries between protein coding and non-coding regions. However exonic splicing enhancers have been shown to enhance the utilization of nearby splice sites.

On the Cost of Persistence and Authentication in Skip Lists - Goodrich, Michael T.; Charalampos Papamanthou; Tamassia, Roberto (Experimental Algorithms, 2007)
We present an extensive experimental study of authenticated data structures for dictionaries and maps implemented with skip lists. We consider realizations of these data structures that allow us to study the performance overhead of authentication and persistence. We explore various design decisions and analyze the impact of garbage collection and virtual memory paging, as well. Our empirical study confirms the efficiency of authenticated skip lists and offers guidelines for incorporating them in various applications.
Keywords: Algorithm Analysis and Problem Complexity; algorithms; Computer Graphics; Data structures; Discrete Mathematics in Computer Science; Numeric Computing

Creating a nationwide wireless detection sensor network for chemical, biological and radiological threats - Rita R Colwell; Peeters,J. (Gentag White Paper, 2007)

Cross-layer latency minimization in wireless networks with SINR constraints - Chafekar,Deepti; Kumar,V. S. Anil; Marathe,Madhav V.; Parthasarathy,Srinivasan; Srinivasan, Aravind (Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, 2007)
Recently, there has been substantial interest in the design of cross-layer protocols for wireless networks. These protocols optimize certain performance metric(s) of interest (e.g. latency, energy, rate) by jointly optimizing the performance of multiple layers of the protocol stack. Algorithm designers often use geometric-graph-theoretic models for radio interference to design such cross-layer protocols. In this paper we study the problem of designing cross-layer protocols for multi-hop wireless networks using a more realistic Signal to Interference plus Noise Ratio (SINR) model for radio interference. The following cross-layer latency minimization problem is studied: Given a set V of transceivers, and a set of source-destination pairs, (i) choose power levels for all the transceivers, (ii) choose routes for all connections, and (iii) construct an end-to-end schedule such that the SINR constraints are satisfied at each time step so as to minimize the make-span of the schedule (the time by which all packets have reached their respective destinations). We present a polynomial-time algorithm with provable worst-case performance guarantee for this cross-layer latency minimization problem. As corollaries of the algorithmic technique we show that a number of variants of the cross-layer latency minimization problem can also be approximated efficiently in polynomial time. Our work extends the results of Kumar et al. (Proc. SODA, 2004) and Moscibroda et al. (Proc. MOBIHOC, 2006). Although our algorithm considers multiple layers of the protocol stack, it can naturally be viewed as compositions of tasks specific to each layer --- this allows us to improve the overall performance while preserving the modularity of the layered structure.
Keywords: cross-layer design; end-to-end scheduling; Interference; SINR model; Wireless networks

Crystal Structure and Solution NMR Studies of Lys48-linked Tetraubiquitin at Neutral pH - Eddins,Michael J.; Varadan,Ranjani; Fushman, David; Pickart,Cecile M.; Wolberger,Cynthia (Journal of Molecular Biology, 2007)
Ubiquitin modification of proteins is used as a signal in many cellular processes. Lysine side-chains can be modified by a single ubiquitin or by a polyubiquitin chain, which is defined by an isopeptide bond between the C terminus of one ubiquitin and a specific lysine in a neighboring ubiquitin. Polyubiquitin conformations that result from different lysine linkages presumably differentiate their roles and ability to bind specific targets and enzymes. However, conflicting results have been obtained regarding the precise conformation of Lys48-linked tetraubiquitin. We report the crystal structure of Lys48-linked tetraubiquitin at near-neutral pH. The two tetraubiquitin complexes in the asymmetric unit show the complete connectivity of the chain and the molecular details of the interactions. This tetraubiquitin conformation is consistent with our NMR data as well as with previous studies of diubiquitin and tetraubiquitin in solution at neutral pH. The structure provides a basis for understanding Lys48-linked polyubiquitin recognition under physiological conditions.
Keywords: crystal structure; Lys48-linked; polyubiquitin chains; tetraubiquitin; ubiquitin

Detecting stochastically scheduled activities in video - Albanese, M.; Moscato, V.; Picariello, A.; V.S. Subrahmanian; Udrea,O. (International Joint Conference on Artificial Intelligence, 2007)
The ability to automatically detect activities invideo is of increasing importance in applications such as bank security, airport tarmac security, bag- gage area security and building site surveillance. We present a stochastic activity model composed of atomic actions which are directly observable through image understanding primitives. We focus on answering two types of questions: (i) what are the minimal sub-videos in which a given action is identified with probability above a certain thresh- old and (ii) for a given video, can we decide which activity from a given set most likely occurred? We provide the MPS algorithm for the first problem, as well as two different algorithms (naiveMPA and MPA) to solve the second. Our experimental re- sults on a dataset consisting of staged bank robbery videos (described in [Vu et al., 2003]) show that our algorithms are both fast and provide high qual- ity results when compared to human reviewers.

Direct-dependency-based software compatibility testing - Yoon,Il-Chul; Sussman, Alan; Memon, Atif M.; Porter, Adam (Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, 2007)
Software compatibility testing is an important quality assurance task aimed at ensuring that component-based software systems build and/or execute properly across a broad range of user system configurations. Because each configuration can involve multiple components with different versions, and because there are complex and changing interdependencies between components and their versions, it is generally infeasible to test all potential configurations. Therefore, compatibility testing usually means examining only a handful of default or popular configurations to detect problems, and as a result costly errors can and do escape to the field This paper presents an improved approach to compatibility testing called RACHET. We formally model the configuration space for component-based systems and use the model to generate test plans covering user-specified portion of the space - the example in this paper is covering all it direct dependencies between components. The test plan is executed efficiently in parallel, by distributing work so as to best utilize test resources. We conducted experimentsand simulation studies applying our approach to a large-scale data management middleware system. The results showed that for this system RACHET discovered incompatibilities between components at a small fraction of the cost for exhaustive testing without compromising test quality
Keywords: compatibility testing; component-based software system

Discovering interesting usage patterns in text collections: integrating text mining with visualization - Don,Anthony; Zheleva,Elena; Gregory,Machon; Tarkan,Sureyya; Auvil,Loretta; Clement,Tanya; Shneiderman, Ben; Plaisant, Catherine (Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007)
This paper addresses the problem of making text mining results more comprehensible to humanities scholars, journalists, intelligence analysts, and other researchers, in order to support the analysis of text collections. Our system, FeatureLens1, visualizes a text collection at several levels of granularity and enables users to explore interesting text patterns. The current implementation focuses on frequent itemsets of n-grams, as they capture the repetition of exact or similar expressions in the collection. Users can find meaningful co-occurrences of text patterns by visualizing them within and across documents in the collection. This also permits users to identify the temporal evolution of usage such as increasing, decreasing or sudden appearance of text patterns. The interface could be used to explore other text features as well. Initial studies suggest that FeatureLens helped a literary scholar and 8 users generate new hypotheses and interesting insights using 2 text collections.
Keywords: digital humanities; frequent closed itemsets; n-grams; text mining; user interface

Distributed Ranked Search - Gopalakrishnan,Vijay; Morselli,Ruggero; Bhattacharjee, Bobby; Keleher,Pete; Srinivasan, Aravind (High Performance Computing – HiPC 2007High Performance Computing – HiPC 2007, 2007)
P2P deployments are a natural infrastructure for building distributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them. Users, however, are primarily interested in the most relevant results, not necessarily all possible results. Using random sampling, we extend a class of well-known information retrieval ranking algorithms such that they can be applied in this decentralized setting. We analyze the overhead of our approach, and quantify how our system scales with increasing number of documents, system size, document to node mapping (uniform versus non-uniform), and types of queries (rare versus popular terms). Our analysis and simulations show that a) these extensions are efficient, and scale with little overhead to large systems, and b) the accuracy of the results obtained using distributed ranking is comparable to that of a centralized implementation.

Draft Genome of the Filarial Nematode Parasite Brugia Malayi - Ghedin,Elodie; Wang,Shiliang; Spiro,David; Caler,Elisabet; Zhao,Qi; Crabtree,Jonathan; Allen,Jonathan E; Delcher,Arthur L.; Guiliano,David B; Miranda-Saavedra,Diego; Angiuoli,Samuel V; Creasy,Todd; et al. (Science, 2007)
Parasitic nematodes that cause elephantiasis and river blindness threaten hundreds of millions of people in the developing world. We have sequenced the ∼90 megabase (Mb) genome of the human filarial parasite Brugia malayi and predict ∼11,500 protein coding genes in 71 Mb of robustly assembled sequence. Comparative analysis with the free-living, model nematode Caenorhabditis elegans revealed that, despite these genes having maintained little conservation of local synteny during ∼350 million years of evolution, they largely remain in linkage on chromosomal units. More than 100 conserved operons were identified. Analysis of the predicted proteome provides evidence for adaptations of B. malayi to niches in its human and vector hosts and insights into the molecular basis of a mutualistic relationship with its Wolbachia endosymbiont. These findings offer a foundation for rational drug design.

EcoLens: Integration and interactive visualization of ecological datasets - Parr,Cynthia Sims; Lee,Bongshin; Bederson, Benjamin B. (Ecological Informatics, 2007)
Complex multi-dimensional datasets are now pervasive in science and elsewhere in society. Better interactive tools are needed for visual data exploration so that patterns in such data may be easily discovered, data can be proofread, and subsets of data can be chosen for algorithmic analysis. In particular, synthetic research such as ecological interaction research demands effective ways to examine multiple datasets. This paper describes our integration of hundreds of food-web datasets into a common platform, and the visualization software, EcoLens, we developed for exploring this information. This publicly-available application and integrated dataset have been useful for our research predicting large complex food webs, and EcoLens is favorably reviewed by other researchers. Many habitats are not well represented in our large database. We confirm earlier results about the small size and lack of taxonomic resolution in early food webs but find that they and a non-food-web source provide trophic information about a large number of taxa absent from more modern studies. Corroboration of Tuesday Lake trophic links across studies is usually possible, but lack of links among congeners may have several explanations. While EcoLens does not provide all kinds of analytical support, its label- and item-based approach is effective at addressing concerns about the comparability and taxonomic resolution of food-web data.
Keywords: Data integration; Food webs; Taxonomy; Visualization

Efficient simulation of critical synchronous dataflow graphs - Hsu,C. J; Ko,M. Y; Bhattacharyya, Shuvra S.; Ramasubbu,S.; Pino,J. L (ACM Transactions on Design Automation of Electronic Systems (TODAES), 2007)

Electron beam and optical proximity effect reduction for nanolithography: New results - Peckerar,Martin; Sander,David; Srivastava,Ankur; Foli,Adakou; Vishkin, Uzi (Journal of Vacuum Science & Technology B, 2007)
Proximity effect correction by dose modulation is widely practiced in electron-beam lithography. Optical proximity control is also possible using a combination of shape adjustment and phase control. Assigning “the right” dose (or fill factor and phase for optics) is a well known mathematical inverse problem. Linear programming, by definition, is the appropriate method for determining dose. In the past, the technique was too slow for full-scale implementation in mask making. Here, the authors discuss how recent developments in computer speed and architecture have improved the prospects for full-scale implementation. In addition, the authors discuss some numerical techniques, analogous to gridding and relaxation, that make linear programming more attractive in mask making.
Keywords: electron beam lithography; Linear programming; masks; nanolithography; proximity effect (lithography)

Energy-aware data compression for wireless sensor networks - Puthenpurayil,S.; Gu,R.; Bhattacharyya, Shuvra S. (Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, 2007)

An energy-driven design methodology for distributing DSP applications across wireless sensor networks - Shen,C. C; Plishker,W.; Bhattacharyya, Shuvra S.; Goldsman,N. (Proceedings of RTSS, 2007)

Estimation of contour motion and deformation for nonrigid object tracking - Jie Shao; Porikli,Fatih; Chellapa, Rama (Journal of the Optical Society of America AJ. Opt. Soc. Am. A, 2007)
We present an algorithm for nonrigid contour tracking in heavily cluttered background scenes. Based on the properties of nonrigid contour movements, a sequential framework for estimating contour motion and deformation is proposed. We solve the nonrigid contour tracking problem by decomposing it into three subproblems: motion estimation, deformation estimation, and shape regulation. First, we employ a particle filter to estimate the global motion parameters of the affine transform between successive frames. Then we generate a probabilistic deformation map to deform the contour. To improve robustness, multiple cues are used for deformation probability estimation. Finally, we use a shape prior model to constrain the deformed contour. This enables us to retrieve the occluded parts of the contours and accurately track them while allowing shape changes specific to the given object types. Our experiments show that the proposed algorithm significantly improves the tracker performance.
Keywords: Motion detection; VISION

Evaluating a cross-cultural children’s online book community: Lessons learned for sociability, usability, and cultural exchange - Komlodi,Anita; Hou,Weimin; Preece,Jenny; Druin, Allison; Golub,Evan; Alburo,Jade; Liao,Sabrina; Elkiss,Aaron; Resnik, Philip (Interacting with Computers, 2007)
The use of computers for human-to-human communication among adults has been studied for many years, but using computer technology to enable children from all over the world to talk to each other has rarely been discussed by researchers. The goal of our research is to fill this gap and explore the design and evaluation of children’s cross-language online communities via a case study of the International Children’s Digital Library Communities (ICDLCommunities). This project supports the development of communities for children (ages 7–11) that form around the International Digital Children’s Library (ICDL) book collection. In this community the children can learn about each others’ cultures and make friends even if they do not speak the same language. They can also read and create stories and ask and answer questions about these. From this evaluation study we learned that: (i) children are very interested in their counterparts in other countries and a remarkable amount of communication takes place even when they do not share a common language; (ii) representing their identity online in many different forms is particularly important to children when communicating in an online community; (iii) children enjoy drawing but representing stories in a sequence of diagrams is challenging and needs support; and (iv) asking and answering questions without language is possible using graphical templates. In this paper we present our findings and make recommendations for designing children’s cross-cultural online communities.
Keywords: children; Cross-cultural; Evaluation and design; International Children’s Digital Library; Online communities

Evolution of genes and genomes on the Drosophila phylogeny - Clark,Andrew G.; Eisen,Michael B.; Smith,Douglas R.; Bergman,Casey M.; Oliver,Brian; Markow,Therese A.; Kaufman,Thomas C.; Kellis,Manolis; Gelbart,William; Iyer,Venky N.; Pollard,Daniel A.; Sackton,Timothy B.; et al. (Nature, 2007)
Comparative analysis of multiple genomes in a phylogenetic framework dramatically improves the precision and sensitivity of evolutionary inference, producing more robust results than single-genome analyses can provide. The genomes of 12 Drosophila species, ten of which are presented here for the first time (sechellia, simulans, yakuba, erecta, ananassae, persimilis, willistoni, mojavensis, virilis and grimshawi), illustrate how rates and patterns of sequence divergence across taxa can illuminate evolutionary processes on a genomic scale. These genome sequences augment the formidable genetic tools that have made Drosophila melanogaster a pre-eminent model for animal genetics, and will further catalyse fundamental research on mechanisms of development, cell biology, genetics, disease, neurobiology, behaviour, physiology and evolution. Despite remarkable similarities among these Drosophila species, we identified many putatively non-neutral changes in protein-coding genes, non-coding RNA genes, and cis-regulatory regions. These may prove to underlie differences in the ecology and behaviour of these diverse species.

Finding Most Probable Worlds of Probabilistic Logic Programs - Khuller, Samir; Martinez,Vanina; Nau, Dana S.; Simari,Gerardo; Sliva,Amy; Subrahmanian,V. (Scalable Uncertainty Management, 2007)
Probabilistic logic programs have primarily studied the problem of entailment of probabilistic atoms. However, there are some interesting applications where we are interested in finding a possible world that is most probable. Our first result shows that the problem of computing such ”maximally probable worlds” (MPW) is intractable. We subsequently show that we can often greatly reduce the size of the linear program used in past work (by Ng and Subrahmanian) and yet solve the problem exactly. However, the intractability results still make computational efficiency quite impossible. We therefore also develop several heuristics to solve the MPW problem and report extensive experimental results on the accuracy and efficiency of such heuristics.
Keywords: Computer science

Generating Multi-Stage Molding Plans for Articulated Assemblies - Priyadarshi,A. K.; Gupta,S.K. (2007)
Multi-stage molding is capable of producing better-quality articulated products at a lower cost. During the multi-stage molding process, assembly operations are performed along with the molding operations. Hence, it adds new constraints to the assembly planning problem. This paper introduces the problem of generating multi-stage molding plans for articulated assemblies. We present detailed algorithms for determining the molding sequence and intermediate assembly configurations.
Keywords: articulated assemblies; articulated products; assembly planning; assembly planning problem; intermediate assembly configuration; moulding; multistage molding

Genome Analysis Linking Recent European and African Influenza (H5N1) Viruses - Salzberg,Steven L.; Kingsford, Carl; Cattoli,Giovanni; Spiro,David J.; Janies,Daniel A.; Aly,Mona Mehrez; Brown,Ian H.; Couacy-Hymann,Emmanuel; De Mia,Gian Mario; Dung,Do Huu; Guercio,Annalisa; Joannis,Tony; et al. (Emerging Infectious DiseasesEmerg Infect Dis, 2007)
Although linked, these viruses are distinct from earlier outbreak strains., To better understand the ecology and epidemiology of the highly pathogenic avian influenza virus in its transcontinental spread, we sequenced and analyzed the complete genomes of 36 recent influenza A (H5N1) viruses collected from birds in Europe, northern Africa, and southeastern Asia. These sequences, among the first complete genomes of influenza (H5N1) viruses outside Asia, clearly depict the lineages now infecting wild and domestic birds in Europe and Africa and show the relationships among these isolates and other strains affecting both birds and humans. The isolates fall into 3 distinct lineages, 1 of which contains all known non-Asian isolates. This new Euro-African lineage, which was the cause of several recent (2006) fatal human infections in Egypt and Iraq, has been introduced at least 3 times into the European-African region and has split into 3 distinct, independently evolving sublineages. One isolate provides evidence that 2 of these sublineages have recently reassorted.

GRIN: A graph based RDF index - Udrea,O.; Pugliese, A.; V.S. Subrahmanian (Proceedings of the National Conference on Artificial Intelligence, 2007)
RDF (“Resource Description Framework”) is now a widelyused World Wide Web Consortium standard. However, methods to index large volumes of RDF data are still in their infancy. In this paper, we focus on providing a very lightweight indexing mechanism for certain kinds of RDF queries, namely graph-based queries where there is a need to traverse edges in the graph determined by an RDF database. Our approach uses the idea of drawing circles around selected “center” vertices in the graph where the circle would encom- pass those vertices in the graph that are within a given dis- tance of the “center” vertex. We come up with methods of finding such “center” vertices and identifying the radius of the circles and then leverage this to build an index called GRIN. We compare GRIN with three existing RDF indexex: Jena, Sesame, and RDFBroker. We compared (i) the time to an- swer graph based queries, (ii) memory needed to store the index, and (iii) the time to build the index. GRIN outper- forms Jena, Sesame and RDFBroker on all three measures for graph based queries (for other types of queries, it may be worth building one of these other indexes and using it), at the expense of using a larger amount of memory when answering queries.

Grow and Know: Understanding Record-keeping Needs for Tracking the Development of Young Children - Kientz, Julie A.; Arriaga, Rosa I.; Marshini Chetty; Hayes, Gillian R.; Richardson, Jahmeilah; Patel, Shwetak N.; Abowd, Gregory D. (SIGCHI '07, 2007)
From birth through age five, children undergo rapid development and learn skills that will influence them their entire lives. Regular visits to the pediatrician and detailed record-keeping can ensure that children are progressing and can identify early warning signs of developmental delay or disability. However, new parents are often overwhelmed with new responsibilities, and we believe there is an opportunity for computing technology to assist in this process. In this paper, we present a qualitative study aimed at uncovering some specific needs for record-keeping and analysis for new parents and their network of caregivers. Through interviews and focus groups, we have confirmed assumptions about the rationales parents have and the functions required for using technology for record-keeping. We also identify new themes, potential prototypes, and design guidelines for this domain.
Keywords: children; design requirements; developmental delay; healthcare; qualitative study

Hawkeye: an interactive visual analytics tool for genome assemblies - Schatz,Michael C; Phillippy,Adam M; Shneiderman, Ben; Salzberg,Steven L. (Genome Biology, 2007)
Genome sequencing remains an inexact science, and genome sequences can contain significant errors if they are not carefully examined. Hawkeye is our new visual analytics tool for genome assemblies, designed to aid in identifying and correcting assembly errors. Users can analyze all levels of an assembly along with summary statistics and assembly metrics, and are guided by a ranking component towards likely mis-assemblies. Hawkeye is freely available and released as part of the open source AMOS project http://amos.sourceforge.net/hawkeye.

Hood College, Master of Business Administration, 2005 Hood College, Master of Science (Computer Science), 2001 Hood College, Bachelor of Science (Computer Science), 1998 Frederick Community College, Associate in Arts (Business Administration), 1993 - Anderson,M. L; Schmill,M.; Oates,T.; Perlis, Don; Josyula,D.; Wright,D.; Human,S. W.T.D.N; Metacognition,L.; Fults,S.; Josyula,D. P (Proceedings of the Workshop on Metareasoning in Agent-Based Systems, 2007)

Human activity understanding using visibility context - Morariu,V.I.; Prasad,V. S.N; Davis, Larry S. (IEEE/RSJ IROS Workshop: From sensors to human spatial concepts (FS2HSC), 2007)
Visibility in architectural layouts affects humannavigation, so a suitable representation of visibility context is useful in understanding human activity. Motivated by studies of spatial behavior, we use a set of features from visibility analysis to represent spatial context in the interpretation of human activity. An agent’s goal, belief about the world, trajectory and visible layout are considered to be random variables that evolve with time during the agent’s movement, and are modeled in a Bayesian framework. We design a search-based task in a sprite-world, and compare the results of our framework to those of human subject experiments. Our findings confirm that knowledge of spatial layout improves human interpretations of the trajectories (implying that visibility context is useful in this task). Since our framework demonstrates performance close to that of human subjects with knowledge of spatial layout, our findings confirm that our model makes adequate use of visibility context. In addition, the representation we use for visibility context allows our model to generalize well when presented with new scenes.

Human Values for Shaping the Made World - Shneiderman, Ben (Human-Computer Interaction – INTERACT 2007Human-Computer Interaction – INTERACT 2007, 2007)
Interface design principles have been effective in shaping new desktop applications, web-based resources, and mobile devices. Usability and sociability promote successful online communities and social network services. The contributions of human-computer interaction researchers have been effective in raising the quality of design of many products and services. As our influence grows, we can play an even more profound role in guaranteeing that enduring human values are embedded in the next generation of technology. This talk identifies which goals are realistic, such as universality, responsibility, trust, empathy, and privacy, and how we might ensure that they become part of future services and systems.

Improving software quality with static analysis - Foster, Jeffrey S.; Hicks, Michael W.; Pugh, William (Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, 2007)
At the University of Maryland, we have been working to improve the reliability and security of software by developing new, effective static analysis tools. These tools scan software for bug patterns or show that the software is free from a particular class of defects. There are two themes common to our different projects: 1. Our ultimate focus is on utility: can a programmer actually improve the quality of his or her software using an analysis tool? The important first step toward answering this question is to engineer tools so that they can analyze existing, nontrivial programs, and to carefully report the results of such analyses experimentally. The desire to better understand a more human-centered notion of utility underlies much of our future work. 2. We release all of our tools open source. This allows other researchers to verify our results, and to reuse some or all of our implementations, which often required significant effort to engineer. We believe that releasing source code is important for accelerating the pace of research results software quality, and just as importantly allows feedback from the wider community. In this research group presentation, we summarize some recent work and sketch future directions.
Keywords: bug patterns; bugs; C; Data races; FFIs; java; modularity; network protocols; Software quality

Knowledge discovery using the sand spatial browser - Samet, Hanan; Phillippy,Adam; Sankaranarayanan,Jagan (Proceedings of the 8th annual international conference on Digital government research: bridging disciplines & domains, 2007)
The use of the SAND Internet Browser as a knowledge discovery tool for epidemiological cartography is highlighted by recreating the results of Dr. John Snow's study of the 1854 Cholera epidemic in Soho, London.
Keywords: distance semi-join; knowledge discovery; sand database system; snow cholera map

MAGIC: A Multi-Activity Graph Index for Activity Detection - Albanese, M.; Pugliese, A.; V.S. Subrahmanian; Udrea,O. (Information Reuse and Integration, 2007. IRI 2007. IEEE International Conference on, 2007)
Suppose we are given a set A of activities of interest, a set O of observations, and a probability threshold p. We are interested in finding the set of all pairs (a, O'), where a epsi A and O' sube O, that minimally validate the fact that an instance of activity a occurs in O with probability p or more. The novel contribution of this paper is the notion of the multi-activity graph index (MAGIC), which can index very large numbers of observations from interleaved activities and quickly retrieve completed instances of the monitored activities. We introduce two complexity reducing restrictions of the problem (which takes exponential time) and develop algorithms for each. We experimentally evaluate our exponential algorithm as well as the restricted algorithms on both synthetic data and a real (depersonalized) travel data set consisting of 5.5 million observations. Our experiments show that MAGIC consumes reasonable amounts of memory and can retrieve completed instances of activities in just a few seconds. We also report appropriate statistical significance results validating our experimental hypotheses.
Keywords: complexity; graph; detection; complexity; graph; index; probability; MAGIC; activity; reducing; restrictions; exponential; theory; probability; threshold; computational; time; multiactivity

Manufacturing multi-material articulated plastic products using in-mold assembly - Priyadarshi,Alok; Gupta, Satyandra K.; Gouker,Regina; Krebs,Florian; Shroeder,Martin; Warth,Stefan (The International Journal of Advanced Manufacturing Technology, 2007)
In-mold assembly can be used to create plastic products with articulated joints. This process eliminates the need for post-molding assembly and reduces the number of parts being used in the product, hence improving the product quality. However, designing both products and molds is significantly more challenging in case of in-mold assembly. Currently, a systematic methodology does not exist for developing product and processes to exploit potential benefits of in-mold assembly for creating articulated joints. This paper is a step towards creating such a methodology and reports the following three results. First, it presents a model for designing assemblies and molding process so that the joint clearances and variation in the joint clearances can meet the performance goals. Second, it describes proven mold design templates for realizing revolute, prismatic, and spherical joints. Third, it describes a mold design methodology for designing molds for products that contain articulated joints and will be produced using in-mold assembly process. Three case studies are also presented to illustrate how in-mold assembly process can be used to create articulated devices.
Keywords: engineering

An M-channel directional filter bank compatible with the contourlet and shearlet frequency tiling - Easley,G. R; Patel, Vishal M.; Healy Jr,D.M. (Proceedings of SPIE, 2007)

Measuring variability in sentence ordering for news summarization - Madnani,Nitin; Passonneau,Rebecca; Ayan,Necip Fazil; Conroy,John M.; Dorr, Bonnie J; Klavans,Judith L.; O'Leary, Dianne P.; Schlesinger,Judith D. (Proceedings of the Eleventh European Workshop on Natural Language Generation, 2007)
The issue of sentence ordering is an important one for natural language tasks such as multi-document summarization, yet there has not been a quantitative exploration of the range of acceptable sentence orderings for short texts. We present results of a sentence reordering experiment with three experimental conditions. Our findings indicate a very high degree of variability in the orderings that the eighteen subjects produce. In addition, the variability of reorderings is significantly greater when the initial ordering seen by subjects is different from the original summary. We conclude that evaluation of sentence ordering should use multiple reference orderings. Our evaluation presents several metrics that might prove useful in assessing against multiple references. We conclude with a deeper set of questions: (a) what sorts of independent assessments of quality of the different reference orderings could be made and (b) whether a large enough test set would obviate the need for such independent means of quality assessment.

Microarray analysis of gene expression induced by sexual contact in Schistosoma mansoni - Waisberg,Michael; Lobo,Francisco; Cerqueira,Gustavo; Passos,Liana; Carvalho,Omar; Franco,Gloria; El‐Sayed, Najib M. (BMC Genomics, 2007)
BACKGROUND:The parasitic trematode Schistosoma mansoni is one of the major causative agents of Schistosomiasis, a disease that affects approximately 200 million people, mostly in developing countries. Since much of the pathology is associated with eggs laid by the female worm, understanding the mechanisms involved in oogenesis and sexual maturation is an important step towards the discovery of new targets for effective drug therapy. It is known that the adult female worm only develops fully in the presence of a male worm and that the rates of oviposition and maturation of eggs are significantly increased by mating. In order to study gene transcripts associated with sexual maturation and oviposition, we compared the gene expression profiles of sexually mature and immature parasites using DNA microarrays.RESULTS:For each experiment, three amplified RNA microarray hybridizations and their dye swaps were analyzed. Our results show that 265 transcripts are differentially expressed in adult females and 53 in adult males when mature and immature worms are compared. Of the genes differentially expressed, 55% are expressed at higher levels in paired females while the remaining 45% are more expressed in unpaired ones and 56.6% are expressed at higher levels in paired male worms while the remaining 43.4% are more expressed in immature parasites. Real-time RT-PCR analysis validated the microarray results. Several new maturation associated transcripts were identified. Genes that were up-regulated in single-sex females were mostly related to energy generation (i.e. carbohydrate and protein metabolism, generation of precursor metabolites and energy, cellular catabolism, and organelle organization and biogenesis) while genes that were down-regulated related to RNA metabolism, reactive oxygen species metabolism, electron transport, organelle organization and biogenesis and protein biosynthesis.CONCLUSION:Our results confirm previous observations related to gene expression induced by sexual maturation in female schistosome worms. They also increase the list of S. mansoni maturation associated transcripts considerably, therefore opening new and exciting avenues for the study of the conjugal biology and development of new drugs against schistosomes.

Minimus: a fast, lightweight genome assembler - Sommer,Daniel D; Delcher,Arthur L.; Salzberg,Steven L.; Pop, Mihai (BMC Bioinformatics, 2007)
Genome assemblers have grown very large and complex in response to the need for algorithms to handle the challenges of large whole-genome sequencing projects. Many of the most common uses of assemblers, however, are best served by a simpler type of assembler that requires fewer software components, uses less memory, and is far easier to install and run.

Model and algorithms for point cloud construction using digital projection patterns - Peng,T.; Gupta,S.K. (Journal of Computing and Information Science in Engineering, 2007)

Multi-Dimensional Range Query over Encrypted Data - Elaine Shi; Bethencourt, J.; Chan, T.-H.H.; Song, Dawn; Perrig, A. (2007)
We design an encryption scheme called multi-dimensional range query over encrypted data (MRQED), to address the privacy concerns related to the sharing of network audit logs and various other applications. Our scheme allows a network gateway to encrypt summaries of network flows before submitting them to an untrusted repository. When network intrusions are suspected, an authority can release a key to an auditor, allowing the auditor to decrypt flows whose attributes (e.g., source and destination addresses, port numbers, etc.) fall within specific ranges. However, the privacy of all irrelevant flows are still preserved. We formally define the security for MRQED and prove the security of our construction under the decision bilinear Diffie-Hellman and decision linear assumptions in certain bilinear groups. We study the practical performance of our construction in the context of network audit logs. Apart from network audit logs, our scheme also has interesting applications for financial audit logs, medical privacy, untrusted remote storage, etc. In particular, we show that MRQED implies a solution to its dual problem, which enables investors to trade stocks through a broker in a privacy-preserving manner.
Keywords: auditing; cryptography; data privacy; decision bilinear Diffie-Hellman; decision linear assumptions; encrypted data; multi-dimensional range query; network audit logs; network gateway; network intrusions

NetLens: Iterative Exploration of Content-Actor Network Data - Kang,Hyunmo; Plaisant, Catherine; Lee,Bongshin; Bederson, Benjamin B. (Information VisualizationInformation Visualization, 2007)
Networks have remained a challenge for information retrieval and visualization because of the rich set of tasks that users want to accomplish. This paper offers an abstract Content-Actor network data model, a classification of tasks, and a tool to support them. The NetLens interface was designed around the abstract Content-Actor network data model to allow users to pose a series of elementary queries and iteratively refine visual overviews and sorted lists. This enables the support of complex queries that are traditionally hard to specify. NetLens is general and scalable in that it applies to any data set that can be represented with our abstract data model. This paper describes the use of NetLens with a subset of the ACM Digital Library consisting of about 4000 papers from the CHI conference written by about 6000 authors, and reports on a usability study with nine participants.
Keywords: content-actor network data; digital library; incremental data exploration; iterative query refinement; User interfaces

NetLens: iterative exploration of content-actor network data - Kang,H.; Plaisant, Catherine; Lee,B.; Bederson, Benjamin B. (Information Visualization, 2007)

Ontologies for reasoning about failures in AI systems - Schmill,M.; Josyula,D.; Anderson,M. L; Wilson,S.; Oates,T.; Perlis, Don; Fults,S. (Proceedings from the Workshop on Metareasoning in Agent Based Systems at the Sixth International Joint Conference on Autonomous Agents and Multiagent Sytems, 2007)

Out-of-core Multi-resolution Terrain Modeling - Danovaro,E.; De Floriani, Leila; Puppo,E.; Samet, Hanan (Spatial data on the Web: modeling and management, 2007)

Parameterized Looped Schedules for Compact Representation of Execution Sequences in DSP Hardware and Software Implementation - Ming-Yung Ko; Zissulescu,C.; Puthenpurayil,S.; Bhattacharyya, Shuvra S.; Kienhuis,B.; Deprettere,E. F (IEEE Transactions on Signal Processing, 2007)
In this paper, we present a technique for compact representation of execution sequences in terms of efficient looping constructs. Here, by a looping construct, we mean a compact way of specifying a finite repetition of a set of execution primitives. Such compaction, which can be viewed as a form of hierarchical run-length encoding (RLE), has application in many very large scale integration (VLSI) signal processing contexts, including efficient control generation for Kahn processes on field-programmable gate arrays (FPGAs), and software synthesis for static dataflow models of computation. In this paper, we significantly generalize previous models for loop-based code compaction of digital signal processing (DSP) programs to yield a configurable code compression methodology that exhibits a broad range of achievable tradeoffs. Specifically, we formally develop and apply to DSP hardware and software synthesis a parameterizable loop scheduling approach with compact format, dynamic reconfigurability, and low-overhead decompression
Keywords: Application software; array signal processing; code compression methodology; compact representation; Compaction; data compression; Design automation; Digital signal processing; digital signal processing chips; DSP; DSP hardware; embedded systems; Encoding; Field programmable gate arrays; field-programmable gate arrays (FPGAs); FPGA; Hardware; hierarchical runlength encoding; high-level synthesis; Kahn process; loop-based code compaction; looping construct; parameterized loop schedules; program compilers; reconfigurable design; runlength codes; scheduling; Signal generators; Signal processing; Signal synthesis; software engineering; software implementation; static dataflow models; Very large scale integration; VLSI

Parameterized st-Orientations of Graphs: Algorithms and Experiments - Charalampos Papamanthou; Tollis, Ioannis G. (Graph Drawing, 2007)
st-orientations (st-numberings) or bipolar orientations of undirected graphs are central to many graph algorithms and applications. Several algorithms have been proposed in the past to compute an st-orientation of a biconnected graph. However, as indicated in [1], the computation of more than one st-orientation is very important for many applications in multiple research areas, such as this of Graph Drawing. In this paper we show how to compute such orientations with certain (parameterized) characteristics in the final st-oriented graph, such as the length of the longest path. Apart from Graph Drawing, this work applies in other areas such as Network Routing and in tackling difficult problems such as Graph Coloring and Longest Path. We present primary approaches to the problem of computing longest path parameterized st-orientations of graphs, an analytical presentation (together with proof of correctness) of a new O(mlog5 n) (O(mlogn) for planar graphs) time algorithm that computes such orientations (and which was used in [1]) and extensive computational results that reveal the robustness of the algorithm.
Keywords: Algorithm Analysis and Problem Complexity; Computer Graphics; Data structures; Discrete Mathematics in Computer Science

Portcullis: protecting connection setup from denial-of-capability attacks - Parno, Bryan; Wendlandt, Dan; Elaine Shi; Perrig, Adrian; Maggs, Bruce; Hu, Yih-Chun (ACM, 2007)
Systems using capabilities to provide preferential service to selected flows have been proposed as a defense against large-scale network denial-of-service attacks. While these systems offer strong protection for established network flows, the Denial-of-Capability (DoC) attack, which prevents new capability-setup packets from reaching the destination, limits the value of these systems. Portcullis mitigates DoC attacks by allocating scarce link bandwidth for connection establishment packets based on per-computation fairness. We prove that a legitimate sender can establish a capability with high probability regardless of an attacker's resources or strategy and that no system can improve on our guarantee. We simulate full and partial deployments of Portcullis on an Internet-scale topology to confirm our theoretical results and demonstrate the substantial benefits of using per-computation fairness.
Keywords: network capability; per-computation fairness

Probabilistic go theories - Parker,A.; Yaman,F.; Nau, Dana S.; V.S. Subrahmanian (2007)
There are numerous cases where we need to rea- son about vehicles whose intentions and itineraries are not known in advance to us. For example, Coast Guard agents tracking boats don’t always know where they are headed. Likewise, in drug en- forcement applications, it is not always clear where drug-carrying airplanes (which do often show up on radar) are headed, and how legitimate planes with an approved flight manifest can avoid them. Likewise, traffic planners may want to understand how many vehicles will be on a given road at a given time. Past work on reasoning about vehi- cles (such as the “logic of motion” by Yaman et. al. [Yaman et al., 2004]) only deals with vehicles whose plans are known in advance and don’t cap- ture such situations. In this paper, we develop a for- mal probabilistic extension of their work and show that it captures both vehicles whose itineraries are known, and those whose itineraries are not known. We show how to correctly answer certain queries against a set of statements about such vehicles. A prototype implementation shows our system to work efficiently in practice.

Probabilistic Relational Models - Getoor, Lise; Friedman,N.; Koller,D.; Pfeffer,A.; Taskar,B. (Introduction to Statistical Relational LearningIntroduction to Statistical Relational Learning, 2007)

Provable algorithms for joint optimization of transport, routing and MAC layers in wireless ad hoc networks - Kumar,V. S.A; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind (Proc. DialM-POMC Workshop on Foundations of Mobile Computing, 2007)

Recovery in culture of viable but nonculturable Vibrio parahaemolyticus: regrowth or resuscitation? - Coutard,Fran|[ccedil]|ois; Crassous,Philippe; Droguet,Micka|[euml]|l; Gobin,Eric; Rita R Colwell; Pommepuy,Monique; Hervio-Heath,Dominique (The ISME Journal, 2007)
The objective of this study was to explore the recovery of culturability of viable but nonculturable (VBNC) Vibrio parahaemolyticus after temperature upshift and to determine whether regrowth or resuscitation occurred. A clinical strain of V. parahaemolyticus Vp5 was rendered VBNC by exposure to artificial seawater (ASW) at 4°C. Aliquots of the ASW suspension of cells (0.1, 1 and 10 ml) were subjected to increased temperatures of 20°C and 37°C. Culturability of the cells in the aliquots was monitored for colony formation on a rich medium and changes in morphology were measured by scanning (SEM) and transmission (TEM) electron microscopy. Samples of VBNC cells were fixed and examined by SEM, revealing a heterogeneous population comprising small cells and larger, flattened cells. Forty-eight hours after temperature upshift to 20°C or 37°C, both elongation and division by binary fission of the cells were observed, employing SEM and TEM, but only in the 10-ml aliquots. The results suggest that a portion of VBNC cells is able to undergo cell division. It is concluded that a portion of VBNC cells of V. parahaemolyticus subjected to cold temperatures remain viable. After temperature upshift, regrowth of those cells, rather than resuscitation of all bacteria of the initial inoculum, appears to be responsible for recovery of culturability of VBNC cells of V. parahaemolyticus. Nutrient in filtrates of VBNC cells is hypothesized to allow growth of the temperature-responsive cells, with cell division occurring via binary fission, but also including an atypical, asymmetric cell division.
Keywords: ecophysiology; ecosystems; environmental biotechnology; geomicrobiology; ISME J; microbe interactions; microbial communities; microbial ecology; microbial engineering; microbial epidemiology; microbial genomics; microorganisms

Reliable Effects Screening: A Distributed Continuous Quality Assurance Process for Monitoring Performance Degradation in Evolving Software Systems - Yilmaz,C.; Porter, Adam; Krishna,A. S; Memon, Atif M.; Schmidt,D. C; Gokhale,A.S.; Natarajan,B. (Software Engineering, IEEE Transactions on, 2007)
Developers of highly configurable performance-intensive software systems often use in-house performance-oriented "regression testing" to ensure that their modifications do not adversely affect their software's performance across its large configuration space. Unfortunately, time and resource constraints can limit in-house testing to a relatively small number of possible configurations, followed by unreliable extrapolation from these results to the entire configuration space. As a result, many performance bottlenecks escape detection until systems are fielded. In our earlier work, we improved the situation outlined above by developing an initial quality assurance process called "main effects screening". This process 1) executes formally designed experiments to identify an appropriate subset of configurations on which to base the performance-oriented regression testing, 2) executes benchmarks on this subset whenever the software changes, and 3) provides tool support for executing these actions on in-the-field and in-house computing resources. Our initial process had several limitations, however, since it was manually configured (which was tedious and error-prone) and relied on strong and untested assumptions for its accuracy (which made its use unacceptably risky in practice). This paper presents a new quality assurance process called "reliable effects screening" that provides three significant improvements to our earlier work. First, it allows developers to economically verify key assumptions during process execution. Second, it integrates several model-driven engineering tools to make process configuration and execution much easier and less error prone. Third, we evaluate this process via several feasibility studies of three large, widely used performance-intensive software frameworks. Our results indicate that reliable effects screening can detect performance degradation in large-scale systems more reliably and with significantly less resources than conventional t- echniques
Keywords: configuration subset; distributed continuous quality assurance process; evolving software systems; in house testing; main effects screening; performance bottlenecks; performance degradation monitoring; performance intensive software systems; process configuration; process execution; program testing; regression testing; reliable effects screening; software benchmarks; Software performance; software performance evaluation; Software quality; software reliability; tool support

Scalable Uncertainty Management: First International Conference, SUM 2007, Washington, DC, USA, October 10-12, 2007 : Proceedings - Prade,Henri; V.S. Subrahmanian (Springer, 2007)
This book constitutes the refereed proceedings of the First International Conference on Scalable Uncertainty Management, SUM 2007, held in Washington, DC, USA, in Oktober 2007.The 20 revised full papers presented were carefully reviewed and selected from numerous submissions for inclusion in the book. The papers address artificial intelligence researchers, database researchers, and practitioners to demonstrate theoretical techniques required to manage the uncertainty that arises in large scale real world applications. The papers deal with the following topics: uncertainty models, probabilistic logics, fuzzy logics, and annotated logics, inconsistency logics, database algebras and calculi, scalable database systems, spatial, temporal, mobile and multimedia databases, as well as implementations, and applications.
Keywords: Artificial intelligence; Computers / Information Theory; Computers / Intelligence (AI) & Semantics; Electronic books; Mathematics / Logic; Uncertainty (Information theory)

A semantic web environment for digital shapes understanding - De Floriani, Leila; Hui,Annie; Papaleo,Laura; Huang,May; Hendler,James (Proceedings of the semantic and digital media technologies 2nd international conference on Semantic Multimedia, 2007)
In the last few years, the volume of multimedia content available on the Web significantly increased. This led to the need for techniques to handle such data. In this context, we see a growing interest in considering the Semantic Web in action and in the definition of tools capable of analyzing and organizing digital shape models. In this paper, we present a Semantic Web environment, be-SMART, for inspecting 3D shapes and for structuring and annotating such shapes according to ontology-driven metadata. Specifically, we describe in details the first module of be-SMART, the Geometry and Topology Analyzer, and the algorithms we have developed for extracting geometrical and topological information from 3D shapes. We also describe the second module, the Topological Decomposer, which produces a graph-based representation of the decomposition of the shape into manifold components. This is successively modified by the third and the fourth modules, which perform the automatic and manual segmentation of the manifold parts.
Keywords: digital shapes; semantic annotation; semantic web; shape analysis; shape understanding

Sentiment analysis: Adjectives and adverbs are better than adjectives alone - Benamara,F.; Cesarano,C.; Picariello, A.; Reforgiato,D.; V.S. Subrahmanian (Proceedings of the International Conference on Weblogs and Social Media (ICWSM), 2007)
Most past work on determining the strength of subjective expres-sions within a sentence or a document use specific parts of speech such as adjectives, verbs and nouns. To date, there is almost no work on the use of adverbs in sentiment analysis, nor has there been any work on the use of adverb-adjective combinations (AACs). We propose an AAC-based sentiment analysis technique that uses a lin- guistic analysis of adverbs of degree. We define a set of general axioms (based on a classification of adverbs of degree into five cat- egories) that all adverb scoring techniques must satisfy. Instead of aggregating scores of both adverbs and adjectives using simple scor- ing functions, we propose an axiomatic treatment of AACs based on the linguistic classification of adverbs. Three specific AAC scor- ing methods that satisfy the axioms are presented. We describe the results of experiments on an annotated set of 200 news articles (an- notated by 10 students) and compare our algorithms with some exist- ing sentiment analysis algorithms. We show that our results lead to higher accuracy based on Pearson correlation with human subjects.

Signal Processing for Biometric Systems [DSP Forum] - Jain, A.K.; Chellapa, Rama; Draper, S.C.; Memon, N.; Phillips,P.J.; Vetro, A. (Signal Processing Magazine, IEEE, 2007)
This IEEE signal processing magazine (SPM) forum discuses signal processing applications, technologies, requirements, and standardization of biometric systems. The forum members bring their expert insights into issues such as biometric security, privacy, and multibiometric and fusion techniques. The invited forum members are Prof. Anil K. Jain of Michigan State University, Prof. Rama Chellappa of the University of Maryland, Dr. Stark C. Draper of theUniversity of Wisconsin in Madison, Prof. Nasir Memon of Polytechnic University, and Dr. P. Jonathon Phillips of the National Institute of Standards and Technology. The moderator of the forum is Dr. Anthony Vetro of Mitsubishi Electric Research Labs, and associate editor of SPM.
Keywords: (access; biometric; control); security; signal; forum; signal; magazine; PROCESSING; processing; security; biometric; standardization; fusion; systems; technique; multibiometric; technique; signal; technology; biometrics

Similarity-Based Forecasting with Simultaneous Previews: A River Plot Interface for Time Series Forecasting - Buono,P.; Plaisant, Catherine; Simeone,A.; Aris,A.; Shneiderman, Ben; Shmueli,G.; Jank,W. (Information Visualization, 2007. IV '07. 11th International Conference, 2007)
Time-series forecasting has a large number of applications. Users with a partial time series for auctions, new stock offerings, or industrial processes desire estimates of the future behavior. We present a data driven forecasting method and interface called similarity-based forecasting (SBF). A pattern matching search in an historical time series dataset produces a subset of curves similar to the partial time series. The forecast is displayed graphically as a river plot showing statistical information about the SBF subset. A forecasting preview interface allows users to interactively explore alternative pattern matching parameters and see multiple forecasts simultaneously. User testing with 8 users demonstrated advantages and led to improvements.
Keywords: data driven forecasting method; data visualisation; Data visualization; Economic forecasting; forecasting preview interface; Graphical user interfaces; historical time series dataset; Laboratories; new stock offerings; partial time series; pattern matching; pattern matching search; Predictive models; river plot interface; Rivers; similarity-based forecasting; Smoothing methods; Technological innovation; Testing; time series; time series forecasting; Weather forecasting

Skoll: A Process and Infrastructure for Distributed Continuous Quality Assurance - Porter, Adam; Yilmaz,C.; Memon, Atif M.; Schmidt,D. C; Natarajan,B. (Software Engineering, IEEE Transactions on, 2007)
Software engineers increasingly emphasize agility and flexibility in their designs and development approaches. They increasingly use distributed development teams, rely on component assembly and deployment rather than green field code writing, rapidly evolve the system through incremental development and frequent updating, and use flexible product designs supporting extensive end-user customization. While agility and flexibility have many benefits, they also create an enormous number of potential system configurations built from rapidly changing component implementations. Since today's quality assurance (QA) techniques do not scale to handle highly configurable systems, we are developing and validating novel software QA processes and tools that leverage the extensive computing resources of user and developer communities in a distributed, continuous manner to improve software quality significantly. This paper provides several contributions to the study of distributed, continuous QA (DCQA). First, it shows the structure and functionality of Skoll, which is an environment that defines a generic around-the-world, around-the-clock QA process and several sophisticated tools that support this process. Second, it describes several novel QA processes built using the Skoll environment. Third, it presents two studies using Skoll: one involving user testing of the Mozilla browser and another involving continuous build, integration, and testing of the ACE+TAO communication software package. The results of our studies suggest that the Skoll environment can manage and control distributed continuous QA processes more effectively than conventional QA processes. For example, our DCQA processes rapidly identified problems that had taken the ACE+TAO developers much longer to find and several of which they had not found. Moreover, the automatic analysis of QA results provided developers information that enabled them to quickly find the root causes of problems
Keywords: ACE+TAO communication software package; component assembly; component deployment; distributed continuous quality assurance; distributed development teams; distributed processing; end-user customization; flexible product design; incremental development; object-oriented programming; Skoll; software engineering; Software quality; systems analysis

Software configuration management using ontologies - Shahri,H. H; Hendler,J. A; Porter, Adam (3rd International Workshop on Semantic Web Enabled Software Engineering (SWESE 2007), Innsubruk, Austria, 2007)

Something that is interesting is interesting then: Using text minig and visualizations to aid interpreting repetition in Gertrude Stein’s The Making of Americans - Clement,T.; Don,A.; Plaisant, Catherine; Auvil,L.; Pape,G.; Goren,V. (Proceedings of the Digital Humanities Conference, 2007)

Special Issue in Honor of Ben Shneiderman's 60th Birthday: Reflections on Human-Computer Interaction - Plaisant, Catherine; North,Chris (International Journal of Human-Computer Interaction, 2007)

Story creation from heterogeneous data sources - Fayzullin,M.; V.S. Subrahmanian; Albanese, M.; Cesarano,C.; Picariello, A. (Multimedia Tools and Applications, 2007)
There are numerous applications where there is a need to rapidly infer a story about a given subject from a given set of potentially heterogeneous data sources. In this paper, we formally define a story to be a set of facts about a given subject that satisfies a “story length” constraint. An optimal story is a story that maximizes the value of an objective function measuring the goodness of a story. We present algorithms to extract stories from text and other data sources. We also develop an algorithm to compute an optimal story, as well as three heuristic algorithms to rapidly compute a suboptimal story. We run experiments to show that constructing stories can be efficiently performed and that the stories constructed by these heuristic algorithms are high quality stories. We have built a prototype STORY system based on our model—we briefly describe the prototype as well as one application in this paper.

Structural Footprinting in Protein Structure Comparison: The Impact of Structural Fragments - Zotenko,Elena; Dogan,Rezarta Islamaj; Wilbur,W. John; O'Leary, Dianne P.; Przytycka,Teresa M. (BMC Structural Biology, 2007)
Abstract Background One approach for speeding-up protein structure comparison is the projection approach, where a protein structure is mapped to a high-dimensional vector and structural similarity is approximated by distance between the corresponding vectors. Structural footprinting methods are projection methods that employ the same general technique to produce the mapping: first select a representative set of structural fragments as models and then map a protein structure to a vector in which each dimension corresponds to a particular model and "counts" the number of times the model appears in the structure. The main difference between any two structural footprinting methods is in the set of models they use; in fact a large number of methods can be generated by varying the type of structural fragments used and the amount of detail in their representation. How do these choices affect the ability of the method to detect various types of structural similarity? Results To answer this question we benchmarked three structural footprinting methods that vary significantly in their selection of models against the CATH database. In the first set of experiments we compared the methods' ability to detect structural similarity characteristic of evolutionarily related structures, i.e., structures within the same CATH superfamily. In the second set of experiments we tested the methods' agreement with the boundaries imposed by classification groups at the Class, Architecture, and Fold levels of the CATH hierarchy. Conclusion In both experiments we found that the method which uses secondary structure information has the best performance on average, but no one method performs consistently the best across all groups at a given classification level. We also found that combining the methods' outputs significantly improves the performance. Moreover, our new techniques to measure and visualize the methods' agreement with the CATH hierarchy, including the threshholded affinity graph, are useful beyond this work. In particular, they can be used to expose a similar composition of different classification groups in terms of structural fragments used by the method and thus provide an alternative demonstration of the continuous nature of the protein structure universe.

Surface Segmentation through Concentrated Curvature - Mesmoudi,M. M.; Danovaro,E.; De Floriani, Leila; Port,U. (Image Analysis and Processing, 2007. ICIAP 2007. 14th International Conference on, 2007)
Curvature is one of the most relevant notions that links the metric properties of a surface to its geometry and to its topology (Gauss-Bonnet theorem). In the literature, a variety of approaches exist to compute curvatures in the discrete case. Several techniques are computationally intensive or suffer from convergence problems. In this paper, we discuss the notion of concentrated curvature, introduced by Troyanov [24]. We discuss properties of this curvature and compare with a widely-used technique that estimates the Gaussian curvatures on a triangulated surface. We apply our STD method [13] for terrain segmentation to segment a surface by using different curvature approaches and we illustrate our comparisons through examples.
Keywords: curvature; convergence; curvatures; concentrated; Gauss-Bonnet; problems; surface; processes; image; segmentation; segmentation; terrain; segmentation; triangulated; surface; Gaussian; theorem; Gaussian

Swarm Intelligence Systems Using Guided Self-Organization for Collective Problem Solving - RodrIGuez,A.; Grushin,A.; Reggia, James A.; HAUPTMAN,AMI; SIPPER,M.; PAN,Z.; Reggia, James A.; GAO,D.; DARABOS,C.; GIACOBINI,M.; others (Advances in Complex Systems, 2007)

Task-based interaction with an integrated multilingual, multimedia information system: a formative evaluation - Zhang,Pengyi; Plettenberg,Lynne; Klavans,Judith L.; Oard, Douglas; Soergel,Dagobert (Proceedings of the 7th ACM/IEEE-CS joint conference on Digital libraries, 2007)
This paper describes a formative evaluation of an integrated multilingual, multimedia information system, a series of user studies designed to guide system development. The system includes automatic speech recognition for English, Chinese, and Arabic, automatic translation from Chinese and Arabic into English, and query-based and profile-based search options. The study design emphasizes repeated evaluation with the same (increasingly experienced) participants, exploration of alternative task designs, rich qualitative and quantitative data collection, and rapid analysis to provide the timely feedback needed to support iterative and responsive development. Results indicate that users presented with materials in a language that they do not know can generate remarkably useful work products, but that integration of transcription, translation, search and profile management poses challenges that would be less evident were each technology to be evaluated in isolation.
Keywords: Cross-language information retrieval; multimedia; User studies

A taxonomy for medical image registration acceleration techniques - Plishker,W.; Dandekar,O.; Bhattacharyya, Shuvra S.; Shekhar,R. (Life Science Systems and Applications Workshop, 2007. LISA 2007. IEEE/NIH, 2007)

Techniques for Classifying Executions of Deployed Software to Support Software Engineering Tasks - Haran,Murali; Karr,Alan; Last,Michael; Orso,Alessandro; Porter, Adam; Sanil,Ashish; Fouch?,Sandro (IEEE Transactions on Software Engineering, 2007)
There is an increasing interest in techniques that support analysis and measurement of fielded software systems. These techniques typically deploy numerous instrumented instances of a software system, collect execution data when the instances run in the field, and analyze the remotely collected data to better understand the system's in-the-field behavior. One common need for these techniques is the ability to distinguish execution outcomes (e.g., to collect only data corresponding to some behavior or to determine how often and under which condition a specific behavior occurs). Most current approaches, however, do not perform any kind of classification of remote executions and either focus on easily observable behaviors (e.g., crashes) or assume that outcomes' classifications are externally provided (e.g., by the users). To address the limitations of existing approaches, we have developed three techniques for automatically classifying execution data as belonging to one of several classes. In this paper, we introduce our techniques and apply them to the binary classification of passing and failing behaviors. Our three techniques impose different overheads on program instances and, thus, each is appropriate for different application scenarios. We performed several empirical studies to evaluate and refine our techniques and to investigate the trade-offs among them. Our results show that 1) the first technique can build very accurate models, but requires a complete set of execution data; 2) the second technique produces slightly less accurate models, but needs only a small fraction of the total execution data; and 3) the third technique allows for even further cost reductions by building the models incrementally, but requires some sequential ordering of the software instances' instrumentation.
Keywords: execution classification; remote analysis/measurement.

Time and Space Efficient Algorithms for Two-Party Authenticated Data Structures - Charalampos Papamanthou; Tamassia, Roberto (Information and Communications Security, 2007)
Authentication is increasingly relevant to data management. Data is being outsourced to untrusted servers and clients want to securely update and query their data. For example, in database outsourcing, a client’s database is stored and maintained by an untrusted server. Also, in simple storage systems, clients can store very large amounts of data but at the same time, they want to assure their integrity when they retrieve them. In this paper, we present a model and protocol for two-party authentication of data structures. Namely, a client outsources its data structure and verifies that the answers to the queries have not been tampered with. We provide efficient algorithms to securely outsource a skip list with logarithmic time overhead at the server and client and logarithmic communication cost, thus providing an efficient authentication primitive for outsourced data, both structured (e.g., relational databases) and semi-structured (e.g., XML documents). In our technique, the client stores only a constant amount of space, which is optimal. Our two-party authentication framework can be deployed on top of existing storage applications, thus providing an efficient authentication service. Finally, we present experimental results that demonstrate the practical efficiency and scalability of our scheme.
Keywords: Algorithm Analysis and Problem Complexity; Computer Communication Networks; computers and society; Data Encryption; Management of Computing and Information Systems; Systems and Data Security

Toward domain-neutral human-level metacognition - Anderson,M. L; Schmill,M.; Oates,T.; Perlis, Don; Josyula,D.; Wright,D.; Wilson,S. (AAAI Spring Symposium on Logical Formalizations of Commonsense Reasoning, 2007)

Towards a heterogeneous medical image registration acceleration platform - Plishker,W.; Dandekar,O.; Bhattacharyya, Shuvra S.; Shekhar,R. (Biomedical Circuits and Systems Conference, 2007. BIOCAS 2007. IEEE, 2007)

Towards a semantic web system for understanding real world representations - Papaleo,L.; De Floriani, Leila; Hendler,J.; Hui,A. (Proceedings of the Tenth International Conference on Computer Graphics and Artificial Intelligence, 2007)
As the volume of multimedia content available on the Web continues to increase, there is a clearneed for more advanced techniques for effective retrieval and management of such data. In this context, we see a growing interest in exploiting the potential of the Semantic Web in different research fields. But, on the other hand, there is a general lack of tools able to analyse, organize and understand digital shape models (especially 3D models) for easily populating repositories with complete and well-detailed metadata. Several steps are necessary to create and associate semantics with a shape and some of them are clearly context-dependent. In this paper, we present the design details of our new system, that we call be-SMART, for inspecting digital 3D shapes by extracting geometrical and topological information from them and for structuring and annotating these shapes using ontology-driven metadata. In particular, we describe the general structure of the system, the different modules and their mutual relations. We then concentrate on the first two modules of the system showing how the 3D models are annotated following ontology-driven metadata. We also provide motivations for further work in developing new techniques for both annotating and managing 3D models on the Web.

Towards the development of a virtual environment-based training system for mechanical assembly operations - Brough,John; Schwartz,Maxim; Gupta, Satyandra K.; Anand,Davinder; Kavetsky,Robert; Pettersen,Ralph (Virtual Reality, 2007)
In this paper, we discuss the development of Virtual Training Studio (VTS), a virtual environment-based training system that allows training supervisors to create training instructions and allows trainees to learn assembly operations in a virtual environment. Our system is mainly focused on the cognitive side of training so that trainees can learn to recognize parts, remember assembly sequences, and correctly orient the parts during assembly operations. Our system enables users to train using the following three training modes: (1) Interactive Simulation, (2) 3D Animation, and (3) Video. Implementing these training modes required us to develop several new system features. This paper presents an overview of the VTS system and describes a few main features of the system. We also report user test results that show how people train using our system. The user test results indicate that the system is able to support a wide variety of training preferences and works well to support training for assembly operations.
Keywords: Computer science

Variola virus topoisomerase: DNA cleavage specificity and distribution of sites in Poxvirus genomes - Minkah,Nana; Hwang,Young; Perry,Kay; Van Duyne,Gregory D.; Hendrickson,Robert; Lefkowitz,Elliot J.; Hannenhalli, Sridhar; Bushman,Frederic D. (Virology, 2007)
Topoisomerase enzymes regulate superhelical tension in DNA resulting from transcription, replication, repair, and other molecular transactions. Poxviruses encode an unusual type IB topoisomerase that acts only at conserved DNA sequences containing the core pentanucleotide 5'-(T/C)CCTT-3'. In X-ray structures of the variola virus topoisomerase bound to DNA, protein-DNA contacts were found to extend beyond the core pentanucleotide, indicating that the full recognition site has not yet been fully defined in functional studies. Here we report quantitation of DNA cleavage rates for an optimized 13 bp site and for all possible single base substitutions (40 total sites), with the goals of understanding the molecular mechanism of recognition and mapping topoisomerase sites in poxvirus genome sequences. The data allow a precise definition of enzyme-DNA interactions and the energetic contributions of each. We then used the resulting "action matrix" to show that favorable topoisomerase sites are distributed all along the length of poxvirus DNA sequences, consistent with a requirement for local release of superhelical tension in constrained topological domains. In orthopox genomes, an additional central cluster of sites was also evident. A negative correlation of predicted topoisomerase sites was seen relative to early terminators, but no correlation was seen with early or late promoters. These data define the full variola virus topoisomerase recognition site and provide a new window on topoisomerase function in vivo.
Keywords: Annotation of topoisomerase sites; Sequence specific recognition; Topoisomerase IB; Variola virus

VAST 2007 Contest - Blue Iguanodon - Grinstein,G.; Plaisant, Catherine; Laskowski,S.; O'Connell,T.; Scholtz,J.; Whiting,M. (Visual Analytics Science and Technology, 2007. VAST 2007. IEEE Symposium on, 2007)
Visual analytics experts realize that one effective way to push the field forward and to develop metrics for measuring the performance of various visual analytics components is to hold an annual competition. The second visual analytics science and technology (VAST) contest was held in conjunction with the 2007 IEEE VAST symposium. In this contest participants were to use visual analytic tools to explore a large heterogeneous data collection to construct a scenario and find evidence buried in the data of illegal and terrorist activities that were occurring. A synthetic data set was made available as well as tasks. In this paper we describe some of the advances we have made from the first competition held in 2006.
Keywords: activities; large; activities; visual; analytic; collection; terrorist; data; heterogeneous; illegal; interfaces; tools; data; user; visualisation; graphical

Achieving anonymity via clustering - Aggarwal,Gagan; Feder,Tomás; Kenthapadi,Krishnaram; Khuller, Samir; Panigrahy,Rina; Thomas,Dilys; Zhu,An (Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2006)
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying records is to remove identifying fields such as social security number, name etc. However, recent research has shown that a large fraction of the US population can be identified using non-key attributes (called quasi-identifiers) such as date of birth, gender, and zip code [15]. Sweeney [16] proposed the k-anonymity model for privacy where non-key attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k−1 other records having exactly the same values for quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a pre-specified number of data records. This technique is more general since we have a much larger choice for cluster centers than k-Anonymity. In many cases, it lets us release a lot more information without compromising privacy. We also provide constant-factor approximation algorithms to come up with such a clustering. This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k. We further observe that a few outlier points can significantly increase the cost of anonymization. Hence, we extend our algorithms to allow an ε fraction of points to remain unclustered, i.e., deleted from the anonymized publication. Thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. Our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.
Keywords: anonymity; Approximation algorithms; clustering; privacy

Acquisition of Articulated Human Body Models Using Multiple Cameras - Sundaresan,Aravind; Chellapa, Rama (Articulated Motion and Deformable ObjectsArticulated Motion and Deformable Objects, 2006)
Motion capture is an important application in different areas such as biomechanics, computer animation, and human-computer interaction. Current motion capture methods typically use human body models in order to guide pose estimation and tracking. We model the human body as a set of tapered super-quadrics connected in an articulated structure and propose an algorithm to automatically estimate the parameters of the model using video sequences obtained from multiple calibrated cameras. Our method is based on the fact that the human body is constructed of several articulated chains that can be visualised as essentially 1-D segments embedded in 3-D space and connected at specific joint locations. The proposed method first computes a voxel representation from the images and maps the voxels to a high dimensional space in order to extract the 1-D structure. A bottom-up approach is then suggested in order to build a parametric (spline-based) representation of a general articulated body in the high dimensional space followed by a top-down probabilistic approach that registers the segments to the known human body model. We then present an algorithm to estimate the parameters of our model using the segmented and registered voxels.

Algorithms for on-line monitoring of components in an optical tweezers-based assembly cell - Peng,T.; Balijepalli,A.; Gupta,S.K.; LeBrun,T. W. (2006)
Optical tweezers have emerged as a powerful tool for microand nanomanipulation. Using optical tweezers to perform auto- mated assembly requires on-line monitoring of components in the assembly workspace. This paper presents algorithms for estimat- ing positions and orientations of microscale and nanoscale com- ponents in the 3-Dimensional assembly workspace. Algorithms presented in this paper use images obtained by optical section microscopy. The images are first segmented to locate areas of in- terest and then image gradient information from the areas of in- terest is used to generate probable locations and orientations of components in the XY-plane. Finally, signature curves are com- puted and utilized to obtain component locations and orienta- tions in 3-D space. We have tested these algorithms with silica micro-spheres as well as metallic nanowires. We believe that the algorithms described in this paper will provide the foundation for realizing automated assembly operations in optical tweezers- based assembly cells.

Annotation compatibility working group report - Meyers,A.; Fang,A. C.; Ferro,L.; Kübler,S.; Jia-Lin,T.; Palmer,M.; Poesio,M.; Dolbey,A.; Schuler,K. K.; Loper,E.; Zinsmeister,H.; Penn,G.; et al. (Proceedings of the Workshop on Frontiers in Linguistically Annotated Corpora 2006, 2006)
This report explores the question of compatibility between annotation projects including translating annotation formalisms to each other or to common forms. Compatibility issues are crucial for systems that use the results of multiple annotation projects. We hope that this report will begin a concerted effort in the field to track the compatibility of annotation schemes for part of speech tagging, time annotation, treebanking, role labeling and other phenomena.

Anonymous multi-attribute encryption with range query and conditional decryption - Bethencourt, J.; Chan, H.; Perrig, A.; Elaine Shi; Song,D. (Carnegie Mellon University, 2006)
We introduce the concept of Anonymous Multi-Attribute Encryption with Range Query and Con-ditional Decryption (AMERQCD). In AMERQCD, a plaintext is encrypted under a point in multi- dimensional space. To a computationally bounded adversary, the ciphertext hides both the plaintext and the point under which it is encrypted. In a range query, a master key owner releases the decryp- tion key for an arbitrary hyper-rectangle in space, thus allowing decryption of ciphertexts previ- ously encrypted under any point within the hyper-rectangle. However, a computationally bounded adversary cannot learn any information on ciphertexts outside the range covered by the decryption key (except the fact that they do not lie within this range). We give an efficient construction based on the Decision Bilinear Diffie-Hellman (D-BDH) and Decision Linear (D-Linear) assumption.

Applications of Parameterized st-Orientations in Graph Drawing Algorithms - Charalampos Papamanthou; Tollis, Ioannis G. (Graph Drawing, 2006)
Many graph drawing algorithms use st-numberings (st-orien-tations or bipolar orientations) as a first step. An st-numbering of a biconnected undirected graph defines a directed graph with no cycles, one single source s and one single sink t. As there exist exponentially many st-numberings that correspond to a certain undirected graph G, using different st-numberings in various graph drawing algorithms can result in aesthetically different drawings with different area bounds. In this paper, we present results concerning new algorithms for parameterized st-orientations, their impact on graph drawing algorithms and especially in visibility representations.
Keywords: Algorithm Analysis and Problem Complexity; Computer Graphics; Data structures; Discrete Mathematics in Computer Science

Applying flow-sensitive CQUAL to verify MINIX authorization check placement - Fraser,Timothy; Petroni,Jr.; Arbaugh, William A. (Proceedings of the 2006 workshop on Programming languages and analysis for security, 2006)
We present the first use of flow-sensitive CQUAL to verify the placement of operating system authorization checks. Our analysis of MINIX 3 system servers and discovery of a non-exploitable Time-Of-Check/Time-Of-Use bug demonstrate the effectiveness of flow sensitive CQUAL and its advantage over earlier flow-insensitive versions. We also identify and suggest alternatives to current CQUAL usability features that encourage analysts to make omissions that cause the otherwise sound tool to produce false-negative results.
Keywords: access controls; cqual; minix

An architecture for adaptive intrusion-tolerant applications - Pal,Partha; Rubel,Paul; Atighetchi,Michael; Webber,Franklin; Sanders,William H.; Seri,Mouna; Ramasamy,HariGovind; Lyons,James; Courtney,Tod; Agbaria,Adnan; Michel Cukier; Gossett,Jeanna; et al. (Software: Practice and Experience, 2006)
Applications that are part of a mission-critical information system need to maintain a usable level of key services through ongoing cyber-attacks. In addition to the well-publicized denial of service (DoS) attacks, these networked and distributed applications are increasingly threatened by sophisticated attacks that attempt to corrupt system components and violate service integrity. While various approaches have been explored to deal with DoS attacks, corruption-inducing attacks remain largely unaddressed. We have developed a collection of mechanisms based on redundancy, Byzantine fault tolerance, and adaptive middleware that help distributed, object-based applications tolerate corruption-inducing attacks. In this paper, we present the ITUA architecture, which integrates these mechanisms in a framework for auto-adaptive intrusion-tolerant systems, and we describe our experience in using the technology to defend a critical application that is part of a larger avionics system as an example. We also motivate the adaptive responses that are key to intrusion tolerance, and explain the use of the ITUA architecture to support them in an architectural framework. Copyright © 2006 John Wiley & Sons, Ltd.
Keywords: adaptive defense; adaptive middleware; Byzantine fault tolerance; intrusion tolerance; redundancy; survivability architecture

An architecture for specification-based detection of semantic integrity violations in kernel dynamic data - Petroni Jr,N. L; Fraser,T.; Walters,A. A; Arbaugh, William A. (Proceedings of the 15th conference on USENIX Security Symposium, 2006)

Atomic instructions in java - Hovemeyer,D.; Pugh, William; Spacco,J. (ECOOP 2002—Object-Oriented Programming, 2006)

Automatic web services composition using Shop2 - Hendler,J.; Nau, Dana S.; Parsia,B.; Sirin,E.; Wu,D. (Department of Computer Science, University of Maryland, College Park, 2006)
Semantic markup of Web services will enable the automation of various kinds of tasks, including discovery, composition, and execution of Web services. We describe how an AI planning system (SHOP2) can be used with DAML-S Web service descriptions to automatically compose Web services.

Balancing Systematic and Flexible Exploration of Social Networks - Perer,A.; Shneiderman, Ben (IEEE Transactions on Visualization and Computer Graphics, 2006)
Social network analysis (SNA) has emerged as a powerful method for understanding the importance of relationships in networks. However, interactive exploration of networks is currently challenging because: (1) it is difficult to find patterns and comprehend the structure of networks with many nodes and links, and (2) current systems are often a medley of statistical methods and overwhelming visual output which leaves many analysts uncertain about how to explore in an orderly manner. This results in exploration that is largely opportunistic. Our contributions are techniques to help structural analysts understand social networks more effectively. We present SocialAction, a system that uses attribute ranking and coordinated views to help users systematically examine numerous SNA measures. Users can (1) flexibly iterate through visualizations of measures to gain an overview, filter nodes, and find outliers, (2) aggregate networks using link structure, find cohesive subgroups, and focus on communities of interest, and (3) untangle networks by viewing different link types separately, or find patterns across different link types using a matrix overview. For each operation, a stable node layout is maintained in the network visualization so users can make comparisons. SocialAction offers analysts a strategy beyond opportunism, as it provides systematic, yet flexible, techniques for exploring social networks
Keywords: Aggregates; algorithms; attribute ranking; Cluster Analysis; Computer Graphics; Computer simulation; Coordinate measuring machines; coordinated views; Data analysis; data visualisation; Data visualization; exploratory data analysis; Filters; Gain measurement; graph theory; Graphical user interfaces; Information Storage and Retrieval; interactive graph visualization; matrix algebra; matrix overview; Models, Biological; Navigation; network visualization; Pattern analysis; Population Dynamics; Social Behavior; social network analysis; Social network services; social networks; social sciences computing; Social Support; SocialAction; software; statistical analysis; statistical methods; User-Computer Interface

Ballistic hand movements - Prasad,V.; Kellokumpu,V.; Davis, Larry S. (Articulated Motion and Deformable Objects, 2006)
Common movements like reaching, striking, etc. observed during surveillance have highly variable target locations. This puts appearance-based techniques at a disadvantage for modelling and recognizing them. Psychological studies indicate that these actions are ballistic in nature. Their trajectories have simple structures and are determined to a great degree by the starting and ending positions. We present an approach for movement recognition that explicitly considers their ballistic nature. This enables the decoupling of recognition from the movement’s trajectory, allowing generalization over a range of target-positions. A given movement is first analyzed to determine if it is ballistic. Ballistic movements are further classified into reaching, striking, etc. The proposed approach was tested with motion capture data obtained from the CMU MoCap database.

Classifying science: Phenomena, data, theory, method, practice: Book Reviews - Perer,Adam; Shneiderman, Ben; Oard, Douglas (J. Am. Soc. Inf. Sci. Technol., 2006)
Due to e-mail's ubiquitous nature, millions of users are intimate with the technology; however, most users are only familiar with managing their own e-mail, which is an inherently different task from exploring an e-mail archive. Historians and social scientists believe that e-mail archives are important artifacts for understanding the individuals and communities they represent. To understand the conversations evidenced in an archive, context is needed. In this article, we present a new way to gain this necessary context: analyzing the temporal rhythms of social relationships. We provide methods for constructing meaningful rhythms from the e-mail headers by identifying relationships and interpreting their attributes. With these visualization techniques, e-mail archive explorers can uncover insights that may have been otherwise hidden in the archive. We apply our methods to an individual's 15-year e-mail archive, which consists of about 45,000 messages and over 4,000 relationships. © 2006 Wiley Periodicals, Inc.
Keywords: corpus_analysis; email; hci; project--email; text_analysis; Visualization

Compression techniques for minimum energy consumption - Puthenpurayil,S.; Gu,R.; Bhattacharyya, Shuvra S. (25th Army Science Conference, 2006)

A computational framework for point cloud construction using digital projection patterns - Peng,T.; Gupta,S.K. (2006)
Many reverse engineering and inspection applications re-quire generation of point clouds representing faces of physical objects. This paper describes a computational framework for constructing point clouds using digital projection patterns. The basic principle behind the approach is to project known patterns on the object using a digital projector. A digital camera is then used to take images of the object with the known projection pat- terns imposed on it. Due to the presence of 3-D faces of the ob- ject, the projection patterns appear distorted in the images. The images are analyzed to construct the 3-D point cloud that is ca- pable of introducing the observed distortions in the images. The approach described in this paper presents three advances over the previously developed approaches. First, it is capable of work- ing with the projection patterns that have variable fringe widths and curved fringes and hence can provide improved accuracy. Second, our algorithm minimizes the number of images needed for creating the 3-D point cloud. Finally, we use a hybrid ap- proach that uses a combination of reference plane images and es- timated system parameters to construct the point cloud. This ap- proach provides good run-time computational performance and simplifies the system calibration.

Context-sensitive correlation analysis for detecting races - Pratikakis,P.; Foster, Jeffrey S.; Hicks, Michael W. (Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI), 2006)

Covering arrays for efficient fault characterization in complex configuration spaces - Yilmaz,C.; Cohen,M. B; Porter, Adam (IEEE Transactions on Software Engineering, 2006)

Creativity Support Tools: Report From a U.S. National Science Foundation Sponsored Workshop - Shneiderman, Ben; Fischer,Gerhard; Czerwinski,Mary; Resnick,Mitch; Myers,Brad; Candy,Linda; Edmonds,Ernest; Eisenberg,Mike; Giaccardi,Elisa; Hewett,Tom; Jennings,Pamela; Kules,Bill; et al. (International Journal of Human-Computer Interaction, 2006)
Creativity support tools is a research topic with high risk but potentially very high payoff. The goal is to develop improved software and user interfaces that empower users to be not only more productive but also more innovative. Potential users include software and other engineers, diverse scientists, product and graphic designers, architects, educators, students, and many others. Enhanced interfaces could enable more effective searching of intellectual resources, improved collaboration among teams, and more rapid discovery processes. These advanced interfaces should also provide potent support in hypothesis formation, speedier evaluation of alternatives, improved understanding through visualization, and better dissemination of results. For creative endeavors that require composition of novel artifacts (e.g., computer programs, scientific papers, engineering diagrams, symphonies, artwork), enhanced interfaces could facilitate exploration of alternatives, prevent unproductive choices, and enable easy backtracking. This U.S. National Science Foundation sponsored workshop brought together 25 research leaders and graduate students to share experiences, identify opportunities, and formulate research challenges. Two key outcomes emerged: (a) encouragement to evaluate creativity support tools through multidimensional in-depth longitudinal case studies and (b) formulation of 12 principles for design of creativity support tools.Creativity support tools is a research topic with high risk but potentially very high payoff. The goal is to develop improved software and user interfaces that empower users to be not only more productive but also more innovative. Potential users include software and other engineers, diverse scientists, product and graphic designers, architects, educators, students, and many others. Enhanced interfaces could enable more effective searching of intellectual resources, improved collaboration among teams, and more rapid discovery processes. These advanced interfaces should also provide potent support in hypothesis formation, speedier evaluation of alternatives, improved understanding through visualization, and better dissemination of results. For creative endeavors that require composition of novel artifacts (e.g., computer programs, scientific papers, engineering diagrams, symphonies, artwork), enhanced interfaces could facilitate exploration of alternatives, prevent unproductive choices, and enable easy backtracking. This U.S. National Science Foundation sponsored workshop brought together 25 research leaders and graduate students to share experiences, identify opportunities, and formulate research challenges. Two key outcomes emerged: (a) encouragement to evaluate creativity support tools through multidimensional in-depth longitudinal case studies and (b) formulation of 12 principles for design of creativity support tools.

Cross-Language Access to Recorded Speech in the MALACH Project - Oard, Douglas; Demner-Fushman,Dina; Hajič,Jan; Ramabhadran,Bhuvana; Gustman,Samuel; Byrne,William; Soergel,Dagobert; Dorr, Bonnie J; Resnik, Philip; Picheny,Michael (Text, Speech and DialogueText, Speech and Dialogue, 2006)
The MALACH project seeks to help users find information in a vast multilingual collections of untranscribed oral history interviews. This paper introduces the goals of the project and focuses on supporting access by users who are unfamiliar with the interview language. It begins with a review of the state of the art in crosslanguage speech retrieval; approaches that will be investigated in the project are then described. Czech was selected as the first non-English language to be supported, so results of an initial experiment with Czech/English cross-language retrieval are reported.

Dataflow transformations in high-level DSP system design - Saha,S.; Puthenpurayil,S.; Bhattacharyya, Shuvra S. (Proceedings of the International Symposium on System-on-Chip, Tampere, Finland, 2006)

Dependent rounding and its applications to approximation algorithms - Gandhi,Rajiv; Khuller, Samir; Parthasarathy,Srinivasan; Srinivasan, Aravind (Journal of the ACM, 2006)
We develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to improved (approximation) algorithms for various problems. These include:---low congestion multi-path routing;---richer random-graph models for graphs with a given degree-sequence;---improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, as well as (iii) capacitated vertex cover; and---fair scheduling of jobs on unrelated parallel machines.
Keywords: broadcast scheduling; Randomized rounding

Dwarf cube architecture for reducing storage sizes of multidimensional data - Roussopoulos, Nick; Sismanis,John; Deligiannakis,Antonios (2006)
The invention relates to data warehouses and the ability to create and maintain data cubes of multi-dimensional data. More specifically, the invention pertains to data cube architectures that permit significant reduction of storage, exhibit very efficient retrieval and provide a very efficient incremental update of the data cubes.

Edge affinity for pose-contour matching - Prasad,V. S.N; Davis, Larry S.; Tran,Son Dinh; Elgammal,Ahmed (Computer Vision and Image Understanding, 2006)
We present an approach for whole-body pose-contour matching. Contour matching in natural images in the absence of foreground–background segmentation is difficult. Usually an asymmetric approach is adopted, where a contour is said to match well if it aligns with a subset of the image’s gradients. This leads to problems as the contour can match with a portion of an object’s outline and ignore the remainder. We present a model for using edge continuity to address this issue. Pairs of edge elements in the image are linked with affinities if they are likely to belong to the same object. A contour that matches with a set of image gradients is constrained to also match with other gradients having high affinities with the chosen ones. Experimental results show that this improves matching performance.
Keywords: Contour matching; Edge continuity

Efficient simulation of critical synchronous dataflow graphs - Hsu,C. J; Ramasubbu,S.; Ko,M. Y; Pino,J. L; Bhattacharyya, Shuvra S. (Proceedings of the 43rd annual Design Automation Conference, 2006)

Enhancing reinforcement learning with metacognitive monitoring and control for improved perturbation tolerance - Anderson,M. L; Oates,T.; Chong,W.; Perlis, Don (Journal of Experimental and Theoretical Artificial Intelligence, 2006)

Evaluation of Multilingual and Multi-modal Information Retrieval-Seventh Workshop of the Cross-Language Evaluation Forum, CLEF 2006, Alicante, Spain, September 19-21, 2006, Revised Selected Papers - Peters,C.; Clough,P.; Gey,F.; Karlgren,J.; Magnini,B.; Oard, Douglas; De Rijke,M.; Stempfhuber,M. (Seventh Workshop of the Cross-Language Evaluation Forum, CLEF 2006, 2006)

Existential Label Flow Inference Via CFL Reachability - Pratikakis,Polyvios; Foster, Jeffrey S.; Hicks, Michael W. (Static AnalysisStatic Analysis, 2006)
In programming languages, existential quantification is useful for describing relationships among members of a structured type. For example, we may have a list in which there exists some mutual exclusion lock l in each list element such that l protects the data stored in that element. With this information, a static analysis can reason about the relationship between locks and locations in the list even when the precise identity of the lock and/or location is unknown. To facilitate the construction of such static analyses, this paper presents a context-sensitive label flow analysis algorithm with support for existential quantification. Label flow analysis is a core part of many static analysis systems. Following Rehof et al, we use context-free language (CFL) reachability to develop an efficient O(n 3) label flow inference algorithm. We prove the algorithm sound by reducing its derivations to those in a system based on polymorphically-constrained types, in the style of Mossin. We have implemented a variant of our analysis as part of a data race detection tool for C programs.

Exploring auction databases through interactive visualization - Shmueli,Galit; Jank,Wolfgang; Aris,Aleks; Plaisant, Catherine; Shneiderman, Ben (Decision Support Systems, 2006)
We introduce AuctionExplorer, a suite of tools for exploring databases of online auctions. The suite combines tools for collecting, processing, and interactively exploring auction attributes (e.g., seller rating), and the bid history (price evolution represented as a time series). Part of AuctionExplorer's power comes from its coupling of the two information structures, thereby allowing exploration of relationships between them. Exploration can be directed by hypothesis testing or exploratory data analysis. We propose a process for visual data analysis and illustrate AuctionExplorer's operations with a dataset of eBay auctions. Insights may improve seller, bidder, auction house, and other vendors' understanding of the market, thereby assisting their decision making process.
Keywords: Auction dynamics; Bid history; Online auctions; time series; user interface

Exploring content-actor paired network data using iterative query refinement with NetLens - Lee,Bongshin; Kang,Hyunmo; Plaisant, Catherine; Bederson, Benjamin B. (Digital Libraries, 2006. JCDL '06. Proceedings of the 6th ACM/IEEE-CS Joint Conference on, 2006)
Networks have remained a challenge for information retrieval and visualization because of the rich set of tasks that users want to accomplish. This paper demonstrates a tool, NetLens, to explore a content-actor paired network data model. The NetLens interface was designed to allow users to pose a series of elementary queries and iteratively refine visual overviews and sorted lists. This enables the support of complex queries that are traditionally hard to specify in node-link visualizations. NetLens is general and scalable in that it applies to any dataset that can be represented with our abstract content-actor data model
Keywords: data; interface; libraries; query; management; model; data; models; data; NetLens; content-actor; network; pair; processing; user; query; refinement; data; retrieval; iterative; systems; visualisation; digital; visualization; information

Exploring erotics in Emily Dickinson's correspondence with text mining and visual interfaces - Plaisant, Catherine; Rose,James; Yu,Bei; Auvil,Loretta; Kirschenbaum,Matthew G.; Smith,Martha Nell; Clement,Tanya; Lord,Greg (Proceedings of the 6th ACM/IEEE-CS joint conference on Digital libraries, 2006)
This paper describes a system to support humanities scholars in their interpretation of literary work. It presents a user interface and web architecture that integrates text mining, a graphical user interface and visualization, while attempting to remain easy to use by non specialists. Users can interactively read and rate documents found in a digital libraries collection, prepare training sets, review results of classification algorithms and explore possible indicators and explanations. Initial evaluation steps suggest that there is a rationale for "provocational" text mining in literary interpretation.
Keywords: case studies; humanities; literary criticism; text mining; user interface; Visualization

Finding Mold-Piece Regions Using Computer Graphics Hardware - Priyadarshi,Alok; Gupta, Satyandra K. (Geometric Modeling and Processing - GMP 2006, 2006)
An important step in the mold design process that ensures disassembly of mold pieces consists of identifying various regions on the part that will be formed by different mold pieces. This paper presents an efficient and robust algorithm to find and highlight the mold-piece regions on a part. The algorithm can be executed on current-generation computer graphics hardware. The complexity of the algorithm solely depends on the time to render the given part. By using a system that can quickly find various mold-piece regions on a part, designers can easily optimize the part and mold design and if needed make appropriate corrections upfront, streamlining the subsequent design steps.
Keywords: Computer science

High-confidence medical device software and systems - Lee,I.; Pappas,G. J; Cleaveland, Rance; Hatcliff,J.; Krogh,B. H; Lee,P.; Rubin,H.; Sha,L. (Computer, 2006)
Given the shortage of caregivers and the increase in an aging US population, the future of US healthcare quality does not look promising and definitely is unlikely to be cheaper. Advances in health information systems and healthcare technology offer a tremendous opportunity for improving the quality of care while reducing costs. The development and production of medical device software and systems is a crucial issue, both for the US economy and for ensuring safe advances in healthcare delivery. As devices become increasingly smaller in physical terms but larger in software terms, the design, testing, and eventual Food and Drug Administration (FDA) device approval is becoming much more expensive for medical device manufacturers both in terms of time and cost. Furthermore, the number of devices that have recently been recalled due to software and hardware problems is increasing at an alarming rate. As medical devices are becoming increasingly networked, ensuring even the same level of health safety seems a challenge.
Keywords: Aging; biomedical equipment; Clinical software engineering; Costs; FDA device; Food and Drug Administration device; health and safety; health care; health information system; health safety; healthcare delivery; Healthcare technology; Information systems; medical computing; medical device manufacturing; medical device software development; medical device systems development; medical information systems; Medical services; Medical software; Medical tests; networked medical devices; Production systems; Software design; Software safety; Software systems; Software testing; US healthcare quality

How Multirobot Systems Research will Accelerate our Understanding of Social Animal Behavior - Balch, T.; Dellaert, F.; Feldman, A.; Guillory, A.; Isbell, C.L.; Zia Khan; Pratt, S.C.; Stein, A.N.; Wilde, H. (Proceedings of the IEEE, 2006)
Our understanding of social insect behavior has significantly influenced artificial intelligence (AI) and multirobot systems' research (e.g., ant algorithms and swarm robotics). In this work, however, we focus on the opposite question: "How can multirobot systems research contribute to the understanding of social animal behavior?" As we show, we are able to contribute at several levels. First, using algorithms that originated in the robotics community, we can track animals under observation to provide essential quantitative data for animal behavior research. Second, by developing and applying algorithms originating in speech recognition and computer vision, we can automatically label the behavior of animals under observation. In some cases the automatic labeling is more accurate and consistent than manual behavior identification. Our ultimate goal, however, is to automatically create, from observation, executable models of behavior. An executable model is a control program for an agent that can run in simulation (or on a robot). The representation for these executable models is drawn from research in multirobot systems programming. In this paper we present the algorithms we have developed for tracking, recognizing, and learning models of social animal behavior, details of their implementation, and quantitative experimental results using them to study social insects
Keywords: Acceleration; Animal behavior; ant movement tracking; Artificial intelligence; biology computing; Computer vision; control engineering computing; Insects; Intelligent robots; Labeling; monkey movement tracking; multi-robot systems; multirobot systems; robotics algorithms; Robotics and automation; social animal behavior; social animals; social insect behavior; Speech recognition; tracking

Identification and cross-species comparison of canine osteoarthritic gene regulatory cis-elements - Hannenhalli, Sridhar; Middleton,R.P.; Levy,S.; Perroud,B.; Holzwarth,J.A.; McDonald,K.; Hannah,S.S. (Osteoarthritis and Cartilage, 2006)
SummaryObjectiveTo better understand transcription regulation of osteoarthritis (OA) by examining common promoter motifs in canine osteoarthritic genes, to identify other genes containing these motifs and to assess the conservation of these motifs between canine, human, mouse and rat. Design Differentially expressed transcripts in canine OA were mapped to the human genome. We thus identified 20 orthologous human transcripts representing 19 up-regulated genes and 62 orthologous transcripts representing 60 down-regulated genes. The 5 kbp upstream regions of these transcripts were used to identify binding sites and build promoter models based on those sites. The human genome was subsequently searched for other transcripts likely to be regulated by the same promoter models. Orthologous transcripts were then identified in canine, rat and mouse for determination of potential cross-species conservation of binding sites comprising the promoter model. Results Four promoter models containing 5–6 transcripts and 5–8 common transcription factor binding sites were developed. They include binding sites for AP-4, AP-2α and γ, and E2F. Several hundred other human genes were found to contain these promoter motifs. Furthermore these motifs were significantly over represented in the orthologous genes in canine, rat and mouse genomes. Conclusions We have developed and applied a computational methodology to identify common promoter elements implicated in OA and shared amongst four higher vertebrates. The transcription factors associated with these binding sites and other genes driven by these promoter motifs have been implicated in OA, chondrocyte development and with other biological factors involved in the disease.
Keywords: Chondrocyte; Gene expression; Osteoarthritis; Promoter

In VINI veritas: realistic and controlled network experimentation - Bavier,Andy; Feamster, Nick; Huang,Mark; Peterson,Larry; Rexford,Jennifer (SIGCOMM Comput. Commun. Rev., 2006)
This paper describes VINI, a virtual network infrastructure that allows network researchers to evaluate their protocols and services in a realistic environment that also provides a high degree of control over network conditions. VINI allows researchers to deploy and evaluate their ideas with real routing software, traffic loads, and network events. To provide researchers flexibility in designing their experiments, VINI supports simultaneous experiments with arbitrary network topologies on a shared physical infrastructure. This paper tackles the following important design question: What set of concepts and techniques facilitate flexible, realistic, and controlled experimentation (e.g., multiple topologies and the ability to tweak routing algorithms) on a fixed physical infrastructure? We first present VINI's high-level design and the challenges of virtualizing a single network. We then present PL-VINI, an implementation of VINI on PlanetLab, running the "Internet In a Slice". Our evaluation of PL-VINI shows that it provides a realistic and controlled environment for evaluating new protocols and services.
Keywords: architecture; experimentation; Internet; Routing; virtualization

Integrating data and interfaces to enhance understanding of government statistics: toward the national statistical knowledge network project briefing - Marchionini,G.; Haas,S.; Plaisant, Catherine; Shneiderman, Ben (Proceedings of 7th Annual International Conference on Digital Libraries (DG06), 2006)
This paper reports the results of work in the final no-costextension year of a digital government project that developed user interface models and prototypes to help people find and understand government statistics; proposed a Statistical Knowledge Network architecture that supports cross agency information access; and demonstrated models for government- academic collaboration.

Interactive sonification for blind people exploration of geo-referenced data: comparison between a keyboard-exploration and a haptic-exploration interfaces - Delogu,Franco; Belardinelli,Marta; Palmiero,Massimiliano; Pasqualotto,Emanuele; Zhao,Haixia; Plaisant, Catherine; Federici,Stefano (Cognitive Processing, 2006)

Leveraging recurrent phrase structure in large-scale ontology translation - Murray,G. C; Dorr, Bonnie J; Jimmy Lin; Hajič,J.; Pecina,P. (Proceedings of the 11th Annual Conference of the European Association for Machine Translation, 2006)
This paper presents a process for leveraging structural relationships and reusablephrases when translating large-scale ontologies. Digital libraries are becoming more and more prevalent. An important step in providing universal access to such material is to pro- vide multi-lingual access to the underlying principles of organization via ontologies, thesauri, and controlled vocabularies. Machine translation of these resources requires high accuracy and a deep vocabulary. Human input is often required, but full manual translation can be slow and expensive. We report on a cost-effective approach to ontology translation. We describe our technique of prioritization, our process of collecting aligned translations and generating a new lexicon, and the resulting improvement to translation system output. Our preliminary evaluation indicates that this technique provides significant cost savings for human-assisted translation. The process we developed can be applied to ontologies in other domains and is easily incorporated into other translation systems.

Leveraging reusability: cost-effective lexical acquisition for large-scale ontology translation - Murray,G. Craig; Dorr, Bonnie J; Jimmy Lin; Hajič,Jan; Pecina,Pavel (Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, 2006)
Thesauri and ontologies provide important value in facilitating access to digital archives by representing 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 ontologies precludes fully-automated machine translation using general-domain lexical resources. In this paper, we present an efficient process for leveraging human translations when constructing domain-specific lexical resources. We evaluate the effectiveness of this process by producing a probabilistic phrase dictionary and translating a thesaurus of 56,000 concepts used to catalogue a large archive of oral histories. Our experiments demonstrate a cost-effective technique for accurate machine translation of large ontologies.

Lock inference for atomic sections - Hicks, Michael W.; Foster, Jeffrey S.; Pratikakis,P. (Proceedings of the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, 2006)
To prevent unwanted interactions in multithreaded programs, pro-grammers have traditionally employed pessimistic, blocking con- currency primitives. Using such primitives correctly and efficiently is notoriously difficult. To simplify the problem, recent research proposes that programmers specify atomic sections of code whose executions should be atomic with respect to one another, without dictating exactly how atomicity enforced. Much work has explored using optimistic concurrency, or software transactions, as a means to implement atomic sections. This paper proposes to implement atomic sections using a static whole-program analysis to insert necessary uses of pessimistic con- currency primitives. Given a program that contains programmer- specified atomic sections and thread creations, our mutex infer- ence algorithm efficiently infers a set of locks for each atomic section that should be acquired (released) upon entering (exiting) the atomic section. The key part of this algorithm is determining which memory locations in the program could be shared between threads, and using this information to generate the necessary locks. To determine sharing, our analysis uses the notion of continuation effects to track the locations accessed after each program point. As continuation effects are flow sensitive, a memory location may be thread-local before a thread creation and thread-shared afterward. We prove that our algorithm is correct, and provides parallelism according to the precision of the points-to analysis. While our al- gorithm also attempts to reduce the number locks while preserving parallelism, we show that minimizing the number of locks is NP- hard.

LOCKSMITH: context-sensitive correlation analysis for race detection - Pratikakis,Polyvios; Foster, Jeffrey S.; Hicks, Michael W. (SIGPLAN Not., 2006)
One common technique for preventing data races in multi-threaded programs is to ensure that all accesses to shared locations are consistently protected by a lock. We present a tool called LOCKSMITH for detecting data races in C programs by looking for violations of this pattern. We call the relationship between locks and the locations they protect consistent correlation, and the core of our technique is a novel constraint-based analysis that infers consistent correlation context-sensitively, using the results to check that locations are properly guarded by locks. We present the core of our algorithm for a simple formal language λ> which we have proven sound, and discuss how we scale it up to an algorithm that aims to be sound for all of C. We develop several techniques to improve the precision and performance of the analysis, including a sharing analysis for inferring thread locality; existential quantification for modeling locks in data structures; and heuristics for modeling unsafe features of C such as type casts. When applied to several benchmarks, including multi-threaded servers and Linux device drivers, LOCKSMITH found several races while producing a modest number of false alarm.
Keywords: context-sensitivity; correlation; locksmith; multi-threaded programming; race detection; Type inference

The metacognitive loop I: Enhancing reinforcement learning with metacognitive monitoring and control for improved perturbation tolerance - Anderson,M. L; Oates,T.; Chong,W.; Perlis, Don (Journal of Experimental & Theoretical Artificial Intelligence, 2006)

Metagenomic Analysis of the Human Distal Gut Microbiome - Gill,Steven R.; Pop, Mihai; DeBoy,Robert T.; Eckburg,Paul B; Turnbaugh,Peter J; Samuel,Buck S; Gordon,Jeffrey I; Relman,David A; Fraser-Liggett,Claire M; Nelson,Karen E. (Science, 2006)
The human intestinal microbiota is composed of 1013 to 1014 microorganisms whose collective genome (“microbiome”) contains at least 100 times as many genes as our own genome. We analyzed ∼78 million base pairs of unique DNA sequence and 2062 polymerase chain reaction–amplified 16S ribosomal DNA sequences obtained from the fecal DNAs of two healthy adults. Using metabolic function analyses of identified genes, we compared our human genome with the average content of previously sequenced microbial genomes. Our microbiome has significantly enriched metabolism of glycans, amino acids, and xenobiotics; methanogenesis; and 2-methyl-d-erythritol 4-phosphate pathway–mediated biosynthesis of vitamins and isoprenoids. Thus, humans are superorganisms whose metabolism represents an amalgamation of microbial and human attributes.

A multi-resolution representation for terrain morphology - Danovaro,E.; De Floriani, Leila; Papaleo,L.; Vitali,M. (Geographic Information Science, 2006)
Mesh-based terrain representations provide accurate descriptions of a terrain, but fail in capturing its morphological structure. The morphology of a terrain is defined by its critical points and by the critical lines joining them, which form a so-called surface network. Because of the large size of current terrain data sets, a multi-resolution representation of the terrain morphology is crucial. Here, we address the problem of representing the morphology of a terrain at different resolutions. The basis of the multi-resolution terrain model, that we call a Multi-resolution Surface Network (MSN), is a generalization operator on a surface network, which produces a simplified representation incrementally. An MSN is combined with a multi-resolution mesh-based terrain model, which encompasses the terrain morphology at different resolutions. We show how variable-resolution representations can be extracted from an MSN, and we present also an implementation of an MSN in a compact encoding data structure.

Nuclear Envelope Dystrophies Show a Transcriptional Fingerprint Suggesting Disruption of Rb–MyoD Pathways in Muscle Regeneration - Bakay,Marina; Wang,Zuyi; Melcon,Gisela; Schiltz,Louis; Xuan,Jianhua; Zhao,Po; Sartorelli,Vittorio; Seo,Jinwook; Pegoraro,Elena; Angelini,Corrado; Shneiderman, Ben; Escolar,Diana; et al. (BrainBrain, 2006)
Mutations of lamin A/C (LMNA) cause a wide range of human disorders, including progeria, lipodystrophy, neuropathies and autosomal dominant Emery–Dreifuss muscular dystrophy (EDMD). EDMD is also caused by X-linked recessive loss-of-function mutations of emerin, another component of the inner nuclear lamina that directly interacts with LMNA. One model for disease pathogenesis of LMNA and emerin mutations is cell-specific perturbations of the mRNA transcriptome in terminally differentiated cells. To test this model, we studied 125 human muscle biopsies from 13 diagnostic groups (125 U133A, 125 U133B microarrays), including EDMD patients with LMNA and emerin mutations. A Visual and Statistical Data Analyzer (VISDA) algorithm was used to statistically model cluster hierarchy, resulting in a tree of phenotypic classifications. Validations of the diagnostic tree included permutations of U133A and U133B arrays, and use of two probe set algorithms (MAS5.0 and MBEI). This showed that the two nuclear envelope defects (EDMD LMNA, EDMD emerin) were highly related disorders and were also related to fascioscapulohumeral muscular dystrophy (FSHD). FSHD has recently been hypothesized to involve abnormal interactions of chromatin with the nuclear envelope. To identify disease-specific transcripts for EDMD, we applied a leave-one-out (LOO) cross-validation approach using LMNA patient muscle as a test data set, with reverse transcription–polymerase chain reaction (RT–PCR) validations in both LMNA and emerin patient muscle. A high proportion of top-ranked and validated transcripts were components of the same transcriptional regulatory pathway involving Rb1 and MyoD during muscle regeneration (CRI-1, CREBBP, Nap1L1, ECREBBP/p300), where each was specifically upregulated in EDMD. Using a muscle regeneration time series (27 time points) we develop a transcriptional model for downstream consequences of LMNA and emerin mutations. We propose that key interactions between the nuclear envelope and Rb and MyoD fail in EDMD at the point of myoblast exit from the cell cycle, leading to poorly coordinated phosphorylation and acetylation steps. Our data is consistent with mutations of nuclear lamina components leading to destabilization of the transcriptome in differentiated cells.
Keywords: EDMD = Emery–Dreifuss muscular dystrophy; emerin; Emery-Dreifuss muscular dystrophy; FSHD = fascioscapulohumeral muscular dystrophy; IDG = individual discriminatory genes; JDG = jointly discriminatory genes; lamin A/C; LGMD = limb-girdle muscular dystrophy; LOO = leave-one-out; RT–PCR = reverse transcription–polymerase chain reaction; VISDA = Visual and Statistical Data Analyzer; Skeletal muscle; wFC = weighted Fisher criterion

Observations about software development for high end computing - Carver, J. C; Hochstein, L. M; Kendall,R. P; Nakamura, T.; Zelkowitz, Marvin V; Basili, Victor R.; Post,D. E (CTWatch Quarterly, 2006)
In this paper, we have summarized our findings from a series of case studies conducted with ten ASC and MP Codes as a series of observations. Due to different environments in which each code is developed, some of the observations are consistent across code teams while others vary across code teams. Overall, we found high consistency among the ASC Codes and the MP Codes. Due to the different environments and foci of these projects, this result is both surprising and positive. In addition, despite the fact that a large majority of the developers on these teams have little or no formal training in software engineering, they have been able to make use of some basic software engineering principles. Further education and motivation could increase the use of these principles and further increase the quality of scientific and engineering software that has already demonstrated its value.Based on the positive results thus far, we have plans to conduct additional case studies to gather more data in support of or in contradiction to the observations presented in this paper. In future case studies, we will strive to investigate codes from additional domains, thereby allowing broader, more inclusive conclusions to be drawn.

Opinion Analysis in Document Databases - Cesarano,C.; Dorr, Bonnie J; Picariello, A.; Reforgiato,D.; Sagoff,A.; V.S. Subrahmanian (Proc. AAAI Spring Symposium on Computational Approaches to Analyzing Weblogs, Stanford, CA, 2006)
There are numerous applications in which we would like toassess what opinions are being expressed in text documents. Forr example, Martha Stewart’s company may have wished to assess the degree of harshness of news articles about her in the recent past. Likewise, a World Bank official may wish to as- sess the degree of criticism of a proposed dam in Bangladesh. The ability to gauge opinion on a given topic is therefore of critical interest. In this paper, we develop a suite of algo- rithms which take as input, a set D of documents as well as a topic t, and gauge the degree of opinion expressed about topic t in the set D of documents. Our algorithms can return both a number (larger the number, more positive the opinion) as well as a qualitative opinion (e.g. harsh, complimentary). We as- sess the accuracy of these algorithms via human experiments and show that the best of these algorithms can accurately re- flect human opinions. We have also conducted performance experiments showing that our algorithms are computationally fast.

An optimized system for expression and purification of secreted bacterial proteins - Geisbrecht,Brian V.; Bouyain,Samuel; Pop, Mihai (Protein Expression and Purification, 2006)
In this report, we describe an optimized system for the efficient overexpression, purification, and refolding of secreted bacterial proteins. Candidate secreted proteins were produced recombinantly in Escherichia coli as Tobacco Etch Virus protease-cleavable hexahistidine-c-myc eptiope fusion proteins. Without regard to their initial solubility, recombinant fusion proteins were extracted from whole cells with guanidium chloride, purified under denaturing conditions by immobilized metal affinity chromatography, and refolded by rapid dilution into a solution containing only Tris buffer and sodium chloride. Following concentration on the same resin under native conditions, each protein was eluted for further purification and/or characterization. Preliminary studies on a test set of 12 secreted proteins ranging in size from 13 to 130 kDa yielded between 10 and 50 mg of fusion protein per liter of induced culture at greater than 90% purity, as judged by Coomassie-stained SDS–PAGE. Of the nine proteins further purified, analytical gel filtration chromatography indicated that each was a monomer in solution and circular dichroism spectroscopy revealed that each had adopted a well-defined secondary structure. While there are many potential applications for this system, the results presented here suggest that it will be particularly useful for investigators employing structural approaches to understand protein function, as attested to by the crystal structures of three proteins purified using this methodology (B.V. Geisbrecht, B.Y. Hamaoka, B. Perman, A. Zemla, D.J. Leahy, J. Biol. Chem. 280 (2005) 17243–17250).
Keywords: Pathogens; Secreted proteins; Toxins; Virulence factors

Out–of–Core Multiresolution Terrain Modeling - Danovaro,E.; De Floriani, Leila; Puppo,E.; Samet, Hanan (Modeling and Management of Geographical Data over Distributed Architectures. Springer–Verlag, 2006)

Overconfidence or paranoia? search in imperfect-information games - Parker,A.; Nau, Dana S.; V.S. Subrahmanian (PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2006)
We derive a recursive formula for expected utility valuesin imperfect- information game trees, and an imperfect- information game tree search algorithm based on it. The for- mula and algorithm are general enough to incorporate a wide variety of opponent models. We analyze two opponent mod- els. The “paranoid” model is an information-set analog of the minimax rule used in perfect-information games. The “over- confident” model assumes the opponent moves randomly. Our experimental tests in the game of kriegspiel chess (an imperfect-information variant of chess) produced surpris- ing results: (1) against each other, and against one of the kriegspiel algorithms presented at IJCAI-05, the overconfi- dent model usually outperformed the paranoid model; (2) the performance of both models depended greatly on how well the model corresponded to the opponent’s behavior. These re- sults suggest that the usual assumption of perfect-information game tree search—that the opponent will choose the best pos- sible move—isn’t as useful in imperfect-information games.

OverDoSe: A generic DDoS protection service using an overlay network - Elaine Shi; Stoica,I.; Andersen,D.G.; Perrig, A. (School of Computer Science, Carnegie Mellon University, 2006)
We present the design and implementation of OverDoSe, an overlay network offering generic DDoS protection for targeted sites. OverDoSe clients and servers are isolated at the IP level. Overlay nodes route packets between a client and a server, and regulate traffic according to the server’s instructions. Through the use of light-weight security primitives, OverDoSe achieves resilience against compromised overlay nodes with a minimal performance overhead. OverDoSe can be deployed by a single ISP who wishes to offer DDoS protection as a value-adding service to its customers.

The priority curve algorithm for video summarization - Albanese, M.; Fayzullin,M.; Picariello, A.; V.S. Subrahmanian (Information Systems, 2006)
In this paper, we introduce the concept of a priority curve associated with a video. We then provide an algorithm that can use the priority curve to create a summary (of a desired length) of any video. The summary thus created exhibits nice continuity properties and also avoids repetition. We have implemented the priority curve algorithm (PriCA) and compared it with other summarization algorithms in the literature with respect to both performance and the output quality. The quality of summaries was evaluated by a group of 200 students in Naples, Italy, who watched soccer videos. We show that PriCA is faster than existing algorithms and also produces better quality summaries. We also briefly describe a soccer video summarization system we have built on using the PriCA architecture and various (classical) image processing algorithms.
Keywords: Content based retrieval; Video databases; Video summarization

Provable algorithms for parallel generalized sweep scheduling - Anil Kumar,V. S; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind; Zust,S. (Journal of Parallel and Distributed Computing, 2006)

Secondary Structure Spatial Conformation Footprint: A Novel Method for Fast Protein Structure Comparison and Classification - Zotenko,Elena; O'Leary, Dianne P.; Przytycka,Teresa M. (BMC Structural Biology, 2006)
Recently a new class of methods for fast protein structure comparison has emerged. We call the methods in this class projection methods as they rely on a mapping of protein structure into a high-dimensional vector space. Once the mapping is done, the structure comparison is reduced to distance computation between corresponding vectors. As structural similarity is approximated by distance between projections, the success of any projection method depends on how well its mapping function is able to capture the salient features of protein structure. There is no agreement on what constitutes a good projection technique and the three currently known projection methods utilize very different approaches to the mapping construction, both in terms of what structural elements are included and how this information is integrated to produce a vector representation. Results In this paper we propose a novel projection method that uses secondary structure information to produce the mapping. First, a diverse set of spatial arrangements of triplets of secondary structure elements, a set of structural models, is automatically selected. Then, each protein structure is mapped into a high-dimensional vector of "counts" or footprint, where each count corresponds to the number of times a given structural model is observed in the structure, weighted by the precision with which the model is reproduced. We perform the first comprehensive evaluation of our method together with all other currently known projection methods. Conclusion The results of our evaluation suggest that the type of structural information used by a projection method affects the ability of the method to detect structural similarity. In particular, our method that uses the spatial conformations of triplets of secondary structure elements outperforms other methods in most of the tests.

Shape-Regulated Particle Filtering for Tracking Non-Rigid Objects - Jie Shao; Chellapa, Rama; Porikli, F. (Image Processing, 2006 IEEE International Conference on, 2006)
This paper presents an active contour based algorithm for tracking non-rigid objects in heavily cluttered scenes. We decompose the non-rigid contour tracking problem into three subproblems: 2D motion estimation, deformation detection, and shape regulation. First, we employ a particle filter to estimate the affine transform parameters between successive frames. Second, by using a dynamic object model, we generate a probabilistic map of deformation to reshape its contour. Finally, we project the updated model onto a trained shape subspace to constrain deformations to be within possible object appearances. Our experiments show that the proposed algorithm significantly improves the performance of the tracker
Keywords: (numerical; 2D; algorithm; affine; based; contour; detection; dynamic; detection; motion; detection; parameter; estimation; active; estimation; object; estimation; particle; Filtering; filtering; probabilistic; filters; map; shape-regulation; affine; methods); tracking; model; nonrigid; MOTION; object; scenes; deformation; tracking; parameter; transform; cluttered; transforms; clutter; edge

Shared family calendars: Promoting symmetry and accessibility - Plaisant, Catherine; Clamage,Aaron; Hutchinson,Hilary Browne; Bederson, Benjamin B.; Druin, Allison (ACM Trans. Comput.-Hum. Interact., 2006)
We describe the design and use of a system facilitating the sharing of calendar information between remotely located, multi-generational family members. Most previous work in this area involves software enabling younger family members to monitor their parents. We have found, however, that older adults are equally if not more interested in the activities of younger family members. The major obstacle preventing them from participating in information sharing is the technology itself. Therefore, we developed a multi-layered interface approach that offers simple interaction to older users. In our system, users can choose to enter information into a computerized calendar or write it by hand on digital paper calendars. All of the information is automatically shared among everyone in the distributed family. By making the interface more accessible to older users, we promote symmetrical sharing of information among both older and younger family members. We present our participatory design process, describe the user interface, and report on an exploratory field study in three households of an extended family.
Keywords: calendar; digital paper; elderly; family technology; Home; layered interface; privacy; universal usability

Special Issue on Biometrics: Algorithms and Applications - Chellapa, Rama; Phillips, J.; Reynolds, D. (Proceedings of the IEEE, 2006)

A Statistical Analysis of Attack Data to Separate Attacks - Michel Cukier; Berthier,R.; Panjwani,S.; Tan,S. (2006)
This paper analyzes malicious activity collected from a test-bed, consisting of two target computers dedicated solely to the purpose of being attacked, over a 109 day time period. We separated port scans, ICMP scans, and vulnerability scans from the malicious activity. In the remaining attack data, over 78% (i.e., 3,677 attacks) targeted port 445, which was then statistically analyzed. The goal was to find the characteristics that most efficiently separate the attacks. First, we separated the attacks by analyzing their messages. Then we separated the attacks by clustering characteristics using the K-Means algorithm. The comparison between the analysis of the messages and the outcome of the K-Means algorithm showed that 1) the mean of the distributions of packets, bytes and message lengths over time are poor characteristics to separate attacks and 2) the number of bytes, the mean of the distribution of bytes and message lengths as a function of the number packets are the best characteristics for separating attacks
Keywords: attack data statistical analysis; attack separation; computer crime; Data analysis; data mining; ICMP scans; K-Means algorithm; pattern clustering; port scans; statistical analysis; vulnerability scans

Strategies for evaluating information visualization tools: multi-dimensional in-depth long-term case studies - Shneiderman, Ben; Plaisant, Catherine (Proceedings of the 2006 AVI workshop on BEyond time and errors: novel evaluation methods for information visualization, 2006)
After an historical review of evaluation methods, we describe an emerging research method called Multi-dimensional In-depth Long-term Case studies (MILCs) which seems well adapted to study the creative activities that users of information visualization systems engage in. We propose that the efficacy of tools can be assessed by documenting 1) usage (observations, interviews, surveys, logging etc.) and 2) expert users' success in achieving their professional goals. We summarize lessons from related ethnography methods used in HCI and provide guidelines for conducting MILCs for information visualization. We suggest ways to refine the methods for MILCs in modest sized projects and then envision ambitious projects with 3-10 researchers working over 1-3 years to understand individual and organizational use of information visualization by domain experts working at the frontiers of knowledge in their fields.

Target size study for one-handed thumb use on small touchscreen devices - Parhi,P.; Karlson,A.K.; Bederson, Benjamin B. (Proceedings of the 8th conference on Human-computer interaction with mobile devices and services, 2006)

Task taxonomy for graph visualization - Lee,Bongshin; Plaisant, Catherine; Parr,Cynthia Sims; Fekete,Jean-Daniel; Henry,Nathalie (Proceedings of the 2006 AVI workshop on BEyond time and errors: novel evaluation methods for information visualization, 2006)
Our goal is to define a list of tasks for graph visualization that has enough detail and specificity to be useful to: 1) designers who want to improve their system and 2) to evaluators who want to compare graph visualization systems. In this paper, we suggest a list of tasks we believe are commonly encountered while analyzing graph data. We define graph specific objects and demonstrate how all complex tasks could be seen as a series of low-level tasks performed on those objects. We believe that our taxonomy, associated with benchmark datasets and specific tasks, would help evaluators generalize results collected through a series of controlled experiments.
Keywords: Evaluation; graph visualization; task taxonomy

Techniques and processes for improving the quality and performance of open-source software - Porter, Adam; Yilmaz,Cemal; Memon, Atif M.; Krishna,Arvind S.; Schmidt,Douglas C.; Gokhale,Aniruddha (Software Process: Improvement and Practice, 2006)
Open-source development processes have emerged as an effective approach to reduce cycle-time and decrease design, implementation, and quality assurance (QA) costs for certain types of software, particularly systems infrastructure software, such as operating systems (OS), compilers and language processing tools, text and drawing editors, and middleware. This article presents two contributions to the study of open-source software processes. First, we describe key challenges of open-source software and illustrate how QA processes—specifically those tailored to open-source development—help mitigate these challenges better than traditional closed-source processes do. Second, we summarize results of empirical studies that evaluate how our Skoll distributed continuous quality assurance (DCQA) techniques and processes help to resolve key challenges in developing and validating open-source software. Our results show that: (a) using models to configure and guide the DCQA process improves developer understanding of open-source software, (b) improving the diversity of platform configurations helps QA engineers find defects missed during conventional testing, and (c) centralizing control of QA activities helps to eliminate redundant work. Copyright © 2006 John Wiley & Sons, Ltd.
Keywords: distributed continuous quality assurance; open-source software development and testing

Theory and Application of Self-Reference: Logic and Beyond - Perlis, Don (Self-reference, 2006)

Is there a grand challenge or X-prize for data mining? - Piatetsky-Shapiro,Gregory; Grossman,Robert; Djeraba,Chabane; Feldman,Ronen; Getoor, Lise; Zaki,Mohammed (Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 2006)
This panel will discuss possible exciting and motivating Grand Challenge problems for Data Mining, focusing on bioinformatics, multimedia mining, link mining, text mining, and web mining.
Keywords: Bioinformatics; data mining; grand challenge; image mining; link mining; multimedia mining; text mining; video mining; web mining; X-prize

Topology-based reasoning on non-manifold shapes - De Floriani, Leila; Hui,A.; Papaleo,L. (Proceedings of the 1st International Symposium on Shapes and Semantics, Matsushima, Japan, 2006)
Topological information is a promising resource to research in shape-understanding as it provides a high-level description of the characteristics of a shape, and such high-level description often has strong association with the semantics of an object. The Shape Acquisition and Processing (SAP) ontology has been designed to maintain useful information of a model. We propose here an extension to the SAP ontology, that addresses the non-manifold properties of a model. Useful information about the connectivity of an object can be obtained based on an analysis of its non- manifold properties, because the structure of a non-manifold object can be considered as a graph of manifold parts connected together at non-manifold joints. The manifold parts are often pieces that have strong semantic associations. In this work, we describe the type of non-manifold properties, the various types of connected components in a non-manifold object and their semantical significance. We address how the Euler’ characteristics of a non-manifold object can be found based on such information. All such information are extractable from a model using TopMesh, a tool that we have developed. In this work, we also describe the features of TopMesh, namely, all the topological properties it extracts.

Towards Dependability in Everyday Software Using Software Telemetry - Gross,Kenny C.; Urmanov,Aleksey; Votta,Lawrence G.; McMaster,Scott; Porter, Adam (Engineering of Autonomic and Autonomous Systems, IEEE International Workshop on, 2006)
Application-level software dependability is difficult to ensure. Thus it?s typically used only in custom systems and is achieved using one-of-a-kind, handcrafted solutions. We are interested in understanding whether and how these techniques can be applied to more common, lower-end systems. To this end, we have adapted a condition-based maintenance (CBM) approach called the Multivariate State Estimation Technique (MSET). This approach automatically creates sophisticated statistical models that predict system failure well before failures occur, leading to simpler and more successful recoveries. We have packaged this approach in the Software Dependability Framework (SDF). The SDF consists of instrumentation and data management libraries, a CBM module, performance visualization tools, and a software architecture that supports system designers. Finally, we evaluated our framework on a simple video game application. Our results suggest that we can cheaply and reliably predict impending runtime failures and respond to them in time to improve the system?s dependability.

Transcriptional Genomics Associates FOX Transcription Factors With Human Heart Failure - Hannenhalli, Sridhar; Putt,Mary E.; Gilmore,Joan M.; Wang,Junwen; Parmacek,Michael S.; Epstein,Jonathan A.; Morrisey,Edward E.; Margulies,Kenneth B.; Cappola,Thomas P. (Circulation, 2006)
Background— Specific transcription factors (TFs) modulate cardiac gene expression in murine models of heart failure, but their relevance in human subjects remains untested. We developed and applied a computational approach called transcriptional genomics to test the hypothesis that a discrete set of cardiac TFs is associated with human heart failure.Methods and Results— RNA isolates from failing (n=196) and nonfailing (n=16) human hearts were hybridized with Affymetrix HU133A arrays, and differentially expressed heart failure genes were determined. TF binding sites overrepresented in the −5-kb promoter sequences of these heart failure genes were then determined with the use of public genome sequence databases. Binding sites for TFs identified in murine heart failure models (MEF2, NKX, NF-AT, and GATA) were significantly overrepresented in promoters of human heart failure genes (P<0.002; false discovery rate 2% to 4%). In addition, binding sites for FOX TFs showed substantial overrepresentation in both advanced human and early murine heart failure (P<0.002 and false discovery rate <4% for each). A role for FOX TFs was supported further by expression of FOXC1, C2, P1, P4, and O1A in failing human cardiac myocytes at levels similar to established hypertrophic TFs and by abundant FOXP1 protein in failing human cardiac myocyte nuclei.Conclusions— Our results provide the first evidence that specific TFs identified in murine models (MEF2, NKX, NFAT, and GATA) are associated with human heart failure. Moreover, these data implicate specific members of the FOX family of TFs (FOXC1, C2, P1, P4, and O1A) not previously suggested in heart failure pathogenesis. These findings provide a crucial link between animal models and human disease and suggest a specific role for FOX signaling in modulating the hypertrophic response of the heart to stress in humans.

TreePlus: Interactive Exploration of Networks with Enhanced Tree Layouts - Lee,B.; Parr,C.S.; Plaisant, Catherine; Bederson, Benjamin B.; Veksler,V.D.; Gray,W.D.; Kotfila,C. (Visualization and Computer Graphics, IEEE Transactions on, 2006)
Despite extensive research, it is still difficult to produce effective interactive layouts for large graphs. Dense layout and occlusion make food Webs, ontologies and social networks difficult to understand and interact with. We propose a new interactive visual analytics component called TreePlus that is based on a tree-style layout. TreePlus reveals the missing graph structure with visualization and interaction while maintaining good readability. To support exploration of the local structure of the graph and gathering of information from the extensive reading of labels, we use a guiding metaphor of "plant a seed and watch it grow." It allows users to start with a node and expand the graph as needed, which complements the classic overview techniques that can be effective at (but often limited to) revealing clusters. We describe our design goals, describe the interface and report on a controlled user study with 28 participants comparing TreePlus with a traditional graph interface for six tasks. In general, the advantage of TreePlus over the traditional interface increased as the density of the displayed data increased. Participants also reported higher levels of confidence in their answers with TreePlus and most of them preferred TreePlus
Keywords: Automated; Software; User-Computer Interface; Biological; Pattern Recognition; data visualization; graph structure; graphical user interface; interactive visual analytics; occlusion; tree-style layout; data visualisation; graphical user interfaces; hidden feature removal; interactive systems; trees (mathematics); Algorithms; Computer Graphics; C

Using PlanetLab for network research - Spring, Neil; Peterson,Larry; Bavier,Andy; Pait,Vivek (ACM SIGOPS Operating Systems Review, 2006)

Using rhythms of relationships to understand e‐mail archives - Perer,Adam; Shneiderman, Ben; Oard, Douglas (Journal of the American Society for Information Science and Technology, 2006)
Due to e-mail's ubiquitous nature, millions of users are intimate with the technology; however, most users are only familiar with managing their own e-mail, which is an inherently different task from exploring an e-mail archive. Historians and social scientists believe that e-mail archives are important artifacts for understanding the individuals and communities they represent. To understand the conversations evidenced in an archive, context is needed. In this article, we present a new way to gain this necessary context: analyzing the temporal rhythms of social relationships. We provide methods for constructing meaningful rhythms from the e-mail headers by identifying relationships and interpreting their attributes. With these visualization techniques, e-mail archive explorers can uncover insights that may have been otherwise hidden in the archive. We apply our methods to an individual's 15-year e-mail archive, which consists of about 45,000 messages and over 4,000 relationships.

VAST 2006 Contest - A Tale of Alderwood - Grinstein,G.; O'Connell,T.; Laskowski,S.; Plaisant, Catherine; Scholtz,J.; Whiting,M. (Visual Analytics Science And Technology, 2006 IEEE Symposium On, 2006)
Visual analytics experts realize that one effective way to push the field forward and to develop metrics for measuring the performance of various visual analytics components is to hold an annual competition. The first visual analytics science and technology (VAST) contest was held in conjunction with the 2006 IEEE VAST Symposium. The competition entailed the identification of possible political shenanigans in the fictitious town of Alderwood. A synthetic data set was made available as well as tasks. We summarize how we prepared and advertised the contest, developed some initial metrics for evaluation, and selected the winners. The winners were invited to participate at an additional live competition at the symposium to provide them with feedback from senior analysts
Keywords: Alderwood; human; analysis; data; analytics; and; contest; data; information; interaction; sense; making; visual; Science; technology; visualisation

Video Mensuration Using a Stationary Camera - Guo,Feng; Chellapa, Rama (Computer Vision – ECCV 2006Computer Vision – ECCV 2006, 2006)
This paper presents a method for video mensuration using a single stationary camera. The problem we address is simple, i.e., the mensuration of any arbitrary line segment on the reference plane using multiple frames with minimal calibration. Unlike previous solutions that are based on planar rectification, our approach is based on fitting the image of multiple concentric circles on the plane. Further, the proposed method aims to minimize the error in mensuration. Hence we can calculate the mensuration of the line segments not lying on the reference plane. Using an algorithm for detecting and tracking wheels of an automobile, we have implemented a fully automatic system for wheel base mensuration. The mensuration results are accurate enough that they can be used to determine the vehicle classes. Furthermore, we measure the line segment between any two points on the vehicle and plot them in top and side views.

View Invariance for Human Action Recognition - Parameswaran,Vasu; Chellapa, Rama (International Journal of Computer Vision, 2006)
This paper presents an approach for viewpoint invariant human action recognition, an area that has received scant attention so far, relative to the overall body of work in human action recognition. It has been established previously that there exist no invariants for 3D to 2D projection. However, there exist a wealth of techniques in 2D invariance that can be used to advantage in 3D to 2D projection. We exploit these techniques and model actions in terms of view-invariant canonical body poses and trajectories in 2D invariance space, leading to a simple and effective way to represent and recognize human actions from a general viewpoint. We first evaluate the approach theoretically and show why a straightforward application of the 2D invariance idea will not work. We describe strategies designed to overcome inherent problems in the straightforward approach and outline the recognition algorithm. We then present results on 2D projections of publicly available human motion capture data as well on manually segmented real image sequences. In addition to robustness to viewpoint change, the approach is robust enough to handle different people, minor variabilities in a given action, and the speed of aciton (and hence, frame-rate) while encoding sufficient distinction among actions.

Visualization Support for Fusing Relational, Spatio-Temporal Data: Building Career Histories - Blythe,Jim; Patwardhan,Mithila; Oates,Tim; desJardins, Marie; Rheingans,Penny (Information Fusion, 2006 9th International Conference on, 2006)
Many real-world domains resist analysis because they are best characterized by a variety of data types, including relational, spatial, and temporal components. Examples of such domains include disease outbreaks, criminal networks, and the World-Wide Web. We present two types of visualizations based on physical metaphors that facilitate fusion, analysis, and deep understanding of relational, spatio-temporal data. The first visualization is based on the metaphor of fluid flow through elastic pipes, and the second on wave propagation. We discuss both types of visualizations in the context of fusing information about the activities of scientists over time with the goal of constructing career histories

Visualizing Graphs as Trees: Plant a Seed and Watch it Grow - Lee,Bongshin; Parr,Cynthia; Plaisant, Catherine; Bederson, Benjamin B. (Graph DrawingGraph Drawing, 2006)
TreePlus is a graph browsing technique based on a tree-style layout. It shows the missing graph structure using interaction techniques and enables users to start with a specific node and incrementally explore the local structure of graphs. We believe that it supports particularly well tasks that require rapid reading of labels.

Voting with Your Feet: An Investigative Study of the Relationship Between Place Visit Behavior and Preference - Jon Froehlich; Chen,Mike; Smith,Ian; Potter,Fred (UbiComp 2006: Ubiquitous Computing, 2006)
Real world recommendation systems, personalized mobile search, and online city guides could all benefit from data on personal place preferences. However, collecting explicit rating data of locations as users travel from place to place is impractical. This paper investigates the relationship between explicit place ratings and implicit aspects of travel behavior such as visit frequency and travel time. We conducted a four-week study with 16 participants using a novel sensor-based experience sampling tool, called My Experience (Me), which we developed for mobile phones. Over the course of the study Me was used to collect 3,458 in-situ questionnaires on 1,981 place visits. Our results show that, first, sensor-triggered experience sampling is a useful methodology for collecting targeted information in situ. Second, despite the complexities underlying travel routines and visit behavior, there exist positive correlations between place preference and automatically detectable features like visit frequency and travel time. And, third, we found that when combined, visit frequency and travel time result in stronger correlations with place rating than when measured individually. Finally, we found no significant difference in place ratings due to the presence of others.

Wavelet-Based Super-Resolution Reconstruction: Theory and Algorithm - Hui Ji; Fermüller, Cornelia (Computer Vision – ECCV 2006Computer Vision – ECCV 2006, 2006)
We present a theoretical analysis and a new algorithm for the problem of super-resolution imaging: the reconstruction of HR (high-resolution) images from a sequence of LR (low-resolution) images. Super-resolution imaging entails solutions to two problems. One is the alignment of image frames. The other is the reconstruction of a HR image from multiple aligned LR images. Our analysis of the latter problem reveals insights into the theoretical limits of super-resolution reconstruction. We find that at best we can reconstruct a HR image blurred by a specific low-pass filter. Based on the analysis we present a new wavelet-based iterative reconstruction algorithm which is very robust to noise. Furthermore, it has a computationally efficient built-in denoising scheme with a nearly optimal risk bound. Roughly speaking, our method could be described as a better-conditioned iterative back-projection scheme with a fast and optimal regularization criteria in each iteration step. Experiments with both simulated and real data demonstrate that our approach has significantly better performance than existing super-resolution methods. It has the ability to remove even large amounts of mixed noise without creating smoothing artifacts.

What are the grand challenges for data mining? - KDD-2006 panel report - Piatetsky-Shapiro,G.; Djeraba,C.; Getoor, Lise; Grossman,R.; Feldman,R.; Zaki,M. (ACM SIGKDD Explorations Newsletter, 2006)
We discuss what makes exciting and motivating Grand Challenge problems for Data Mining, and propose criteria for a good Grand Challenge. We then consider possible GC problems from multimedia mining, link mining, large- scale modeling, text mining, and proteomics. This report is the result of a panel held at KDD-2006 conference.

What do high-level memory models mean for transactions? - Grossman,Dan; Manson,Jeremy; Pugh, William (Proceedings of the 2006 workshop on Memory system performance and correctness - MSPC '06, 2006)

What Is the Range of Surface Reconstructions from a Gradient Field? - Agrawal,Amit; Raskar,Ramesh; Chellapa, Rama (Computer Vision – ECCV 2006Computer Vision – ECCV 2006, 2006)
We propose a generalized equation to represent a continuum of surface reconstruction solutions of a given non-integrable gradient field. We show that common approaches such as Poisson solver and Frankot-Chellappa algorithm are special cases of this generalized equation. For a N × N pixel grid, the subspace of all integrable gradient fields is of dimension N 2 – 1. Our framework can be applied to derive a range of meaningful surface reconstructions from this high dimensional space. The key observation is that the range of solutions is related to the degree of anisotropy in applying weights to the gradients in the integration process. While common approaches use isotropic weights, we show that by using a progression of spatially varying anisotropic weights, we can achieve significant improvement in reconstructions. We propose (a) α-surfaces using binary weights, where the parameter α allows trade off between smoothness and robustness, (b) M-estimators and edge preserving regularization using continuous weights and (c) Diffusion using affine transformation of gradients. We provide results on photometric stereo, compare with previous approaches and show that anisotropic treatment discounts noise while recovering salient features in reconstructions.

3D Facial Pose Tracking in Uncalibrated Videos - Aggarwal,Gaurav; Veeraraghavan,Ashok; Chellapa, Rama (Pattern Recognition and Machine IntelligencePattern Recognition and Machine Intelligence, 2005)
This paper presents a method to recover the 3D configuration of a face in each frame of a video. The 3D configuration consists of the 3 translational parameters and the 3 orientation parameters which correspond to the yaw, pitch and roll of the face, which is important for applications like face modeling, recognition, expression analysis, etc. The approach combines the structural advantages of geometric modeling with the statistical advantages of a particle-filter based inference. The face is modeled as the curved surface of a cylinder which is free to translate and rotate arbitrarily. The geometric modeling takes care of pose and self-occlusion while the statistical modeling handles moderate occlusion and illumination variations. Experimental results on multiple datasets are provided to show the efficacy of the approach. The insensitivity of our approach to calibration parameters (focal length) is also shown.

3D Visualization of Semantic Metadata Models and Ontologies - Charalampos Papamanthou; Tollis, Ioannis G.; Doerr, Martin (Graph Drawing, 2005)
We propose an algorithm for the 3D visualization of general ontology models used in many applications, such as semantic web, entity-relationship diagrams and other database models. The visualization places entities in the 3D space. Previous techniques produce drawings that are 2-dimensional, which are often complicated and hard to comprehend. Our technique uses the third dimension almost exclusively for the display of the isa relationships (links) while the property relationships (links) are placed on some layer (plane). Thus the semantic difference between isa links and property links, which should be as vertical or as horizontal as possible respectively, is emphasized. Special reference is made on a certain model, the CIDOC Conceptual Reference Model.
Keywords: Algorithm Analysis and Problem Complexity; Computer Graphics; Data structures; Discrete Mathematics in Computer Science

Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices - Berry,M. W; Pulatova,S. A; Stewart, G.W. (ACM Transactions on Mathematical Software-TOMS, 2005)

Algorithmic aspects of capacity in wireless networks - Kumar,V. S. Anil; Marathe,Madhav V.; Parthasarathy,Srinivasan; Srinivasan, Aravind (Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, 2005)
This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(si,ti)}, what is the maximum throughput capacity of the network, i.e. the rate at which data from the sources to their corresponding destinations can be transferred in the network? (ii) Can network protocols be designed that jointly route the packets and schedule transmissions at rates close to the maximum throughput capacity? Much of the earlier work focused on random instances and proved analytical lower and upper bounds on the maximum throughput capacity. Here, in contrast, we consider arbitrary wireless networks. Further, we study the algorithmic aspects of the above questions: the goal is to design provably good algorithms for arbitrary instances. We develop analytical performance evaluation models and distributed algorithms for routing and scheduling which incorporate fairness, energy and dilation (path-length) requirements and provide a unified framework for utilizing the network close to its maximum throughput capacity.Motivated by certain popular wireless protocols used in practice, we also explore "shortest-path like" path selection strategies which maximize the network throughput. The theoretical results naturally suggest an interesting class of congestion aware link metrics which can be directly plugged into several existing routing protocols such as AODV, DSR, etc. We complement the theoretical analysis with extensive simulations. The results indicate that routes obtained using our congestion aware link metrics consistently yield higher throughput than hop-count based shortest path metrics.
Keywords: capacity modeling; end-to-end scheduling; Linear programming; Wireless networks

Algorithms for constructing 3-D point clouds using multiple digital fringe projection patterns - Peng,T.; Gupta,S.K.; Lau,K. (Computer-Aided Design and Applications, 2005)
This paper describes algorithms for generating 3-D point clouds from a set of digital imagesobtained from projecting phase-shifted sinusoidal fringe patterns onto object. In this paper, a mathematical model is introduced for describing the geometric relationship between the fringe patterns being projected, the image captured and the shape of the object being measured. This model allows considerable flexibility in the spatial configuration of shape measurement system. The algorithms for point cloud construction described in this paper present an improvement over the existing algorithms in terms of accuracy, ease of system calibration, and sensitivity to parameter errors. These algorithms have been incorporated in a shape measurement system and shown to have a very good performance.

And away we go: understanding the complexity of launching complex HPC applications - Yoon,Il-Chul; Sussman, Alan; Porter, Adam (Proceedings of the second international workshop on Software engineering for high performance computing system applications, 2005)
Although not well-studied, launching HPC applications is extremely complex. To better understand the launching process, we conducted a simple case study. Based in part on this study and an examination of existing toolkits, we have begun to develop a prototype environment to support HPC application launching.
Keywords: development; high-performance; Productivity; software

Are GSM phones THE solution for localization? - Varshavsky,A.; Chen,M.Y.; de Lara,E.; Jon Froehlich; Haehnel,D.; Hightower,J.; LaMarca,A.; Potter,F.; Sohn,T.; Tang,K.; others (Mobile Computing Systems and Applications, 2006. WMCSA'06. Proceedings. 7th IEEE Workshop on, 2005)

BIND: a fine-grained attestation service for secure distributed systems - Elaine Shi; Perrig, A.; Van Doorn, L. (2005)
In this paper we propose BIND (binding instructions and data), a fine-grained attestation service for securing distributed systems. Code attestation has recently received considerable attention in trusted computing. However, current code attestation technology is relatively immature. First, due to the great variability in software versions and configurations, verification of the hash is difficult. Second, the time-of-use and time-of-attestation discrepancy remains to be addressed, since the code may be correct at the time of the attestation, but it may be compromised by the time of use. The goal of BIND is to address these issues and make code attestation more usable in securing distributed systems. BIND offers the following properties: (1) BIND performs fine-grained attestation. Instead of attesting to the entire memory content, BIND attests only to the piece of code we are concerned about. This greatly simplifies verification. (2) BIND narrows the gap between time-of-attestation and time-of-use. BIND measures a piece of code immediately before it is executed and uses a sandboxing mechanism to protect the execution of the attested code. (3) BIND ties the code attestation with the data that the code produces, such that we can pinpoint what code has been run to generate that data. In addition, by incorporating the verification of input data integrity into the attestation, BIND offers transitive integrity verification, i.e., through one signature, we can vouch for the entire chain of processes that have performed transformations over a piece of data. BIND offers a general solution toward establishing a trusted environment for distributed system designers.
Keywords: BIND; binding instructions and data; code attestation; data integrity; digital signatures; distributed processing; fine-grained attestation service; input data integrity; program verification; sandboxing mechanism; secure distributed systems; signature; time-of-attestation; time-of-use; transitive integrity verification; trusted computing

Broadening Access to Large Online Databases by Generalizing Query Previews (2000) - Tanin,Egemen; Plaisant, Catherine; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Companies, government agencies, and other types of organizations are making their large databases available to the world over the Internet. Current database front-ends do not give users information about the distribution of data. This leads many users to waste time and network resources posing queries that have either zero-hit or mega-hit result sets. Query previews form a novel visual approach for browsing large databases. Query previews supply data distribution information about the database that is being searched and give continuous feedback about the size of the result set for the query as it is being formed. On the other hand, query previews use only a few pre-selected attributes of the database. The distribution information is displayed only on these attributes. Unfortunately, many databases are formed of numerous relations and attributes. This paper introduces a generalization of query previews. We allow users to browse all of the relations and attributes of a database using a hierarchical browser. Any of the attributes can be used to display the distribution information, making query previews applicable to many public online databases.
Keywords: Technical Report

The Challenge of Personal Information Management - Dix,A.; Jones,W.; Czerwinski,M.; Teevan,J.; Plaisant, Catherine; Moran,TP (INTERACT'05: Communicating Naturally through Computers (Adjunct Proceedings), 2005)

Clustering Techniques for Out-of-Core Multi-resolution Modeling - Danovaro,Emanuele; De Floriani, Leila; Puppo,Enrico; Samet, Hanan (Visualization Conference, IEEE, 2005)
Thanks to improvements in simulation tools, high resolution scanning facilities and multidimensional medical imaging, huge datasets are commonly available. Multi-resolution models manage the complexity of such data sets, by varying resolution and focusing detail in specific areas of interests. Since many currently available data sets cannot fit in main memory, the need arises to design data structures, construction and query algorithms for multi-resolution models which work in secondary memory.

Comparative Genomics of Trypanosomatid Parasitic Protozoa - El‐Sayed, Najib M.; Myler,Peter J.; Blandin,Gaëlle; Berriman,Matthew; Crabtree,Jonathan; Aggarwal,Gautam; Caler,Elisabet; Renauld,Hubert; Worthey,Elizabeth A.; Hertz-Fowler,Christiane; Ghedin,Elodie; Peacock,Christopher; et al. (Science, 2005)
A comparison of gene content and genome architecture of Trypanosoma brucei, Trypanosoma cruzi, and Leishmania major, three related pathogens with different life cycles and disease pathology, revealed a conserved core proteome of about 6200 genes in large syntenic polycistronic gene clusters. Many species-specific genes, especially large surface antigen families, occur at nonsyntenic chromosome-internal and subtelomeric regions. Retroelements, structural RNAs, and gene family expansion are often associated with syntenic discontinuities that—along with gene divergence, acquisition and loss, and rearrangement within the syntenic regions—have shaped the genomes of each parasite. Contrary to recent reports, our analyses reveal no evidence that these species are descended from an ancestor that contained a photosynthetic endosymbiont.

Content Index to Volume 18 - Kuniavsky,M.; Vaughan,M.; Bederson, Benjamin B.; Shneiderman, Ben; Rau,P.L.P.; from Menus,T.; Lane,D.M.; Napier,H.A.; Peres,S.C.; Sándor,A. (INTERNATIONAL JOURNAL OF HUMAN–COMPUTER INTERACTION, 2005)

The CPR model for summarizing video - Fayzullin,M.; V.S. Subrahmanian; Picariello, A.; Sapino,M. L (Multimedia Tools and Applications, 2005)
Most past work on video summarization has been based on selecting key frames from videos. We propose a model of video summarization based on three important parameters: Priority (of frames), Continuity (of the summary), and non-Repetition (of the summary). In short, a summary must include high priority frames and must be continuous and non-repetitive. An optimal summary is one that maximizes an objective function based on these three parameters. We show examples of how CPR parameters can be computed and provide algorithms to find optimal summaries based on the CPR approach. Finally, we briefly report on the performance of these algorithms.

Data sharing in ecology and evolution - Parr,Cynthia S.; Cummings, Michael P. (Trends in Ecology & Evolution, 2005)

Designing The User Interface - Shneiderman, Ben; Plaisant, Catherine (Pearson Addison Wesley, USA, 2005)

Detection of denial-of-message attacks on sensor network broadcasts - McCune, J.M.; Elaine Shi; Perrig, A.; Reiter, M.K. (2005)
So far sensor network broadcast protocols assume a trustworthy environment. However in safety and mission-critical sensor networks this assumption may not be valid and some sensor nodes might be adversarial. In these environments, malicious sensor nodes can deprive other nodes from receiving a broadcast message. We call this attack a denial-of-message attack (DoM). In this paper we model and analyze this attack, and present countermeasures. We present SIS, a secure implicit sampling scheme that permits a broadcasting base station to probabilistically detect the failure of nodes to receive its broadcast, even if these failures result from an attacker motivated to induce these failures undetectably. SIS works by eliciting authenticated acknowledgments from a subset of nodes per broadcast, where the subset is unpredictable to the attacker and tunable so as to mitigate acknowledgment implosion on the base station. We use a game-theoretic approach to evaluate this scheme in the face of an optimal attacker that attempts to maximize the number of nodes it denies the broadcast while remaining undetected by the base station, and show that SIS significantly constrains such an attacker even in sensor networks exhibiting high intrinsic loss rates. We also discuss extensions that permit more targeted detection capabilities.
Keywords: authenticated acknowledgments; broadcast channels; broadcast protocols; broadcasting base station; countermeasures; denial-of-message attacks; DoM; game theory; game-theoretic approach; malicious sensor nodes; Mobile computing; optimal attacker; probabilistic detection; probability; Protocols; Sampling methods; secure implicit sampling; sensor network broadcasts; SIS; telecommunication security; Wireless sensor networks

Distributed performance testing using statistical modeling - Karr,A. F; Porter, Adam (Proceedings of the 1st international workshop on Advances in model-based testing, 2005)

Diverse polyubiquitin interaction properties of ubiquitin-associated domains - Raasi,Shahri; Varadan,Ranjani; Fushman, David; Pickart,Cecile M. (Nature Structural & Molecular Biology, 2005)
The ubiquitin-associated (UBA) domain occurs frequently in proteins involved in ubiquitin-dependent signaling pathways. Although polyubiquitin chain binding is considered to be a defining feature of the UBA domain family, the generality of this property has not been established. Here we have surveyed the polyubiquitin interaction properties of 30 UBA domains, including 16 of 17 occurrences in budding yeast. The UBA domains sort into four classes that include linkage-selective polyubiquitin binders and domains that bind different chains (and monoubiquitin) in a nondiscriminatory manner; one notable class (30%) did not bind any ubiquitin ligand surveyed. The properties of a given UBA domain are conserved from yeast to mammals. Their functional relevance is further suggested by the ability of an ectopic UBA domain to alter the specificity of a deubiquitylating enzyme in a predictable manner. Conversely, non-UBA sequences can modulate the interaction properties of a UBA domain.
Keywords: apoptosis; basic cellular processes; Biochemistry; biophysics; cell biology; cell cycle; cell surface proteins; cell-cell interactions; checkpoints; chromatin; chromatin remodeling; chromatin structure; content; DNA recombination; DNA repair; DNA replication; Gene expression; Genetics; intracellular signaling; journal; macromolecules; mechanism; membrane processes; molecular; molecular basis of disease; molecular biology; molecular interactions; multi-component complexes; nature publishing group; nature structural molecular biology; nucleic acids; protein degradation; protein folding; protein processing; Proteins; regulation of transcription; regulation of translation; RNA; RNA processing; RNAi; signal transduction; single molecule studies; structure and function of proteins; transcription; translation

An empirical study of regression test application frequency - Kim,J. M; Porter, Adam; Rothermel,G. (Software Testing, Verification and Reliability, 2005)

Evaluating and tuning a static analysis to find null pointer bugs - Hovemeyer,D.; Spacco,J.; Pugh, William (Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, 2005)

Evaluation Methodologies for Visual Analytics - Laskowski,S.; Plaisant, Catherine (Illuminating the Path: The Research and Development Agenda for Visual AnalyticsIlluminating the Path: The Research and Development Agenda for Visual Analytics, 2005)
Keywords: file-import-09-03-18

Evolutionary discovery of arbitrary self-replicating structures - PAN,Z.; Reggia, James A. (Computational Science–ICCS 2005, 2005)

EvoSTOC Contributions - Merkle,D.; Middendorf,M.; Scheidler,A.; Avigad,G.; Moshaiov,A.; Brauner,N.; Parsopoulos,K.E.; Vrahatis,M.N.; Rand, William; Riolo,R (Applications of evolutionary computing: EvoWorkshops 2005, EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoMUSART, and EvoSTOC, 2005)

An experimental evaluation to determine if port scans are precursors to an attack - Panjwani,S.; Tan,S.; Jarrin,K.M.; Michel Cukier (2005)
This paper describes an experimental approach to determine the correlation between port scans and attacks. Discussions in the security community often state that port scans should be considered as precursors to an attack. However, very few studies have been conducted to quantify the validity of this hypothesis. In this paper, attack data were collected using a test-bed dedicated to monitoring attackers. The data collected consist of port scans, ICMP scans, vulnerability scans, successful attacks and management traffic. Two experiments were performed to validate the hypothesis of linking port scans and vulnerability scans to the number of packets observed per connection. Customized scripts were then developed to filter the collected data and group them on the basis of scans and attacks between a source and destination IP address pair. The correlation of the filtered data groups was assessed. The analyzed data consists of forty-eight days of data collection for two target computers on a heavily utilized subnet.
Keywords: attack data collection; computer crime; filtered data groups; ICMP scans; IP address; IP networks; management traffic; port scans; telecommunication security; Telecommunication traffic; vulnerability scans

Extending the Utility of Treemaps with Flexible Hierarchy (2004) - Chintalapani,Gouthami; Plaisant, Catherine; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Treemaps is a visualization technique for presenting hierarchical information on two dimensional displays. Prior implementations limit the visualization to pre-defined static hierarchies. Flexible hierarchy, a new capability of Treemap 4.0, enables users to define various hierarchies through dynamically selecting a series of data attributes so that they can discover patterns, clusters and outliers. This paper describes the design and implementation issues of flexible hierarchy. It then reports on a usability study which led to enhancements to the interface.
Keywords: Technical Report

Extracting regions of symmetry - Gupta,A.; Prasad,V. S.N; Davis, Larry S. (Image Processing, 2005. ICIP 2005. IEEE International Conference on, 2005)
This paper presents an approach for extending the normalized-cut (n-cut) segmentation algorithm to find symmetric regions present in natural images. We use an existing algorithm to quickly detect possible symmetries present in an image. The detected symmetries are then individually verified using the modified n-cut algorithm to eliminate spurious detections. The weights of the n-cut algorithm are modified so as to include both symmetric and spatial affinities. A global parameter is defined to model the tradeoff between spatial coherence and symmetry. Experimental results indicate that symmetric quality measure for a region segmented by our algorithm is a good indicator for the significance of the principal axis of symmetry.
Keywords: algorithm; coherence; DETECTION; detection; elimination; extraction; feature; image; images; natural; normalized-cut; object; region; segmentation; segmentation; spatial; spurious; symmetry

Fast illumination-invariant background subtraction using two views: error analysis, sensor placement and applications - Lim,Ser-Nam; Mittal,A.; Davis, Larry S.; Paragios,N. (Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2005)
Background modeling and subtraction to detect new or moving objects in a scene is an important component of many intelligent video applications. Compared to a single camera, the use of multiple cameras leads to better handling of shadows, specularities and illumination changes due to the utilization of geometric information. Although the result of stereo matching can be used as the feature for detection, it has been shown that the detection process can be made much faster by a simple subtraction of the intensities observed at stereo-generated conjugate pairs in the two views. The methodology however, suffers from false and missed detections due to some geometric considerations. In this paper, we perform a detailed analysis of such errors. Then, we propose a sensor configuration that eliminates false detections. Algorithms are also proposed that effectively eliminate most detection errors due to missed detections, specular reflections and objects being geometrically close to the background. Experiments on several scenes illustrate the utility and enhanced performance of the proposed approach compared to existing techniques.
Keywords: analysis; application; background; cameras; configuration; DETECTION; detection; error; error; extraction; false; feature; handling; illumination-invariance; image; intelligent; matching; modeling; object; placement; processing; sensor; sensors; shadow; stereo; subtraction; video

Formal approaches to teamwork - Grant,J.; Kraus,S.; Perlis, Don (We Will Show Them: Essays in Honour of Dov Gabbay, 2005)

A framework for set-oriented computation in inductive logic programming and its application in generalizing inverse entailment - Corrada Bravo, Hector; Page,D.; Ramakrishnan,R.; Shavlik,J.; Costa,V. S (Inductive Logic Programming, 2005)

Fusing Depth and Video Using Rao-Blackwellized Particle Filter - Agrawal,Amit; Chellapa, Rama (Pattern Recognition and Machine IntelligencePattern Recognition and Machine Intelligence, 2005)
We address the problem of fusing sparse and noisy depth data obtained from a range finder with features obtained from intensity images to estimate ego-motion and refine 3D structure of a scene using a Rao-Blackwellized particle filter. For scenes with low depth variability, the algorithm shows an alternate way of performing Structure from Motion (SfM) starting with a flat depth map. Instead of using 3D depths, we formulate the problem using 2D image domain parallax and show that conditioned on non-linear motion parameters, the parallax magnitude with respect to the projection of the vanishing point forms a linear subsystem independent of camera motion and their distributions can be analytically integrated. Thus, the structure is obtained by estimating parallax with respect to the given depths using a Kalman filter and only the ego-motion is estimated using a particle filter. Hence, the required number of particles becomes independent of the number of feature points which is an improvement over previous algorithms. Experimental results on both synthetic and real data show the effectiveness of our approach.