Optimal Cryptographic Hardness of Learning Monotone Functions - Dana Dachman-Soled; Lee, Homin K.; Malkin, Tal; Servedio, Rocco A.; Wan, Andrew; Wee, Hoeteck (Automata, Languages and Programming, 2008)
A wide range of positive and negative results have been established for learning different classes of Boolean functions from uniformly distributed random examples. However, polynomial-time algorithms have thus far been obtained almost exclusively for various classes of monotone functions, while the computational hardness results obtained to date have all been for various classes of general (nonmonotone) functions. Motivated by this disparity between known positive results (for monotone functions) and negative results (for nonmonotone functions), we establish strong computational limitations on the efficient learnability of various classes of monotone functions. We give several such hardness results which are provably almost optimal since they nearly match known positive results. Some of our results show cryptographic hardness of learning polynomial-size monotone circuits to accuracy only slightly greater than 1/2+1/n‾‾√1/2 + 1/\sqrt{n} ; this accuracy bound is close to optimal by known positive results (Blum et al., FOCS ’98). Other results show that under a plausible cryptographic hardness assumption, a class of constant-depth, sub-polynomial-size circuits computing monotone functions is hard to learn; this result is close to optimal in terms of the circuit size parameter by known positive results as well (Servedio, Information and Computation ’04). Our main tool is a complexity-theoretic approach to hardness amplification via noise sensitivity of monotone functions that was pioneered by O’Donnell (JCSS ’04).
Keywords: Data structures; Data Structures, Cryptology and Information Theory; Discrete Mathematics in Computer Science; Numeric Computing; Software Engineering/Programming and Operating Systems; Theory of computation

A pilot study to compare programming effort for two parallel programming models - Hochstein, Lorin; Basili, Victor R.; Vishkin, Uzi; Gilbert,John (Journal of Systems and Software, 2008)
ContextWriting software for the current generation of parallel systems requires significant programmer effort, and the community is seeking alternatives that reduce effort while still achieving good performance. Objective Measure the effect of parallel programming models (message-passing vs. PRAM-like) on programmer effort. Design, setting, and subjects One group of subjects implemented sparse-matrix dense-vector multiplication using message-passing (MPI), and a second group solved the same problem using a PRAM-like model (XMTC). The subjects were students in two graduate-level classes: one class was taught MPI and the other was taught XMTC. Main outcome measures Development time, program correctness. Results Mean XMTC development time was 4.8 h less than mean MPI development time (95% confidence interval, 2.0–7.7), a 46% reduction. XMTC programs were more likely to be correct, but the difference in correctness rates was not statistically significant (p = .16). Conclusions XMTC solutions for this particular problem required less effort than MPI equivalents, but further studies are necessary which examine different types of problems and different levels of programmer experience.
Keywords: effort; empirical study; Message-passing; MPI; parallel programming; PRAM; XMT

Preserving the privacy of sensitive relationships in graph data - Zheleva,Elena; Getoor, Lise (Proceedings of the 1st ACM SIGKDD international conference on Privacy, security, and trust in KDD, 2008)
In this paper, we focus on the problem of preserving the privacy of sensitive relationships in graph data. We refer to the problem of inferring sensitive relationships from anonymized graph data as link reidentification. We propose five different privacy preservation strategies, which vary in terms of the amount of data removed (and hence their utility) and the amount of privacy preserved. We assume the adversary has an accurate predictive model for links, and we show experimentally the success of different link re-identification strategies under varying structural characteristics of the data.
Keywords: anonymization; graph data; identification; link mining; noisy-or; privacy; social network analysis

Promoting Insight-Based Evaluation of Visualizations: From Contest to Benchmark Repository - Plaisant, Catherine; Fekete,J.-D.; Grinstein,G. (Visualization and Computer Graphics, IEEE Transactions on, 2008)
Information visualization (InfoVis) is now an accepted and growing field, but questions remain about the best uses for and the maturity of novel visualizations. Usability studies and controlled experiments are helpful, but generalization is difficult. We believe that the systematic development of benchmarks will facilitate the comparison of techniques and help identify their strengths under different conditions. We were involved in the organization and management of three InfoVis contests for the 2003, 2004, and 2005 IEEE InfoVis Symposia, which requested teams to report on insights gained while exploring data. We give a summary of the state of the art of evaluation in InfoVis, describe the three contests, summarize their results, discuss outcomes and lessons learned, and conjecture the future of visualization contests. All materials produced by the contests are archived in the InfoVis benchmark repository.
Keywords: Computer-Assisted; Software; Software Validation; User-Computer Interface; Factual; Evaluation Studies as Topic; Image Interpretation; InfoVis contest; benchmark repository; information visualization; data visualisation; Algorithms; Benchmarking; Computer Graphics; Databases

The Randomized Coloring Procedure with Symmetry-Breaking - Pemmaraju,Sriram; Srinivasan, Aravind (Automata, Languages and ProgrammingAutomata, Languages and Programming, 2008)
A basic randomized coloring procedure has been used in probabilistic proofs to obtain remarkably strong results on graph coloring. These results include the asymptotic version of the List Coloring Conjecture due to Kahn, the extensions of Brooks’ Theorem to sparse graphs due to Kim and Johansson, and Luby’s fast parallel and distributed algorithms for graph coloring. The most challenging aspect of a typical probabilistic proof is showing adequate concentration bounds for key random variables. In this paper, we present a simple symmetry-breaking augmentation to the randomized coloring procedure that works well in conjunction with Azuma’s Martingale Inequality to easily yield the requisite concentration bounds. We use this approach to obtain a number of results in two areas: frugal coloring and weighted equitable coloring . A β-frugal coloring of a graph G is a proper vertex-coloring of G in which no color appears more than β times in any neighborhood. Let G = ( V , E ) be a vertex-weighted graph with weight function w : V →[0, 1] and let W = ∑ v ∈ V w ( v ). A weighted equitable coloring of G is a proper k -coloring such that the total weight of every color class is “large”, i.e., “not much smaller” than W / k ; this notion is useful in obtaining tail bounds for sums of dependent random variables.

Resolving arthropod phylogeny: exploring phylogenetic signal within 41 kb of protein-coding nuclear gene sequence - Regier,J. C; Shultz,J. W; Ganley,A. R.D; Hussey,A.; Shi,D.; Ball,B.; Zwick,A.; Stajich,J. E; Cummings, Michael P.; Martin,J. W; Cunningham,CW (Syst Biol, 2008)
This study attempts to resolve relationships among and within the four basal arthropod lineages (Pancrustacea, Myriapoda, Euchelicerata, Pycnogonida) and to assess the widespread expectation that remaining phylogenetic problems will yield to increasing amounts of sequence data. Sixty-eight regions of 62 protein-coding nuclear genes (approximately 41 kilobases (kb)/taxon) were sequenced for 12 taxonomically diverse arthropod taxa and a tardigrade outgroup. Parsimony, likelihood, and Bayesian analyses of total nucleotide data generally strongly supported the monophyly of each of the basal lineages represented by more than one species. Other relationships within the Arthropoda were also supported, with support levels depending on method of analysis and inclusion/exclusion of synonymous changes. Removing third codon positions, where the assumption of base compositional homogeneity was rejected, altered the results. Removing the final class of synonymous mutations–first codon positions encoding leucine and arginine, which were also compositionally heterogeneous–yielded a data set that was consistent with a hypothesis of base compositional homogeneity. Furthermore, under such a data-exclusion regime, all 68 gene regions individually were consistent with base compositional homogeneity. Restricting likelihood analyses to nonsynonymous change recovered trees with strong support for the basal lineages but not for other groups that were variably supported with more inclusive data sets. In a further effort to increase phylogenetic signal, three types of data exploration were undertaken. (1) Individual genes were ranked by their average rate of nonsynonymous change, and three rate categories were assigned–fast, intermediate, and slow. Then, bootstrap analysis of each gene was performed separately to see which taxonomic groups received strong support. Five taxonomic groups were strongly supported independently by two or more genes, and these genes mostly belonged to the slow or intermediate categories, whereas groups supported only by a single gene region tended to be from genes of the fast category, arguing that fast genes provide a less consistent signal. (2) A sensitivity analysis was performed in which increasing numbers of genes were excluded, beginning with the fastest. The number of strongly supported nodes increased up to a point and then decreased slightly. Recovery of Hexapoda required removal of fast genes. Support for Mandibulata (Pancrustacea + Myriapoda) also increased, at times to "strong" levels, with removal of the fastest genes. (3) Concordance selection was evaluated by clustering genes according to their ability to recover Pancrustacea, Euchelicerata, or Myriapoda and analyzing the three clusters separately. All clusters of genes recovered the three concordance clades but were at times inconsistent in the relationships recovered among and within these clades, a result that indicates that the a priori concordance criteria may bias phylogenetic signal in unexpected ways. In a further attempt to increase support of taxonomic relationships, sequence data from 49 additional taxa for three slow genes (i.e., EF-1 alpha, EF-2, and Pol II) were combined with the various 13-taxon data sets. The 62-taxon analyses supported the results of the 13-taxon analyses and provided increased support for additional pancrustacean clades found in an earlier analysis including only EF-1 alpha, EF-2, and Pol II.

Review of Classifier Combination Methods - Tulyakov,Sergey; Jaeger,Stefan; Govindaraju,Venu; David Doermann (Studies in Computational Intelligence: Machine Learning in Document Analysis and RecognitionStudies in Computational Intelligence: Machine Learning in Document Analysis and Recognition, 2008)
Classifier combination methods have proved to be an effective tool to increase the performance of pattern recognition applications. In this chapter we review and categorize major advancements in this field. Despite a significant number of publications describing successful classifier combination implementations, the theoretical basis is still missing and achieved improvements are inconsistent. By introducing different categories of classifier combinations in this review we attempt to put forward more specific directions for future theoretical research.We also introduce a retraining effect and effects of locality based training as important properties of classifier combinations. Such effects have significant influence on the performance of combinations, and their study is necessary for complete theoretical understanding of combination algorithms.

Role of transposable elements in trypanosomatids - Bringaud,Frédéric; Ghedin,Elodie; El‐Sayed, Najib M.; Papadopoulou,Barbara (Microbes and Infection, 2008)
Transposable elements constitute 2-5% of the genome content in trypanosomatid parasites. Some of them are involved in critical cellular functions, such as the regulation of gene expression in Leishmania spp. In this review, we highlight the remarkable role extinct transposable elements can play as the source of potential new functions.
Keywords: Cellular function; Domestication; Evolution; Gene expression; Leishmania; Regulation of mRNA stability; Retroposon; Transposable element; Trypanosoma

Satisfying Complex Data Needs using Pull-Based Online Monitoring of Volatile Data Sources - Roitman,Haggai; Gal,Avigdor; Raschid, Louiqa (Data Engineering, International Conference on, 2008)
Emerging applications on the Web require better management of volatile data in pull-based environments. In a pull based setting, data may be periodically removed from the server. Data may also become obsolete, no longer serving client needs. In both cases, we consider such data to be volatile. To model such constraints on data usability, and support complex user needs we define profiles to specify which data sources are to be monitored and when. Using a novel abstraction of execution intervals we model complex profiles that access simultaneously several servers to gain from the used data. Given some budgetary constraints (e.g., bandwidth), the paper formalizes the problem of maximizing completeness.

SCALABLE CATALOG INFRASTRUCTURE FOR MANAGING ACCESS COSTS AND SOURCE SELECTION IN WIDE AREA NETWORKS - Zadorozhny,V.; Raschid, Louiqa; Gal,A. (International Journal of Cooperative Information Systems, 2008)

Searching Electronic Health Records for Temporal Patterns in Patient Histories: A Case Study with Microsoft Amalga - Plaisant, Catherine; Lam,Stanley; Shneiderman, Ben; Smith,Mark S.; Roseman,David; Marchand,Greg; Gillam,Michael; Feied,Craig; Handler,Jonathan; Rappaport,Hank (AMIA Annual Symposium ProceedingsAMIA Annu Symp Proc, 2008)
As electronic health records (EHR) become more widespread, they enable clinicians and researchers to pose complex queries that can benefit immediate patient care and deepen understanding of medical treatment and outcomes. However, current query tools make complex temporal queries difficult to pose, and physicians have to rely on computer professionals to specify the queries for them. This paper describes our efforts to develop a novel query tool implemented in a large operational system at the Washington Hospital Center (Microsoft Amalga, formerly known as Azyxxi). We describe our design of the interface to specify temporal patterns and the visual presentation of results, and report on a pilot user study looking for adverse reactions following radiology studies using contrast.

Sex and Age Dimorphism of Myocardial Gene Expression in Nonischemic Human Heart Failure - Fermin,David R.; Barac,Ana; Lee,Sangjin; Polster,Sean P.; Hannenhalli, Sridhar; Bergemann,Tracy L.; Grindle,Suzanne; Dyke,David B.; Pagani,Francis; Miller,Leslie W.; Tan,Sarah; dos Remedios,Cris; et al. (Circulation: Cardiovascular Genetics, 2008)
Background— We report the first comprehensive analysis of gene expression differences by sex and age in left ventricular samples from 102 patients with dilated cardiomyopathy.Methods and Results— Gene expression data (HG-U133A gene chip, Affymetrix) were analyzed from 30 females and 72 males from 3 separate centers. More than 1800 genes displayed sexual dimorphism in the heart (adjusted P value <0.05). A significant number of these genes were highly represented in gene ontology pathways involved in ion transport and G-protein-coupled receptor signaling. Localization of these genes revealed enrichment on both the sex chromosomes as well as chromosomes 3, 4, and 14. The second goal of this study was to determine the effect of age on gene expression. Within the female cohort, >140 genes were differentially expressed in the <55 years age group compared with the >55 years age group. These genes were highly represented in gene ontology pathways involved in DNA damage. In contrast, zero genes in the male cohort <55 years met statistical significance when compared with the >55 years age group.Conclusions— Gene expression in dilated cardiomyopathy displayed evidence of sexual dimorphism similar to other somatic tissues and age dimorphism within the female cohort.

A “Shape Aware” Model for semi-supervised Learning of Objects and its Context - Gupta,A.; Shi,J.; Davis, Larry S. (Proc. of NIPS, 2008)
We present an approach that combines bag-of-words and spatial models to performsemantic and syntactic analysis for recognition of an object based on its internal appearance and its context. We argue that while object recognition requires mod- eling relative spatial locations of image features within the object, a bag-of-word is sufficient for representing context. Learning such a model from weakly labeled data involves labeling of features into two classes: foreground(object) or “infor- mative” background(context). We present a “shape-aware” model which utilizes contour information for efficient and accurate labeling of features in the image. Our approach iterates between an MCMC-based labeling and contour based la- beling of features to integrate co-occurrence of features and shape similarity.

SNARE: Spatio-temporal Network-level Automatic Reputation Engine - Feamster, Nick; Gray,A.G.; Krasser,S.; Syed,N.A. (Georgia Institute of Technology, 2008)
Current spam filtering techniques classify email based oncontent and IP reputation blacklists or whitelists. Unfortu- nately, spammers can alter spam content to evade content- based filters, and spammers continually change the IP ad- dresses from which they send spam. Previous work has sug- gested that filters based on network-level behavior might be more efficient and robust, by making decisions based on how messages are sent, as opposed to what is being sent or who is sending them. This paper presents a technique to identify spammers based on features that exploit the network-level spatio- temporal behavior of email senders to differentiate the spam- ming IPs from legitimate senders. Our behavioral classifier has two benefits: (1) it is early (i.e., it can automatically detect spam without seeing a large amount of email from a sending IP address—sometimes even upon seeing only a single packet); (2) it is evasion-resistant (i.e., it is based on spatial and temporal features that are difficult for a sender to change). We build classifiers based on these features us- ing two different machine learning methods, support vec- tor machine and decision trees, and we study the efficacy of these classifiers using labeled data from a deployed com- mercial spam-filtering system. Surprisingly, using only fea- tures from a single IP packet header (i.e., without looking at packet contents), our classifier can identify spammers with about 93% accuracy and a reasonably low false-positive rate (about 7%). After looking at a single message spammer identification accuracy improves to more than 94% with a false rate of just over 5%. These suggest an effective sender reputation mechanism.

Sound field decomposition using spherical microphone arrays - Zotkin,Dmitry N; Duraiswami, Ramani; Gumerov, Nail A. (IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. ICASSP 2008, 2008)
Spherical microphone arrays offer a number of attractive properties such as direction-independent acoustic behavior and ability to reconstruct the sound field in the vicinity of the array. Such ability is necessary in applications such as ambisonics and recreating auditory environment over headphones. We compare the performance of two scene reconstruction algorithms - one based on least-squares fitting the observed potentials and another based on computing the far-field signature function directly from the microphone measurements. A number of features important for the design and operation of spherical microphone arrays in real applications are revealed. Results indicate that it is possible to reconstruct the sound scene up to order p with p2 microphones.
Keywords: Acoustic applications; Acoustic arrays; Acoustic fields; acoustic position measurement; Acoustic propagation; acoustic signal processing; acoustic waves; array signal processing; Equations; far-field signature function; Layout; least-squares fitting; microphone arrays; scene reconstruction algorithms; Signal processing algorithms; sound field decomposition; spherical microphone arrays; Surface acoustic waves

Spherical Arrays Near Boundaries - Duraiswami, Ramani; Gumerov, Nail A.; O'Donovan,A. (Hands-Free Speech Communication and Microphone Arrays, 2008. HSCMA 2008, 2008)
Summary form only given. Solid spherical microphone arrays are beginning to be used for purposes such as beamforming, sound field capture and as audio cameras. They rely on the scattering of sound off their surface to achieve their purpose. This behavior is significantly affected in the presence of boundaries (floors, walls, ceilings), and the edges and corners they form. Algorithms designed for array analysis in a free field will work erroneously in this situation. We describe adaptation of the spherical microphone analysis algorithms to constructively use the scattering off the boundaries to significantly improve array performance. We also assess the influence of walls on beamforming algorithms for regular spherical arrays. Both synthetic and experimental results are presented.
Keywords: analysis; audio; analysis; microphone; array; arrays; arrays; sound; arrays; spherical; cameras; beamforming; solid; capture; spherical; field; microphone; spherical

Statistical Relational Learning as an Enabling Technology for Data Acquisition and Data Fusion in Heterogeneous Sensor Networks - Jacobs, David W.; Getoor, Lise (OFFICE OF RESEARCH ADMINISTRATION AND ADVANCEMENT, UNIVERSITY OF MARYLAND COLLEGE PARK, 2008)
Our work has focused on developing new cost sensitive feature acquisition and classification algorithms, mapping these algorithms onto camera networks, and creating a test bed of video data and implemented vision algorithms that we can use to implement these. First, we will describe a new algorithm that we have developed for feature acquisition in Hidden Markov Models (HMMs). This is particularly useful for inference tasks involving video from a single camera, in which the relationship between frames of video can be modeled as a Markov chain. We describe this algorithm in the context of using background subtraction results to identify portions of video that contain a moving object. Next, we will describe new algorithms that apply to general graphical models. These can be tested using existing test sets that are drawn from a range of domains in addition to sensor networks.
Keywords: *ALGORITHMS; *CLASSIFICATION; data acquisition; DATA FUSION; Detectors; Feature extraction; HMM(HIDDEN MARKOV MODELS); NETWORKS; NUMERICAL MATHEMATICS; PE611102; RANDOM FIELDS; STATISTICS AND PROBABILITY; TEST SETS; VIDEO SIGNALS

Structural Sampling for Statistical Software Testing - Baskiotis,N.; Sebag,M.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Kersting,K.; Muggleton,S. H (Probabilistic, Logical and Relational Learning-A Further Synthesis, 2008)
Structural Statistical Software Testing exploits the control flow graph of the program being tested to construct test cases. While test cases can easily be extracted from {em feasible paths} in the control flow graph, that is, paths which are actually exerted for some values of the program input, the feasible path region is a tiny fraction of the graph paths (less than $10^{-5}]$ for medium size programs). The S4T algorithm presented in this paper aims to address this limitation; as an Active Relational Learning Algorithm, it uses the few feasible paths initially available to sample new feasible paths. The difficulty comes from the non-Markovian nature of the feasible path concept, due to the long-range dependencies between the nodes in the control flow graph. Experimental validation on real-world and artificial problems demonstrates significant improvements compared to the state of the art.

Structured machine learning: the next ten years - Dietterich,T. G; Domingos,P.; Getoor, Lise; Muggleton,S.; Tadepalli,P. (Machine Learning, 2008)
The field of inductive logic programming (ILP) has made steady progress, since the first ILP workshop in 1991, based on a balance of developments in theory, implementations and applications. More recently there has been an increased emphasis on Probabilistic ILP and the related fields of Statistical Relational Learning (SRL) and Structured Prediction. The goal of the current paper is to consider these emerging trends and chart out the strategic directions and open problems for the broader area of structured machine learning for the next 10 years.

A Survey of the Virtual Environments-based Assembly Training Applications - Gupta,S.K.; Anand,D. K.; Brough,J. E.; Kavetsky,R. A.; Schwartz,M.; Thakur,A. (2008)
The advent of virtual environments is presenting new ways of trainingtomorrow’s workforce. Virtual environments offer numerous benefits in training applications. First, virtual environments allow extensive user interactions in a very convenient and natural manner. This interaction is greatly beneficial for increasing the user’s retention of spatial information compared to text-based or video-based instructions that are non-interactive in nature. Second, virtual environments provide users with a 3D immersive experience. This feature helps users gain a better understanding of spatial relationships compared to 2D displays. Third, virtual environments support multi-media instructions. One can watch standard videos, view 3D animations, view text instructions, listen to audio instructions, and interact with 3D objects in the scene. This paper describes representative research and associated systems that use of virtual environments in assembly training applications.

System-Level Optimization Model for a Snake-Inspired Robot Based on a Rectilinear Gait - Hopkins,James K.; Spranklin,Brent W.; Gupta, Satyandra K. (ASME, 2008)
Physical parameters of modules and gait parameters affect the overall snake-inspired robot performance. Hence the system-level optimization model has to concurrently optimize the module parameters and the gait. The equations of motion associated with the rectilinear gait are quite complex due to the changing topology of the rectilinear gait. Embedding these equations in the system-level optimization model leads to a computationally challenging formulation. This paper presents a system-level optimization model that utilizes a hierarchical optimization approach and meta-models of the pre-computed optimal gaits to reduce the complexity of the optimization model. This approach enabled us to use an experimentally validated physics-based model of the rectilinear gait and yet at the same time enabled us to create a system-level optimization model with a manageable complexity. A detailed case study is presented to show the importance of concurrently optimizing the module parameters and the gait using our model to obtain the optimal performance for a given mission.

Towards Design and Fabrication of a Miniature MRI-Compatible Robot for Applications in Neurosurgery - Pappafotis,Nicholas; Bejgerowski,Wojciech; Gullapalli,Rao; Simard,J. Marc; Gupta, Satyandra K.; Desai,Jaydev P. (ASME, 2008)
Brain tumors are among the most feared complications of cancer and they occur in 20–40% of adult cancer patients. Despite numerous advances in treatment, the prognosis for these patients is poor, with a median survival of 4–8 months. The primary reasons for poor survival rate are the lack of good continuous imaging modality for intraoperative intracranial procedures and the inability to remove the complete tumor tissue due to its placement in the brain and the corresponding space constraints to reach it. Intraoperative magnetic resonance imaging (MRI) supplements the surgeon's visual and tactile senses in a way that no other imaging device can achieve resulting in less trauma to surrounding healthy brain tissue during surgery. To minimize the trauma to surrounding healthy brain tissue, it would be beneficial to operate through a narrow surgical corridor dissected by the neurosurgeon. Facilitating tumor removal by accessing regions outside the direct “line-of-sight” of the neurosurgical corridor will require a highly dexterous, small cross section, and MRI-compatible robot. Developing such a robot is extremely challenging task. In this paper we report a preliminary design of 6-DOF robot for possible application in neurosurgery. The robot actuators and body parts are constructed from MRI compatible materials. The current prototype is 0.36” in diameter and weighs only 0.0289 N (2.95 grams). The device was actuated using Flexinol® which is a shape memory alloy manufactured by Dynalloy, Inc. The end-effector forces ranged from 12 mN to 50 mN depending on the robot configuration. The end-effector force to robot weight ratio varied from 0.41 to 1.73. During trials the robot motion was repeatable and the range of motion of the robot was about 90 degrees for the end-effector when one side shape memory alloy (SMA) channel was actuated. The actuation time from the start to finish was about 2.5 s.

Trusting spam reporters: A reporter-based reputation system for email filtering - Zheleva,Elena; Kolcz,Aleksander; Getoor, Lise (ACM Transactions on Information Systems (TOIS), 2008)
Spam is a growing problem; it interferes with valid email and burdens both email users and service providers. In this work, we propose a reactive spam-filtering system based on reporter reputation for use in conjunction with existing spam-filtering techniques. The system has a trust-maintenance component for users, based on their spam-reporting behavior. The challenge that we consider is that of maintaining a reliable system, not vulnerable to malicious users, that will provide early spam-campaign detection to reduce the costs incurred by users and systems. We report on the utility of a reputation system for spam filtering that makes use of the feedback of trustworthy users. We evaluate our proposed framework, using actual complaint feedback from a large population of users, and validate its spam-filtering performance on a collection of real email traffic over several weeks. To test the broader implication of the system, we create a model of the behavior of malicious reporters, and we simulate the system under various assumptions using a synthetic dataset.
Keywords: reputation systems; Spam filtering; trust

A Unified Framework for Multipath Routing for Unicast and Multicast Traffic - Guven,T.; La,R.J.; Shayman,M.A.; Bhattacharjee, Bobby (Networking, IEEE/ACM Transactions on, 2008)
We study the problem of load balancing the traffic from a set of unicast and multicast sessions. The problem is formulated as an optimization problem. However, we assume that the gradient of the network cost function is not available and needs to be estimated. Multiple paths are provided between a source and a destination using application-layer overlay. We propose a novel algorithm that is based on what is known as simultaneous perturbation stochastic approximation and utilizes only noisy measurements collected and reported to the sources, using an overlay architecture. We consider three network models that reflect different sets of assumptions regarding multicast capabilities of the network. Using an analytical model we first prove the almost sure convergence of the algorithm to a corresponding optimal solution under each network model considered in this paper with decreasing step sizes. Then, we establish the weak convergence (or convergence in distribution) with a fixed step size. In addition, we investigate the benefits acquired from implementing additional multicast capabilities by studying the relative performance of our algorithm under the three network models.
Keywords: application-layer; approximation; unicast; balancing; multicast; channels; stochastic; communication; multipath; cost; function; optimization; network; overlay; load; perturbation; problem; simultaneous; processes; telecommunication; routing; network; routing; telecommunication; Stochastic; traffic; traffic; multicast; traffic; multipath

Universally composable multi-party computation with an unreliable common reference string - Goyal,V.; Katz, Jonathan (Theory of Cryptography, 2008)
Universally composable (UC) multi-party computation has been studied in two settings. When a majority of parties are honest, UC multi-party computation is possible without any assumptions. Without a majority of honest parties, UC multi-party computation is impossible in the plain model, but feasibility results have been obtained in various augmented models. The most popular such model posits a common reference string (CRS) available to parties executing the protocol.In either of the above settings, some assumption regarding the protocol execution is made: i.e., that many parties are honest in the first case, or that a legitimately-chosen string is available in the second. If this assumption is incorrect then all security is lost. A natural question is whether it is possible to design protocols secure if either one of these assumptions holds, i.e., a protocol which is secure if either at most s players are dishonest or if up to t > s players are dishonest but the CRS is chosen in the prescribed manner. We show that such protocols exist if and only if s + t < n. This work was done in part while the authors were visiting IPAM.

Variational Bayes via Propositionalization - Sato,T.; Kameya,Y.; Kurihara,K.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Kersting,K.; Muggleton,S. H (Probabilistic, Logical and Relational Learning-A Further Synthesis, 2008)

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

An adaptive mean shift tracking method using multiscale images - Zhuolin Jiang; Li,Shao-Fa; Gao,Dong-Fa (Wavelet Analysis and Pattern Recognition, 2007. ICWAPR '07. International Conference on, 2007)
An adaptive mean shift tracking method for object tracking using multiscale images is presented in this paper. A bandwidth matrix and a Gaussian kernel are used to extend the definition of target model. The method can exactly estimate the position of the tracked object using multiscale images from Gaussian pyramid. The tracking method determines the parameters of kernel bandwidth by maximizing the lower bound of a log-likelihood function, which is derived from a kernel density estimate with the bandwidth matrix and the modified weight function. The experimental results show that it can averagely converge in 2.55 iterations per frame.
Keywords: adaptive mean shift tracking method; bandwidth matrix; Gaussian kernel; Gaussian processes; Image sequences; log-likelihood function; matrix algebra; maximum likelihood estimation; multiscale image; Object detection; object tracking

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.

Assessment of WENO methods with shock-confining filtering for LES of compressible turbulence - Grube,N. E; Taylor,E. M; Martin, M.P (AIAA Paper 2007, 2007)

Backbone construction in selfish wireless networks - Lee,Seungjoon; Levin,Dave; Gopalakrishnan,Vijay; Bhattacharjee, Bobby (Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, 2007)
We present a protocol to construct routing backbones in wireless networks composed of selfish participants. Backbones are inherently cooperative, so constructing them in selfish environments is particularly difficult; participants want a backbone to exist (soothers relay their packets) but do not want to join the backbone (so they do not have to relay packets for others). We model the wireless backbone as a public good and use impatience as an incentive for cooperation. To determine if and when to donate to this public good, each participant calculates how patient it should be in obtaining the public good. We quantify patience using the Volunteer's Timing Dilemma (VTD), which we extend to general multihop network settings. Using our generalized VTD analysis, each node individually computes as its dominant strategy the amount of time to wait before joining the backbone. We evaluate our protocol using both simulations and an implementation. Our results show that, even though participants in our system deliberately wait before volunteering, a backbone is formed quickly. Further, the quality of the backbone (such as the size and resulting network lifetime) is comparable to that of existing backbone protocols that assume altruistic behavior.
Keywords: incentives; public good; selfish network; volunteer's dilemma; wireless backbone

Biased data reduce efficiency and effectiveness of conservation reserve networks - Grand,Joanna; Cummings, Michael P.; Rebelo,Tony G; Ricketts,Taylor H; Neel,Maile C (Ecology Letters, 2007)
Complementarity-based reserve selection algorithms efficiently prioritize sites for biodiversity conservation, but they are data-intensive and most regions lack accurate distribution maps for the majority of species. We explored implications of basing conservation planning decisions on incomplete and biased data using occurrence records of the plant family Proteaceae in South Africa. Treating this high-quality database as ‘complete’, we introduced three realistic sampling biases characteristic of biodiversity databases: a detectability sampling bias and two forms of roads sampling bias. We then compared reserve networks constructed using complete, biased, and randomly sampled data. All forms of biased sampling performed worse than both the complete data set and equal-effort random sampling. Biased sampling failed to detect a median of 1–5% of species, and resulted in reserve networks that were 9–17% larger than those designed with complete data. Spatial congruence and the correlation of irreplaceability scores between reserve networks selected with biased and complete data were low. Thus, reserve networks based on biased data require more area to protect fewer species and identify different locations than those selected with randomly sampled or complete data.
Keywords: Bias; biodiversity conservation; complementarity; efficiency; marxan; rarity; reserve networks; reserve selection algorithms; species detection

Bridging art and science with creativity support tools - Shneiderman, Ben; Rita R Colwell; Diamond,Sara; Greenhalgh,Paul; Wulf,William (Proceedings of the 6th ACM SIGCHI conference on Creativity & cognition, 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.

Characterizing RNA Secondary-Structure Features and Their Effects on Splice-Site Prediction - Dogan,R. I; Getoor, Lise; Wilbur,W. J (Data Mining Workshops, 2007. ICDM Workshops 2007. Seventh IEEE International Conference on, 2007)
RNA molecules are distinguished by their sequence composition and by their three-dimensional shape, called the secondary structure. The secondary structure of a pre-mRNA sequence may have a strong influence on gene splicing. In our previous work, we showed that a splice-site model employing sequence features built using our feature generation algorithm was very effective in predicting splice sites. The generated sequence features also contained biologically relevant features. In this paper, we extend the feature generation algorithm to construct secondary-structure features. These features capture the nucleotide pairing tendency in the splice-site neighborhood. We extend the splice-site model to include both pre-mRNA sequence and structure characteristics. The new model significantly outperforms the sequence-based features model. The identified secondary-structure features capture biologically relevant signals such as splicing silencers. We also found these signals to prefer specific regions around the splice-site neighborhood and we detail their preference.
Keywords: algorithm; gene; biophysics; molecular; composition; splice-site; compounds; sequences; computing; genetics; macromolecules; molecular; configurations; organic; features; feature; generation; model; splice-site; molecules; RNA; neighborhood; three-dimensional; pairing; RNA; secondary-structure; sequence; shape; biology; splicing; nucleotide; tendency; pre-mRNA

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

Collective entity resolution in relational data - Bhattacharya,Indrajit; Getoor, Lise (ACM Trans. Knowl. Discov. Data, 2007)
Many databases contain uncertain and imprecise references to real-world entities. The absence of identifiers for the underlying entities often results in a database which contains multiple references to the same entity. This can lead not only to data redundancy, but also inaccuracies in query processing and knowledge extraction. These problems can be alleviated through the use of entity resolution. Entity resolution involves discovering the underlying entities and mapping each database reference to these entities. Traditionally, entities are resolved using pairwise similarity over the attributes of references. However, there is often additional relational information in the data. Specifically, references to different entities may cooccur. In these cases, collective entity resolution, in which entities for cooccurring references are determined jointly rather than independently, can improve entity resolution accuracy. We propose a novel relational clustering algorithm that uses both attribute and relational information for determining the underlying domain entities, and we give an efficient implementation. We investigate the impact that different relational similarity measures have on entity resolution quality. We evaluate our collective entity resolution algorithm on multiple real-world databases. We show that it improves entity resolution performance over both attribute-based baselines and over algorithms that consider relational information but do not resolve entities collectively. In addition, we perform detailed experiments on synthetically generated data to identify data characteristics that favor collective relational resolution over purely attribute-based algorithms.
Keywords: data cleaning; entity resolution; graph clustering; record linkage

Combining Collective Classification and Link Prediction - Bilgic,M.; Namata,G.M.; Getoor, Lise (Data Mining Workshops, 2007. ICDM Workshops 2007. Seventh IEEE International Conference on, 2007)
The problems of object classification (labeling the nodes of a graph) and link prediction (predicting the links in a graph) have been largely studied independently. Commonly, object classification is performed assuming a complete set of known links and link prediction is done assuming a fully observed set of node attributes. In most real world domains, however, attributes and links are often missing or incorrect. Object classification is not provided with all the links relevant to correct classification and link prediction is not provided all the labels needed for accurate link prediction. In this paper, we propose an approach that addresses these two problems by interleaving object classification and link prediction in a collective algorithm. We investigate empirically the conditions under which an integrated approach to object classification and link prediction improves performance, and find that performance improves over a wide range of network types, and algorithm settings.
Keywords: algorithm; link; classification; classification; graph; collective; prediction; object; theory; pattern

Combining statistical and logical inference for ontology alignment - Udrea,O.; Getoor, Lise (Workshop on Semantic Web for Collaborative Knowledge Acquisition at the International Joint Conference on Artificial Intelligence, 2007)
In recent years, ontologies have proved a veryattractive medium for storing domain knowl- edge in a variety of organizations; a few ex- ample domains are medicine1 and genetics2. The rapid evolution of representation stan- dards has led to the creation of distinct on- tology bases in overlapping domains, making it paramount for large systems to reconcile on- tological data from multiple sources. A large body of work on ontology integration[Euzenat, 2004] has produced algorithms and heuristics that have proven successful in alleviating the high computation costs of the process. How- ever, the effective use of ontology formalisms – such as rules and axioms – in the integra- tion process remains an open question. In this paper, we present a novel ontology integration method that takes advantage of the logical in- ference capabilities in OWL Lite to improve the recall of the merged ontologies. Our CPI (Clus- tering with Partial Inference) algorithm uses (i) graph clustering techniques to improve the process of selecting candidate matching enti- ties and (ii) a limited, adaptive reasoning pro- cess to account for the effects of introducing relationships between such entities. Our initial experiments, performed on a set of 30 pairs of publicly available ontologies, show that CPI of- fers a 30% improvement in recall and a 25% im- provement in answer quality compared to FCA- merge [Stumme and Maedche, 2001].

Combining Tuple and Attribute Uncertainty in Probabilistic Databases - Getoor, Lise (The first international VLDB workshop on Management of Uncertain Data, 2007)
There has been a long history of work in the database communityon probabilistic databases. There is also a long tradition of work within the machine learning and reasoning under uncertainty communities on tractable factored representations of probability distributions, such as probabilistic graphical models. Recently, research from these two commu- nities are starting to share more and more commonalities, as the proba- bilistic database work incorporates richer probabilistic dependencies and the machine learning work incorporates richer relational models. In this talk, I will survey some of the recent work, including work on probabilistic relational models. I will show how these models can capture both tuple and attribute uncertainty, and discuss effective query methods. Joint work with Prithviraj Sen and Amol Deshpande.

Compact, low power wireless sensor network system for line crossing recognition - Shen,C. C; Kupershtok,R.; Yang,B.; Vanin,F. M; Shao,X.; Sheth,D.; Goldsman,N.; Balzano,Q.; Bhattacharyya, Shuvra S. (Circuits and Systems, 2007. ISCAS 2007. IEEE International Symposium on, 2007)

Conditionalization: Adapting forward-chaining planners to partially observable environments - Kuter,U.; Nau, Dana S.; Reisner,E.; Goldman,R. (2007)
We provide a general way to take forward-chainingplanners for classical planning domains and condition- alize them, i.e., adapt them to generate policies for partially observable planning domains. For domain-configurable planners such as SHOP2, TLPlan, and TALplanner, our generalization tech- nique preserves the ability to use domain knowledge to achieve highly efficient planning. We demonstrate this experimentally in two problem domains. The experi- ments compare PKS and MBP (two existing planners for partially observable planning) and CondSHOP2, a version of the HTN planner SHOP2 created by apply- ing our conditionalization method. To our surprise, PKS and MBP could solve only the simplest problems in our test domains. In contrast, CondSHOP2 solved all of the test problems quite eas- ily. This suggests that the ability to use domain knowl- edge may be not just desirable but indeed essential for solving large problems in partially observable domains.

Confidentiality-preserving rank-ordered search - Swaminathan,Ashwin; Mao,Yinian; Su,Guan-Ming; Gou,Hongmei; Varna,Avinash L.; He,Shan; M. Wu; Oard, Douglas (Proceedings of the 2007 ACM workshop on Storage security and survivability, 2007)
This paper introduces a new framework for confidentiality preserving rank-ordered search and retrieval over large document collections. The proposed framework not only protects document/query confidentiality against an outside intruder, but also prevents an untrusted data center from learning information about the query and the document collection. We present practical techniques for proper integration of relevance scoring methods and cryptographic techniques, such as order preserving encryption, to protect data collections and indices and provide efficient and accurate search capabilities to securely rank-order documents in response to a query. Experimental results on the W3C collection show that these techniques have comparable performance to conventional search systems designed for non-encrypted data in terms of search accuracy. The proposed methods thus form the first steps to bring together advanced information retrieval and secure search capabilities for a wide range of applications including managing data in government and business operations, enabling scholarly study of sensitive data, and facilitating the document discovery process in litigation.
Keywords: encrypted domain search; Ranked retrieval; secure index

COST: An Approach for Camera Selection and Multi-Object Inference Ordering in Dynamic Scenes - Gupta,Abhinav; Mittal,Anurag; Davis, Larry S. (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
Development of multiple camera based vision systems for analysis of dynamic objects such as humans is challenging due to occlusions and similarity in the appearance of a person with the background and other people- visual "confusion". Since occlusion and confusion depends on the presence of other people in the scene, it leads to a dependency structure where there are often loops in the resulting Bayesian network. While approaches such as loopy belief propagation can be used for inference, they are computationally expensive and convergence is not guaranteed in many situations. We present a unified approach, COST, that reasons about such dependencies and yields an order for the inference of each person in a group of people and a set of cameras to be used for inferences for a person. Using the probabilistic distribution of the positions and appearances of people, COST performs visibility and confusion analysis for each part of each person and computes the amount of information that can be computed with and without more accurate estimation of the positions of other people. We present an optimization problem to select set of cameras and inference dependencies for each person which attempts to minimize the computational cost under given performance constraints. Results show the efficiency of COST in improving the performance of such systems and reducing the computational resources required.

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

Data Management in the Worldwide Sensor Web - Balazinska,Magdalena; Deshpande, Amol; Franklin,Michael J.; Gibbons,Phillip B.; Gray,Jim; Hansen,Mark; Liebhold,Michael; Nath,Suman; Szalay,Alexander; Tao,Vincent (IEEE Pervasive Computing, 2007)
Advances in hardware and miniaturization technologies have led to a rapid increase in the number of large-scale sensor network deployments around the world, bringing us closer to the vision of a worldwide sensor web. Exploiting the sensor web to its full potential, however, raises several hard data management challenges. Addressing these challenges requires a concerted multidisciplinary effort encompassing many computer science fields. This article outlines some of the key data management challenges of a worldwide sensor web. It also presents recent advances in data management research that aim to address these challenges. Hopefully, the scientific, ubiquitous computing, and sensor network communities will adopt some of these solutions for managing their data. The article also attempts to bring many of the remaining open issues to the attention of the database community. This article is part of a special issue on Building a Sensor-Rich World.
Keywords: data modeling; data streams; data uncertainty; distributed systems; interoperability; sensor networks

Deductive Databases - Grant,John; Minker, Jack (Wiley Encyclopedia of Computer Science and EngineeringWiley Encyclopedia of Computer Science and Engineering, 2007)
Keywords: answer set semantics; Datalog; deductive database; disjunctive database; extended database

Description of Computer Science Higher Education in Sub-Saharan Africa: Initial Explorations - Marshini Chetty; Buckhalter, Celeste; Best, Michael L.; Grinter, Rebecca E.; Guzdial, Mark (2007)
Many countries in Sub-Saharan Africa (SSA) are in need oftechnology innovators who are equipped to leverage technologies in locally relevant domains such as health, government and education. To create skilled graduates who can build and shape locally relevant technologies, higher education institutes in Africa must have Computer Science (CS) education programs that meet local needs, for example, to satisfy the demand for entrepreneurs to build industry and strengthen an economy. This paper characterizes the current state of CS education in SSA in order to identify opportunities for addressing education challenges and to make suggestions that may improve the Information and Communication Technology (ICT) infrastructure in this region. We present the results of a survey of CS educators in SSA institutions of higher education, which was aimed at exploring the issues they face. In addition to the continued chronic under-funding of SSA education, we found that universities in SSA have smaller departments, less focus on Human Computer Interaction (HCI) and offer a variety of courses aside from undergraduate Bachelors degrees. We discuss directions to improve CS curricula through investing in locally tailored courses and changing perceptions of the value of SSA CS higher education programs, standards and educators. Further, we reflect on the challenges of conducting research on SSA. We conclude that further research in this area is needed to build on the ideas we offer here to continue to strengthen CS higher education in SSA.
Keywords: Sub-Saharan Africa; Undergraduate computing education

Development of in-mold assembly process for realizing mesoscale revolute joints - Ananthanarayanan,A.; Gupta,S.K.; Bruck,H. A.; Yu,Z.; Rajurkar,K. P. (Transactions of North American Manufacturing Research Institution of SME, 2007)
In-mold Assembly process at the mesoscalepresents several manufacturing challenges. Results reported in this paper demonstrate the technical feasibility of creating rigid body mesoscale revolute joints using In-Mold Assembly process. The following new results are reported in this paper. First, we describe a mold design with varying cavity shape to perform In-Mold Assembly. This mold design uses an accurate mold piece positioning method to avoid damage to delicate mesoscale parts during the cavity change step. Second, we describe a mold insert fabrication process for making mold inserts with the desired surface characteristics for mesoscale molding. Finally, we describe methods to limit the adhesion at the interfaces and hence create articulated revolute joint. Using the advances reported in this paper we have successfully molded a mesoscale revolute joint. To the best of our knowledge, this is the first demonstration of In-Mold Assembly process using a varying cavity shape mold to create a mesoscale revolute joint.

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.

Distributed ranked search - Gopalakrishnan,V.; Morselli,R.; Bhattacharjee, Bobby; Keleher,P.; Srinivasan, Aravind (High 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.

A dual-view approach to interactive network visualization - Namata,Galileo Mark; Staats,Brian; Getoor, Lise; Shneiderman, Ben (Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007)
Visualizing network data, from tree structures to arbitrarily connected graphs, is a difficult problem in information visualization. A large part of the problem is that in network data, users not only have to visualize the attributes specific to each data item, but also the links specifying how those items are connected to each other. Past approaches to resolving these difficulties focus on zooming, clustering, filtering and applying various methods of laying out nodes and edges. Such approaches, however, focus only on optimizing a network visualization in a single view, limiting the amount of information that can be shown and explored in parallel. Moreover, past approaches do not allow users to cross reference different subsets or aspects of large, complex networks. In this paper, we propose an approach to these limitations using multiple coordinated views of a given network. To illustrate our approach, we implement a tool called DualNet and evaluate the tool with a case study using an email communication network. We show how using multiple coordinated views improves navigation and provides insight into large networks with multiple node and link properties and types.
Keywords: coordinated views; Information Visualization; interactive graph visualization; social networks

Ecotopia: An Ecological Framework for Change Management in Distributed Systems - Tudor Dumitras; Roşu, Daniela; Dan, Asit; Narasimhan, Priya (Architecting Dependable Systems IV, 2007)
Dynamic change management in an autonomic, service-oriented infrastructure is likely to disrupt the critical services delivered by the infrastructure. Furthermore, change management must accommodate complex real-world systems, where dependability and performance objectives are managed across multiple distributed service components and have specific criticality/value models. In this paper, we present Ecotopia, a framework for change management in complex service-oriented architectures (SOA) that is ecological in its intent: it schedules change operations with the goal of minimizing the service-delivery disruptions by accounting for their impact on the SOA environment. The change-planning functionality of Ecotopia is split between multiple objective-advisors and a system-level change-orchestrator component. The objective advisors assess the change-impact on service delivery by estimating the expected values of the Key Performance Indicators (KPIs), during and after change. The orchestrator uses the KPI estimations to assess the per-objective and overall business-value changes over a long time-horizon and to identify the scheduling plan that maximizes the overall business value. Ecotopia handles both external change requests, like software upgrades, and internal changes requests, like fault-recovery actions. We evaluate the Ecotopia framework using two realistic change-management scenarios in distributed enterprise systems.
Keywords: Autonomic Computing; Dynamic Change Management; Fault-Tolerant Architecture; Operating systems; Performability; Service Orchestration; software engineering

Efficient Conversion of X.Y Surround Sound Content to Binaural Head-Tracked Form for HRTF-Enabled Playback - Zotkin,Dmitry N; Duraiswami, Ramani; Gumerov, Nail A. (IEEE International Conference on Acoustics, Speech and Signal Processing, 2007. ICASSP 2007, 2007)
Binaural presentation of X.Y sound is usually performed using virtual audio principles - that is, by attempting to virtually reproduce the setup of the X+Y loudspeakers in the reference room configuration. The computational cost of such playback is linear in the number of channels in the X.Y setup. We present a novel scheme that computes, offline, a spatio-temporal representation of the sound field in the listening area and store it as a multipole expansion. During head-tracked playback, the binaural signal is obtained by evaluating the multipole expansion at the ear position corresponding to the current user pose, resulting in a fixed playback cost. The representation is further extended to incorporate individualized HRTFs at no additional cost. Simulation results are presented.
Keywords: Acoustic fields; Acoustic scattering; acoustic signal processing; audio acoustics; Audio systems; binaural head-tracked; binaural presentation; Computational efficiency; Costs; Ear; head-related transfer function; Headphones; HRTF-enabled playback; Loudspeakers; Music; reverberation; sound field; spatio-temporal representation; surround sound; surround sound content; Transfer functions; virtual audio principles

Efficient parallel memory organization for turbo decoders - Salmela,P.; Gu,R.; Bhattacharyya, Shuvra S.; Takala,J. (Red, 2007)

Efficient signature schemes with tight reductions to the Diffie-Hellman problems - Goh,E. J; Jarecki,S.; Katz, Jonathan; Wang,N. (Journal of Cryptology, 2007)
We propose and analyze two efficient signature schemes whose security is tightly related to the Diffie-Hellman problems in the random oracle model. The security of our first scheme relies on the hardness of the computational Diffie-Hellman problem; the security of our second scheme - which is more efficient than the first-is based on the hardness of the decisional Diffie-Hellman problem, a stronger assumption. Given the current state of the art, it is as difficult to solve the Diffie-Hellman problems as it is to solve the discrete logarithm problem in many groups of cryptographic interest. Thus, the signature schemes shown here can currently offer substantially better efficiency (for a given level of provable security) than existing schemes based on the discrete logarithm assumption. The techniques we introduce can also be applied in a wide variety of settings to yield more efficient cryptographic schemes (based on various number-theoretic assumptions) with tight security reductions.

An empirical study of filesystem activity following a SSH compromise - Molina,J.; Gordon,J.; Chorin,X.; Michel Cukier (2007)
Monitoring filesystem data is a common method used to detect attacks. Once a computer is compromised, attackers will likely alter files, add new files or delete existing files. The changes that attackers make may target any part of the filesystem, including metadata along with files (e.g., permissions, ownerships and inodes). In this paper, we describe an empirical study that focused on SSH compromised attacks. First statistical data on the number of files targeted and the associated activity (e.g., read, write, delete, ownership and rights) is reported. Then, we refine the analysis to identify and understand patterns in the attack activity.
Keywords: attack activity; filesystem activity; filesystem data monitoring; intrusion detection systems evaluation; meta data; metadata; security of data; SSH compromised attacks

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)

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

Evaluation of Traditional and Shock-Confining LES Filters using DNS Data of Compressible Turbulence - Taylor,E. M; Grube,N. E; Martin, M.P (Proceedings of 18th AIAA Computational Fluid Dynamics Conference, 2007)
Uniformly high-order-accurate filtering of fluid flow properties in the presence of shocksand shocklets is theoretically susceptible to the same problem that afflicts uniformly high- order-accurate numerical methods for approximating the convective terms of the Navier- Stokes equations: the introduction of new, non-physical extrema near discontinuities. Ex- tensive investigations have been conducted into myriad types of shock-capturing methods, which adaptively decrease their order of accuracy within shock-containing regions in order to maintain accuracy and stability over time. Inspired by such work, Grube et al. (AIAA 2007-4198) have proposed the conceptually similar idea of “shock-confining” filtering (SCF) for compressible large-eddy simulations (LES), in which a class of linear filters is subject to adaptive adjustments based on smoothness information provided by a weighted essen- tially non-oscillatory (WENO) method. In the current work, we utilize the turbulent flow fields produced by direct numerical simulations (DNS) of shock/isotropic-turbulence inter- action to perform preliminary a priori testing of these shock-confining filters against the corresponding linear filters. Although additional study, both a priori and a posteriori, is required to verify the necessity and suitability of SCF for LES, we conclude that linear filtering can indeed create serious qualitative discrepancies in global flow characteristics, discrepancies that are avoided by the use of SCF.

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.

Evolution of genes and genomes on the Drosophila phylogeny - Clark, A.G.; Eisen,M. B; Smith,D. R; Bergman, C.M.; Oliver, B.; Markow, T.A.; Kaufman, T.C.; Kellis, M.; Gelbart, W.; Iyer, V.N.; others (Nature, 2007)

Exploiting aspectual features and connecting words for summarization-inspired temporal-relation extraction - Dorr, Bonnie J; Gaasterland,Terry (Information Processing & Management, 2007)
This paper presents a model that incorporates contemporary theories of tense and aspect and develops a new framework for extracting temporal relations between two sentence-internal events, given their tense, aspect, and a temporal connecting word relating the two events. A linguistic constraint on event combination has been implemented to detect incorrect parser analyses and potentially apply syntactic reanalysis or semantic reinterpretation—in preparation for subsequent processing for multi-document summarization. An important contribution of this work is the extension of two different existing theoretical frameworks—Hornstein’s 1990 theory of tense analysis and Allen’s 1984 theory on event ordering—and the combination of both into a unified system for representing and constraining combinations of different event types (points, closed intervals, and open-ended intervals). We show that our theoretical results have been verified in a large-scale corpus analysis. The framework is designed to inform a temporally motivated sentence-ordering module in an implemented multi-document summarization system.
Keywords: Parsing and corpus analysis; Summarization; temporal ordering; Temporal-relation extraction; Tense, aspect and connecting words

Extended wavelets for multiple measures - Deligiannakis,Antonios; Garofalakis,Minos; Roussopoulos, Nick (ACM Transactions on Database SystemsACM Trans. Database Syst., 2007)

Fast computation of sums of Gaussians - Raykar,V.C.; Duraiswami, Ramani; Gumerov, Nail A. (Journal of Machine Learning Research (submitted), 2007)
Evaluating sums of multivariate Gaussian kernels is a key computational task in manyproblems in computational statistics and machine learning. The computational cost of the direct evaluation of such sums scales as the product of the number of kernel functions and the evaluation points. The fast Gauss transform proposed by Greengard and Strain (1991) is a ǫ-exact approximation algorithm that reduces the computational complexity of the evaluation of the sum of N Gaussians at M points in d dimensions from O(MN) to O(M + N). However, the constant factor in O(M + N) grows exponentially with increasing dimensionality d, which makes the algorithm impractical for dimensions greater than three. In this paper we present a new algorithm where the constant factor is reduced to asymptotically polynomial order. The reduction is based on a new multivariate Taylor’s series expansion (which can act both as a local as well as a far field expansion) scheme combined with the efficient space subdivision using the k-center algorithm. The proposed method differs from the original fast Gauss transform in terms of a different factorization, efficient space subdivision, and the use of different error bounds for each source point. Algorithm details, error bounds, a procedure to choose the parameters, and numerical experiments are presented. We also compare our algorithm with the dual-tree algorithm of Gray and Moore (2003). As an example we show how the proposed method can be used for very fast ǫ-exact multivariate kernel density estimation.

Fast Evaluation of the Room Transfer Function Using Multipole Expansion - Duraiswami, Ramani; Zotkin,Dmitry N; Gumerov, Nail A. (Audio, Speech, and Language Processing, IEEE Transactions on, 2007)
Reverberation in rooms is often simulated with the image method due to Allen and Berkley (1979). This method has an asymptotic complexity that is cubic in terms of the simulated reverberation length. When employed in the frequency domain, it is relatively computationally expensive if there are many receivers in the room or if the source or receiver positions are changing with time. The computational complexity of the image method is due to the repeated summation of the fields generated by a large number of image sources. In this paper, a fast method to perform such summations is presented. The method is based on multipole expansion of the monopole source potential. For offline computation of the room transfer function for N image sources and M receiver points, use of the Allen-Berkley algorithm requires O(NM) operations, whereas use of the proposed method requires only O(N+M) operations, resulting in significantly faster computation of reverberant sound fields. The proposed method also has a considerable speed advantage in situations where the room transfer function must be rapidly updated online in response to source/receiver location changes. Simulation results are presented, and algorithm accuracy, speed, and implementation details are discussed. For problems that require frequency-domain computations, the algorithm is found to generate sound fields identical to the ones obtained with the frequency-domain version of the Allen-Berkley algorithm at a fraction of computational cost
Keywords: acoustics; computational; algorithm; frequency-domain; Alien-Berkley; analysis; reverberation; complexity; frequency-domain; computations; image; expansion; receivers; reverberant; field; architectural; fields; reverberation; room; function; acoustic; method; image; potential; multipole; sound; source; sources; monopole; transfer

Fast Multipole Accelerated Boundary Elements for Numerical Computation of the Head Related Transfer Function - Gumerov, Nail A.; Duraiswami, Ramani; Zotkin,Dmitry N (IEEE International Conference on Acoustics, Speech and Signal Processing, 2007. ICASSP 2007, 2007)
The numerical computation of head related transfer functions has been attempted by a number of researchers. However, the cost of the computations has meant that usually only low frequencies can be computed and further the computations take inordinately long times. Because of this, comparisons of the computations with measurements are also difficult. We present a fast multipole based iterative preconditioned Krylov solution of a boundary element formulation of the problem and use a new formulation that enables the reciprocity technique to be accurately employed. This allows the calculation to proceed for higher frequencies and larger discretizations. Preliminary results of the computations and of comparisons with measured HRTFs are presented.
Keywords: Acceleration; Acoustic measurements; Acoustic scattering; audio signal processing; boundary element formulation; Boundary element method; Boundary element methods; boundary-elements methods; Costs; Ear; Fast Multipole Method; Frequency; Head related transfer function; HUMANS; Irrigation; iterative methods; multipole accelerated boundary elements; multipole based iterative preconditioned Krylov solution; numerical computation; Reciprocity; Transfer functions

Features generated for computational splice-site prediction correspond to functional elements - Dogan,Rezarta I.; Getoor,Lise; Wilbur,W. John; Mount, Stephen M. (BMC Bioinformatics, 2007)
Accurate selection of splice sites during the splicing of precursors to messenger RNA requires both relatively well-characterized signals at the splice sites and auxiliary signals in the adjacent exons and introns. We previously described a feature generation algorithm (FGA) that is capable of achieving high classification accuracy on human 3' splice sites. In this paper, we extend the splice-site prediction to 5' splice sites and explore the generated features for biologically meaningful splicing signals.

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.

GeoDDupe: A Novel Interface for Interactive Entity Resolution in Geospatial Data - Kang,Hyunmo; Sehgal,V.; Getoor, Lise (Information Visualization, 2007. IV '07. 11th International Conference, 2007)
Due to the growing interest in geospatial data mining and analysis, data cleaning and integration in geospatial data is becoming an important issue. Geospatial entity resolution is the process of reconciling multiple location references to the same real world location within a single data source (deduplication) or across multiple data sources (integration). In this paper, we introduce an interactive tool called GeoDDupe which effectively combines automatic data mining algorithms for geospatial entity resolution with a novel network visualization supporting users' resolution analysis and decisions. We illustrate the GeoDDupe interface with an example geospatial dataset and show how users can efficiently and accurately resolve location entities. Finally, the case study with two real-world geospatial datasets demonstrates the potential of GeoDDupe.
Keywords: algorithms; data; cleaning; geospatial; data; entity; GeoDDupe; automatic; interfaces; mining; mining; geography; user; mining; geospatial; resolution; interactive; tool; network; visualization; data

Geometrical algorithms for automated design of side actions in injection moulding of complex parts - Banerjee,Ashis Gopal; Gupta, Satyandra K. (Computer-Aided Design, 2007)
This paper describes algorithms for generating shapes of side actions to minimize a customizable injection moulding cost function. Given a set of undercut facets on a polyhedral part and the main mold opening directions, our approach works in the following manner: first, we compute candidate retraction space for every undercut facet. This space represents the set of candidate translation vectors that can be used by the side action to completely disengage from the undercut facet. As the next step, we generate a discrete set of feasible, nondominated retractions. Then we group the undercut facets into undercut regions by performing state space search over such retractions. This search step is performed by minimizing the given moulding cost function. After identifying the undercut regions, we generate the shapes of individual side actions. We believe that the results presented in this paper will provide the foundations for developing fully automated software for designing side actions.
Keywords: Configuration spaces; Geometrical reasoning; Mould design

Geometry and Charge State of Mixed‐Ligand Au13 Nanoclusters - Frenkel, A. I.; Menard, L. D.; Northrup, P.; Rodriguez, J. A.; Zypman, F.; Dana Dachman-Soled; Gao, S.-P.; Xu, H.; Yang, J. C.; Nuzzo, R. G. (X-RAY ABSORPTION FINE STRUCTURE - XAFS13: 13th International Conference, 2007)
The integration of synthetic, experimental and theoretical tools into a self‐consistent data analysis methodology allowed us to develop unique new levels of detail in nanoparticle characterization. We describe our methods using an example of Au 13 monolayer‐protected clusters (MPCs), synthesized by ligand exchange methods. The combination of atom counting methods of scanning transmission electron microscopy and Au L3‐edge EXAFS allowed us to characterize these clusters as icosahedral, with surface strain reduced from 5% (as in ideal, regular icosahedra) to 3%, due to the interaction with ligands. Charge transfer from Au to the thiol and phosphine ligands was evidenced by S and P K‐edge XANES. A comparison of total energies of bare clusters of different geometries was performed by equivalent crystal theory calculations.
Keywords: Atom surface interactions; Charge transfer; Data analysis; Extended X-ray absorption fine structure spectroscopy; Gold; nanoparticles; Scanning transmission electron microscopy; Surface strains; Total energy calculations; X-ray absorption near edge structure

Graphical Models in a Nutshell - Koller,D.; Friedman,N.; Getoor, Lise; Taskar,B. (Introduction to Statistical Relational LearningIntroduction to Statistical Relational Learning, 2007)

HCI4D: hci challenges in the global south - Marshini Chetty; Grinter, Rebecca E. (SIGCHI EA '07, 2007)
While researchers have designed user-centered systems for the Global South, fewer have discussed the unique challenges facing HCI projects. In this paper, we describe methodological and practical challenges for HCI research and practice in the Global South.
Keywords: global south; hci; methodologies

High frequency acoustic simulations via FMM accelerated BEM - Gumerov, Nail A.; Duraiswami, Ramani (19th Internal congress on acoustics, 2007)
High frequency simulations of acoustics are among the most expensive problems to simulate. Inpractice 6 to 10 points per wavelength are required. Since the wavenumber k is inversely proportional to wavelength, if a numerical method is a surface based method (such as the BEM), then problem size scales as O(k2D2), where D is the size of the domain. Dense matrices appear and typical iter- ative solution can be achieved for O(k4D4) memory and O(k4D4) per iteration cost. We employ an algorithm based on the fast multipole method (FMM) using coaxial and diagonal translation operators based on the frequency of simulation to reduce the memory requirements and per iteration cost to O(k2D2 log kD) for larger kD (kD ~250). The number of iterations needed depend upon the condition of the matrix, and preconditioning chosen. Preconditioned Krylov methods such as the flexible gen- eralized minimum residual method (FGMRES), with preconditioning based upon a lower accuracy FMM, usually ensure a convergent iteration. Example calculations are presented.

HIV risk behaviors among female IDUs in developing and transitional countries - Charles,C.; Des Jarlais Don,P. T; Gerry,S. (BMC Public Health, 2007)

How Smart Homes Learn: The Evolution of the Networked Home and Household - Marshini Chetty; Sung, Ja-Young; Grinter, Rebecca E. (UbiComp 2007: Ubiquitous Computing, 2007)
Despite a growing desire to create smart homes, we know little about how networked technologies interact with a house’s infrastructure. In this paper, we begin to close this gap by presenting findings from a study that examined the relationship between home networking and the house itself—and the work that results for householders as a consequence of this interaction. We discuss four themes that emerged: an ambiguity in understanding the virtual boundaries created by wireless networks, the home network control paradox, a new home network access paradox, and the relationship between increased responsibilities and the possibilities of wireless networking.
Keywords: Computer Communication Networks; computers and society; home networking; Information Systems Applications (incl.Internet); infrastructure; smart home; software engineering; Systems and Data Security; User Interfaces and Human Computer Interaction

How to lease the internet in your spare time - Feamster, Nick; Gao,Lixin; Rexford,Jennifer (SIGCOMM Comput. Commun. Rev., 2007)
Today's Internet Service Providers (ISPs) serve two roles: managing their network infrastructure and providing (arguably limited) services to end users. We argue that coupling these roles impedes the deployment of new protocols and architectures, and that the future Internet should support two separate entities: infrastructure providers (who manage the physical infrastructure) and service providers (who deploy network protocols and offer end-to-end services). We present a high-level design for Cabo, an architecture that enables this separation; we also describe challenges associated with realizing this architecture.

Human Appearance Change Detection - Ghanem,N.M.; Davis, Larry S. (Image Analysis and Processing, 2007. ICIAP 2007. 14th International Conference on, 2007)
We present a machine learning approach to detect changes in human appearance between instances of the same person that may be taken with different cameras, but over short periods of time. For each video sequence of the person, we approximately align each frame in the sequence and then generate a set of features that captures the differences between the two sequences. The features are the occupancy difference map, the codeword frequency difference map (based on a vector quantization of the set of colors and frequencies) at each aligned pixel and the histogram intersection map. A boosting technique is then applied to learn the most discriminative set of features, and these features are then used to train a support vector machine classifier to recognize significant appearance changes. We apply our approach to the problem of left package detection. We train the classifiers on a laboratory database of videos in which people are seen with and without common articles that people carry - backpacks and suitcases. We test the approach on some real airport video sequences. Moving to the real world videos requires addressing additional problems, including the view selection problem and the frame selection problem.
Keywords: (artificial; appearance; approach; occupancy; change; changes; classification; support; classifier; vector; detection; image; detection; machine; difference; Frequency; intelligence); pattern; intersection; learning; machine; machines; vector; map; histogram; map; human; map; support; package; quantisation; video; quantization; video; recognition; boosting; recognition; image; sequence; left; sequences; image; sequences; learning; surveillance; technique; codeword; vector

Improving Embedding Payload in Binary Imageswith "Super-Pixels" - Gou,Hongmei; M. Wu (Image Processing, 2007. ICIP 2007. IEEE International Conference on, 2007)
Hiding data in binary images can facilitate authentication of important documents in the digital domain, which generally requires a high embedding payload. Recently, a steganography framework known as the wet paper coding has been employed in binary image watermarking to achieve high embedding payload. In this paper, we introduce a new concept of super-pixels, and study how to incorporate them in the framework of wet paper coding to further improve the embedding payload in binary images. Using binary text documents as an example, we demonstrate the effectiveness of the proposed super-pixel technique.
Keywords: analysis; watermarking; analysis; wet; authentication; embedding; authentication; text; binary; coding; cryptography; data; coding; message; encapsulation; document; hiding; document; image; paper; payload; steganography; text; processing; image; watermarking; data

Incorporating manufacturability considerations during design of injection molded multi-material objects - Banerjee,Ashis; Li,Xuejun; Fowler,Greg; Gupta, Satyandra K. (Research in Engineering Design, 2007)
The presence of an already molded component during the second and subsequent molding stages makes multi-material injection molding different from traditional injection molding process. Therefore, designing multi-material molded objects requires addressing many additional manufacturability considerations. In this paper, we first present an approach to systematically identifying potential manufacturability problems that are unique to the multi-material molding processes and design rules to avoid these problems. Then we present a comprehensive manufacturability analysis approach that incorporates both the traditional single material molding rules as well as the specific rules that have been identified for multi-material molding. Our analysis shows that sometimes the traditional rules need to be suppressed or modified. Lastly, for each of the new manufacturability problem, this paper describes algorithms for automatically detecting potential occurrences and generating redesign suggestions. These algorithms have been implemented in a computer-aided manufacturability analysis system. The approach presented in this paper is applicable to multi-shot and over molding processes. We expect that the manufacturability analysis techniques presented in this paper will help in decreasing the product development time for the injection molded multi-material objects.
Keywords: engineering

Inferring organizational titles in online communication - Namata,G.; Getoor, Lise; Diehl,C. (Statistical Network Analysis: Models, Issues, and New Directions, 2007)
There is increasing interest in the storage, retrieval, and analysis of email communications. One active area of research focuses on the inference of properties of the underlying social network giving rise to the email communications[1,2]. Email communication between individuals implies some type of relationship, whether it is formal, such as a manager-employee relationship, or informal, such as friendship relationships. Understanding the nature of these observed relationships can be problematic given there is a shared context among the individuals that isn’t necessarily communicated. This provides a challenge for analysts that wish to explore and understand email archives for legal or historical research.

Introduction to Statistical Relational Learning - Getoor, Lise (MIT Press, 2007)
Handling inherent uncertainty and exploiting compositional structure are fundamental to understanding and designing large-scale systems. Statistical relational learning builds on ideas from probability theory and statistics to address uncertainty while incorporating tools from logic, databases and programming languages to represent structure. In Introduction to Statistical Relational Learning, leading researchers in this emerging area of machine learning describe current formalisms, models, and algorithms that enable effective and robust reasoning about richly structured systems and data. The early chapters provide tutorials for material used in later chapters, offering introductions to representation, inference and learning in graphical models, and logic. The book then describes object-oriented approaches, including probabilistic relational models, relational Markov networks, and probabilistic entity-relationship models as well as logic-based formalisms including Bayesian logic programs, Markov logic, and stochastic logic programs. Later chapters discuss such topics as probabilistic models with unknown objects, relational dependency networks, reinforcement learning in relational domains, and information extraction. By presenting a variety of approaches, the book highlights commonalities and clarifies important differences among proposed approaches and, along the way, identifies important representational and algorithmic issues. Numerous applications are provided throughout.Lise Getoor is Assistant Professor in the Department of Computer Science at the University of Maryland. Ben Taskar is Assistant Professor in the Computer and Information Science Department at the University of Pennsylvania.
Keywords: Business & Economics / Statistics; Computer algorithms; Computers / Database Management / General; Computers / Logic Design; Computers / Machine Theory; Computers / Programming / Algorithms; Education / Statistics; machine learning; Machine learning - Statistical methods; Machine learning/ Statistical methods; Relational databases

Introduction to Statistical Relational Learning - Getoor,Lise; Taskar,Ben (MIT Press, 2007)
Handling inherent uncertainty and exploiting compositional structure are fundamental to understanding and designing large-scale systems. Statistical relational learning builds on ideas from probability theory and statistics to address uncertainty while incorporating tools from logic, databases and programming languages to represent structure. In Introduction to Statistical Relational Learning, leading researchers in this emerging area of machine learning describe current formalisms, models, and algorithms that enable effective and robust reasoning about richly structured systems and data. The early chapters provide tutorials for material used in later chapters, offering introductions to representation, inference and learning in graphical models, and logic. The book then describes object-oriented approaches, including probabilistic relational models, relational Markov networks, and probabilistic entity-relationship models as well as logic-based formalisms including Bayesian logic programs, Markov logic, and stochastic logic programs. Later chapters discuss such topics as probabilistic models with unknown objects, relational dependency networks, reinforcement learning in relational domains, and information extraction. By presenting a variety of approaches, the book highlights commonalities and clarifies important differences among proposed approaches and, along the way, identifies important representational and algorithmic issues. Numerous applications are provided throughout.Lise Getoor is Assistant Professor in the Department of Computer Science at the University of Maryland. Ben Taskar is Assistant Professor in the Computer and Information Science Department at the University of Pennsylvania.
Keywords: Computers / Logic Design; Computers / Machine Theory; Education / Statistics

Investigation of Revolute Joint Clearances Created by an In-Mold Assembly Process - Ananthanarayanan,A.; Thamire,C.; Gupta,S.K. (2007)
Revolute joints are frequently used in articulated structures. Traditionally, such a joint is formed by assembling two components. As an alternative, revolute joints can be created inside the mold using an in-mold assembly process. This process eliminates the need for post-molding assembly, thus significantly reducing the cycle time and part count. The functional performance of a revolute joint depends on the clearance in the joint. The clearance in turn depends on the part shrinkage and the mold deformation during the molding process. The presence of a polymer part during the second molding stage makes an in-mold assembly process significantly different from the traditional molding process due to the difference in heat transfer and deformation characteristics. This paper presents experimental data and a preliminary model to explain the differences in clearance produced by an aluminum mold and an Aluminum mold with an Acrylonitrile butadiene styrene (ABS) insert. Our data indicates that there is a significant difference between the clearances observed from these two different types of molds. We believe that clearances produced depend strongly on the thermal history of the parts.
Keywords: acrylonitrile butadiene styrene insert; aluminum mold; assembling; couplings; cycle time reduction; heat transfer; injection moulding; inmold assembly process; mold deformation; molding process; moulding equipment; part count reduction; plastics industry; revolute joint clearances

Joint Acoustic-Video Fingerprinting of Vehicles, Part II - Cevher, V.; Guo, F.; Sankaranarayanan,A. C; Chellapa, Rama (Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, 2007)
In this second paper, we first show how to estimate the wheelbase length of a vehicle using line metrology in video. We then address the vehicle fingerprinting problem using vehicle silhouettes and color invariants. We combine the acoustic metrology and classification results discussed in Part I with the video results to improve estimation performance and robustness. The acoustic video fusion is achieved in a Bayesian framework by assuming conditional independence of the observations of each modality. For the metrology density functions, Laplacian approximations are used for computational efficiency. Experimental results are given using field data
Keywords: acoustic-video; analysis; video; approximations; acoustic; Bayesian; colour; density; efficiency; joint; estimation; Bayes; fingerprinting; metrology; framework; Laplacian; functions; performance; fusion; color; identification; image; invariants; computational; methods; acoustic; metrology; acoustic; processing; processing; fingerprint; signal; video

A Language for Human Action - Guerra-Filho,G.; Aloimonos, J. (Computer, 2007)
Human-centered computing (HCC) involves conforming computer technology to humans while naturally achieving human-machine interaction. In a human-centered system, the interaction focuses on human requirements, capabilities, and limitations. These anthropocentric systems also focus on the consideration of human sensory-motor skills in a wide range of activities. This ensures that the interface between artificial agents and human users accounts for perception and action in a novel interaction paradigm. In turn, this leads to behavior understanding through cognitive models that allow content description and, ultimately, the integration of real and virtual worlds. Our work focuses on building a language that maps to the lower-level sensory and motor languages and to the higher-level natural language. An empirically demonstrated human activity language provides sensory-motor-grounded representations for understanding human actions. A linguistic framework allows the analysis and synthesis of these actions.
Keywords: anthropocentric system; artificial agent; Artificial intelligence; cognitive model; Concrete; Databases; human action; human activity language; Human computer interaction; human factors; human sensory-motor skill; human-centered computing; human-machine interaction; HUMANS; Intelligent sensors; linguistic framework; linguistics; Mirrors; Morphology; natural language; natural languages; Neurons; Power system modeling; user interface; User interfaces

Leveraging data and structure in ontology integration - Udrea,Octavian; Getoor, Lise; Miller,Renée J. (Proceedings of the 2007 ACM SIGMOD international conference on Management of data, 2007)
There is a great deal of research on ontology integration which makes use of rich logical constraints to reason about the structural and logical alignment of ontologies. There is also considerable work on matching data instances from heterogeneous schema or ontologies. However, little work exploits the fact that ontologies include both data and structure. We aim to close this gap by presenting a new algorithm (ILIADS) that tightly integrates both data matching and logical reasoning to achieve better matching of ontologies. We evaluate our algorithm on a set of 30 pairs of OWL Lite ontologies with the schema and data matchings found by human reviewers. We compare against two systems - the ontology matching tool FCA-merge [28] and the schema matching tool COMA++ [1]. ILIADS shows an average improvement of 25% in quality over FCA-merge and a 11% improvement in recall over COMA++.
Keywords: Data integration; logical inference; ontology alignment; schema mapping; statistical inference

Link-based Classification - Sen,Prithviraj; Getoor, Lise (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2007)
Over the past few years, a number of approximate inference algorithms fornetworked data have been put forth. We empirically compare the performance of three of the popular algorithms: loopy belief propagation, mean field relaxation labeling and iterative classification. We rate each algorithm in terms of its robustness to noise, both in attribute values and correlations across links. We also compare them across varying types of correlations across links.
Keywords: Technical Report

Local strategy learning in networked multi-agent team formation - Bulka,Blazej; Gaston,Matthew; desJardins, Marie (Autonomous Agents and Multi-Agent Systems, 2007)
Networked multi-agent systems are comprised of many autonomous yet interdependent agents situated in a virtual social network. Two examples of such systems are supply chain networks and sensor networks. A common challenge in many networked multi-agent systems is decentralized team formation among the spatially and logically extended agents. Even in cooperative multi-agent systems, efficient team formation is made difficult by the limited local information available to the individual agents. We present a model of distributed multi-agent team formation in networked multi-agent systems, describe a policy learning framework for joining teams based on local information, and give empirical results on improving team formation performance. In particular, we show that local policy learning from limited information leads to a significant increase in organizational team formation performance compared to a random policy.

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

Measurement and analysis of online social networks - Mislove,Alan; Marcon,Massimiliano; Gummadi,Krishna P.; Druschel,Peter; Bhattacharjee, Bobby (Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, 2007)
Online social networking sites like Orkut, YouTube, and Flickr are among the most popular sites on the Internet. Users of these sites form a social network, which provides a powerful means of sharing, organizing, and finding content and contacts. The popularity of these sites provides an opportunity to study the characteristics of online social network graphs at large scale. Understanding these graphs is important, both to improve current systems and to design new applications of online social networks. This paper presents a large-scale measurement study and analysis of the structure of multiple online social networks. We examine data gathered from four popular online social networks: Flickr, YouTube, LiveJournal, and Orkut. We crawled the publicly accessible user links on each site, obtaining a large portion of each social network's graph. Our data set contains over 11.3 million users and 328 million links. We believe that this is the first study to examine multiple online social networks at scale. Our results confirm the power-law, small-world, and scale-free properties of online social networks. We observe that the indegree of user nodes tends to match the outdegree; that the networks contain a densely connected core of high-degree nodes; and that this core links small groups of strongly clustered, low-degree nodes at the fringes of the network. Finally, we discuss the implications of these structural properties for the design of social network based systems.
Keywords: analysis; measurement; social networks

Measuring the Contributions of Routing Dynamics to Prolonged End-to-End Internet Path Failures - Wang,Feng; Feamster, Nick; Gao,Lixin (Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE, 2007)
This paper studies the contributions of routing dynamics to the duration of long-lived end-to-end Internet path failures. Studies have shown that end-to-end Internet failures (periods of prolonged packet loss) are widespread. These failures are typically attributed to either congestion or routing dynamics. Unfortunately, the extent to which congestion and routing dynamics contribute to long-lasting path failures, and the effect of routing dynamics on end-to-end performance, are not well understood. This paper uses a joint analysis of active measurements and routing data to characterize end-to-end failures observed over one month on a topologically diverse Internet testbed. We find that routing dynamics coincide with most prolonged end-to-end failures, suggesting that routing dynamics contribute significantly to the duration of these failures. We also find that most long-lived end-to-end path failures that coincide with routing dynamics are caused by BGP convergence or instability. Our results provide new insights into the effects of routing instability on end-to-end Internet path performance.
Keywords: diverse Internet topological testbed; Internet; prolonged end-to-end Internet path failure; routing dynamics; telecommunication network reliability; telecommunication network routing; telecommunication network topology

Middleware for programming NVIDIA GPUs from Fortran 9x - Gumerov, Nail A.; Duraiswami, Ramani; Dorland,W. (Supercomputing, 2007)

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)

Noise Features for Image Tampering Detection and Steganalysis - Gou,Hongmei; Swaminathan,A.; M. Wu (Image Processing, 2007. ICIP 2007. IEEE International Conference on, 2007)
With increasing availability of low-cost image editing softwares, the authenticity of digital images can no longer be taken for granted. Digital images have also been used as cover data for transmitting secret information in the field of steganography. In this paper, we introduce a new set of features for multimedia forensics to determine if a digital image is an authentic camera output or if it has been tampered or embedded with hidden data. We perform such image forensic analysis employing three sets of statistical noise features, including those from denoising operations, wavelet analysis, and neighborhood prediction. Our experimental results demonstrate that the proposed method can effectively distinguish digital images from their tampered or stego versions.
Keywords: analysis; cryptography; data; analysis; image; analysis; wavelet; authenticity; hidden; computing; statistical; data; image; denoising; denoising; multimedia; detection; low-cost; editing; encapsulation; feature; extraction; image; features; steganalysis; wavelet; forensic; forensics; neighborhood; image; NOISE; operations; digital; prediction; statistical; softwares; multimedia; tampering; transforms

Numerical Analysis of Plasmon Resonances in Nanoparticles Based on Fast Multipole Method - Zhang,Zhenyu; Mayergoyz, Issak D; Gumerov, Nail A.; Duraiswami, Ramani (Magnetics, IEEE Transactions on, 2007)
A novel technique for the numerical analysis of plasmon resonances by using the fast multipole method (FMM) is presented. This approach is based on the solution of the eigenvalue problem for boundary integral equations, which can be naturally implemented by using the FMM. Numerical examples that highlight the efficiency of the fast multipole implementation are reported
Keywords: analysis; boundary; and; boundary; eigenfunctions; nanoparticles; plasmons; equations; eigenvalue; equations; eigenvalues; integral; method; nanoparticle; multipole; plasmon; problems; fast; resonance; numerical

Objects in Action: An Approach for Combining Action Understanding and Object Perception - Gupta,A.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2007. CVPR '07. IEEE Conference on, 2007)
Analysis of videos of human-object interactions involves understanding human movements, locating and recognizing objects and observing the effects of human movements on those objects. While each of these can be conducted independently, recognition improves when interactions between these elements are considered. Motivated by psychological studies of human perception, we present a Bayesian approach which unifies the inference processes involved in object classification and localization, action understanding and perception of object reaction. Traditional approaches for object classification and action understanding have relied on shape features and movement analysis respectively. By placing object classification and localization in a video interpretation framework, we can localize and classify objects which are either hard to localize due to clutter or hard to recognize due to lack of discriminative features. Similarly, by applying context on human movements from the objects on which these movements impinge and the effects of these movements, we can segment and recognize actions which are either too subtle to perceive or too hard to recognize using motion features alone.
Keywords: analysis; image; approach; action; Bayesian; classification; image; classification; object; framework; Bayes; interactions; inference; interpretation; localization; object; methods; gesture; MOTION; movements; human; perception; perception; human-object; perception; object; process; object; processing; visual; recognition; image; recognition; video; segmentation; action; segmentation; object; signal; understanding; human

Online collective entity resolution - Bhattacharya,I.; Getoor, Lise (PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2007)
Entity resolution is a critical component of data integration where the goal is to reconcile database references correspond- ing to the same real-world entities. Given the abundance of publicly available databases that have unresolved entities, we motivate the problem of quick and accurate resolution for an- swering queries over such ‘unclean’ databases. Since collec- tive entity resolution approaches — where related references are resolved jointly — have been shown to be more accu- rate than independent attribute-based resolution, we focus on adapting collective resolution for answering queries. We pro- pose a two-stage collective resolution strategy for processing queries. We then show how it can be performed on-the-fly by adaptively extracting and resolving those database references that are the most helpful for resolving the query. We validate our approach on two large real-world publication databases where we show the usefulness of collective resolution and at the same time demonstrate the need for adaptive strategies for query processing. We then show how the same queries can be answered in real time using our adaptive approach while pre- serving the gains of collective resolution. This work extends work presented in (Bhattacharya, Licamele, & Getoor 2006).

Predicting Protein-Protein Interactions Using Relational Features - Licamele,Louis; Getoor, Lise (Department of Computer Science, University of Maryland, College Park, 2007)
Proteins play a fundamental role in ever y process within the cell.Understanding how proteins interact, and the functional units they are par t of, is important to furthering our knowledge of the entire biological process. There has been a growing amount of work, both experimental and computational, on determining the protein-protein interaction network. Recently researchers have had success looking at this as a relational learning problem. In this work, we further this investigation, proposing several novel relational features for predicting protein-protein interaction. These features can be used in any classifier. Our approach allows large and complex networks to be analyzed and is an alternative to using more expensive relational methods. We show that we are able to get an accuracy of 81.7% when predicting new links from noisy high throughput data.
Keywords: Technical Report

Probabilistic interval XML - Hung,Edward; Getoor, Lise; V.S. Subrahmanian (ACM Transactions on Computational Logic (TOCL), 2007)
Interest in XML databases has been expanding rapidly over the last few years. In this paper, we study the problem of incorporating probabilistic information into XML databases. We propose the Probabilistic Interval XML (PIXML for short) data model in this paper. Using this data model, users can express probabilistic information within XML markups. In addition, we provide two alternative formal model-theoretic semantics for PIXML data. The first semantics is a “global” semantics which is relatively intuitive, but is not directly amenable to computation. The second semantics is a “local” semantics which supports efficient computation. We prove several correspondence results between the two semantics. To our knowledge, this is the first formal model theoretic semantics for probabilistic interval XML. We then provide an operational semantics that may be used to compute answers to queries and that is correct for a large class of probabilistic instances.
Keywords: Semistructured Databases; XML

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

Probabilistic wavelet synopses for multiple measures - Deligiannakis,Antonios; Garofalakis,Minos N.; Roussopoulos, Nick (2007)
A technique for building probabilistic wavelet synopses for multi-measure data sets is provided. In the presence of multiple measures, it is demonstrated that the problem of exact probabilistic coefficient thresholding becomes significantly more complex. An algorithmic formulation for probabilistic multi-measure wavelet thresholding based on the idea of partial-order dynamic programming (PODP) is provided. A fast, greedy approximation algorithm for probabilistic multi-measure thresholding based on the idea of marginal error gains is provided. An empirical study with both synthetic and real-life data sets validated the approach, demonstrating that the algorithms outperform naive approaches based on optimizing individual measures independently and the greedy thresholding scheme provides near-optimal and, at the same time, fast and scalable solutions to the probabilistic wavelet synopsis construction problem.

Real Time Capture of Audio Images and their Use with Video - O'donovan,Adam; Duraiswami, Ramani; Gumerov, Nail A. (Applications of Signal Processing to Audio and Acoustics, 2007 IEEE Workshop on, 2007)
Spherical microphone arrays provide an ability to compute the acoustical intensity corresponding to different spatial directions in a given frame of audio-data. These intensities may be exhibited as an image and these images updated at a high frame rate to achieve a video stream if the data capture and intensity computations can be performed sufficiently quickly, there by creating a frame-rate audio camera. We describe how such a camera can be built and the processing done sufficiently quickly using graphics processors. The joint processing of captured frame-rate audio and video images enables applications such as visual identification of noise sources, beamforming and noise-suppression in video conferencing and others, provided it is possible to account for the spatial differences in the location of the audio and the video cameras. Based on the recognition that the spherical array can be viewed as a central projection camera it is possible to perform such joint analysis. We provide several examples of real-time applications.

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

Relationship identification for social network discovery - Diehl,C. P; Namata,G.; Getoor, Lise (PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2007)
In recent years, informal, online communication has trans- formed the ways in which we connect and collaborate with friends and colleagues. With millions of individuals commu- nicating online each day, we have a unique opportunity to ob- serve the formation and evolution of roles and relationships in networked groups and organizations. Yet a number of chal- lenges arise when attempting to infer the underlying social network from data that is often ambiguous, incomplete and context-dependent. In this paper, we consider the problem of collaborative network discovery from domains such as intel- ligence analysis and litigation support where the analyst is at- tempting to construct a validated representation of the social network. We specifically address the challenge of relation- ship identification where the objective is to identify relevant communications that substantiate a given social relationship type. We propose a supervised ranking approach to the prob- lem and assess its performance on a manager-subordinate re- lationship identification task using the Enron email corpus. By exploiting message content, the ranker routinely cues the analyst to relevant communications relationships and mes- sage traffic that are indicative of the social relationship.

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

Representing Tuple and Attribute Uncertainty in Probabilistic Databases - Sen,P.; Deshpande, Amol; Getoor, Lise (Seventh IEEE International Conference on Data Mining Workshops, 2007. ICDM Workshops 2007, 2007)
There has been a recent surge in work in probabilistic databases, propelled in large part by the huge increase in noisy data sources-sensor data, experimental data, data from uncurated sources, and many others. There is a growing need to be able to flexibly represent the uncertainties in the data, and to efficiently query the data. Building on existing probabilistic database work, we present a unifying framework which allows a flexible representation of correlated tuple and attribute level uncertainties. An important capability of our representation is the ability to represent shared correlation structures in the data. We provide motivating examples to illustrate when such shared correlation structures are likely to exist. Representing shared correlations structures allows the use of sophisticated inference techniques based on lifted probabilistic inference that, in turn, allows us to achieve significant speedups while computing probabilities for results of user-submitted queries.
Keywords: attribute uncertainty; Computer science; Conferences; correlation structures; data mining; Data models; database management systems; Educational institutions; inference mechanisms; noisy data sources; probabilistic database; probabilistic inference; Probability distribution; Query processing; Relational databases; Sensor phenomena and characterization; tuple representation; Uncertainty; uncertainty handling

Retrieving matching CAD models by using partial 3D point clouds - Ip,C. Y; Gupta,S.K. (Computer-Aided Design & Applications, 2007)
The ability to search for a CAD model that represents a specific physical part is a useful capabilitythat can be used in many different applications. This paper presents an approach to use partial 3D point cloud of an artifact for retrieving the CAD model of the artifact. We assume that the information about the physical parts will be captured by a single 3D scan that produces dense point clouds. CAD models in our approach are represented as polygonal meshes. Our approach involves segmenting the point cloud and CAD mesh models into surface patches. The next step is to identify corresponding surface patches in point clouds and CAD models that could potentially match. Finally, we compute transformations to align the point cloud to the CAD model and compute distance between them. We also present experimental results to show that our approach can be used to retrieve CAD models of mechanical parts.

Robust scanner identification based on noise features - Gou,H.; Swaminathan,A.; Wu,M. (Proc. SPIE, Electronic Imaging, Security, Steganography, and Watermarking of Multimedia Contents IX, 2007)
A large portion of digital image data available today is acquired using digital cameras or scanners. While camerasallow digital reproduction of natural scenes, scanners are often used to capture hardcopy art in more controlled scenarios. This paper proposes a new technique for non-intrusive scanner model identification, which can be further extended to perform tampering detection on scanned images. Using only scanned image samples that contain arbitrary content, we construct a robust scanner identifier to determine the brand/model of the scanner used to capture each scanned image. The proposed scanner identifier is based on statistical features of scanning noise. We first analyze scanning noise from several angles, including through image de-noising, wavelet analysis, and neighborhood prediction, and then obtain statistical features from each characterization. Experimental results demonstrate that the proposed method can effectively identify the correct scanner brands/models with high accuracy.

Round Complexity of Authenticated Broadcast with a Dishonest Majority - Garay,J. A; Katz, Jonathan; Koo,Chiu-Yuen; Ostrovsky,R. (Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on, 2007)
Broadcast among n parties in the presence of t ges n/3 malicious parties is possible only with some additional setup. The most common setup considered is the existence of a PKI and secure, digital signatures, where so-called authenticated broadcast is achievable for any t lt; n. It is known that t + 1 rounds are necessary and sufficient for deterministic protocols achieving authenticated broadcast. Recently, however, randomized protocols running in expected constant rounds have been shown for the case of t lt; n/2. It has remained open whether randomization can improve the round complexity when an honest majority is not present. We address this question and show upper/lower bounds on how much randomization can help: ldr For t les n/2 + k, we. show a randomized broadcast protocol that runs in expected O(k2) rounds. In particular, we obtain expected constant-round pivtocols for t = n/2 + O(1). ldr On the negative side, we show that even randomized protocols require Omega(2n/(n-t)) rounds. This in particular rules out expected constant-round protocols when the fraction of honest parties is sub-constant.
Keywords: broadcast; complexity; cryptographic; complexity; deterministic; cryptography; key; majority; randomized; PKI; authenticated; protocols; broadcasting; computational; protocols; digital; round; signatures; dishonest; signatures; public

SAAR: A shared control plane for overlay multicast - Nandi,A.; Ganjam,A.; Druschel,P.; Ng,T. S.E; Stoica,I.; Zhang,H.; Bhattacharjee, Bobby (Proceedings of 4th USENIX Symposium on Networked Systems Design & Implementation, 2007)
Many cooperative overlay multicast systems of diverse designs have been implemented and deployed. In this paper, we explore a new architecture for overlay multicast: we factor out the control plane into a separate overlay that provides a single primitive: a configurable anycast for peer selection. This separation of control and data overlays has several advantages. Data overlays can be optimized for efficient content delivery, while the control overlay can be optimized for flexible and efficient peer selection. Several data channels can share a control plane for fast switching among content channels, which is particularly important for IPTV. And, the control overlay can be reused in multicast systems with different data plane organizations.We designed and evaluated a decentralized control overlay for endsystem multicast. The overlay proactively aggregates system state and implements a powerful anycast primitive for peer selection. We demonstrate that SAAR's efficiency in locating peers reduces channel switching time, improves the quality of content delivery, and reduces overhead, even under dynamic conditions and at scale. An experimental evaluation demonstrates that the system can efficiently support single-tree, multi-tree and block-based multicast systems.

A scalar potential formulation and translation theory for the time-harmonic Maxwell equations - Gumerov, Nail A.; Duraiswami, Ramani (Journal of Computational Physics, 2007)
We develop a computational method based on the Debye scalar potential representation, which efficiently reduces the solution of Maxwell’s equations to the solution of two scalar Helmholtz equations. One of the key contributions of this paper is a theory for the translation of Maxwell solutions using such a representation, since the scalar potential form is not invariant with respect to translations. The translation theory is developed by introducing “conversion” operators, which enable the representation of the electric and magnetic vector fields via scalar potentials in an arbitrary reference frame. Advantages of this representation include the fact that only two Helmholtz equations need be solved, and moreover, the divergence free constraints are satisfied automatically by construction. Truncation error bounds are also presented. The availability of a translation theory and error bounds for this representation can find application in methods such as the Fast Multipole Method.For illustration of the use of the representation and translation theory we implemented an algorithm for the simulation of Mie scattering off a system of spherical objects of different sizes and dielectric properties using a variant of the T-matrix method. The resulting system was solved using an iterative method based on GMRES. The results of the computations agree well with previous computational and experimental results.
Keywords: Debye potentials; Electromagnetic scattering; Fast Multipole Method; Helmholtz equation; Maxwell equations; Mie scattering; T-matrix method; Translation operators

Scheduling to minimize gaps and power consumption - Demaine,E. D; Ghodsi,M.; Hajiaghayi, Mohammad T.; Sayedi-Roshkhar,A. S; Zadimoghaddam,M. (Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, 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)

Spliceosomal small nuclear RNA genes in 11 insect genomes - Mount, Stephen M.; Gotea,Valer; Lin,Chiao-Feng; Hernandez,Kristina; Makałowski,Wojciech (RNARNA, 2007)
A monthly journal publishing high-quality, peer-reviewed research on all topics related to RNA and its metabolism in all organisms
Keywords: honeybee; Insecta; secondary structure; snRNA; spliceosomal snRNA; U12 introns

SplicePort--An interactive splice-site analysis tool - Dogan,R. I; Getoor, Lise; Wilbur,W. J; Mount, Stephen M. (Nucleic Acids Research, 2007)
SplicePort is a web-based tool for splice-site analysis that allows the user to make splice-site predictions for submitted sequences. In addition, the user can also browse the rich catalog of features that underlies these predictions, and which we have found capable of providing high classification accuracy on human splice sites. Feature selection is optimized for human splice sites, but the selected features are likely to be predictive for other mammals as well. With our interactive feature browsing and visualization tool, the user can view and explore subsets of features used in splice-site prediction (either the features that account for the classification of a specific input sequence or the complete collection of features). Selected feature sets can be searched, ranked or displayed easily. The user can group features into clusters and frequency plot WebLogos can be generated for each cluster. The user can browse the identified clusters and their contributing elements, looking for new interesting signals, or can validate previously observed signals. The SplicePort web server can be accessed at http://www.cs.umd.edu/projects/SplicePort and http://www.spliceport.org.

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)

A theoretical model of children's storytelling using physically-oriented technologies (SPOT) - Guha,M.L.; Druin, Allison; Montemayor,J.; Chipman,G.; Farber,A. (Journal of Educational Multimedia and Hypermedia, 2007)

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

Type qualifier inference for Java - Greenfieldboyce,D.; Foster, Jeffrey S. (ACM SIGPLAN Notices, 2007)

Ultrastructure of coccoid viable but non‐culturable Vibrio cholerae - Chaiyanan,Saipin; Chaiyanan,Sitthipan; Grim,Christopher; Maugel,Timothy; Huq,Anwar; Rita R Colwell (Environmental Microbiology, 2007)
Morphology of viable but non-culturable Vibrio cholerae was monitored for 2 years by scanning and transmission electron microscopy. Morphological changes included very small coccoid forms, after extended incubation at 4°C and room temperature, and sequential transformation from curved rods to irregular (∼1 μm) rods to ∼0.8 μm coccoid cells and, ultimately, to tiny coccoid forms (0.07–0.4 μm). Irregular rod-shaped and coccoid cells were equally distributed in microcosms during the first 30–60 days of incubation at both temperatures, but only coccoid cells were observed after incubation for 60 days at 4°C. When V. cholerae O1 and O139, maintained for 30–60 days at both temperatures, were heated to 45°C for 60 s, after serial passage through 0.45 μm and 0.1 μm filters, and plating on Luria–Bertania (LB) agar, only cells larger than 1 μm yielded colonies on LB agar. Approximately 0.1% of heat-treated cultures were culturable. Cell division in the smallest coccoid cells was observed, yielding daughter cells of equal size, whereas other coccoid cells revealed bleb-like, cell wall evagination, followed by transfer of nuclear material. Coccoid cells of V. cholerae O1 and O139 incubated at 4°C for more than 1 year remained substrate responsive and antigenic.

Using virtual demonstrations for creating multi-media training instructions - Schwartz,M.; Gupta,S.K.; Anand,D. K.; Brough,J. E.; Kavetsky,R. (2007)
Often generating training instructions for virtual environments is a long and tedious process. In thispaper, we discuss the development of a virtual environment (VE) instruction generating tool called Virtual Author which is the main component of the Virtual Training Studio (VTS). VTS is a virtual environment-based training system that provides instructors with a tool to create training instructions and allows trainees to learn assembly operations in a personal virtual environment. The Virtual Author tool is designed to allow an instructor to perform virtual demonstrations using CAD models in the virtual environment in order to quickly generate VE-based training instructions for use in VTS. This paper describes the algorithms used to carry out motion smoothening of instructor’s actions, automated text instruction generation based on part and assembly motions, and extraction of alignment constraints from 3D CAD models to support instruction generation. We also present examples to illustrate how the use of the Virtual Author tool leads to a significant reduction in the training instruction generation time.

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

Visual analysis of dynamic group membership in temporal social networks - Kang,Hyunmo; Getoor, Lise; Singh,Lisa (ACM SIGKDD Explorations Newsletter, 2007)
C-Group is a tool for analyzing dynamic group membership in temporal social networks over time. Unlike most network visualization tools, which show the group structure within an entire network, or the group membership for a single actor, C-Group allows users to focus their analysis on a pair of individuals. While C-Group allows for viewing the addition and deletion of nodes (actors) and edges (relationships) over time, its major contribution is its focus on changing group memberships over time. By doing so, users can investigate the context of temporal group memberships for the pair. C-Group provides users with a flexible interface for defining (and redefining) groups interactively, and supports two novel visual representations of the evolving group memberships. This flexibility gives users alternate views that are appropriate for different network sizes and provides users with different insights into the grouping behavior. We demonstrate the utility of the tool on a scientific publication network.
Keywords: dynamic group detection; group visualization; visual data mining

Visual Mining of Multi-Modal Social Networks at Different Abstraction Levels - Singh,L.; Beard,M.; Getoor, Lise; Blake,M.B. (Information Visualization, 2007. IV '07. 11th International Conference, 2007)
Social networks continue to become more and more feature rich. Using local and global structural properties and descriptive attributes are necessary for more sophisticated social network analysis and support for visual mining tasks. While a number of visualization tools for social network applications have been developed, most of them are limited to uni-modal graph representations. Some of the tools support a wide range of visualization options, including interactive views. Others have better support for calculating structural graph properties such as the density of the graph or deploying traditional statistical social network analysis. We present Invenio, a new tool for visual mining of socials. Invenio integrates a wide range of interactive visualization options from Prefuse, with graph mining algorithm support from JUNG. While the integration expands the breadth of functionality within the core engine of the tool, our goal is to interactively explore multi-modal, multi-relational social networks. Invenio also supports construction of views using both database operations and basic graph mining operations.
Keywords: computing; database; interactive; graph; management; mining; data; network; structural; property; visual; sciences; social; systems; graph; systems; social; theory; interactive; visualisation; database; visualization; multimodal

Voila: Efficient feature-value acquisition for classification - Bilgic,M.; Getoor, Lise (PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2007)
We address the problem of efficient feature-value acquisi- tion for classification in domains in which there are varying costs associated with both feature acquisition and misclassi- fication. The objective is to minimize the sum of the infor- mation acquisition cost and misclassification cost. Any de- cision theoretic strategy tackling this problem needs to com- pute value of information for sets of features. Having cal- culated this information, different acquisition strategies are possible (acquiring one feature at time, acquiring features in sets, etc.). However, because the value of information cal- culation for arbitrary subsets of features is computationally intractable, most traditional approaches have been greedy, computing values of features one at a time. We make the problem of value of information calculation tractable in prac- tice by introducing a novel data structure called the Value of Information Lattice (VOILA). VOILA exploits dependencies between missing features and makes sharing of information value computations between different feature subsets possi- ble. To the best of our knowledge, performance differences between greedy acquisition, acquiring features in sets, and a mixed strategy have not been investigated empirically in the past, due to inherit intractability of the problem. With the help of VOILA, we are able to evaluate these strategies on five real world datasets under various cost assumptions. We show that VOILA reduces computation time dramatically. We also show that the mixed strategy outperforms both greedy acqui- sition and acquisition in sets.

3D structure recovery and unwarping of surfaces applicable to planes - Gumerov, Nail A.; Zandifar,A.; Duraiswami, Ramani; Davis, Larry S. (International journal of computer vision, 2006)
The deformation of applicable surfaces such as sheets of paper satisfies the differential geometric constraints of isometry (lengths and areas are conserved) and vanishing Gaussian curvature. We show that these constraints lead to a closed set of equations that allow recovery of the full geometric structure from a single image of the surface and knowledge of its undeformed shape. We show that these partial differential equations can be reduced to the Hopf equation that arises in non-linear wave propagation, and deformations of the paper can be interpreted in terms of the characteristics of this equation. A new exact integration of these equations is developed that relates the 3-D structure of the applicable surface to an image. The solution is tested by comparison with particular exact solutions. We present results for both the forward and the inverse 3D structure recovery problem.

Adaptive pull-based policies for wide area data delivery - Bright,L.; Gal,A.; Raschid, Louiqa (ACM Transactions on Database Systems (TODS), 2006)

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.

Approximation algorithms for channel allocation problems in broadcast networks - Gandhi,Rajiv; Khuller, Samir; Srinivasan, Aravind; Wang,Nan (Networks, 2006)
We study two packing problems that arise in the area of dissemination-based information systems; a second theme is the study of distributed approximation algorithms. The problems considered have the property that the space occupied by a collection of objects together could be significantly less than the sum of the sizes of the individual objects. In the Channel Allocation Problem, there are requests that are subsets of topics. There are a fixed number of channels that can carry an arbitrary number of topics. All the topics of each request must be broadcast on some channel. The load on any channel is the number of topics that are broadcast on that channel; the objective is to minimize the maximum load on any channel. We present approximation algorithms for this problem, and also show that the problem is MAX-SNP hard. The second problem is the Edge Partitioning Problem addressed by Goldschmidt, Hochbaum, Levin, and Olinick (Networks, 41:13–23, 2003). Each channel here can deliver topics for at most k requests, and we aim to minimize the total load on all channels. We present an O(n1/3)–approximation algorithm, and also show that the algorithm can be made fully distributed with the same approximation guarantee; we also generalize the (nondistributed) Edge Partitioning Problem of graphs to the case of hypergraphs. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 225–236 2006
Keywords: channel allocation problem; distributed approximation algorithm; edge partitioning problem

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

Back to Basics: CLASSY 2006 - Conroy,John M.; Schlesinger,Judith D.; O'Leary, Dianne P.; Goldstein,Jade (DUC 06 Conference ProceedingsDUC 06 Conference Proceedings, 2006)
The IDA/CCS summarization system, CLASSY, underwent significant change for this year’sDUC. Two changes made processing simpler and faster: 1) we eliminated the use of a POS (part of speech) tagger for sentence splitting and to assist sentence trimming, and 2) we simplified the scoring of sentences for inclusion in the summary by introducing a new “approximate oracle” score. An additional change introduced a modest amount of extra computation: we ordered sentences in the summary using a new Traveling Salesperson (TSP) formulation. These changes improved ROUGE scores on the DUC 2005 data from last year and gave strong performance in the DUC 2006 competition.

Bio-inspired, Modular, and Multifunctional Thermal and Impact Protected (TIPed) Embedded Sensing Controls Actuation Power Element (ESCAPE) Structures - Gyger Jr,L. S.; Spranklin,B. W.; Gupta,S.K.; Bruck,H. A. (2006)
There is a great deal of interest in creating new structural concepts, such as snake robots, from analogousbiological systems. These biological systems are typically composed of materials that serve multiple functions. For example, the skin of a snake is a system consisting of a soft, hyperelastic covering, with nerves providing thermal and pressure sensitivity, and a hard, scaly coating to resist wear and tear from hard particles such as sand. Therefore, bio-inspired structures can also be composed of multifunctional materials. There are currently many approaches to fabricating bio-inspired structures with conventional materials. These concepts typically utilize a system-of-systems design approach where the structure will be composed of a structural framework, an actuation system, a power source for the actuation system, controllers, and external sensors. The drawbacks to these structures include the need to assemble all of the components, interfaces between components that can compromise reliability, constraints on scaling down the structure, and very high power consumption and power generation requirements. These problems have been addressed by developing a new scalable approach to creating multifunctional materials for bio-inspired structures where the controllers, actuators, and sensors are integrated into a modular, multifunctional structure. This approach is facilitated by using multi-material multi-stage molding processes with fully embedded electronic systems, and has resulted in new Thermal and Impact Protected (TIPed) Embedded Sensing Controls Actuation Power Element (ESCAPE) Structures for compact and rugged robotic applications.

Case study of gate-level logic simulation on an extremely fine-grained chip multiprocessor - Gu,Pei; Vishkin, Uzi (Journal of Embedded Computing, 2006)
Explicit-multi-threading (XMT) is a parallel programming approach for exploiting on-chip parallelism. Its fine-grained single program multiple data (SPMD) programming model is suitable for many computing intensive applications. In this paper, we present a parallel gate level logic simulator implemented on an XMT platform and study its performance. Test results show potential for achieving more than a hundred-fold speedup over a serial implementation. This indicates an interesting possibility for a certain type of a single chip multicore architecture: use an existing easy-to-program API, such as VHDL or Verilog, for reduced application-software development time and better performance over serial performance-driven languages, such as C.

A case study of tangible flags: a collaborative technology to enhance field trips - Chipman,G.; Druin, Allison; Beer,D.; Fails,J. A; Guha,M.L.; Simms,S. (Proceedings of the 2006 conference on Interaction design and children, 2006)

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.

Constraint Integration for Multiview Pose Estimation of Humans with Self-Occlusions - Gupta,A.; Mittal,A.; Davis, Larry S. (3D Data Processing, Visualization, and Transmission, Third International Symposium on, 2006)
Detection of articulated objects such as humans is an important task in computer vision. We present a system that incorporates a variety of constraints in a unified multi- view framework to automatically detect humans in possibly crowded scenes. These constraints include the kinematic constraints, the occlusion of one part by another and the high correlation between the appearance of parts such as the two arms. The graphical structure (non-tree) obtained is optimized in a nonparametric belief propagation framework using prior based search.
Keywords: articulated; belief; constraint; multiview; detection; computer; detection; pose; estimation; estimation; nonparametric; framework; self-occlusion; computer; graphics; computer; method; graphical; methods; object; object; pose; propagation; structure; kinematic; vision; correlation

Content-based search techniques for searching CAD databases - Gupta, Satyandra K.; Cardone, Antonio; Deshmukh,A. (CAD Conference, 2006)
The popularity of 3D CAD systems is resulting in large assembly and part databases being createdby product development organizations. Over the last few years several content-based techniques have emerged to search these databases. Ability to perform content-based searches on CAD databases is expected to help the designers and manufacturing engineers in many different ways. Representative examples include part-family formation, redesign suggestion generation, supplier selection, cost estimation, tooling design, machine selection, stock selection, and design reuse. This paper covers the following three topics. First, it presents an overview of different types of part search techniques. Second, it presents an overview of the different aspects of assembly search techniques. Finally, it identifies the open challenges in these areas and outlines future research directions.

Cost-sensitive learning with conditional Markov networks - Sen,Prithviraj; Getoor, Lise (Proceedings of the 23rd international conference on Machine learning, 2006)
There has been a recent, growing interest in classification and link prediction in structured domains. Methods such as CRFs (Lafferty et al., 2001) and RMNs (Taskar et al., 2002) support flexible mechanisms for modeling correlations due to the link structure. In addition, in many structured domains, there is an interesting structure in the risk or cost function associated with different misclassifications. There is a rich tradition of cost-sensitive learning applied to unstructured (IID) data. Here we propose a general framework which can capture correlations in the link structure and handle structured cost functions. We present a novel cost-sensitive structured classifier based on Maximum Entropy principles that directly determines the cost-sensitive classification. We contrast this with an approach which employs a standard 0/1 loss structured classifier followed by minimization of the expected cost of misclassification. We demonstrate the utility of our proposed classifier with experiments on both synthetic and real-world data.

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.

D-Dupe: An Interactive Tool for Entity Resolution in Social Networks - Bilgic,M.; Licamele,L.; Getoor, Lise; Shneiderman, Ben (Visual Analytics Science And Technology, 2006 IEEE Symposium On, 2006)
Visualizing and analyzing social networks is a challenging problem that has been receiving growing attention. An important first step, before analysis can begin, is ensuring that the data is accurate. A common data quality problem is that the data may inadvertently contain several distinct references to the same underlying entity; the process of reconciling these references is called entity-resolution. D-Dupe is an interactive tool that combines data mining algorithms for entity resolution with a task-specific network visualization. Users cope with complexity of cleaning large networks by focusing on a small subnetwork containing a potential duplicate pair. The subnetwork highlights relationships in the social network, making the common relationships easy to visually identify. D-Dupe users resolve ambiguities either by merging nodes or by marking them distinct. The entity resolution process is iterative: as pairs of nodes are resolved, additional duplicates may be revealed; therefore, resolution decisions are often chained together. We give examples of how users can flexibly apply sequences of actions to produce a high quality entity resolution result. We illustrate and evaluate the benefits of D-Dupe on three bibliographic collections. Two of the datasets had already been cleaned, and therefore should not have contained duplicates; despite this fact, many duplicates were rapidly identified using D-Dupe's unique combination of entity resolution algorithms within a task-specific visual interface
Keywords: algorithm; data; analysis; social; computing; user; D-Dupe; interactive; interface; data; interfaces; mining; mining; interactive; network; problem; entity; QUALITY; resolution; entity-resolution; social; sciences; systems; social; tool; data; visual; visualization; task-specific

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

Detection, Isolation, and Identification of Vibrio cholerae from the Environment - Huq,Anwar; Grim,Christopher; Rita R Colwell; Nair,G. Balakrish (Current Protocols in MicrobiologyCurrent Protocols in Microbiology, 2006)
Keywords: culturable; DETECTION; Environment; identification; isolation; nonculturable; viable; Vibrio cholerae

Distributing Google - Gopalakrishnan,V.; Bhattacharjee, Bobby; Keleher,P. (Data Engineering Workshops, 2006. Proceedings. 22nd International Conference on, 2006)
We consider the problem of wide-area large-scale text search over a peer-to-peer infrastructure. A wide-area search infrastructure with billions of documents and millions of search terms presents unique challenges in terms of the amount of state that must be maintained and updated. Distributing such a system would require tens of thousands of hosts leading to the usual problems associated with node failures, churn and data migration. Localities inherent in query patterns will cause load imbalances and hot spots that can severely impair performance. In this paper, we describe an architecture for constructing a scalable search infrastructure that is designed to cope with the challenges of scale described above. Our architecture consists of a data store layer which is used to reliably store and recompute indexes over a slow timescale and a caching layer that is used to respond to most queries. Our primary insight is that the problem of efficiently retrieving a small number of relevant results must be decoupled from the problem of reliably storing potentially huge indexes. Relevant results can be quickly retrieved from caches of ranked results, which can be replicated based upon query load. An entirely different set of mechanisms, such as encoded storage and/or data partitioning, should be used to store large indexes reliably. These indexes should only be used to compute results when there is a miss in the cache.

Efficient computation of 3-D acoustical scattering from multiple arbitrarily shaped objects using the boundary element method/fast multipole method (BEM/FMM) - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2006)
Many applications require computation of acoustic fields in systems consisting of a large number of scatterers, which may have complex shape. Despite the boundary element method being a well‐known technique for solution of the boundary value problems for the Helmholtz equation, its capabilities are usually limited by the memory and speed of computers, and conventional methods can be applicable to relatively small (up to order of 10 000 boundary elements) problems. We developed and implemented an efficient computational technique, based on an iterative solver employing generalized minimal residual method in combination with matrix‐vector multiplication speeded up with the fast multipole method. We demonstrate that this technique has O(N) memory and computational complexity and enables solution of problems with thousands of scatterers (millions of boundary elements) on a desktop PC. The test problems solved are of moderate frequency (up to kD≤150, where k is the wavenumber and D is the size of the computational domain). Solution of large scale scattering problems was tested by comparison with the FMM‐based T‐matrix method applicable for simple shape objects reported earlier [Gumerov and Duraiswami, J. Acoust. Soc. Am., 117(4), 1744–1761 (2005)], visualization, and physical interpretation of the results.

An Efficient Computational Method for Predicting Rotational Diffusion Tensors of Globular Proteins Using an Ellipsoid Representation - Ryabov,Yaroslav E.; Geraghty,Charles; Varshney, Amitabh; Fushman, David (Journal of the American Chemical Society, 2006)
We propose a new computational method for predicting rotational diffusion properties of proteins in solution. The method is based on the idea of representing protein surface as an ellipsoid shell. In contrast to other existing approaches this method uses principal component analysis of protein surface coordinates, which results in a substantial increase in the computational efficiency of the method. Direct comparison with the experimental data as well as with the recent computational approach (Garcia de la Torre; et al. J. Magn. Reson. 2000, B147, 138?146), based on representation of protein surface as a set of small spherical friction elements, shows that the method proposed here reproduces experimental data with at least the same level of accuracy and precision as the other approach, while being approximately 500 times faster. Using the new method we investigated the effect of hydration layer and protein surface topography on the rotational diffusion properties of a protein. We found that a hydration layer constructed of approximately one monolayer of water molecules smoothens the protein surface and effectively doubles the overall tumbling time. We also calculated the rotational diffusion tensors for a set of 841 protein structures representing the known protein folds. Our analysis suggests that an anisotropic rotational diffusion model is generally required for NMR relaxation data analysis in single-domain proteins, and that the axially symmetric model could be sufficient for these purposes in approximately half of the proteins.We propose a new computational method for predicting rotational diffusion properties of proteins in solution. The method is based on the idea of representing protein surface as an ellipsoid shell. In contrast to other existing approaches this method uses principal component analysis of protein surface coordinates, which results in a substantial increase in the computational efficiency of the method. Direct comparison with the experimental data as well as with the recent computational approach (Garcia de la Torre; et al. J. Magn. Reson. 2000, B147, 138?146), based on representation of protein surface as a set of small spherical friction elements, shows that the method proposed here reproduces experimental data with at least the same level of accuracy and precision as the other approach, while being approximately 500 times faster. Using the new method we investigated the effect of hydration layer and protein surface topography on the rotational diffusion properties of a protein. We found that a hydration layer constructed of approximately one monolayer of water molecules smoothens the protein surface and effectively doubles the overall tumbling time. We also calculated the rotational diffusion tensors for a set of 841 protein structures representing the known protein folds. Our analysis suggests that an anisotropic rotational diffusion model is generally required for NMR relaxation data analysis in single-domain proteins, and that the axially symmetric model could be sufficient for these purposes in approximately half of the proteins.

Empirical comparison of approximate inference algorithms for networked data - Sen,P.; Getoor, Lise (Open Problems in Statistical Relational Learning: Papers from the ICML Workshop. Pittsburgh, PA: www. cs. umd. edu/projects/srl2006, 2006)
Over the past few years, a number of approx-imate inference algorithms for networked data have been put forth. We empirically compare the performance of three of the popular algorithms: loopy belief propagation, mean field relaxation labeling and iterative classification. We rate each algorithm in terms of its robustness to noise, both in attribute values and correlations across links. A novel observation from our experiments is that loopy belief propagation faces difficulty when in- ferring over data with homophily, a common type of link correlation observed in relational data.

Entity and relationship labeling in affiliation networks - Zhao,B.; Sen,P.; Getoor, Lise (ICML Workshop on Statistical Network Analysis, 2006)
Many domains are best characterized as anaffiliation network describing a set of actors and a set of events interlinked together in a variety of relationships. Relational clas- sification in these domains requires the col- lective classification of both entities (actors and events) and relationships. We investigate the use of relational Markov networks (RMN) for relational classification in affiliation net- works. In this paper, we introduce a novel dataset, Profile in Terror (PIT) knowledge base, that provides a rich source of various af- filiation networks. We study two tasks, entity labeling and relationship labeling. We high- light several important issues concerning the effectiveness of relational classification. Our results show that the PIT dataset has a rich source of relational structure and therefore it is a useful dataset for statisical relational network learning community.

Entity resolution in geospatial data integration - Sehgal,Vivek; Getoor, Lise; Viechnicki,Peter D (Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, 2006)
Due to the growing availability of geospatial data from a wide variety of sources, there is a pressing need for robust, accurate and automatic merging and matching techniques. Geospatial Entity Resolution is the process of determining, from a collection of database sources referring to geospatial locations, a single consolidated collection of 'true' locations. At the heart of this process is the problem of determining when two locations references match---i.e., when they refer to the same underlying location. In this paper, we introduce a novel method for resolving location entities in geospatial data. A typical geospatial database contains heterogeneous features such as location name, spatial coordinates, location type and demographic information. We investigate the use of all of these features in algorithms for geospatial entity resolution. Entity resolution is further complicated by the fact that the different sources may use different vocabularies for describing the location types and a semantic mapping is required. We propose a novel approach which learns how to combine the different features to perform accurate resolutions. We present experimental results showing that methods combining spatial and non-spatial features (e.g., location-name, location-type, etc.) together outperform methods based on spatial or name information alone.

Entity Resolution in Graphs - Bhattacharya,Indrajit; Getoor, Lise (Mining Graph DataMining Graph Data, 2006)
This chapter contains sections titled:Introduction Related Work Motivating Example for Graph-Based Entity Resolution Graph-Based Entity Resolution: Problem Formulation Similarity Measures for Entity Resolution Graph-Based Clustering for Entity Resolution Experimental Evaluation Conclusion References
Keywords: entity resolution in graphs; graph‐based clustering for entity resolution; graph‐based entity resolution problem

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)

Event classification and relationship labeling in affiliation networks - Zhao,B.; Sen,P.; Getoor, Lise (Proceedings of the Workshop on Statistical Network Analysis (SNA) at the 23rd International Conference on Machine Learning (ICML), 2006)
Many domains are best described as an affiliation network in which there are entities such as actors, events and organizations linked together in a variety of relationships. Relational classification in these domains requires the collective classification of both entities and relationships. In this paper, we investigate the use of relational Markov networks (RMN) for relational classification in affiliation networks. We study two tasks, event classification and relationship labeling, and discuss general issues in constructing an appropriate RMN from an affiliation network. We evaluate our methods on a novel dataset describing terrorist affiliation networks which includes data about actors (terrorists), events (terrorist attacks) and organizations (terrorist organizations). Our results highlight several important issues concerning the effectiveness of relational classification and our experiments show that the relational structure significantly helps relationship labeling.

Evolution of non-LTR retrotransposons in the trypanosomatid genomes: Leishmania major has lost the active elements - Bringaud,Frédéric; Ghedin,Elodie; Blandin,Gaëlle; Bartholomeu,Daniella C.; Caler,Elisabet; Levin,Mariano J.; Baltz,Théo; El‐Sayed, Najib M. (Molecular and Biochemical Parasitology, 2006)
The ingi and L1Tc non-LTR retrotransposons - which constitute the ingi clade - are abundant in the genome of the trypanosomatid species Trypanosoma brucei and Trypanosoma cruzi, respectively. The corresponding retroelements, however, are not present in the genome of a closely related trypanosomatid, Leishmania major. To study the evolution of non-LTR retrotransposons in trypanosomatids, we have analyzed all ingi/L1Tc elements and highly degenerate ingi/L1Tc-related sequences identified in the recently completed T. brucei, T. cruzi and L. major genomes. The coding sequences of 242 degenerate ingi/L1Tc-related elements (DIREs) in all three genomes were reconstituted by removing the numerous frame shifts. Three independent phylogenetic analyses conducted on the conserved domains encoded by these elements show that all DIREs, including the 52 L. major DIREs, form a monophyletic group belonging to the ingi clade. This indicates that the trypanosomatid ancestor contained active mobile elements that have been retained in the Trypanosoma species, but were lost from L. major genome, where only remnants (DIRE) are detectable. All 242 DIREs analyzed group together according to their species origin with the exception of 11 T. cruzi DIREs which are close to the T. brucei ingi/DIRE families. Considering the absence of known horizontal transfer between the African T. brucei and the South-American T. cruzi, this suggests that this group of elements evolved at a lower rate when compared to the other trypanosomatid elements. Interestingly, the only nucleotide sequence conserved between ingi and L1Tc (the first 79 residues) is also present at the 5'-extremity of all the full length DIREs and suggests a possible role for this conserved motif, as well as for DIREs.
Keywords: Degenerate retroelement; Evolution; Ingi; L1Tc; Leishmania major; Non-LTR retrotransposon; Retroposon; Trypanosoma brucei; Trypanosoma cruzi

Exploiting independence for branch operations in Bayesian learning of C&RTs - Angelopoulos,N.; Cussens,J.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H (Probabilistic, Logical and Relational Learning-Towards a Synthesis, 2006)
In this paper we extend a methodology for Bayesian learning via MCMC, with the ability to grow arbitrarily long branches in C&RT models. We are able to do so by exploiting independence in the model construction process. The ability to grow branches rather than single nodes has been noted as desirable in the literature. The most singular feature of the underline methodology used here in comparison to other approaches is the coupling of the prior and the proposal. The main contribution of this paper is to show how taking advantage of independence in the coupled process, can allow branch growing and swapping for proposal models.

Fast head-related transfer function measurement via reciprocity - Zotkin,Dmitry N; Duraiswami, Ramani; Grassi,Elena; Gumerov, Nail A. (The Journal of the Acoustical Society of America, 2006)
An efficient method for head-related transfer function (HRTF) measurement is presented. By applying the acoustical principle of reciprocity, one can swap the speaker and the microphone positions in the traditional (direct) HRTF measurement setup, that is, insert a microspeaker into the subject’s ear and position several microphones around the subject, enabling simultaneous HRTF acquisition at all microphone positions. The setup used for reciprocal HRTF measurement is described, and the obtained HRTFs are compared with the analytical solution for a sound-hard sphere and with KEMAR manikin HRTF obtained by the direct method. The reciprocally measured sphere HRTF agrees well with the analytical solution. The reciprocally measured and the directly measured KEMAR HRTFs are not exactly identical but agree well in spectrum shape and feature positions. To evaluate if the observed differences are significant, an auditory localization model based on work byJ. C. Middlebrooks [J. Acoust. Soc. Am. 92, 2607–2624 (1992) ] was used to predict where a virtual sound source synthesized with the reciprocally measured HRTF would be localized if the directly measured HRTF were used for the localization. It was found that the predicted localization direction generally lies close to the measurement direction, indicating that the HRTFs obtained via the two methods are in good agreement.
Keywords: hearing; Microphones; Transfer functions

Fast multipole method for the biharmonic equation in three dimensions - Gumerov, Nail A.; Duraiswami, Ramani (Journal of Computational Physics, 2006)
The evaluation of sums (matrix–vector products) of the solutions of the three-dimensional biharmonic equation can be accelerated using the fast multipole method, while memory requirements can also be significantly reduced. We develop a complete translation theory for these equations. It is shown that translations of elementary solutions of the biharmonic equation can be achieved by considering the translation of a pair of elementary solutions of the Laplace equations. The extension of the theory to the case of polyharmonic equations in R 3 is also discussed. An efficient way of performing the FMM for biharmonic equations using the solution of a complex valued FMM for the Laplace equation is presented. Compared to previous methods presented for the biharmonic equation our method appears more efficient. The theory is implemented and numerical tests presented that demonstrate the performance of the method for varying problem sizes and accuracy requirements. In our implementation, the FMM for the biharmonic equation is faster than direct matrix–vector product for a matrix size of 550 for a relative L2 accuracy ϵ2 = 10−4, and N = 3550 for ϵ2 = 10−12.

A feature generation algorithm for sequences with application to splice-site prediction - Islamaj,R.; Getoor, Lise; Wilbur,W. (Knowledge Discovery in Databases: PKDD 2006, 2006)
In this paper we present a new approach to feature selection for sequence data. We identify general feature categories and give construction algorithms for each of them. We show how they can be integrated in a system that tightly couples feature construction and feature selection. This integrated process, which we refer to as feature generation, allows us to systematically search a large space of potential features. We demonstrate the effectiveness of our approach for an important component of the gene finding problem, splice-site prediction. We show that predictive models built using our feature generation algorithm achieve a significant improvement in accuracy over existing, state-of-the-art approaches.

File System Support for Collaboration in theWide Area - Gaburici,V.; Keleher,P.; Bhattacharjee, Bobby (Distributed Computing Systems, 2006. ICDCS 2006. 26th IEEE International Conference on, 2006)
We describe the design, implementation, and performance of MFS, a new file system designed to support efficient widearea collaboration. MFS is structured around the twin abstractions of lightweight sessions and snapshots, along with a highly configurable capability-based security architecture. Sessions simplify and clarify collaborative semantics. Snapshots allow atomic access to arbitrary collections of files, and allow sharing to be defined in a simple and expressive fashion. MFS #146;s security architecture is a layered system that allows diverse usage scenarios. Pure capability-based access allows clients to access data without needing expensive public key or authentication servers, or complicated administration. However, MFS #146;s capabilities can also be watermarked, allowing a range of services to be added on a per-mount basis, up to and including traditional user authentication based on passwords or public keys. Basing the system around the use of immutable snapshots enables the underlying system to use several performance optimizations aggressively. Performance results from our MFS prototype show that, far from adding overhead, the use of snapshots allows the system to perform comparably to NFS in the local-area case and significantly outperform existing systems in wide-area environments.

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

Fingerprinting digital elevation maps - Gou,H.; Wu,M. (Proceedings of SPIE, 2006)
Digital elevation maps (DEMs) provide a digital representation of 3-D terrain information. In civilian appli-cations, high-precision DEMs carry a high commercial value owing to the large amount of effort in acquiring them; and in military applications, DEMs are often used to represent critical geospatial information in sensitive operations. These call for new technologies to prevent unauthorized distribution and to trace traitors in the event of information leak related to DEMs. In this paper, we propose a new digital fingerprinting technique to protect DEM data from illegal re-distribution. The proposed method enables reliable detection of fingerprints from both 3-D DEM data set and its 2-D rendering, whichever format that is available to a detector. Our method starts with extracting from a DEM a set of critical contours either corresponding to important topographic features of the terrain or having application-dependent importance. Fingerprints are then embedded into these critical contours by employing parametric curve modeling and spread spectrum embedding. Finally, a fingerprinted DEM is constructed to incorporate the marked 2-D contours. Through experimental results, we demonstrate the robustness of the proposed method against a number of challenging attacks applied to either DEMs or their contour representations.

A flexible system framework for a nanoassembly cell using optical tweezers - Balijepalli,A.; LeBrun,T. W.; Gupta,S.K. (2006)
The optical tweezers instrument is a unique tool fordirected assembly of nanocomponents. In order to function as a viable nanomanufacturing tool, a software architecture is needed to run the optical tweezers hardware, provide an effective user interface, and allow automated operation. A flexible software system framework is described to utilize the optical tweezers hardware to its full potential. Initially we lay out the requirements for the system framework and define the broad architectural choices made while implementing the different modules. Implementation details of key system modules are then described. The flexible nature of the architecture is demonstrated by showing how a simulation module can be seamlessly included into the framework to replace the optical tweezers hardware as necessary. Finally, we show some representative assembly operations to demonstrate the capabilities of the system.

FMM accelerated BEM for 3D Laplace & Helmholtz equations - Gumerov, Nail A.; Duraiswami, Ramani (Proceedings Int. Conf. on Boundary Element Techniques, 2006)

Frequency Independent Flexible Spherical Beamforming Via Rbf Fitting - Yerukhimovich,A.; Duraiswami, Ramani; Gumerov, Nail A.; Zotkin,Dmitry N (2006 IEEE International Conference on Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings, 2006)
We describe a new method for sound analysis using a spherical microphone array without the use of quadrature over the sphere. Quadrature based solutions are very sensitive to the placement of microphones on the sphere, needing measurements to be made at exactly the quadrature positions. We propose to use fitting with band-limited radial basis functions (RBFs) rather than quadrature. Our approach results in frequency independent beamformer weights for flexibly placed microphone locations. Results are demonstrated using both synthetic and real spherical array data
Keywords: acoustic signal processing; array signal processing; band-limited radial basis functions; Computer science; Educational institutions; Eigenvalues and eigenfunctions; Equations; Frequency; frequency independent beamformer weights; frequency independent flexible spherical beamforming; microphone arrays; Nails; Position measurement; RBF fitting; Robustness; sound analysis; spherical array data; spherical microphone array

Head-related transfer functions via the fast multipole accelerated boundary element method - Gumerov, Nail A.; Duraiswami, Ramani; Zotkin,Dmitry N (The Journal of the Acoustical Society of America, 2006)
Computation of head‐related transfer functions (HRTF) via geometrical meshes and numerical methods has been suggested by a number of authors. An issue facing this approach is the large computational time needed for high frequencies, where the discretization must include hundreds of thousands of elements. Conventional computational methods are unable to achieve such computations without excessive time or memory. We use a newly developed fast multipole accelerated boundary element method (FMM/BEM) that scales linearly both in time and memory. The method is applied to the mesh of the widely used KEMAR manikin and its HRTF computed up to 20 kHz. The results are compared with available experimental measurements.

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

Human activity language: Grounding concepts with a linguistic framework - Guerra-Filho,G.; Aloimonos, J. (Semantic Multimedia, 2006)

Implementing a bioinformatics pipeline (bip) on a mediator platform: Comparing cost and quality of alternate choices - Eckman,B. A; Gaasterland,T.; Lacroix,Z.; Raschid, Louiqa; Snyder,B.; Vidal,M. E (Data Engineering Workshops, 2006. Proceedings. 22nd International Conference on, 2006)

An improved approximation algorithm for vertex cover with hard capacities - Gandhi,Rajiv; Halperin,Eran; Khuller, Samir; Kortsarz,Guy; Srinivasan, Aravind (Journal of Computer and System Sciences, 2006)
We study the capacitated vertex cover problem, a generalization of the well-known vertex-cover problem. Given a graph G = ( V , E ) , the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex-cover problem. Previously, approximation algorithms with an approximation factor of 2 were developed with the assumption that an arbitrary number of copies of a vertex may be chosen in the cover. If we are allowed to pick at most a fixed number of copies of each vertex, the approximation algorithm becomes much more complex. Chuzhoy and Naor (FOCS, 2002) have shown that the weighted version of this problem is at least as hard as set cover; in addition, they developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy–Naor bound of three and matching (up to lower-order terms) the best approximation ratio known for the vertex-cover problem.
Keywords: Approximation algorithms; Capacitated covering; Linear programming; Randomized rounding; Set cover; Vertex cover

Inferring formal titles in organizational email archives - Namata,G.M.; Getoor, Lise; Diehl,C. (Proc. of the ICML Workshop on Statistical Network Analysis, 2006)
In the social network of large groups of people, such as companiesand organizations, formal hierarchies with titles and lines of authority are established to define the responsibilities and order of power within that group. Although this information may be readily available for individuals within that group, the context this hierarchy provides in communications is not available to those outside the group. In this paper, we define the problem of inferring this formal hierarchy in the context of organizational email archives. We present a new dataset for the widely used Enron email dataset, for use with analysis of the Enron social network hierarchy. We then provide some preliminary results on the problem of classifying individuals to their formal titles using standard classification algorithms.

An introduction to probabilistic graphical models for relational data - Getoor, Lise (Data Engineering Bulletin, 2006)
We survey some of the recent work on probabilistic graphical models for relational data. The models thatwe describe are all based upon ’graphical models’ [12]. The models can capture statistical correlations among attributes within a single relational table, between attributes in different tables, and can capture certain structural properties, such as the expected size of a join between tables. These models can then be used for a variety of tasks including filling in missing values, data summarization and anomaly detection. Here we describe two complementary semantics for the models: one approach suited to making probabilistic statements about individuals and the second approach suited to making statements about frequencies in relational data. After describing the semantics, we briefly describe algorithms for automatically constructing the models from an existing (non-probabilistic) database.

A latent dirichlet allocation model for entity resolution - Bhattacharya,I.; Getoor, Lise (6th SIAM Conference on Data Mining (SDM), Bethesda, USA, 2006)
In this paper, we address the problem of entity resolution, where given many references to un-derlying objects, the task is to predict which references correspond to the same object. We propose a probabilistic model for collective entity resolution. Our approach differs from other recently pro- posed entity resolution approaches in that it is a) unsupervised, b) generative and c) introduces a hidden ‘group’ variable to capture collections of entities which are commonly observed together. The entity resolution decisions are not considered on an independent pairwise basis, but instead decisions are made collectively. We focus on how the use of relational links among the references can be exploited. We show how we can use Gibbs Sampling to infer the collaboration groups and the entities jointly from the observed co-author relationships among entity references and how this improves entity resolution performance. We demonstrate the utility of our approach on two real-world bibliographic datasets. In addition, we present preliminary results on characterizing conditions under which collaborative infor- mation is useful.

Learning through failure - Sato,T.; Kameya,Y.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H (Probabilistic, Logical and Relational Learning-Towards a Synthesis, 2006)
PRISM, a symbolic-statistical modeling language we have been developing since '97, recently incorporated a program transformation technique to handle failure in generative modeling. I'll show this feature opens a way to new breeds of symbolic models, including EM learning from negative observations, constrained HMMs and finite PCFGs.

Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems - Ambainis,Andris; Gasarch,William; Srinivasan, Aravind; Utis,Andrey (Algorithms and ComputationAlgorithms and Computation, 2006)
A sub-area of discrepancy theory that has received much attention in computer science re-cently, is that of explicit constructions of low-discrepancy point sets for various types of rectangle families in high dimension. This research has led to interesting applications in error-control cod- ing, distributed protocols, Web document filtering, derandomization, and other areas. We give a short survey of this area here.

Machining feature-based similarity assessment algorithms for prismatic machined parts - Cardone, Antonio; Gupta, Satyandra K.; Deshmukh,Abhijit; Karnik,Mukul (Computer-Aided Design, 2006)
This paper presents algorithms for identifying machined parts in a database that are similar to a given query part based on machining features. In this paper we only consider parts that are machined on 3-axis machining centers. We utilize reduced feature vectors consisting of machining feature access directions, feature types, feature volumes, feature dimensional tolerances and feature group cardinality as a basis for assessing shape similarity. We have defined a distance function between two sets of reduced feature vectors to assess the similarity between them from the machining effort point of view. To assess the similarity between the two parts, one set of reduced feature vectors is transformed in space using rigid body transformations with respect to the other set such that the distance between them is minimized. The distance between the two sets of aligned reduced feature vectors is used as a measure of similarity between the two parts. The existing machined parts are rank ordered based on the value of the distance with respect to the query part. The cost of previously machined parts that have a very small distance from the query part can be used as a basis for estimating the cost of machining the new part.
Keywords: Feature vector alignment; Machining features; Similarity assessment

Manufacturing of multi-material compliant mechanisms using multi-material molding - Gouker,Regina; Gupta, Satyandra K.; Bruck,Hugh; Holzschuh,Tobias (The International Journal of Advanced Manufacturing Technology, 2006)
Multi-material compliant mechanisms enable many new design possibilities. Significant progress has been made in the area of design and analysis of multi-material compliant mechanisms. What is now needed is a method to mass-produce such mechanisms economically. A feasible and practical way of producing such mechanisms is through multi-material molding. Devices based on compliant mechanisms usually consist of compliant joints. Compliant joints in turn are created by carefully engineering interfaces between a compliant and a rigid material. This paper presents an overview of multi-material molding technology and describes feasible mold designs for creating different types of compliant joints found in multi-material compliant mechanisms. It also describes guidelines essential to successfully utilizing the multi-material molding process for creating compliant mechanisms. Finally, practical applications for the use of multi-material molding to create compliant mechanisms are demonstrated.
Keywords: engineering

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.

Moving Object Verification from Airborne Video - Yue,Zhanfeng; Chellapa, Rama; Guarino, D. (Computer Vision Systems, 2006 ICVS '06. IEEE International Conference on, 2006)
This paper presents an end-to-end verification system for moving objects in airborne video. Lacking prior training data, the object information is collected on the fly from a short real-time learning sequence. Using a sample selection module, the system selects samples from the learning sequence and stores them in an exemplar database. To handle appearance change due to potentially large aspect angle variations, a homography-based view synthesis method is used to generate a novel view of each image in the exemplar database at the same pose as the query object in each frame of a query sequence. A spatial match score is obtained using a Distance Transform to compare the novel view and query object. After looping over all query frames, the set of match scores is passed to a temporal analysis module to examine the behavior of the query object, and calculate a final likelihood. Very good verification performance is achieved over thousands of trials for both color and infrared video sequences using the proposed system.

Multi-View Learning and Link Farm Discovery - Scheffer,T.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H (Probabilistic, Logical and Relational Learning-Towards a Synthesis, 2006)
The first part of this abstract focuses on estimation of mixture models for problems in which multiple views of the instances are available. Examples of this setting include clustering web pages or research papers that have intrinsic (text) and extrinsic (references) attributes. Mixture model estimation is a key problem for both semi-supervised and unsupervised learning. An appropriate optimization criterion quantifies the likelihood and the consensus among models in the individual views; maximizing this consensus minimizes a bound on the risk of assigning an instance to an incorrect mixture component. An EM algorithm maximizes this criterion. The second part of this abstract focuses on the problem of identifying link spam. Search engine optimizers inflate the page rank of a target site by spinning an artificial web for the sole purpose of providing inbound links to the target. Discriminating natural from artificial web sites is a difficult multi-view problem.

Name reference resolution in organizational email archives - Diehl,C. P; Getoor, Lise; Namata,G. (SIAM International Conference on Data Mining, 2006)

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

Numerical Analysis of Plasmon Resonances Based on Fast Multipole Method - Zhang,Zhenyu; Mayergoyz, Issak D; Gumerov, Nail A.; Duraiswami, Ramani (Electromagnetic Field Computation, 2006 12th Biennial IEEE Conference on, 2006)
A novel technique for the numerical analysis of plasmon resonances by using fast multipole method (FMM) is presented. This approach is based on the solution of eigenvalue problem for boundary integral equations, which can be naturally implemented by using the fast multipole method. Numerical examples that highlight the efficiency of the fast multipole implementation are reported
Keywords: analysis; plasmon; and; boundary; eigenfunctions; plasmons; equations; eigenvalue; equations; eigenvalues; integral; method; numerical; multipole; problem; fast; resonances; boundary

Oblivious network design - Gupta,A.; Hajiaghayi, Mohammad T.; R\äcke,H. (Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006)

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

Parallel syntactic annotation of multiple languages - Rambow,O.; Dorr, Bonnie J; Farwell,D.; Green,R.; Habash,N.; Helmreich,S.; Hovy,E.; Levin,L.; Miller,K.J.; Mitamura,T.; others (Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC2006). Genoa, Italy, 2006)
This paper describes an effort to investigate the incrementally deepening development of an interlingua notation, validated by humanannotation of texts in English plus six languages. We begin with deep syntactic annotation, and in this paper present a series of annotation manuals for six different languages at the deep-syntactic level of representation. Many syntactic differences between languages are removed in the proposed syntactic annotation, making them useful resources for multilingual NLP projects with semantic components.

Postmodern internetwork architecture - Bhattacharjee, Bobby; Calvert,K.; Griffioen,J.; Spring, Neil; Sterbenz,J. P.G (ITTC-FY2006-TR-45030-01, Information and Telecommunication Center, The University of Kansas, 2006)
Network-layer innovation has proven surprisingly difficult, in part because internetworking protocols ignore com-peting economic interests and because a few protocols dominate, enabling layer violations that entrench technologies. Many shortcomings of today’s internetwork layer result from its inflexibility with respect to the policies of the stake- holders: users and service providers. The consequences of these failings are well-known: various hacks, layering violations, and overloadings are introduced to enforce policies and attempt to get the upper hand in various “tus- sles”. The result is a network that is increasingly brittle, hostile to innovation, vulnerable to attack, and insensitive to concerns about accountability and privacy. Our project aims to design, implement, and evaluate through daily use a minimalist internetwork layer and aux- iliary functionality that anticipates tussles and allows them to be played out in policy space, as opposed to in the packet-forwarding path. We call our approach postmodern internetwork architecture, because it is a reaction against many established network layer design concepts. The overall goal of the project is to make a larger portion of the network design space accessible without sacrificing the economy of scale offered by the unified Internet. We will use the postmodern architecture to explore basic architectural questions. These include: • What mechanisms should be supported by the network such that any foreseeable policy requirement can be explicitly addressed? • To what extent can routing and forwarding be isolated from each other while maintaining an efficient and usable network? • What forms of identity should be visible within the network, and what forms of accountability do different identities enable? • What mechanisms are needed to enable efficient access to cross-layer information and mechanisms such that lower layers can express their characteristics and upper layers can exert control downward? We plan to build and evaluate a complete end-to-end networking layer to help us understand feasible solutions to these questions. The Internet has fulfilled the potential of a complete generation of networking research by producing a global platform for innovation, commerce, and democracy. Unfortunately, the Internet also amply demonstrates the com- plexity and architectural ugliness that ensue when competing interests vie for benefits beyond those envisioned in the original design. This project is about redesigning the waist of the architectural hourglass to foster innovation, enhance security and accountability, and accomodate competing interests.

PRL: A probabilistic relational language - Getoor, Lise; Grant,J. (Machine Learning, 2006)
In this paper, we describe the syntax and semantics for a probabilistic relational language (PRL). PRL is a recasting of recent work in Probabilistic Relational Models (PRMs) into a logic programming framework. We show how to represent varying degrees of complexity in the semantics including attribute uncertainty, structural uncertainty and identity uncertainty. Our approach is similar in spirit to the work in Bayesian Logic Programs (BLPs), and Logical Bayesian Networks (LBNs). However, surprisingly, there are still some important differences in the resulting formalism; for example, we introduce a general notion of aggregates based on the PRM approaches. One of our contributions is that we show how to support richer forms of structural uncertainty in a probabilistic logical language than have been previously described. Our goal in this work is to present a unifying framework that supports all of the types of relational uncertainty yet is based on logic programming formalisms. We also believe that it facilitates understanding the relationship between the frame-based approaches and alternate logic programming approaches, and allows greater transfer of ideas between them.

Probabilistic, Logical and Relational Learning-Towards a Synthesis - De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H; Lloyd,J. W; Sears,T. D; Milch,B.; Marthi,B.; Russell,S.; Sontag,D. (Dagstuhl Seminar Proceedings, 2006)

ProMo-A Scalable and Efficient Framework for Online Data Delivery - Roitman,H.; Gal,A.; Raschid, Louiqa (Lecture notes in computer science, 2006)

Quantifying the effects of routing dynamics on end-to-end Internet path failures - Wang,F.; Feamster, Nick; Gao,L. (University of Massachusetts, 2006)

Query-time entity resolution - BHATTACHARVA,I.; Getoor, Lise; Licamele,L. (International conference on knowledge discovery and data mining, 2006)
The goal of entity resolution is to reconcile database references corresponding to the same real-world entities. Given the abundance of publicly available databases where entities are not resolved, we motivate the problem of quickly processing queries that require resolved entities from such 'unclean' databases. We propose a two-stage collective resolution strategy for processing queries. We then show how it can be performed on-the-fly by adaptively extracting and resolving those database references that are the most helpful for resolving the query. We validate our approach on two large real-world publication databases where we show the usefulness of collective resolution and at the same time demonstrate the need for adaptive strategies for query processing. We then show how the same queries can be answered in real time using our adaptive approach while preserving the gains of collective resolution.

Ranking search results in P2P systems - Gopalakrishnan,V.; Morselli,R.; Bhattacharjee, Bobby; Keleher,P.; Srinivasan, Aravind (Technical Report, CR-TR-4779, Department of Computer Science, University of Maryland, 2006)
P2P deployments are a natural infrastructure for buildingdistributed 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, and not 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 distributed setting. We analyze the overhead of our approach, and quantify exactly 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 can scale with little overhead to large systems, and b) the accuracy of the results ob- tained using distributed ranking is comparable to a cen- tralized implementation.

Ranking search results in peer-to-peer systems - Gopalakrishnan,V.; Morselli,R.; Bhattacharjee, Bobby; Keleher,P.; Srinivasan, Aravind (Technical Reports from UMIACS, 2006)
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, and not 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 distributed setting. We analyze the overhead of our approach, and quantify exactly 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 can scale with little overhead to large systems, and b) the accuracy of the results obtained using distributed ranking is comparable to a centralized implementation.

Rational secret sharing, revisited - Gordon,S.; Katz, Jonathan (Security and Cryptography for Networks, 2006)
We consider the problem of secret sharing among n rational players. This problem was introduced by Halpern and Teague (STOC 2004), who claim that a solution is impossible for n=2 but show a solution for the case n≥3. Contrary to their claim, we show a protocol for rational secret sharing among n=2 players; our protocol extends to the case n≥3, where it is simpler than the Halpern-Teague solution and also offers a number of other advantages. We also show how to avoid the continual involvement of the dealer, in either our own protocol or that of Halpern and Teague.Our techniques extend to the case of rational players trying to securely compute an arbitrary function, under certain assumptions on the utilities of the players.