On the importance of sharing negative results - Giraud-Carrier,C.; Dunham,M.H.; Atreya,A.; Elkan,C.; Perlich,C.; Swirszcz,G.; Shi,X.; Philip,S.Y.; Fürnkranz,J.; Sima,J.F. (SIGKDD explorations, 2010)

Indirect two-sided relative ranking: a robust similarity measure for gene expression data - Licamele,L.; Getoor, Lise (BMC bioinformatics, 2010)
There is a large amount of gene expression data that exists in the public domain. This data has been generated under a variety of experimental conditions. Unfortunately, these experimental variations have generally prevented researchers from accurately comparing and combining this wealth of data, which still hides many novel insights. Results In this paper we present a new method, which we refer to as indirect two-sided relative ranking, for comparing gene expression profiles that is robust to variations in experimental conditions. This method extends the current best approach, which is based on comparing the correlations of the up and down regulated genes, by introducing a comparison based on the correlations in rankings across the entire database. Because our method is robust to experimental variations, it allows a greater variety of gene expression data to be combined, which, as we show, leads to richer scientific discoveries. Conclusions We demonstrate the benefit of our proposed indirect method on several datasets. We first evaluate the ability of the indirect method to retrieve compounds with similar therapeutic effects across known experimental barriers, namely vehicle and batch effects, on two independent datasets (one private and one public). We show that our indirect method is able to significantly improve upon the previous state-of-the-art method with a substantial improvement in recall at rank 10 of 97.03% and 49.44%, on each dataset, respectively. Next, we demonstrate that our indirect method results in improved accuracy for classification in several additional datasets. These datasets demonstrate the use of our indirect method for classifying cancer subtypes, predicting drug sensitivity/resistance, and classifying (related) cell types. Even in the absence of a known (i.e., labeled) experimental barrier, the improvement of the indirect method in each of these datasets is statistically significant.

Integrating structured metadata with relational affinity propagation - Plangprasopchok,A.; Lerman,K.; Getoor, Lise (In proceedings of AAAI Workshop on Statistical Relational AI, 2010)
Structured and semi-structured data describing entities, tax- onomies and ontologies appears in many domains. There is a huge interest in integrating structured information from multiple sources; however integrating structured data to in- fer complex common structures is a difficult task because the integration must aggregate similar structures while avoiding structural inconsistencies that may appear when the data is combined. In this work, we study the integration of struc- tured social metadata: shallow personal hierarchies specified by many individual users on the Social Web, and focus on in- ferring a collection of integrated, consistent taxonomies. We frame this task as an optimization problem with structural constraints. We propose a new inference algorithm, which we refer to as Relational Affinity Propagation (RAP) that ex- tends affinity propagation (Frey and Dueck 2007) by intro- ducing structural constraints. We validate the approach on a real-world social media dataset, collected from the photoshar- ing website Flickr. Our empirical results show that our pro- posed approach is able to construct deeper and denser struc- tures compared to an approach using only the standard affin- ity propagation algorithm.

Interlingual Annotation of Parallel Text Corpora: A New Framework for Annotation and Evaluation - Dorr, Bonnie J; Passonneau,Rebecca J.; Farwell,David; Green,Rebecca; Habash,Nizar; Helmreich,Stephen; Hovy,Eduard; Levin,Lori; Miller,Keith J.; Mitamura,Teruko; Rambow,Owen; Siddharthan,Advaith (Natural Language Engineering, 2010)
This paper focuses on an important step in the creation of a system of meaning representation and the development of semantically annotated parallel corpora, for use in applications such as machine translation, question answering, text summarization, and information retrieval. The work described below constitutes the first effort of any kind to annotate multiple translations of foreign-language texts with interlingual content. Three levels of representation are introduced: deep syntactic dependencies (IL0), intermediate semantic representations (IL1), and a normalized representation that unifies conversives, nonliteral language, and paraphrase (IL2). The resulting annotated, multilingually induced, parallel corpora will be useful as an empirical basis for a wide range of research, including the development and evaluation of interlingual NLP systems and paraphrase-extraction systems as well as a host of other research and development efforts in theoretical and applied linguistics, foreign language pedagogy, translation studies, and other related disciplines.

Investigating the impact of design processes on children - Guha,M.L.; Druin, Allison; Fails,J. A (Proceedings of the 9th International Conference on Interaction Design and Children, 2010)

Learning algorithms for link prediction based on chance constraints - Doppa,J.; Yu,J.; Tadepalli,P.; Getoor, Lise (Machine Learning and Knowledge Discovery in Databases, 2010)
In this paper, we consider the link prediction problem, where we are given a partial snapshot of a network at some time and the goal is to predict the additional links formed at a later time. The accuracy of current prediction methods is quite low due to the extreme class skew and the large number of potential links. Here, we describe learning algorithms based on chance constrained programs and show that they exhibit all the properties needed for a good link predictor, namely, they allow preferential bias to positive or negative class; handle skewness in the data; and scale to large networks. Our experimental results on three real-world domains—co-authorship networks, biological networks and citation networks—show significant performance improvement over baseline algorithms. We conclude by briefly describing some promising future directions based on this work.

A Learning Approach Towards Detection and Tracking of Lane Markings - Gopalan,R.; Hong, T.; Shneier, M.; Chellapa, Rama (IEEE Transactions on Intelligent Transportation Systems, 2010)
Road scene analysis is a challenging problem that has applications in autonomous navigation of vehicles. An integral component of this system is the robust detection and tracking of lane markings. It is a hard problem primarily due to large appearance variations in lane markings caused by factors such as occlusion (traffic on the road), shadows (from objects like trees), and changing lighting conditions of the scene (transition from day to night). In this paper, we address these issues through a learning-based approach using visual inputs from a camera mounted in front of a vehicle. We propose the following: 1) a pixel-hierarchy feature descriptor to model the contextual information shared by lane markings with the surrounding road region; 2) a robust boosting algorithm to select relevant contextual features for detecting lane markings; and 3) particle filters to track the lane markings, without knowledge of vehicle speed, by assuming the lane markings to be static through the video sequence and then learning the possible road scene variations from the statistics of tracked model parameters. We investigate the effectiveness of our algorithm on challenging daylight and night-time road video sequences.
Keywords: Boosting; Context; Context modeling; Feature extraction; lane marking detection; outlier robustness; Roads; tracking and learning; Training; Vehicles

Learning what and how of contextual models for scene labeling - Jain, A.; Gupta,A.; Davis, Larry S. (Computer Vision–ECCV 2010, 2010)
We present a data-driven approach to predict the importance of edges and construct a Markov network for image analysis based on statistical models of global and local image features. We also address the coupled problem of predicting the feature weights associated with each edge of a Markov network for evaluation of context. Experimental results indicate that this scene dependent structure construction model eliminates spurious edges and improves performance over fully-connected and neighborhood connected Markov network.

Loudspeaker and Microphone Array Signal Processing-Plane-Wave Decomposition of Acoustical Scenes Via Spherical and Cylindrical Microphone Arrays - Zotkin,Dmitry N; Duraiswami, Ramani; Gumerov, Nail A. (IEEE transactions on audio, speech, and language processing, 2010)

LP-rounding algorithms for facility-location problems - Byrka,Jaroslaw; Ghodsi,Mohammadreza; Srinivasan, Aravind (arXiv:1007.3611, 2010)
We study LP-rounding approximation algorithms for metric uncapacitated facility-location problems. We first give a new analysis for the algorithm of Chudak and Shmoys, which differs from the analysis of Byrka and Aardal in that now we do not need any bound based on the solution to the dual LP program. Besides obtaining the optimal bifactor approximation as do Byrka and Aardal, we can now also show that the algorithm with scaling parameter equaling 1.58 is, in fact, an 1.58-approximation algorithm. More importantly, we suggest an approach based on additional randomization and analyses such as ours, which could achieve or approach the conjectured optimal 1.46...--approximation for this basic problem. Next, using essentially the same techniques, we obtain improved approximation algorithms in the 2-stage stochastic variant of the problem, where we must open a subset of facilities having only stochastic information about the future demand from the clients. For this problem we obtain a 2.2975-approximation algorithm in the standard setting, and a 2.4957-approximation in the more restricted, per-scenario setting. We then study robust fault-tolerant facility location, introduced by Chechik and Peleg: solutions here are designed to provide low connection cost in case of failure of up to $k$ facilities. Chechik and Peleg gave a 6.5-approximation algorithm for $k=1$ and a ($7.5k + 1.5$)-approximation algorithm for general $k$. We improve this to an LP-rounding $(k+5+4/k)$-approximation algorithm. We also observe that in case of oblivious failures the expected approximation ratio can be reduced to $k + 1.5$, and that the integrality gap of the natural LP-relaxation of the problem is at least $k + 1$.
Keywords: Computer Science - Data Structures and Algorithms

ManyNets: an interface for multiple network analysis and visualization - Freire,Manuel; Plaisant, Catherine; Shneiderman, Ben; Golbeck,Jen (Proceedings of the 28th international conference on Human factors in computing systems, 2010)
Traditional network analysis tools support analysts in studying a single network. ManyNets offers these analysts a powerful new approach that enables them to work on multiple networks simultaneously. Several thousand networks can be presented as rows in a tabular visualization, and then inspected, sorted and filtered according to their attributes. The networks to be displayed can be obtained by subdivision of larger networks. Examples of meaningful subdivisions used by analysts include ego networks, community extraction, and time-based slices. Cell visualizations and interactive column overviews allow analysts to assess the distribution of attributes within particular sets of networks. Details, such as traditional node-link diagrams, are available on demand. We describe a case study analyzing a social network geared towards film recommendations by means of decomposition. A small usability study provides feedback on the use of the interface on a set of tasks issued from the case study.
Keywords: exploratory analysis; graphical user interface; Information Visualization; interaction; network analysis; table interface

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

Mesh saliency and human eye fixations - Kim,Youngmin; Varshney, Amitabh; Jacobs, David W.; Guimbretière,François (ACM Transactions on Applied Perception (TAP), 2010)
Mesh saliency has been proposed as a computational model of perceptual importance for meshes, and it has been used in graphics for abstraction, simplification, segmentation, illumination, rendering, and illustration. Even though this technique is inspired by models of low-level human vision, it has not yet been validated with respect to human performance. Here, we present a user study that compares the previous mesh saliency approaches with human eye movements. To quantify the correlation between mesh saliency and fixation locations for 3D rendered images, we introduce the normalized chance-adjusted saliency by improving the previous chance-adjusted saliency measure. Our results show that the current computational model of mesh saliency can model human eye movements significantly better than a purely random model or a curvature-based model.
Keywords: eye-tracker; mesh saliency; Visual perception

MetaPhyler: Taxonomic profiling for metagenomic sequences - Liu,Bo; Gibbons,T.; Ghodsi,M.; Pop, Mihai (2010 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), 2010)
A major goal of metagenomics is to characterize the microbial diversity of an environment. The most popular approach relies on 16S rRNA sequencing, however this approach can generate biased estimates due to differences in the copy number of the 16S rRNA gene between even closely related organisms, and due to PCR artifacts. The taxonomic composition can also be determined from whole-metagenome sequencing data by matching individual sequences against a database of reference genes. One major limitation of prior methods used for this purpose is the use of a universal classification threshold for all genes at all taxonomic levels. We propose that better classification results can be obtained by tuning the taxonomic classifier to each matching length, reference gene, and taxonomic level. We present a novel taxonomic profiler MetaPhyler, which uses marker genes as a taxonomic reference. Results on simulated datasets demonstrate that MetaPhyler outperforms other tools commonly used in this context (CARMA, Megan and PhymmBL). We also present interesting results obtained by applying MetaPhyler to a real metagenomic dataset.
Keywords: Bioinformatics; CARMA comparison; Databases; Genomics; Linear regression; marker genes; matching length; Megan comparison; metagenomic sequences; metagenomics; MetaPhyler; microbial diversity; microorganisms; molecular biophysics; molecular configurations; Pattern classification; pattern matching; phylogenetic classification; Phylogeny; PhymmBL comparison; reference gene database; Sensitivity; sequence matching; taxonomic classifier; taxonomic level; taxonomic profiling; whole metagenome sequencing data

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

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

Methods for efficient implementation of Model Predictive Control on multiprocessor systems - Gu, Ruirui; Bhattacharyya, Shuvra S.; Levine,W. S (2010 IEEE International Conference on Control Applications (CCA), 2010)
Model Predictive Control (MPC) has been used in a wide range of application areas including chemical engineering, food processing, automotive engineering, aerospace, and metallurgy. An important limitation on the application of MPC is the difficulty in completing the necessary computations within the sampling interval. Recent trends in computing hardware towards greatly increased parallelism offer a solution to this problem. This paper describes modeling and analysis tools to facilitate implementing the MPC algorithms on parallel computers, thereby greatly reducing the time needed to complete the calculations. The use of these tools is illustrated by an application to a class of MPC problems.
Keywords: Computational modeling; COMPUTERS; Equations; Hardware; Linear systems; Mathematical model; model predictive control; MPC algorithms; Multiprocessing systems; Multiprocessor systems; parallel computers; predictive control; Program processors

Mobile collaboration: collaboratively reading and creating children's stories on mobile devices - Fails,J. A; Druin, Allison; Guha,M.L. (Proceedings of the 9th International Conference on Interaction Design and Children, 2010)

A new framework for efficient password-based authenticated key exchange - Groce,Adam; Katz, Jonathan (Proceedings of the 17th ACM conference on Computer and communications security, 2010)
Protocols for password-based authenticated key exchange (PAKE) allow two users who share only a short, low-entropy password to agree on a cryptographically strong session key. The challenge in designing such protocols is that they must be immune to off-line dictionary attacks in which an eavesdropping adversary exhaustively enumerates the dictionary of likely passwords in an attempt to match a password to the set of observed transcripts. To date, few general frameworks for constructing PAKE protocols in the standard model are known. Here, we abstract and generalize a protocol by Jiang and Gong to give a new methodology for realizing PAKE without random oracles, in the common reference string model. In addition to giving a new approach to the problem, the resulting construction off ers several advantages over prior work. We also describe an extension of our protocol that is secure within the universal composability (UC) framework and, when instantiated using El Gamal encryption, is more efficient than a previous protocol of Canetti et al.
Keywords: exchange; key; password-based

A New Framework for Password-Based Authenticated Key Exchange - Groce,Adam; Katz, Jonathan (ACM CCCS 2010, 2010)
Protocols for password-based authenticated key exchange (PAKE) allowtwo users who share only a short, low-entropy password to agree on a cryptographically strong session key. The challenge in designing such protocols is that they must be immune to off-line dictionary attacks in which an eavesdropping adversary exhaustively enumerates the dictionary of likely passwords in an attempt to match a password to the set of observed transcripts. To date, few general frameworks for constructing PAKE protocols in the standard model are known. Here, we abstract and generalize a protocol by Jiang and Gong to give a new methodology for realizing PAKE without random oracles, in the common reference string model. In addition to giving a new approach to the problem, the resulting construction offers several advantages over prior work. We also describe an extension of our protocol that is secure within the universal composability~(UC) framework and, when instantiated using El Gamal encryption, is more efficient than a previous protocol of Canetti et al.
Keywords: Cryptographic protocols; password-based key exchange

Object Classification Using Taxonomies - Tsaparas,Panayiotis; Papadimitriou,Panagiotis; Fuxman,Ariel D.; Getoor, Lise; Agrawal,Rakesh (2010)
As provided herein objects from a source catalog, such as a provider's catalog, can be added to a target catalog, such as an enterprise master catalog, in a scalable manner utilizing catalog taxonomies. A baseline classifier determines probabilities for source objects to target catalog classes. Source objects can be assigned to those classes with probabilities that meet a desired threshold and meet a desired rate. A classification cost for target classes can be determined for respective unassigned source objects, which can comprise determining an assignment cost and separation cost for the source objects for respective desired target classes. The separation and assignment costs can be combined to determine the classification cost, and the unassigned source objects can be assigned to those classes having a desired classification cost.

Occurrence of the Vibrio cholerae seventh pandemic VSP-I island and a new variant - Grim,Christopher J.; Choi,Jinna; Jongsik Chun; Jeon,Yoon-Seong; Taviani,Elisa; Hasan,Nur A.; Haley,Bradd; Huq,Anwar; Rita R Colwell (OMICS: A Journal of Integrative Biology, 2010)

One experience collecting sensitive mobile data - Niu, Y.; Elaine Shi; Chow, R.; Golle, P.; Jakobsson, M. (2010)
We report on our efforts to collect behavioral data basedon activities recorded by phones. We recruited Android de- vice owners and offered entry into a raffle for participants. Our application was distributed from the Android Market, and its placement there unexpectedly helped us find par- ticipants from casual users browsing for free applications. We collected data from 267 total participants who gave us varying amounts of data.

Parsimonious rule generation for a nature-inspired approach to self-assembly - Grushin,A.; Reggia, James A. (ACM Transactions on Autonomous and Adaptive Systems (TAAS), 2010)

Partial fairness in secure two-party computation - Gordon,S.; Katz, Jonathan (Advances in Cryptology–EUROCRYPT 2010, 2010)
A seminal result of Cleve (STOC ’86) is that complete fairness is impossible to achieve in two-party computation. In light of this, various techniques for obtaining partial fairness have been suggested in the literature. We propose a definition of partial fairness within the standard real-/ideal-world paradigm that addresses deficiencies of prior definitions. We also show broad feasibility results with respect to our definition: partial fairness is possible for any (randomized) functionality f:X ×Y →Z 1 ×Z 2 at least one of whose domains or ranges is polynomial in size. Our protocols are always private, and when one of the domains has polynomial size our protocols also simultaneously achieve the usual notion of security with abort. In contrast to some prior work, we rely on standard assumptions only.We also show that, as far as general feasibility is concerned, our results are optimal (with respect to our definition).

Plane-Wave Decomposition of Acoustical Scenes Via Spherical and Cylindrical Microphone Arrays - Zotkin,Dmitry N; Duraiswami, Ramani; Gumerov, Nail A. (IEEE Transactions on Audio, Speech, and Language Processing, 2010)
Spherical and cylindrical 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. Beamforming and scene analysis for such arrays is typically done using sound field representation in terms of orthogonal basis functions (spherical/cylindrical harmonics). In this paper, an alternative sound field representation in terms of plane waves is described, and a method for estimating it directly from measurements at microphones is proposed. It is shown that representing a field as a collection of plane waves arriving from various directions simplifies source localization, beamforming, and spatial audio playback. A comparison of the new method with the well-known spherical harmonics based beamforming algorithm is done, and it is shown that both algorithms can be expressed in the same framework but with weights computed differently. It is also shown that the proposed method can be extended to cylindrical arrays. 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 spherical array.
Keywords: Acoustic fields; acoustic position measurement; acoustic signal processing; acoustic waves; acoustical scene analysis; array signal processing; circular arrays; cylindrical microphone arrays; direction-independent acoustic behavior; microphone arrays; orthogonal basis functions; plane-wave decomposition; Position measurement; signal reconstruction; sound field reconstruction; sound field representation; source localization; spatial audio playback; spherical harmonics based beamforming algorithm; spherical microphone arrays

The pre‐seventh pandemic Vibrio cholerae BX 330286 El Tor genome: evidence for the environment as a genome reservoir - Haley,Bradd J.; Grim,Christopher J.; Hasan,Nur A.; Taviani,Elisa; Jongsik Chun; Brettin,Thomas S.; Bruce,David C.; Challacombe,Jean F.; Detter,J. Chris; Han,Cliff S.; Huq,Anwar; Nair,G. Balakrish; et al. (Environmental Microbiology Reports, 2010)
Vibrio cholerae O1 El Tor BX 330286 was isolated from a water sample in Australia in 1986, 9 years after an indigenous outbreak of cholera occurred in that region. This environmental strain encodes virulence factors highly similar to those of clinical strains, suggesting an ability to cause disease in humans. We demonstrate its high similarity in gene content and genome-wide nucleotide sequence to clinical V. cholerae strains, notably to pre-seventh pandemic O1 El Tor strains isolated in 1910 (V. cholerae NCTC 8457) and 1937 (V. cholerae MAK 757), as well as seventh pandemic strains isolated after 1960 globally. Here we demonstrate that this strain represents a transitory clone with shared characteristics between pre-seventh and seventh pandemic strains of V. cholerae. Interestingly, this strain was isolated 25 years after the beginning of the seventh pandemic, suggesting the environment as a genome reservoir in areas where cholera does not occur in sporadic, endemic or epidemic form.

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

Read-once functions and query evaluation in probabilistic databases - Sen,Prithviraj; Deshpande, Amol; Getoor, Lise (Proc. VLDB Endow., 2010)
Probabilistic databases hold promise of being a viable means for large-scale uncertainty management, increasingly needed in a number of real world applications domains. However, query evaluation in probabilistic databases remains a computational challenge. Prior work on efficient exact query evaluation in probabilistic databases has largely concentrated on query-centric formulations (e.g., safe plans, hierarchical queries), in that, they only consider characteristics of the query and not the data in the database. It is easy to construct examples where a supposedly hard query run on an appropriate database gives rise to a tractable query evaluation problem. In this paper, we develop efficient query evaluation techniques that leverage characteristics of both the query and the data in the database. We focus on tuple-independent databases where the query evaluation problem is equivalent to computing marginal probabilities of Boolean formulas associated with the result tuples. This latter task is easy if the Boolean formulas can be factorized into a form that has every variable appearing at most once (called read-once). However, a naive approach that directly uses previously developed Boolean formula factorization algorithms is inefficient, because those algorithms require the input formulas to be in the disjunctive normal form (DNF). We instead develop novel, more efficient factorization algorithms that directly construct the read-once expression for a result tuple Boolean formula (if one exists), for a large subclass of queries (specifically, conjunctive queries without self-joins). We empirically demonstrate that (1) our proposed techniques are orders of magnitude faster than generic inference algorithms for queries where the result Boolean formulas can be factorized into read-once expressions, and (2) for the special case of hierarchical queries, they rival the efficiency of prior techniques specifically designed to handle such queries.

REPORTS AI Theory and Practice: A Discussion on Hard Challenges and Opportunities Ahead - Horvitz,E.; Getoor, Lise; Guestrin,C.; Hendler,J.; Kautz,H.; Konstan,J.; Subramanian,D.; Wellman,M. (AI Magazine, 2010)

A Review of Bird-Inspired Flapping Wing Miniature Air Vehicle Designs - Gerdes,John W.; Gupta, Satyandra K.; Wilkerson,Stephen A. (ASME, 2010)
Physical and aerodynamic characteristics of the bird in flight may offer benefits over typical propeller or rotor driven miniature air vehicle (MAV) locomotion designs in certain types of scenarios. A number of research groups and companies have developed flapping wing vehicles that attempt to harness these benefits. The purpose of this paper is to report different types of flapping wing designs and compare their salient characteristics. For each category, advantages and disadvantages will be discussed. The discussion presented will be limited to miniature-sized flapping wing air vehicles, defined as 10–100 grams total weight. The discussion will be focused primarily on ornithopters which have performed at least one successful test flight. Additionally, this paper is intended to provide a representation of the field of current technology, rather than providing a comprehensive listing of all possible designs. This paper will familiarize a newcomer to the field with existing designs and their distinguishing features. By studying existing designs, future designers will be able to adopt features from other successful designs. This paper also summarizes the design challenges associated with the further advancement of the field and deploying flapping wing vehicles in practice.

A robust and scalable approach to face identification - Schwartz,W.; Guo,H.; Davis, Larry S. (Computer Vision–ECCV 2010, 2010)
The problem of face identification has received significant attention over the years. For a given probe face, the goal of face identification is to match this unknown face against a gallery of known people. Due to the availability of large amounts of data acquired in a variety of conditions, techniques that are both robust to uncontrolled acquisition conditions and scalable to large gallery sizes, which may need to be incrementally built, are challenges. In this work we tackle both problems. Initially, we propose a novel approach to robust face identification based on Partial Least Squares (PLS) to perform multi-channel feature weighting. Then, we extend the method to a tree-based discriminative structure aiming at reducing the time required to evaluate novel probe samples. The method is evaluated through experiments on FERET and FRGC datasets. In most of the comparisons our method outperforms state-of-art face identification techniques. Furthermore, our method presents scalability to large datasets.

Secure network coding over the integers - Gennaro,R.; Katz, Jonathan; Krawczyk,H.; Rabin,T. (Public Key Cryptography–PKC 2010, 2010)
Network coding offers the potential to increase throughput and improve robustness without any centralized control. Unfortunately, network coding is highly susceptible to “pollution attacks” in which malicious nodes modify packets improperly so as to prevent message recovery at the recipient(s); such attacks cannot be prevented using standard end-to-end cryptographic authentication because network coding mandates that intermediate nodes modify data packets in transit.Specialized “network coding signatures” addressing this problem have been developed in recent years using homomorphic hashing and homomorphic signatures. We contribute to this area in several ways: • We show the first homomorphic signature scheme based on the RSA assumption (in the random oracle model). • We give a homomorphic hashing scheme that is more efficient than existing schemes, and which leads to network coding signatures based on the hardness of factoring (in the standard model). • We describe variants of existing schemes that reduce the communication overhead for moderate-size networks, and improve computational efficiency (in some cases quite dramatically – e.g., we achieve a 20-fold speedup in signature generation at intermediate nodes). Underlying our techniques is a modified approach to random linear network coding where instead of working in a vector space over a field, we work in a module over the integers (with small coefficients).

Stochastic simulations with graphics hardware: Characterization of accuracy and performance - Balijepalli,A.; LeBrun,T. W.; Gupta,S.K. (Journal of Computing and Information Science in Engineering, 2010)

Strategy generation in multi-agent imperfect-information pursuit games - Raboin,Eric; Nau, Dana S.; Kuter,Ugur; Gupta, Satyandra K.; Svec,Petr (International Foundation for Autonomous Agents and Multiagent Systems, 2010)
We describe a formalism and algorithms for game-tree search in partially-observable Euclidean space, and implementation and tests in a scenario where a multi-agent team, called tracking agents, pursues a target agent that wants to evade the tracking agents. Our contributions include--- • A formalism that combines geometric elements (agents' locations and trajectories and observable regions, and obstacles that restrict mobility and observability) with game-theoretic elements (information sets, utility functions, and strategies). • A recursive formula for information-set minimax values based on our formalism, and a implementation of the formula in a game-tree search algorithm. • A heuristic evaluation function for use at the leaf nodes of the game-tree search. It works by doing a quick lookahead search of its own, in a relaxed version of the problem. • Experimental results in 500 randomly generated trials. With the strategies generated by our heuristic, the tracking agents were more than twice as likely to know the target agent's location at the end of the game than with the strategies generated by heuristics that compute estimates of the target's possible locations.
Keywords: game tree search; multi-agent planning; visibility-based pursuit-evasion games

Summary of the first ACM SIGKDD workshop on knowledge discovery from uncertain data (U'09) - Pei,Jian; Getoor, Lise; de Keijzer,Ander (ACM SIGKDD Explorations Newsletter, 2010)

A survey of link mining tasks for analyzing noisy and incomplete networks - Namata,G.M.; Sharara,H.; Getoor, Lise (Link Mining: Models, Algorithms, and Applications, 2010)
Many data sets of interest today are best described as networks or graphs of interlinked entities. Examples include Web and text collections, social networks and social media sites, information, transaction and communication networks, and all manner of scientific networks, including biological networks. Unfortunately, often the data collection and extraction process for gathering these network data sets is imprecise, noisy, and/or incomplete. In this chapter, we review a collection of link mining algorithms that are well suited to analyzing and making inferences about networks, especially in the case where the data is noisy or missing.

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

A Systematic Methodology for Accurate Design-Stage Estimation of Energy Consumption for Injection Molded Parts - Weissman,A.; Ananthanarayanan,A.; Gupta,S.K.; Sriram,R.D. (2010)
Today's ubiquitous use of plastics in product designand manufacturing presents significant environmental and human health challenges. Injection molding, one of the most commonly used processes for making plastic products, consumes a significant amount of energy. A methodology for accurately estimating the energy consumed to injection-mold a part would enable environmentally conscious decision making during the product design. Unfortunately, only limited information is available at the design stage. Therefore, accurately estimating energy consumption before the part has gone into production can be challenging. In this paper, we describe a methodology for energy estimation that works with the limited amount of data available during the design stage, namely the CAD model of the part, the material name, and the production requirements. This methodology uses this data to estimate the parameters of the runner system and an appropriately sized molding machine. It then uses these estimates to compute the machine setup time and the cycle time required for the injection molding operation. This is done by appropriately abstracting information available from the mold flow simulation tools and analytical models that are traditionally used during the manufacturing stage. These times are then multiplied by the power consumed by the appropriately sized machine during each stage of the molding cycle to compute the estimated energy consumption per part.

Toque: designing a cooking-based programming language for and with children - Tarkan,S.; Sazawal,V.; Druin, Allison; Golub,E.; Bonsignore,E. M; Walsh,G.; Atrash,Z. (Proceedings of the 28th international conference on Human factors in computing systems, 2010)

On trade-offs in event delivery systems - Roitman,H.; Gal,A.; Raschid, Louiqa (Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems, 2010)

Using friendship ties and family circles for link prediction - Zheleva,E.; Getoor, Lise; Golbeck,J.; Kuter,U. (Advances in Social Network Mining and Analysis, 2010)
Social networks can capture a variety of relationships among the participants. Both friendship and family ties are commonly studied, but most existing work studies them in isolation. Here, we investigate how these networks can be overlaid, and propose a feature taxonomy for link prediction. We show that when there are tightly-knit family circles in a social network, we can improve the accuracy of link prediction models. This is done by making use of the family circle features based on the likely structural equivalence of family members. We investigated the predictive power of overlaying friendship and family ties on three real-world social networks. Our experiments demonstrate significantly higher prediction accuracy (between 15% and 30% more accurate) compared to using more traditional features such as descriptive node attributes and structural features. The experiments also show that a combination of all three types of attributes results in the best precision-recall trade-off.

Validating the systematic position of ıt Plationus Segers, Murugan & Dumont, 1993 (Rotifera: Brachionidae) using sequences of the large subunit of the nuclear ribosomal DNA and of cytochrome C oxidase - Reyna-Fabian,ME; Laclette,J. P; Cummings, Michael P.; García-Varela,M (Hydrobiologia, 2010)
Members of the family Brachionidae are free-living organisms that range in size from 170 to 250 microns. They comprise part of the zooplankton in freshwater and marine systems worldwide. Morphologically, members of the family are characterized by a single piece loricated body without furrows, grooves, sulci or dorsal head shields, and a malleate trophi. Differences in these structures have been traditionally used to recognize 217 species that are classified into seven genera. However, the validity of the species, Plationus patulus, P. patulus macracanthus P. polyacanthus, and P. felicitas have been confused because they were alternatively assigned in Brachionus or Platyias, when considering only morphological and ecological characters. Based on scanning electron microscope (SEM) images of the trophi, these taxa were assigned in a new genus, Plationus. In this study, we examined the systematic position of P. patulus and P. patulus macracanthus using DNA sequences of two genes: the cytochrome oxidase subunit 1 (cox1) and domains D2 and D3 of the large subunit of the nuclear ribosomal RNA (LSU). In addition, the cox1 and LSU sequences representing five genera of Brachionidae (Anuraeopsis, Brachionus, Keratella, Plationus, and Platyias) plus four species of three families from the order Ploima were used as the outgroup. The maximum likelihood (ML) analyses were conducted for each individual gene as well as for the combined (cox1 + LSU) data set. The ML tree from the combined data set yielded the family Brachionidae as a monophyletic group with weak bootstrap support (< 50%). Five main clades in this tree had high (> 85%) bootstrap support. The first clade was composed of three populations of P. patulus + P. patulus macracanthus. The second clade was composed of a single species of Platyias. The third clade was composed of six species of Brachionus. The fourth clade included a single species of the genus Anuraeopsis, and the fifth clade was composed of three species of the genus Keratella. The genetic divergence between Plationus and Platyias ranged from 18.4 to 19.2% for cox1, and from 4.5 to 4.9% for LSU, and between Brachionus and Plationus, it ranged from 16.9 to 23.1% (cox1), and from 7.3 to 9.1% (LSU). Morphological evidence, the amount of genetic divergence, the systematic position of Plationus within the family Brachionidae, and the position of Plationus as a sister group of Brachionus and Platyias support the validity of Plationus patulus and P. patulus macracanthus into the genus Plationus.
Keywords: Cox1; likelihood; LSU; maximum; Phylogeny; Plationus

VAST 2010 Challenge: Arms dealings and pandemics - Grinstein,G.; Konecni,S.; Scholtz,J.; Whiting,M.; Plaisant, Catherine (Visual Analytics Science and Technology (VAST), 2010 IEEE Symposium on, 2010)
The 5th VAST Challenge consisted of three mini-challenges that involved both intelligence analysis and bioinformatics. Teams could solve one, two or all three mini-challenges and assess the overall situation to enter the Grand Challenge. Mini-challenge one involved text reports about people and events giving information about arms dealers, situations in various countries and linkages between different countries. Mini-challenge two involved hospital admission and death records from various countries providing information about the spread of a world wide pandemic. Mini-challenge three involved genetic data to be used to identify the origin of the pandemic and the most dangerous viral mutations. The Grand Challenge was to determine how these various mini-challenges were connected. As always the goal was to analyze the data and provide novel interactive visualizations useful in the analytic process. We received 58 submissions in total and gave 15 awards.
Keywords: 2010; administrative; admission; intelligence; analysis; interactive; analysis; medical; challenge; arms; challenge; hospital; data; data; grand; dealings; bioinformatics; dangerous; mutations; death; processing; weapons; records; genetic; reports; bioinformatics; data; VAST; viral; visualizations; minichallenge; pandemics; text

Video Metrology Using a Single Camera - Guo,Feng; Chellapa, Rama (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2010)
This paper presents a video metrology approach using an uncalibrated single camera that is either stationary or in planar motion. Although theoretically simple, measuring the length of even a line segment in a given video is often a difficult problem. Most existing techniques for this task are extensions of single image-based techniques and do not achieve the desired accuracy especially in noisy environments. In contrast, the proposed algorithm moves line segments on the reference plane to share a common endpoint using the vanishing line information followed by fitting multiple concentric circles on the image plane. A fully automated real-time system based on this algorithm has been developed to measure vehicle wheelbases using an uncalibrated stationary camera. The system estimates the vanishing line using invariant lengths on the reference plane from multiple frames rather than the given parallel lines, which may not exist in videos. It is further extended to a camera undergoing a planar motion by automatically selecting frames with similar vanishing lines from the video. Experimental results show that the measurement results are accurate enough to classify moving vehicles based on their size.
Keywords: camera; vanishing; circles; uncalibrated; concentric; image-based; information; vehicle; line; measurement; video; metrology; cameras; image; processing; segment; multiple; segmentation; video; signal; single; techniques; line; wheelbase

When is it better not to look ahead? - Nau, Dana S.; Luštrek,Mitja; Parker,Austin; Bratko,Ivan; Gams,Matjaž (Artificial Intelligence, 2010)
In situations where one needs to make a sequence of decisions, it is often believed that looking ahead will help produce better decisions. However, it was shown 30 years ago that there are “pathological” situations in which looking ahead is counterproductive. Two long-standing open questions are (a) what combinations of factors have the biggest influence on whether lookahead pathology occurs, and (b) whether it occurs in real-world decision-making.This paper includes simulation results for several synthetic game-tree models, and experimental results for three well-known board games: two chess endgames, kalah (with some modifications to facilitate experimentation), and the 8-puzzle. The simulations show the interplay between lookahead pathology and several factors that affect it; and the experiments confirm the trends predicted by the simulation models. The experiments also show that lookahead pathology is more common than has been thought: all three games contain situations where it occurs.
Keywords: Game-tree search; Lookahead pathology; minimax

Who's Hogging the Bandwidth: The Consequences of Revealing the Invisible in the Home - Marshini Chetty; Banks, Richard; Harper, Richard; Regan, Tim; Sellen, Abigail; Gkantsidis, Christos; Karagiannis, Thomas; Key, Peter (SIGCHI '10, 2010)
As more technologies enter the home, householders are burdened with the task of digital housekeeping-managing and sharing digital resources like bandwidth. In response to this, we created and evaluated a domestic tool for bandwidth management called Home Watcher. Our field trial showed that when resource contention amongst different household members is made visible, people's understanding of bandwidth changes and household politics are revealed. In this paper, we describe the consequences of showing real time resource usage in a home, and how this varies depending on the social make up of the household.
Keywords: bandwidth monitoring; home broadband; home networks

Advancing User-Centered Evaluation of Visual Analytic Environments Through Contests - Costello,Loura; Grinstein,Georges; Plaisant, Catherine; Scholtz,Jean (Information VisualizationInformation Visualization, 2009)
In this paper, the authors describe the Visual Analytics Science and Technology (VAST) Symposium contests run in 2006 and 2007 and the VAST 2008 and 2009 challenges. These contests were designed to provide researchers with a better understanding of the tasks and data that face potential end users. Access to these end users is limited because of time constraints and the classified nature of the tasks and data. In that respect, the contests serve as an intermediary, with the metrics and feedback serving as measures of utility to the end users. The authors summarize the lessons learned and the future directions for VAST Challenges.
Keywords: metrics; synthetic data; user-centered evaluation; visual analytics

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

Algorithms for extraction of nanowire lengths and positions from optical section microscopy image sequence - Peng,T.; Balijepalli,A.; Gupta,S.K.; LeBrun,T. W. (Journal of Computing and Information Science in Engineering, 2009)

Algorithms for generating multi-stage molding plans for articulated assemblies - Priyadarshi,Alok K.; Gupta, Satyandra K. (Robotics and Computer-Integrated Manufacturing, 2009)
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 gives rise to a new type of planning problem. It is difficult to perform the planning manually because it involves evaluating large number of combinations and solving complex geometric reasoning problems. This paper investigates the problem of generating multi-stage molding plans for articulated assemblies. We present a planning framework that allows us to utilize constraints from experimentally proven molding plans. As a part of the planning problem, we determine the molding sequence and intermediate assembly configurations. We present algorithms for all the steps in the planning problem and characterize their computational complexities. Finally, we illustrate our approach with representative examples.
Keywords: In-mold assembly; mold design; Process planning

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

Arabic Cross-Document Coreference Resolution - Sayeed,A.; Elsayed,T.; Garera,N.; Alexander,D.; Xu,T.; Oard, Douglas; Yarowsky,D.; Piatko,C. (Proceedings of the ACL-IJCNLP 2009 Conference Short Papers$}$, 2009)

An assessment of systems and software engineering scholars and institutions (2002–2006) - Wong,W. Eric; Tse,T.H.; Glass,Robert L.; Basili, Victor R.; Chen,T.Y. (Journal of Systems and Software, 2009)
This paper summarizes a survey of publications in the field of systems and software engineering from 2002 to 2006. The survey is an ongoing, annual event that identifies the top 15 scholars and institutions over a 5-year period. The rankings are calculated based on the number of papers published in TSE, TOSEM, JSS, SPE, EMSE, IST, and Software. The top-ranked institution is Korea Advanced Institute of Science and Technology, Korea, and the top-ranked scholar is Magne Jørgensen of Simula Research Laboratory, Norway.
Keywords: Research publications; Systems and software engineering; Top institutions; Top scholars

Attacking cryptographic schemes based on "perturbation polynomials" - Albrecht,Martin; Gentry,Craig; Halevi,Shai; Katz, Jonathan (Proceedings of the 16th ACM conference on Computer and communications security, 2009)
We show attacks on several cryptographic schemes that have recently been proposed for achieving various security goals in sensor networks. Roughly speaking, these schemes all use "perturbation polynomials" to add "noise" to polynomialbased systems that offer information-theoretic security, in an attempt to increase the resilience threshold while maintaining efficiency. We show that the heuristic security arguments given for these modified schemes do not hold, and that they can be completely broken once we allow even a slight extension of the parameters beyond those achieved by the underlying information-theoretic schemes. Our attacks apply to the key predistribution scheme of Zhang et al. (MobiHoc 2007), the access-control schemes of Subramanian et al. (PerCom 2007), and the authentication schemes of Zhang et al. (INFOCOM 2008). Our results cast doubt on the viability of using "perturbation polynomials" for designing secure cryptographic schemes.
Keywords: pairwise key establishment; random perturbation polynomial; sensor network security

Bisimulation-based approximate lifted inference - Sen,Prithviraj; Deshpande, Amol; Getoor, Lise (Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, 2009)
There has been a great deal of recent interest in methods for performing lifted inference; however, most of this work assumes that the first-order model is given as input to the system. Here, we describe lifted inference algorithms that determine symmetries and automatically lift the probabilistic model to speedup inference. In particular, we describe approximate lifted inference techniques that allow the user to trade off inference accuracy for computational efficiency by using a handful of tunable parameters, while keeping the error bounded. Our algorithms are closely related to the graph-theoretic concept of bisimulation. We report experiments on both synthetic and real data to show that in the presence of symmetries, run-times for inference can be improved significantly, with approximate lifted inference providing orders of magnitude speedup over ground inference.

A broadband fast multipole accelerated boundary element method for the three dimensional Helmholtz equation - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2009)
The development of a fast multipole method (FMM) accelerated iterative solution of the boundary element method (BEM) for the Helmholtz equations in three dimensions is described. The FMM for the Helmholtz equation is significantly different for problems with low and high kD (where k is the wavenumber and D the domain size), and for large problems the method must be switched between levels of the hierarchy. The BEM requires several approximate computations (numerical quadrature, approximations of the boundary shapes using elements), and these errors must be balanced against approximations introduced by the FMM and the convergence criterion for iterative solution. These different errors must all be chosen in a way that, on the one hand, excess work is not done and, on the other, that the error achieved by the overall computation is acceptable. Details of translation operators for low and high kD, choice of representations, and BEM quadrature schemes, all consistent with these approximations, are described. A novel preconditioner using a low accuracy FMM accelerated solver as a right preconditioner is also described. Results of the developed solvers for large boundary value problems with 0.0001≲kD≲500 are presented and shown to perform close to theoretical expectations.
Keywords: acoustic wave scattering; boundary-elements methods; boundary-value problems; Helmholtz equations; iterative methods

Chance-constrained programs for link prediction - Doppa,J.R.; Yu,J.; Tadepalli,P.; Getoor, Lise (Proceedings of Workshop on Analyzing Networks and Learning with Graphs at NIPS Conference, 2009)
In this paper, we consider the link prediction problem, where we are given a par-tial snapshot of a network at some time and the goal is to predict additional links at a later time. The accuracy of the current prediction methods is quite low due to the extreme class skew and the large number of potential links. In this paper, we describe learning algorithms based on chance constrained programs and show that they exhibit all the properties needed for a good link predictor, namely, al- low preferential bias to positive or negative class; handle skewness in the data; and scale to large networks. Our experimental results on three real-world co- authorship networks show significant improvement in prediction accuracy over baseline algorithms.

Characterization and control of pin diameter during in-mold assembly of mesoscale revolute joints - Ananthanarayanan,A.; Gupta,S.K.; Bruck,H. A. (North American Manufacturing Research Institute, 2009)
Macro-scale revolute joints can be formed byfirst molding the hole and then molding the pin inside the hole. As the pin shrinks during the solidification process, it moves away from the hole and provides the clearance for the joint to function. The value of clearance in the macro- scale joint can be controlled by carefully selecting the process parameters and the material for the pin. However, in order for this strategy to work at the mesoscale, it requires the use of very thin cores to form sub-millimeter holes. Such thin cores are very difficult to make, are easily damaged during the molding process, and very difficult to retract from the hole. Our previous work has shown that making the pins first and then creating holes on the top of pins leads to successful mesoscale joints. This strategy is counter intuitive based on our experiences at the macro-scale. At the macroscale, as the hole shrinks on top of the pin, the joint is jammed. So a fundamental question is why this counter-intuitive strategy works at the mesoscale. In this paper we show that at the mesoscale, the joint jamming is prevented because of the deformation of the pin under the compressive loading during the second stage molding. We also describe features in the mold that can control the pin deformation and hence control the joint parameters. We present experimental data and computational models to show how mesoscale revolute joints can be formed.

Co-evolution of social and affiliation networks - Zheleva,Elena; Sharara,Hossam; Getoor, Lise (Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009)
In our work, we address the problem of modeling social network generation which explains both link and group formation. Recent studies on social network evolution propose generative models which capture the statistical properties of real-world networks related only to node-to-node link formation. We propose a novel model which captures the co-evolution of social and affiliation networks. We provide surprising insights into group formation based on observations in several real-world networks, showing that users often join groups for reasons other than their friends. Our experiments show that the model is able to capture both the newly observed and previously studied network properties. This work is the first to propose a generative model which captures the statistical properties of these complex networks. The proposed model facilitates controlled experiments which study the effect of actors' behavior on the evolution of affiliation networks, and it allows the generation of realistic synthetic datasets.
Keywords: affiliation network; Evolution; graph generator; groups; social network

Collective classification for text classification - Namata,G.; Sen,P.; Bilgic,M.; Getoor, Lise (Text Mining: Classification, Clustering, and ApplicationsText Mining: Classification, Clustering, and Applications, 2009)

Collective relational clustering - Bhattacharya,I.; Getoor, Lise (Constrained Clustering: Advances in Algorithms, Theory, and ApplicationsConstrained Clustering: Advances in Algorithms, Theory, and Applications, 2009)

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

Comparative genomics reveals mechanism for short-term and long-term clonal transitions in pandemic Vibrio cholerae - Chun,J.; Grim,C. J.; Hasan,N. A.; Lee,J. H.; Choi,S. Y.; Haley,B. J.; Taviani,E.; Jeon,Y. S.; Kim,D.W.; Lee,J. H.; Rita R Colwell (Proceedings of the National Academy of Sciences, 2009)
Vibrio cholerae, the causative agent of cholera, is a bacterium autochthonous to the aquatic environment, and a serious public health threat. V. cholerae serogroup O1 is responsible for the previous two cholera pandemics, in which classical and El Tor biotypes were dominant in the sixth and the current seventh pandemics, respectively. Cholera researchers continually face newly emerging and reemerging pathogenic clones carrying diverse combinations of phenotypic and genotypic properties, which significantly hampered control of the disease. To elucidate evolutionary mechanisms governing genetic diversity of pandemic V. cholerae, we compared the genome sequences of 23 V. cholerae strains isolated from a variety of sources over the past 98 years. The genome-based phylogeny revealed 12 distinct V. cholerae lineages, of which one comprises both O1 classical and El Tor biotypes. All seventh pandemic clones share nearly identical gene content. Using analogy to influenza virology, we define the transition from sixth to seventh pandemic strains as a “shift” between pathogenic clones belonging to the same O1 serogroup, but from significantly different phyletic lineages. In contrast, transition among clones during the present pandemic period is characterized as a “drift” between clones, differentiated mainly by varying composition of laterally transferred genomic islands, resulting in emergence of variants, exemplified by V. cholerae O139 and V. cholerae O1 El Tor hybrid clones. Based on the comparative genomics it is concluded that V. cholerae undergoes extensive genetic recombination via lateral gene transfer, and, therefore, genome assortment, not serogroup, should be used to define pathogenic V. cholerae clones.

Complete fairness in multi-party computation without an honest majority - Gordon,S.; Katz, Jonathan (Theory of Cryptography, 2009)
Gordon et al. recently showed that certain (non-trivial) functions can be computed with complete fairness in the two-party setting. Motivated by their results, we initiate a study of complete fairness in the multi-party case and demonstrate the first completely-fair protocols for non-trivial functions in this setting. We also provide evidence that achieving fairness is “harder” in the multi-party setting, at least with regard to round complexity.

Computation of singular and hypersingular boundary integrals by Green identity and application to boundary value problems - Seydou,F.; Duraiswami, Ramani; Seppänen,T.; Gumerov, Nail A. (Engineering Analysis with Boundary Elements, 2009)
The problem of computing singular and hypersingular integrals involved in a large class of boundary value problems is considered. The method is based on Green's theorem for calculating the diagonal elements of the resulting discretized matrix using the Nyström discretization method. The method is successfully applied to classical boundary value problems. Convergence of the method is also discussed.
Keywords: Bounday integral method; Green identity; Hypersingular integrals; Nyström method; Singular integrals

Computation of the head-related transfer function via the boundary element method and representation via the spherical harmonic spectrum - Gumerov, Nail A.; O'donovan,Adam; Duraiswami, Ramani; Zotkin,Dmitry N (Technical Reports from UMIACS UMIACS-TR-2009-06, 2009)
The head-related transfer function (HRTF) is computed using the fast multipole accelerated boundary element method. For efficiency, the HRTF is computed using the reciprocity principle, by placing a source at the ear and computing its field. Analysis is presented to modify the boundary value problem accordingly. To compute the HRTF corresponding to different ranges via a single computation, a compact and accurate representation of the HRTF, termed the spherical spectrum, is developed. Computations are reduced to a two stage process, the computation of the spherical spectrum and a subsequent evaluation of the HRTF. This representation allows easy interpolation and range extrapolation of HRTFs.HRTF computations are performed for the range of audible frequencies up to 20 kHz for several models including a sphere, human head models (for the “Fritz” and “Kemar”), and head and torso model (the Kemar manikin). Comparisons between the different cases and analysis of limiting cases is provided. Comparisons with the computational data of other authors and available experimental data are conducted and show satisfactory agreement for the frequencies for which reliable experimental data is available. Our results show that, given a good mesh it is feasible to compute the HRTF over the full audible range on a regular personal computer.
Keywords: Technical Report

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

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

CPM: Adaptive Video-on-Demand with Cooperative Peer Assists and Multicast - Gopalakrishnan,V.; Bhattacharjee, Bobby; Ramakrishnan,K.K.; Jana,R.; Srivastava,D. (INFOCOM 2009, IEEE, 2009)
We present CPM, a unified approach that exploits server multicast, assisted by peer downloads, to provide efficient video-on-demand (VoD) in a service provider environment. We describe our architecture and show how CPM is designed to dynamically adapt to a wide range of situations including highly different peer-upload bandwidths, content popularity, user request arrival patterns, video library size, and subscriber population. We demonstrate the effectiveness of CPM using simulations (based on an actual implementation codebase) across the range of situations described above and show that CPM does significantly better than traditional unicast, different forms of multicast, as well as peer-to-peer schemes. Along with synthetic parameters, we augment our experiments using data from a deployed VoD service to evaluate the performance of CPM.
Keywords: assists; multicast; peer-to-peer; communication; peer-to-peer; computing; video; CPM; cooperative; demand; on; parameters; video-on-demand; multicast; peer; schemes; synthetic

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

A Decoupled and Prioritized Stochastic Dynamic Programming Approach for Automated Transport of Multiple Particles Using Optical Tweezers - Banerjee,Ashis Gopal; Losert,Wolfgang; Gupta, Satyandra K. (ASME, 2009)
Automated transport of multiple particles using optical tweezers requires the use of motion planning to move them simultaneously while avoiding collisions amongst themselves and with randomly moving obstacles. This paper develops a decoupled and prioritized stochastic dynamic programming based motion planning framework by sequentially applying a partially observable Markov decision process algorithm on every particle that needs to be transported. An iterative version of a maximum bipartite graph matching algorithm is used to assign given goal locations to such particles. The algorithm for individual particle transport is validated using silica beads in a holographic tweezer set-up. Once the individual plans are computed, a three-step method consisting of clustering, classification, and branch and bound optimization is employed to determine the final collision-free paths. Simulation results in the form of sample trajectories and performance characterization plots are presented to illustrate the usefulness of the developed approach.

Detecting spammers with SNARE: spatio-temporal network-level automatic reputation engine - Hao,Shuang; Syed,Nadeem Ahmed; Feamster, Nick; Gray,Alexander G.; Krasser,Sven (Proceedings of the 18th conference on USENIX security symposium, 2009)
Users and network administrators need ways to filter email messages based primarily on the reputation of the sender. Unfortunately, conventional mechanisms for sender reputation--notably, IP blacklists--are cumbersome to maintain and evadable. This paper investigates ways to infer the reputation of an email sender based solely on network-level features, without looking at the contents of a message. First, we study first-order properties of network-level features that may help distinguish spammers from legitimate senders. We examine features that can be ascertained without ever looking at a packet's contents, such as the distance in IP space to other email senders or the geographic distance between sender and receiver. We derive features that are lightweight, since they do not require seeing a large amount of email from a single IP address and can be gleaned without looking at an email's contents--many such features are apparent from even a single packet. Second, we incorporate these features into a classification algorithm and evaluate the classifier's ability to automatically classify email senders as spammers or legitimate senders. We build an automated reputation engine, SNARE, based on these features using labeled data from a deployed commercial spam-filtering system. We demonstrate that SNARE can achieve comparable accuracy to existing static IP blacklists: about a 70%detection rate for less than a 0.3%false positive rate. Third, we show how SNARE can be integrated into existing blacklists, essentially as a first-pass filter.

Detection of toxigenic Vibrio cholerae O1 in freshwater lakes of the former Soviet Republic of Georgia - Grim,Christopher J.; Jaiani,Ekaterina; Whitehouse,Chris A.; Janelidze,Nino; Kokashvili,Tamuna; Tediashvili,Marina; Rita R Colwell; Huq,Anwar (Environmental Microbiology Reports, 2009)
Three freshwater lakes, Lisi Lake, Kumisi Lake and Tbilisi Sea, near Tbilisi, Georgia, were studied from January 2006 to December 2007 to determine the presence of Vibrio cholerae employing both bacteriological culture method and direct detection methods, namely PCR and direct fluorescent antibody (DFA). For PCR, DNA extracted from water samples was tested for presence of V. cholerae and genes coding for selected virulence factors. Vibrio cholerae non-O1/non-O139 was routinely isolated by culture from all three lakes; whereas V. cholerae O1 and O139 were not. Water samples collected during the summer months from Lisi Lake and Kumisi Lake were positive for both V. cholerae and V. cholerae ctxA, tcpA, zot, ompU and toxR by PCR. Water samples collected during the same period from both Lisi and Kumisi Lake were also positive for V. cholerae serogroup O1 by DFA. All of the samples were negative for V. cholerae serotype O139. The results of this study provide evidence for an environmental presence of toxigenic V. cholerae O1, which may represent a potential source of illness as these lakes serve as recreational water in Tbilisi, Georgia.

Distinguishing knowledge vs social capital in social media with roles and context - Barash,V.; Smith,M.; Getoor, Lise; Welser,H. T (Proceedings of the ICWSM, 2009)
Social media communities (e.g. Wikipedia, Flickr, Live Q&A) give rise to distinct types of content, foremost among which are relational content (discussion, chat) and factual content (answering questions, problem-solving). Both users and researchers are increasingly interested in developing strategies that can rapidly distinguish these types of content. While many text-based and structural strategies are possible, we extend two bodies of research that show how social context, and the social roles of answerers can predict content type. We test our framework on a dataset of manually labeled contributions to Microsoft's Live Q&A and find that it reliably extracts factual and relational messages from the data.

Diversity and Seasonality of Bioluminescent Vibrio Cholerae Populations in Chesapeake Bay - Zo,Young-Gun; Chokesajjawatee,Nipa; Grim,Christopher; Arakawa,Eiji; Watanabe,Haruo; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2009)
Association of luminescence with phenotypic and genotypic traits and with environmental parameters was determined for 278 strains of Vibrio cholerae isolated from the Chesapeake Bay during 1998 to 2000. Three clusters of luminescent strains (A, B, and C) and two nonluminescent clusters (X and Y) were identified among 180 clonal types. V. cholerae O1 strains isolated during pandemics and endemic cholera in the Ganges Delta were related to cluster Y. Heat-stable enterotoxin (encoded by stn) and the membrane protein associated with bile resistance (encoded by ompU) were found to be linked to luminescence in strains of cluster A. Succession from nonluminescent to luminescent populations of V. cholerae occurred during spring to midsummer. Occurrence of cluster A strains in water with neutral pH was contrasted with that of cluster Y strains in water with a pH of >8. Cluster A was found to be associated with a specific calanoid population cooccurring with cyclopoids. Cluster B was related to cluster Y, with its maximal prevalence at pH 8. Occurrence of cluster B strains was more frequent with warmer water temperatures and negatively correlated with maturity of the copepod community. It is concluded that each cluster of luminescent V. cholerae strains occupies a distinct ecological niche. Since the dynamics of these niche-specific subpopulations are associated with zooplankton community composition, the ecology of luminescent V. cholerae is concluded to be related to its interaction with copepods and related crustacean species.

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

Encryption Algorithm Based on Circle Property - Ge,L.N.; He,Z.H.; Zhuolin Jiang (Jisuanji Gongcheng/ Computer Engineering, 2009)

Enhanced force measurement techniques to extend optical trapping towards nanoscale manipulation - Balijepalli,A.; LeBrun,T. W.; Gorman,J. J.; Gupta,S.K. (2009)
We have developed a new force measurement technique based on the random thermal motion of a nanoparticle in an optical trap. We demonstrate this method, in one-dimension, through numerical simulations and laboratory experiments. We show that computer simulations successfully recover the profile of the optical trapping force, beyond the inflection point of the trapping potential for a range of particle sizes. We show, through laboratory experiments, that this technique is effective in recovering higher order terms, in a power series expansion of the trapping force, beyond the widely reported linear trap stiffness. We also show that the first order (stiffness) term in our series expansion is consistent with values reported in the literature.
Keywords: Brownian motion; extend optical trapping; Fokker-Planck equation; force measurement; inflection point; linear trap stiffness; nanoparticle; nanoparticles; nanoscale manipulation; nanotechnology; optical trapping force; power series expansion; radiation pressure; random thermal motion

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

Formal Representation of Product Design Specifications for Validating Product Design - Weissman,Alexander; Gupta, Satyandra K.; Fiorentini,Xenia; Sudarsan,Rachuri; Sriram,Ram (ASME, 2009)
As collaborative efforts in electro-mechanical design have scaled to large, distributed groups working for years on a single product, an increasingly large gulf has developed between the original stated goals of the project and the final design solution. It has thus become necessary to validate the final design solution against a set of requirements to ensure that these goals have, in fact, been met. This process has become tedious for complex products with hundreds of design aspects and requirements. By formalizing the representation of requirements and the design solution, tools can be developed to a large extent automatically perform this validation. In this paper, we propose a formal approach for relating product requirements to the design solution. First, we present a formal model for representing product requirements. Then, we introduce the Core Product Model (CPM) and the Open Assembly Model (OAM) for representing the design solution. Finally, we link these models formally and provide an example with an actual consumer device.

FutureRank: Ranking scientific articles by predicting their future PageRank - Sayyadi,H.; Getoor, Lise (Proceedings of the 9th SIAM International Conference on Data Mining, 2009)
The dynamic nature of citation networks makes the taskof ranking scientific articles hard. Citation networks are continually evolving because articles obtain new citations every day. For ranking scientific articles, we can define the popularity or prestige of a paper based on the number of past citations at the user query time; however, we argue that what is most useful is the expected future references. We define a new measure, FutureRank, which is the expected future PageRank score based on citations that will be obtained in the future. In addition to making use of the citation network, FutureRank uses the authorship network and the publication time of the article in order to predict future citations. Our experiments compare FutureRank with existing approaches, and show that FutureRank is accurate and useful for finding and ranking publications.

Generating simplified trapping probability models from simulation of optical tweezers system - Banerjee,A. G.; Balijepalli,A.; Gupta,S.K.; LeBrun,T. W. (Journal of Computing and Information Science in Engineering, 2009)

The Genus Vibrio and Related Genera - Rita R Colwell; Chun,J. (Practical handbook of microbiologyPractical handbook of microbiology, 2009)

Graphical models for uncertain data - Deshpande, Amol; Getoor, Lise; Sen,P. (Managing and Mining Uncertain Data, 2009)

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

How children search the internet with keyword interfaces - Druin, Allison; Foss,E.; Hatley,L.; Golub,E.; Guha,M.L.; Fails,J.; Hutchinson,H. (Proceedings of the 8th International Conference on Interaction Design and Children, 2009)

Identifying graphs from noisy and incomplete data - Namata,Jr.,Galileo Mark S.; Getoor, Lise (Proceedings of the 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data, 2009)
There is a growing wealth of data describing networks of various types, including social networks, physical networks such as transportation or communication networks, and biological networks. At the same time, there is a growing interest in analyzing these networks, in order to uncover general laws that govern their structure and evolution, and patterns and predictive models to develop better policies and practices. However, a fundamental challenge in dealing with this newly available observational data describing networks is that the data is often of dubious quality -- it is noisy and incomplete -- and before any analysis method can be applied, the data must be cleaned, and missing information inferred. In this paper, we introduce the notion of graph identification, which explicitly models the inference of a "cleaned" output network from a noisy input graph. It is this output network that is appropriate for further analysis. We present an illustrative example and use the example to explore the types of inferences involved in graph identification, as well as the challenges and issues involved in combining those inferences. We then present a simple, general approach to combining the inferences in graph identification and experimentally show the utility of our combined approach and how the performance of graph identification is sensitive to the inter-dependencies among these inferences.
Keywords: classification; data mining; entity resolution; link prediction; social networks; statistical relational learning

Imaging room acoustics with the audio camera. - O'donovan,Adam; Duraiswami, Ramani; Gumerov, Nail A.; Zotkin,Dmitry N (The Journal of the Acoustical Society of America, 2009)
Using a spherical microphone array and real time signal processing using a graphical processing unit (GPU), an audio camera has been developed. This device provides images of the intensity of the sound field arriving at a point from a specified direction to the spherical array. Real‐time performance is achieved via use of GPUs. The intensity can be displayed integrated over the whole frequency band of the array, or in false color, with different frequency bands mapped to different color bands. The resulting audio camera may be combined with video cameras to achieve multimodal scene capture and analysis. A theory of registration of audio camera images with video camera images is developed, and joint analysis of audio and video images performed. An interesting application of the audio camera is the imaging of concert hall acoustics. The individual reflections that constitute the impulse response measured at a particular seat may be imaged, and their spatial origin determined. Other applications of the audio camera to people tracking, noise suppression, and camera pointing are also presented. [Work partially supported by NVIDIA and the VA.]

Implicit authentication for mobile devices - Jakobsson, Markus; Elaine Shi; Golle, Philippe; Chow, Richard (USENIX Association, 2009)
We introduce the notion of implicit authentication - the ability to authenticate mobile users based on actions they would carry out anyway. We develop a model for how to perform implicit authentication, and describe experiments aimed at assessing the benefits of our techniques. Our preliminary findings support that this is a meaningful approach, whether used to increase usability or increase security.

Improving recommendation accuracy by clustering social networks with trust - DuBois,T.; Golbeck,J.; Kleint,J.; Srinivasan, Aravind (Recommender Systems & the Social Web, 2009)
Social trust relationships between users in social networksspeak to the similarity in opinions between the users, both in general and in important nuanced ways. They have been used in the past to make recommendations on the web. New trust metrics allow us to easily cluster users based on trust. In this paper, we investigate the use of trust clusters as a new way of improving recommendations. Previous work on the use of clusters has shown the technique to be relatively un- successful, but those clusters were based on similarity rather than trust. Our results show that when trust clusters are integrated into memory-based collaborative filtering algo- rithms, they lead to statistically significant improvements in accuracy. In this paper we discuss our methods, experi- ments, results, and potential future applications of the tech- nique.

In Situ Characterization and Modeling of Strains near Embedded Electronic Components During Processing and Break-in for Multifunctional Polymer Structures - Gershon,Alan L.; Gyger,Lawrence S.; Bruck,Hugh A.; Gupta, Satyandra K. (Advances in Mathematical Modeling and Experimental Methods for Materials and Structures, 2009)
Emerging molding concepts, such as in-mold assembly, are enabling electronic structures to be directly embedded in thermoplastic polymers to provide integrated packaging for better protection and a more multifunctional structure in “in-mold assembly processes”. During the molding process, stress can develop at the interface of the polymer and embedded electronic component due to shrinkage of the polymer that precipitates fracture or fatigue during the life cycle of the product. Additionally, the interaction between a mold and the polymer melt is altered in a multi-stage molding process where a polymer for superior impact protection can be molded over another polymer that is more compatible with the embedded electronic component. Currently, we do not fully understand the impact of various parameters governing the in-mold assembly process on the residual strains that develop in polymers around embedded electronic components in order to develop process models. Therefore, in this chapter experiments are presented that are designed and executed to measure the strains involved and the manner in which they develop. An in situ open mold experiment is employed using the full-field deformation technique of Digital Image Correlation (DIC) to characterize the displacement and corresponding strain fields that evolve near embedded electronic elements as the polymer shrinks from the molten to the solid state during processes and during break-in of the electronic component. It was determined that the use of multi-stage molding may reduce the residual stresses in addition to providing superior impact protection. However, there was a higher concentration of strain near the polymer-component interface during break-due to lower thermal conductivity. Experimental data was consistent with a thermomechanical model up until the point of failure.
Keywords: engineering

Index interactions in physical design tuning: modeling, analysis, and applications - Schnaitter,Karl; Polyzotis,Neoklis; Getoor, Lise (Proceedings of the VLDB Endowment, 2009)
One of the key tasks of a database administrator is to optimize the set of materialized indices with respect to the current workload. To aid administrators in this challenging task, commercial DBMSs provide advisors that recommend a set of indices based on a sample workload. It is left for the administrator to decide which of the recommended indices to materialize and when. This decision requires some knowledge of how the indices benefit the workload, which may be difficult to understand if there are any dependencies or interactions among indices. Unfortunately, advisors do not provide this crucial information as part of the recommendation. Motivated by this shortcoming, we propose a framework and associated tools that can help an administrator understand the interactions within the recommended set of indices. We formalize the notion of index interactions and develop a novel algorithm to identify the interaction relationships that exist within a set of indices. We present experimental results with a prototype implementation over IBM DB2 that demonstrate the efficiency of our approach. We also describe two new database tuning tools that utilize information about index interactions. The first tool visualizes interactions based on a partitioning of the index-set into non-interacting subsets, and the second tool computes a schedule that materializes the indices over several maintenance windows with maximal overall benefit. In both cases, we provide strong analytical results showing that index interactions can enable enhanced functionality.

Inexact Local Alignment Search over Suffix Arrays - Ghodsi,M.; Pop, Mihai (IEEE International Conference on Bioinformatics and Biomedicine, 2009. BIBM '09, 2009)
We describe an algorithm for finding approximate seeds for DNA homology searches. In contrast to previous algorithms that use exact or spaced seeds, our approximate seeds may contain insertions and deletions. We present a generalized heuristic for finding such seeds efficiently and prove that the heuristic does not affect sensitivity. We show how to adapt this algorithm to work over the memory efficient suffix array with provably minimal overhead in running time. We demonstrate the effectiveness of our algorithm on two tasks: whole genome alignment of bacteria and alignment of the DNA sequences of 177 genes that are orthologous in human and mouse. We show our algorithm achieves better sensitivity and uses less memory than other commonly used local alignment tools.
Keywords: bacteria; Bioinformatics; biology computing; Computational Biology; Costs; DNA; DNA homology searches; DNA sequences; Educational institutions; generalized heuristic; genes; Genetics; genome alignment; Genomics; human; inexact local alignment search; inexact seeds; local alignment; local alignment tools; memory efficient suffix array; microorganisms; molecular biophysics; mouse; Organisms; Sensitivity and Specificity; sequences; suffix array; USA Councils

Inexact Local Alignment Search over Suffix Arrays - Ghodsi,M.; Pop, Mihai (2009)

The Ins and Outs of Home Networking: The Case for Useful and Usable Domestic Networking - Grinter, Rebecca E.; Edwards, W. Keith; Marshini Chetty; Poole, Erika S.; Sung, Ja-Young; Yang, Jeonghwa; Crabtree, Andy; Tolmie, Peter; Rodden, Tom; Greenhalgh, Chris; Benford, Steve (ACM Trans. Comput.-Hum. Interact., 2009)
Householders are increasingly adopting home networking as a solution to the demands created by the presence of multiple computers, devices, and the desire to access the Internet. However, current network solutions are derived from the world of work (and initially the military) and provide poor support for the needs of the home. We present the key findings to emerge from empirical studies of home networks in the UK and US. The studies reveal two key kinds of work that effective home networking relies upon: one, the technical work of setting up and maintaining the home network, and the other, the collaborative and socially organized work of the home which the network is embedded in and supports. The two are thoroughly intertwined and rely upon one another for their realization, yet neither is adequately supported by current networking technologies and applications. Explication of the “work to make the home network work” opens up the design space for the continued integration of the home network in domestic life and elaboration of future support. Key issues for development include the development of networking facilities that do not require advanced networking knowledge, that are flexible and support the local social order of the home and the evolution of its routines, and which ultimately make the home network visible and accountable to household members.
Keywords: home networking; Human computer interaction

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

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

Intrinsic Sensor Noise Features for Forensic Analysis on Scanners and Scanned Images - Gou,Hongmei; Swaminathan,A.; M. Wu (Information Forensics and Security, IEEE Transactions on, 2009)
A large portion of digital images available today are acquired using digital cameras or scanners. While cameras provide digital reproduction of natural scenes, scanners are often used to capture hard-copy art in a more controlled environment. In this paper, new techniques for nonintrusive scanner forensics that utilize intrinsic sensor noise features are proposed to verify the source and integrity of digital scanned images. Scanning noise is analyzed from several aspects using only scanned image samples, including through image denoising, wavelet analysis, and neighborhood prediction, and then obtain statistical features from each characterization. Based on the proposed statistical features of scanning noise, a robust scanner identifier is constructed to determine the model/brand of the scanner used to capture a scanned image. Utilizing these noise features, we extend the scope of acquisition forensics to differentiating scanned images from camera-taken photographs and computer-generated graphics. The proposed noise features also enable tampering forensics to detect postprocessing operations on scanned images. Experimental results are presented to demonstrate the effectiveness of employing the proposed noise features for performing various forensic analysis on scanners and scanned images.
Keywords: analysis; image; camera-taken; cameras; digital; denoising; intrinsic; denoising; wavelet; features; natural; forensics; scanned; graphics; digital; identifier; wavelet; images; digital; images; scanner; NOISE; photographs; computer-generated; prediction; nonintrusive; reproduction; forensic; scanner; scenes; neighborhood; sensor; transforms

Link-based active learning - Bilgic,M.; Getoor, Lise (NIPS Workshop on Analyzing Networks and Learning with Graphs, 2009)
Supervised and semi-supervised data mining techniques require labeled data.However, labeling examples is costly for many real-world applications. To ad- dress this problem, active learning techniques have been developed to guide the labeling process in an effort to minimize the amount of labeled data without sac- rificing much from the quality of the learned models. Yet, most of the active learning methods to date have remained relatively agnostic to the rich structure offered by network data, often ignoring the relationships between the nodes of a network. On the other hand, the relational learning community has shown that the relationships can be very informative for various prediction tasks. In this paper, we propose different ways of adapting existing active learning work to network data while utilizing links to select better examples to label.

The Maryland Modular Method: An Approach to Doctoral Education in Information Studies - Druin, Allison; Jaeger,P. T; Golbeck,J.; Fleischmann,K.R.; Jimmy Lin; Qu,Y.; Wang,P.; Xie,B. (Journal of education for library and information science, 2009)

Matching person names through name transformation - Gong,Jun; Wang,Lidan; Oard, Douglas (Proceedings of the 18th ACM conference on Information and knowledge management, 2009)
Matching person names plays an important role in many applications, including bibliographic databases and indexing systems. Name variations and spelling errors make exact string matching problematic; therefore, it is useful to develop methodologies that can handle variant forms for the same named entity. In this paper, a novel person name matching model is presented. Common name variations in the English speaking world are formalized, and the concept of name transformation paths is introduced; name similarity is measured after the best transformation path has been selected. Supervised techniques are used to learn a similarity function and a decision rule. Experiments with three datasets show the method to be effective.
Keywords: name matching; string distance metrics; string similarity

On maximum coverage in the streaming model & application to multi-topic blog-watch - Saha,B.; Getoor, Lise (2009 SIAM International Conference on Data Mining (SDM09), 2009)
We generalize the graph streaming model to hypergraphs.In this streaming model, hyperedges are arriving online and any computation has to be done on-the-fly using a small amount of space. Each hyperedge can be viewed as a set of elements (nodes), so we refer to our proposed model as the “set-streaming” model of computation. We consider the problem of “maximum coverage”, in which k sets have to be selected that maximize the total weight of the covered elements. In the set-streaming model of computation, we show that our algorithm for maximum- coverage achieves an approximation factor of 1 . When multiple passes are allowed, we also provide a Θ(log n) approximation algorithm for the set-cover. We next consider a multi-topic blog-watch application, an extension of blog- alert like applications for handling simultaneous multiple- topic requests. We show how the problems of maximum- coverage and set-cover in the set-streaming model can be utilized to give efficient online solutions to this problem. We verify the effectiveness of our methods both on synthetic and real weblog data.

More than words: Syntactic packaging and implicit sentiment - Greene,S.; Resnik, Philip (Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2009)

Moving Object Verification in Airborne Video Sequences - Yue,Zhanfeng; Guarino, D.; Chellapa, Rama (Circuits and Systems for Video Technology, IEEE Transactions on, 2009)
This paper presents an end-to-end system for moving object verification in airborne video sequences. Using a sample selection module, the system first selects frames from a short 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 then used to generate a novel view of each image in the exemplar database at the same pose as the testing object in each frame of a testing video segment. A rotationally invariant color matcher and a spatial-feature matcher based on distance transforms are combined using a weighted average rule to compare the novel view and the testing object. After looping over all testing frames, the set of match scores is passed to a temporal analysis module to examine the behavior of the testing 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.
Keywords: airborne; database; homography-based; databases; matcher; color; matcher; image; matching; image; method; infrared; object; sequences; color; sequences; distance; sequences; moving; sequences; video; synthesis; system; exemplar; transforms; end-to-end; verification; spatial-feature; video; view

Network-aware forward caching - Erman,Jeffrey; Gerber,Alexandre; Hajiaghayi, Mohammad T.; Pei,Dan; Spatscheck,Oliver (Proceedings of the 18th international conference on World wide web, 2009)
This paper proposes and evaluates a Network Aware Forward Caching approach for determining the optimal deployment strategy of forward caches to a network. A key advantage of this approach is that we can reduce the network costs associated with forward caching to maximize the benefit obtained from their deployment. We show in our simulation that a 37% increase to net benefits could be achieved over the standard method of full cache deployment to cache all POPs traffic. In addition, we show that this maximal point occurs when only 68% of the total traffic is cached. Another contribution of this paper is the analysis we use to motivate and evaluate this problem. We characterize the Internet traffic of 100K subscribers of a US residential broadband provider. We use both layer 4 and layer 7 analysis to investigate the traffic volumes of the flows as well as study the general characteristics of the applications used. We show that HTTP is a dominant protocol and account for 68% of the total downstream traffic and that 34% of that traffic is multimedia. In addition, we show that multimedia content using HTTP exhibits a 83% annualized growth rate and other HTTP traffic has a 53% growth rate versus the 26% over all annual growth rate of broadband traffic. This shows that HTTP traffic will become ever more dominent and increase the potential caching opportunities. Furthermore, we characterize the core backbone traffic of this broadband provider to measure the distance travelled by content and traffic. We find that CDN traffic is much more efficient than P2P content and that there is large skew in the Air Miles between POP in a typical network. Our findings show that there are many opportunties in broadband provider networks to optimize how traffic is delivered and cached.
Keywords: caching; Web

Observing Human-Object Interactions: Using Spatial and Functional Compatibility for Recognition - Gupta,A.; Kembhavi,A.; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2009)
Interpretation of images and videos containing humans interacting with different objects is a daunting task. It involves understanding scene or event, analyzing human movements, recognizing manipulable objects, and observing the effect of the human movement on those objects. While each of these perceptual tasks can be conducted independently, recognition rate improves when interactions between them are considered. Motivated by psychological studies of human perception, we present a Bayesian approach which integrates various perceptual tasks involved in understanding human-object interactions. Previous approaches to object and action recognition rely on static shape or appearance feature matching and motion analysis, respectively. Our approach goes beyond these traditional approaches and applies spatial and functional constraints on each of the perceptual elements for coherent semantic interpretation. Such constraints allow us to recognize objects and actions when the appearances are not discriminative enough. We also demonstrate the use of such constraints in recognition of actions from static images without using any motion information.
Keywords: Automated; Recognition (Psychology); Video Recording; Bayesian approach; functional compatibility; human perception; human-object interactions; objects recognition; psychological studies; spatial compatibility; Bayes methods; behavioural sciences; human factors; image recognition; motion estimation; object recognition; A; Biological; Movement; Pattern Recognition; Computer-Assisted; Models

Opinion graphs for polarity and discourse classification - Somasundaran,Swapna; Namata,Galileo; Getoor, Lise; Wiebe,Janyce (Proceedings of the 2009 Workshop on Graph-based Methods for Natural Language Processing, 2009)
This work shows how to construct discourse-level opinion graphs to perform a joint interpretation of opinions and discourse relations. Specifically, our opinion graphs enable us to factor in discourse information for polarity classification, and polarity information for discourse-link classification. This inter-dependent framework can be used to augment and improve the performance of local polarity and discourse-link classifiers.

P r DB: managing and exploiting rich correlations in probabilistic databases - Sen,P.; Deshpande, Amol; Getoor, Lise (The VLDB Journal, 2009)
Due to numerous applications producing noisy data, e.g., sensor data, experimental data, data from uncurated sources, information extraction, etc., there has been a surge of interest in the development of probabilistic databases. Most probabilistic database models proposed to date, however, fail to meet the challenges of real-world applications on two counts: (1) they often restrict the kinds of uncertainty that the user can represent; and (2) the query processing algorithms often cannot scale up to the needs of the application. In this work, we define a probabilistic database model, PrDB, that uses graphical models, a state-of-the-art probabilistic modeling technique developed within the statistics and machine learning community, to model uncertain data. We show how this results in a rich, complex yet compact probabilistic database model, which can capture the commonly occurring uncertainty models (tuple uncertainty, attribute uncertainty), more complex models (correlated tuples and attributes) and allows compact representation (shared and schema-level correlations). In addition, we show how query evaluation in PrDB translates into inference in an appropriately augmented graphical model. This allows us to easily use any of a myriad of exact and approximate inference algorithms developed within the graphical modeling community. While probabilistic inference provides a generic approach to solving queries, we show how the use of shared correlations, together with a novel inference algorithm that we developed based on bisimulation, can speed query processing significantly. We present a comprehensive experimental evaluation of the proposed techniques and show that even with a few shared correlations, significant speedups are possible.

PrDB: managing and exploiting rich correlations in probabilistic databases - Sen,Prithviraj; Deshpande, Amol; Getoor, Lise (The VLDB Journal, 2009)
Due to numerous applications producing noisy data, e.g., sensor data, experimental data, data from uncurated sources, information extraction, etc., there has been a surge of interest in the development of probabilistic databases. Most probabilistic database models proposed to date, however, fail to meet the challenges of real-world applications on two counts: (1) they often restrict the kinds of uncertainty that the user can represent; and (2) the query processing algorithms often cannot scale up to the needs of the application. In this work, we define a probabilistic database model, P r DB, that uses graphical models, a state-of-the-art probabilistic modeling technique developed within the statistics and machine learning community, to model uncertain data. We show how this results in a rich, complex yet compact probabilistic database model, which can capture the commonly occurring uncertainty models (tuple uncertainty, attribute uncertainty), more complex models (correlated tuples and attributes) and allows compact representation (shared and schema-level correlations). In addition, we show how query evaluation in P r DB translates into inference in an appropriately augmented graphical model. This allows us to easily use any of a myriad of exact and approximate inference algorithms developed within the graphical modeling community. While probabilistic inference provides a generic approach to solving queries, we show how the use of shared correlations, together with a novel inference algorithm that we developed based on bisimulation, can speed query processing significantly. We present a comprehensive experimental evaluation of the proposed techniques and show that even with a few shared correlations, significant speedups are possible.

PrDB: Managing Large-Scale Correlated Probabilistic Databases (Abstract) - Deshpande, Amol (Scalable Uncertainty ManagementScalable Uncertainty Management, 2009)
Increasing numbers of real-world application domains are generating data that is inherently noisy, incomplete, and probabilistic in nature. Statistical inference and probabilistic modeling often introduce another layer of uncertainty on top of that. Examples of such data include measurement data collected by sensor networks, observation data in the context of social networks, scientific and biomedical data, and data collected by various online cyber-sources. Over the last few years, numerous approaches have been proposed, and several systems built, to integrate uncertainty into databases. However, these approaches typically make simplistic and restrictive assumptions concerning the types of uncertainties that can be represented. Most importantly, they often make highly restrictive independence assumptions, and cannot easily model rich correlations among the tuples or attribute values. Furthermore, they typically lack support for specifying uncertainties at different levels of abstractions, needed to handle large-scale uncertain datasets.

Probabilistic graphical models - Gupta,A.; Kembhavi,A.; Davis, Larry S. (IEEE transactions on pattern analysis and machine intelligence, 2009)

Proceedings of the 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data (ACM, 2009)
The importance of uncertain data is growing quickly in many essential applications such as environmental surveillance, mobile object tracking and data integration. Recently, storing, collecting, processing, and analyzing uncertain data has attracted increasing attention from both academia and industry. Analyzing and mining uncertain data needs collaboration and joint effort from multiple research communities including reasoning under uncertainty, uncertain databases and mining uncertain data. For example, statistics and probabilistic reasoning can provide support with models for representing uncertainty. The uncertain database community can provide methods for storing and managing uncertain data, while research in mining uncertain data can provide data analysis tasks and methods. It is important to build connections among those communities to tackle the overall problem of analyzing and mining uncertain data. There are many common challenges among the communities. One is to understand the different modeling assumptions made, and how they impact the methods, both in terms of accuracy and efficiency. Different researchers hold different assumptions and this is one of the major obstacles in the research of mining uncertain data. Another is the scalability of proposed management and analysis methods. Finally, to make analysis and mining useful and practical, we need real data sets for testing. Unfortunately, uncertain data sets are often hard to get. The goal of the First ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data (U'09) is to discuss in depth the challenges, opportunities and techniques on the topic of analyzing and mining uncertain data. The theme of this workshop is to make connections among the research areas of uncertain databases, probabilistic reasoning, and data mining, as well as to build bridges among the aspects of models, data, applications, novel mining tasks and effective solutions. By making connections among different communities, we aim at understanding each other in terms of scientific foundation as well as commonality and differences in research methodology. The workshop program is very stimulating and exciting. We are pleased to feature two invited talks by pioneers in mining uncertain data. Christopher Jermaine will give an invited talk titled "Managing and Mining Uncertain Data: What Might We Do Better?" Matthias Renz will address the topic "Querying and Mining Uncertain Data: Methods, Applications, and Challenges". Moreover, 8 accepted papers in 4 full presentations and 4 concise presentations will cover a bunch of interesting topics and on-going research projects about uncertain data mining.

Promoting social creativity: a component of a national initiative for social participation - Shneiderman, Ben; Churchill,Elizabeth; Fischer,Gerhard; Goldberg,Ken (Proceedings of the seventh ACM conference on Creativity and cognition, 2009)
This panel will discuss group processes that promote social creativity in science, engineering, arts, and humanities. We will offer positive and negative examples of social creativity projects, while suggesting research directions for dramatically increased social participation. The goal is to develop strategies that would expand resources and opportunities for research and education in social creativity. This requires our community to develop a unified position, then reach out to national science funding agencies, while building the case for the importance of this topic beyond our own community. How can social creativity, collaborative discovery, distributed innovation, and collective intelligence be framed as an international priority to cope with the problems of the 21st century and how can we identify a clear set of research challenges? The theme of technology-mediated social participation is outlined in the white paper for a National Initiative for Social Participation (http://iparticipate.wikispaces.com). The white paper suggests that successful research challenges should have three key elements: (1) compelling national need (healthcare, national security, community safety, education, innovation, cultural heritage, energy sustainability, environmental protection, etc.), (2) scientific foundation based on established theories and well-defined research questions (privacy, reciprocity, trust, motivation, recognition, etc.), and (3) computer science research challenges (security, privacy protection, scalability, visualization, end-user development, distributed data handling for massive user-generated content, network analysis of community evolution, cross network comparison, etc.). We seek recommendations for ways to increase the resources and attention for this field. We hope to inspire: universities to change course content, add courses, and offer new degree programs industry to help researchers on social creativity government to support these ideas and try them out in government applications scientists and artists to open themselves to more social/collaborative approaches
Keywords: research agenda; social creativity; social participation

Protein quantification across hundreds of experimental conditions - Zia Khan; Bloom, Joshua S.; Garcia, Benjamin A.; Singh, Mona; Kruglyak, Leonid (Proceedings of the National Academy of Sciences, 2009)
Quantitative studies of protein abundance rarely span more than a small number of experimental conditions and replicates. In contrast, quantitative studies of transcript abundance often span hundreds of experimental conditions and replicates. This situation exists, in part, because extracting quantitative data from large proteomics datasets is significantly more difficult than reading quantitative data from a gene expression microarray. To address this problem, we introduce two algorithmic advances in the processing of quantitative proteomics data. First, we use space-partitioning data structures to handle the large size of these datasets. Second, we introduce techniques that combine graph-theoretic algorithms with space-partitioning data structures to collect relative protein abundance data across hundreds of experimental conditions and replicates. We validate these algorithmic techniques by analyzing several datasets and computing both internal and external measures of quantification accuracy. We demonstrate the scalability of these techniques by applying them to a large dataset that comprises a total of 472 experimental conditions and replicates.
Keywords: kd-tree; orthogonal range query; quantitative proteomics; space partitioning data structures; tandem mass spectrometry

Reading tea leaves: How humans interpret topic models - Chang,J.; Jordan Boyd-Graber; Gerrish,S.; Wang,C.; Blei,D.M. (Proceedings of the 23rd Annual Conference on Neural Information Processing Systems, 2009)
Probabilistic topic models are a popular tool for the unsupervised analysis of text, providing both a predictive model of future text and a latent topic representation of the corpus. Practitioners typically assume that the latent space is semantically meaningful. It is used to check models, summarize the corpus, and guide explo- ration of its contents. However, whether the latent space is interpretable is in need of quantitative evaluation. In this paper, we present new quantitative methods for measuring semantic meaning in inferred topics. We back these measures with large-scale user studies, showing that they capture aspects of the model that are undetected by previous measures of model quality based on held-out likelihood. Surprisingly, topic models which perform better on held-out likelihood may infer less semantically meaningful topics.

Reflect and correct: A misclassification prediction approach to active inference - Bilgic,Mustafa; Getoor, Lise (ACM Transactions on Knowledge Discovery from Data (TKDD), 2009)
Information diffusion, viral marketing, graph-based semi-supervised learning, and collective classification all attempt to model and exploit the relationships among nodes in a network to improve the performance of node labeling algorithms. However, sometimes the advantage of exploiting the relationships can become a disadvantage. Simple models like label propagation and iterative classification can aggravate a misclassification by propagating mistakes in the network, while more complex models that define and optimize a global objective function, such as Markov random fields and graph mincuts, can misclassify a set of nodes jointly. This problem can be mitigated if the classification system is allowed to ask for the correct labels for a few of the nodes during inference. However, determining the optimal set of labels to acquire is intractable under relatively general assumptions, which forces us to resort to approximate and heuristic techniques. We describe three such techniques in this article. The first one is based on directly approximating the value of the objective function of label acquisition and greedily acquiring the label that provides the most improvement. The second technique is a simple technique based on the analogy we draw between viral marketing and label acquisition. Finally, we propose a method, which we refer to as reflect and correct, that can learn and predict when the classification system is likely to make mistakes and suggests acquisitions to correct those mistakes. We empirically show on a variety of synthetic and real-world datasets that the reflect and correct method significantly outperforms the other two techniques, as well as other approaches based on network structural measures such as node degree and network clustering.
Keywords: active inference; collective classification; information diffusion; label acquisition; viral marketing

Regularized HRTF fitting using spherical harmonics - Zotkin,Dmitry N; Duraiswami, Ramani; Gumerov, Nail A. (IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, 2009. WASPAA '09, 2009)
By the Helmholtz reciprocity principle, the head-related transfer function (HRTF) is equivalent to an acoustic field created by a transmitter placed at the ear location. Therefore, it can be represented as a spherical harmonics spectrum - a weighted sum of spherical harmonics. Such representations are useful in theoretical and computational analysis. Many different (often severely undersampled) grids are used for HRTF measurement, making the spectral reconstruction difficult. In this paper, two methods of obtaining the spectrum are presented and analyzed both on synthetic (ground-truth data available) and real HRTF measurements.
Keywords: Acoustic applications; acoustic field; Acoustic fields; acoustic intensity measurement; Acoustic measurements; acoustic signal processing; Acoustic testing; acoustic waves; array signal processing; audio acoustics; circular arrays; computational analysis; Ear; ear location; head-related transfer function; Helmholtz reciprocity principle; HRTF; HRTF fitting; Loudspeakers; Microphones; Position measurement; signal reconstruction; spatial audio; spectral reconstruction; spherical harmonics; Transfer functions

Rigorous Probabilistic Trust-Inference with Applications to Clustering - DuBois,Thomas; Golbeck,Jennifer; Srinivasan, Aravind (IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies, 2009. WI-IAT '09, 2009)
The World Wide Web has transformed into an environment where users both produce and consume information. In order to judge the validity of information, it is important to know how trustworthy its creator is. Since no individual can have direct knowledge of more than a small fraction of information authors, methods for inferring trust are needed. We propose a new trust inference scheme based on the idea that a trust network can be viewed as a random graph, and a chain of trust as a path in that graph. In addition to having an intuitive interpretation, our algorithm has several advantages, noteworthy among which is the creation of an inferred trust-metric space where the shorter the distance between two people, the higher their trust. Metric spaces have rigorous algorithms for clustering, visualization, and related problems, any of which is directly applicable to our results.
Keywords: Clustering algorithms; Conferences; Educational institutions; Extraterrestrial measurements; Inference algorithms; Intelligent agent; random graphs; Social network services; trust inferrence; Visualization; Voting; Web sites

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

Robust human detection under occlusion by integrating face and person detectors - Schwartz, W.R.; Gopalan,R.; Chellapa, Rama; Davis, Larry S. (Proceedings of the Third International Conference on Advances in Biometrics, 2009)
Human detection under occlusion is a challenging problemin computer vision. We address this problem through a framework which integrates face detection and person detection. We first investigate how the response of a face detector is correlated with the response of a person detector. From these observations, we formulate hypotheses that capture the intuitive feedback between the responses of face and person detectors and use it to verify if the individual detectors’ outputs are true or false. We illustrate the performance of our integration framework on challeng- ing images that have considerable amount of occlusion, and demonstrate its advantages over individual face and person detectors.

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

Scheduling to minimize staleness and stretch in real-time data warehouses - Bateni,M. H; Golab,L.; Hajiaghayi, Mohammad T.; Karloff,H. (Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, 2009)

Selecting hierarchical clustering cut points for web person-name disambiguation - Gong,Jun; Oard, Douglas (Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, 2009)
Hierarchical clustering is often used to cluster person-names referring to the same entities. Since the correct number of clusters for a given person-name is not known a priori, some way of deciding where to cut the resulting dendrogram to balance risks of over- or under-clustering is needed. This paper reports on experiments in which outcome-specific and result-set measures are used to learn a global similarity threshold. Results on the Web People Search (WePS)-2 task indicate that approximately 85% of the optimal F1 measure can be achieved on held-out data.
Keywords: clustering; person-name disambiguation

Semantically informed machine translation (SIMT) - Baker,K.; Bethard,S.; Bloodgood,M.; Brown,R.; Callison-Burch,C.; Coppersmith,G.; Dorr, Bonnie J; Filardo,W.; Giles,K.; Irvine,A.; others (SCALE summer workshop final report, Human Language Technology Center Of Excellence, 2009)

Serogroup, Virulence, and Genetic Traits of Vibrio Parahaemolyticus in the Estuarine Ecosystem of Bangladesh - Alam,Munirul; Chowdhury,Wasimul B.; Bhuiyan,N. A.; Islam,Atiqul; Hasan,Nur A.; Nair,G. Balakrish; Watanabe,H.; Siddique,A. K.; Huq,Anwar; Sack,R. Bradley; Akhter,M. Z.; Grim,Christopher J.; et al. (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2009)
Forty-two strains of Vibrio parahaemolyticus were isolated from Bay of Bengal estuaries and, with two clinical strains, analyzed for virulence, phenotypic, and molecular traits. Serological analysis indicated O8, O3, O1, and K21 to be the major O and K serogroups, respectively, and O8:K21, O1:KUT, and O3:KUT to be predominant. The K antigen(s) was untypeable, and pandemic serogroup O3:K6 was not detected. The presence of genes toxR and tlh were confirmed by PCR in all but two strains, which also lacked toxR. A total of 18 (41%) strains possessed the virulence gene encoding thermostable direct hemolysin (TDH), and one had the TDH-related hemolysin (trh) gene, but not tdh. Ten (23%) strains exhibited Kanagawa phenomenon that surrogates virulence, of which six, including the two clinical strains, possessed tdh. Of the 18 tdh-positive strains, 17 (94%), including the two clinical strains, had the seromarker O8:K21, one was O9:KUT, and the single trh-positive strain was O1:KUT. None had the group-specific or ORF8 pandemic marker gene. DNA fingerprinting employing pulsed-field gel electrophoresis (PFGE) of SfiI-digested DNA and cluster analysis showed divergence among the strains. Dendrograms constructed using PFGE (SfiI) images from a soft database, including those of pandemic and nonpandemic strains of diverse geographic origin, however, showed that local strains formed a cluster, i.e., “clonal cluster,” as did pandemic strains of diverse origin. The demonstrated prevalence of tdh-positive and diarrheagenic serogroup O8:K21 strains in coastal villages of Bangladesh indicates a significant human health risk for inhabitants.

Shape Identification in Temporal Data Sets - Gregory,M.B.; Shneiderman, Ben (Master’s thesis, University of Maryland, 2009)
Shapes are a concise way to describe temporal variable behaviors.Some commonly used shapes are spikes, sinks, rises, and drops. A spike describes a set of variable values that rapidly increase, then immediately rapidly decrease. The variable may be the value of a stock or a person’s blood sugar levels. Shapes are abstract. Details such as the height of spike or its rate increase, are lost in the ab- straction. These hidden details make it difficult to define shapes and compare one to another. For example, what attributes of a spike determine its “spikiness”? The ability to define and com- pare shapes is important because it allows shapes to be identified and ranked, according to an attribute of interest. Work has been done in the area of shape identification through pattern matching and other data mining techniques, but ideas combining the identifi- cation and comparison of shapes have received less attention. This paper fills the gap by presenting a set of shapes and the attributes by which they can identified, compared, and ranked. Neither the set of shapes, nor their attributes presented in this paper are exhaustive, but it provides an example of how a shape’s attributes can be used for identification and comparison. The intention of this paper is not to replace any particular mathematical method of identifying a par- ticular behavior, but to provide a toolset for knowledge discovery and an intuitive method of data mining for novices. Spikes, sinks, rises, drops, lines, plateaus, valleys, and gaps are the shapes pre- sented in this paper. Several attributes for each shape are defined. These attributes will be the basis for constructing definitions that allow the shapes to be identified and ranked. The second contri- bution is an information visualization tool, TimeSearcher: Shape Search Edition (SSE), which allows users to explore data sets using the identification and ranking ideas in this paper.

SPOT Databases: Efficient Consistency Checking and Optimistic Selection in Probabilistic Spatial Databases - Parker,A.; Infantes,G.; Grant,J.; V.S. Subrahmanian (Knowledge and Data Engineering, IEEE Transactions on, 2009)
Spatial probabilistic temporal (SPOT) databases are a paradigm for reasoning with probabilistic statements about where a vehicle may be now or in the future. They express statements of the form "Object O is in spatial region R at some time t with some probability in the interval [L,U]." Past work on SPOT databases has developed selection operators based on selecting SPOT atoms that are entailed by the SPOT database-we call this "cautious" selection. In this paper, we study several problems. First, we note that the runtime of consistency checking and cautious selection algorithms in past work is influenced greatly by the granularity of the underlying Cartesian space. In this paper, we first introduce the notion of "optimistic" selection, where we are interested in returning all SPOT atoms in a database that are consistent with respect to a query, rather than having an entailment relationship. We then develop an approach to scaling SPOT databases that has three main contributions: 1) We develop methods to eliminate variables from the linear programs used in past work, thus greatly reducing the size of the linear programs used-the resulting advances apply to consistency checking, optimistic selection, and cautious selection. 2) We develop a host of theorems to show how we can prune the search space when we are interested in optimistic selection. 3) We use the above contributions to build an efficient index to execute optimistic selection queries over SPOT databases. Our approach is superior to past work in two major respects: First, it makes fewer assumptions than all past works on this topic except that in. Second, our experiments, which are based on real-world data about ship movements, show that our algorithms are much more efficient than those in.
Keywords: Cartesian; checking; database; database; data; databases; databases; visual; indexing; inference; indexing; linear; integrity; database; mechanisms; linear; probabilistic; problem; spatial; problems; temporal; processing; search; program; optimistic; programming; probability; query; query; probabilistic; reasoning; search; selection; selection; consistency; space; cautious; temporal

Streaming for large scale NLP: Language modeling - Goyal,A.; Daumé, Hal; Venkatasubramanian,S. (Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2009)

Supervised and unsupervised methods in employing discourse relations for improving opinion polarity classification - Somasundaran,Swapna; Namata,Galileo; Wiebe,Janyce; Getoor, Lise (Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1 - Volume 1, 2009)
This work investigates design choices in modeling a discourse scheme for improving opinion polarity classification. For this, two diverse global inference paradigms are used: a supervised collective classification framework and an unsupervised optimization framework. Both approaches perform substantially better than baseline approaches, establishing the efficacy of the methods and the underlying discourse scheme. We also present quantitative and qualitative analyses showing how the improvements are achieved.

A survey of CAD model simplification techniques for physics-based simulation applications - Thakur,Atul; Banerjee,Ashis Gopal; Gupta, Satyandra K. (Computer-Aided Design, 2009)
Automated CAD model simplification plays an important role in effectively utilizing physics-based simulation during the product realization process. Currently a rich body of literature exists that describe many successful techniques for fully-automatic or semi-automatic simplification of CAD models for a wide variety of applications. The purpose of this paper is to compile a list of the techniques that are relevant for physics-based simulations problems and to characterize them based on their attributes. We have classified them into the following four categories: techniques based on surface entity based operators, volume entity based operators, explicit feature based operators, and dimension reduction operators. This paper also presents the necessary background information in the CAD model representation to assist the new readers. We conclude the paper by outlining open research directions in this field.
Keywords: CAD model simplification; Physics-based simulation

A survey of snake-inspired robot designs - Hopkins,James K.; Spranklin,Brent W.; Gupta, Satyandra K. (Bioinspiration & Biomimetics, 2009)
Body undulation used by snakes and the physical architecture of a snake body may offer significant benefits over typical legged or wheeled locomotion designs in certain types of scenarios. A large number of research groups have developed snake-inspired robots to exploit these benefits. The purpose of this review is to report different types of snake-inspired robot designs and categorize them based on their main characteristics. For each category, we discuss their relative advantages and disadvantages. This review will assist in familiarizing a newcomer to the field with the existing designs and their distinguishing features. We hope that by studying existing robots, future designers will be able to create new designs by adopting features from successful robots. The review also summarizes the design challenges associated with the further advancement of the field and deploying snake-inspired robots in practice.

A systematic approach for designing multifunctional thermally conducting polymer structures with embedded actuators - Bejgerowski,W.; Gupta,S.K.; Bruck,H. A. (Journal of Mechanical Design, 2009)

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

To join or not to join: the illusion of privacy in social networks with mixed public and private user profiles - Zheleva,Elena; Getoor, Lise (Proceedings of the 18th international conference on World wide web, 2009)
In order to address privacy concerns, many social media websites allow users to hide their personal profiles from the public. In this work, we show how an adversary can exploit an online social network with a mixture of public and private user profiles to predict the private attributes of users. We map this problem to a relational classification problem and we propose practical models that use friendship and group membership information (which is often not hidden) to infer sensitive attributes. The key novel idea is that in addition to friendship links, groups can be carriers of significant information. We show that on several well-known social media sites, we can easily and accurately recover the information of private-profile users. To the best of our knowledge, this is the first work that uses link-based and group-based classification to study privacy implications in social networks with mixed public and private user profiles.
Keywords: attribute inference; groups; privacy; social networks

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

Understanding videos, constructing plots learning a visually grounded storyline model from annotated videos - Gupta,A.; Srinivasan,P.; Shi,Jianbo; Davis, Larry S. (Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, 2009)
Analyzing videos of human activities involves not only recognizing actions (typically based on their appearances), but also determining the story/plot of the video. The storyline of a video describes causal relationships between actions. Beyond recognition of individual actions, discovering causal relationships helps to better understand the semantic meaning of the activities. We present an approach to learn a visually grounded storyline model of videos directly from weakly labeled data. The storyline model is represented as an AND-OR graph, a structure that can compactly encode storyline variation across videos. The edges in the AND-OR graph correspond to causal relationships which are represented in terms of spatio-temporal constraints. We formulate an Integer Programming framework for action recognition and storyline extraction using the storyline model and visual groundings learned from training data.
Keywords: (artificial; action; activity; analysis; integer; AND-OR; annotation; video; coding; constraint; video; construction; semantic; extraction; graph; framework; plots; graph; encoding; human; grounded; intelligence); spatiotemporal; learning; meaning; spatio-temporal; model; phenomena; video; Programming; programming; learning; recognition; human; representation; integer; storyline; theory; image; understanding; visually

Using formal specifications to support testing - Hierons,Robert M.; Krause,Paul; Lüttgen,Gerald; Simons,Anthony J. H.; Vilkomir,Sergiy; Woodward,Martin R.; Zedan,Hussein; Bogdanov,Kirill; Bowen,Jonathan P.; Cleaveland, Rance; Derrick,John; Dick,Jeremy; et al. (ACM Computing Surveys, 2009)

VAST 2009 challenge: An insider threat - Grinstein,G.; Scholtz,J.; Whiting,M.; Plaisant, Catherine (Visual Analytics Science and Technology, 2009. VAST 2009. IEEE Symposium on, 2009)
The 4th VAST Challenge centered on a cyber analytics scenario and offered three mini-challenges with datasets of badge and network traffic data, a social network including geospatial information, and security video. Teams could also enter the Grand challenge which combined all three datasets. In this paper, we summarize the dataset, the overall scenario and the questions asked in the challenges. We describe the judging process and new infrastructure developed to manage the submissions and compute accuracy measures in the social network mini challenge. We received 49 entries from 30 teams, and gave 23 different awards to a total of 16 teams.
Keywords: 2009; analytics; data; analytics; geospatial; challenge; cyber; data; security; information; information; human; interaction; network; interfaces; network; visual; traffic; user; VAST; video; social; visualisation; graphical

Video-based Lane Detection using Boosting Principles - Gopalan,R.; Hong, T.; Shneier, M.; Chellapa, Rama (Snowbird, 2009)
Autonomous navigation of road vehicles is a challenging problem that has widespread applications in intelligent systems, and robotics. An integral componentof such a system is to understand how the road is structured. Detection of road lane markings assumes importance in this regard, and this problem has been approached with different visual input- based inference algorithms ([1], [2]), besides other sensing modalities such as the GPS sensor and the internal vehicle- state sensors. But the challenge still remains when there is considerable amount of shadows on the road, variations in outdoor lighting conditions of the scene (transition from day to night), among others. To address such issues, we propose a machine learning approach based on Real Adaboost [3], and train linear classifiers for both the appearance and edge cues of the training examplars. Additionally, we incorporate prior knowledge about the relative importance of the training samples by computing their weights using kernel discriminant analysis [4], before learning the classification function through boosting. The regions identified as lane markings are then analyzed for gradient direction consistency before making the final detection decision. We illustrate the effectiveness of our algorithm on challenging daylight and night- time road scenarios.

Visibility constraints on features of 3D objects - Basri,R.; Felzenszwalb,P. F; Girshick,R. B; Jacobs, David W.; Klivans,C. J (Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, 2009)
To recognize three-dimensional objects it is important to model how their appearances can change due to changes in viewpoint. A key aspect of this involves understanding which object features can be simultaneously visible under different viewpoints. We address this problem in an image-based framework, in which we use a limited number of images of an object taken from unknown viewpoints to determine which subsets of features might be simultaneously visible in other views. This leads to the problem of determining whether a set of images, each containing a set of features, is consistent with a single 3D object. We assume that each feature is visible from a disk of viewpoints on the viewing sphere. In this case we show the problem is NP-hard in general, but can be solved efficiently when all views come from a circle on the viewing sphere. We also give iterative algorithms that can handle noisy data and converge to locally optimal solutions in the general case. Our techniques can also be used to recover viewpoint information from the set of features that are visible in different images. We show that these algorithms perform well both on synthetic data and images from the COIL dataset.
Keywords: 3D; algorithms; synthetic; complexity; iterative; constraints; computational; data; synthetic; dataset; NP-hard; image-based; features; COIL; framework; iterative; images; three-dimensional; methods; object; object; recognition; recognition; viewing; sphere; visibility

Visual-Analytics Evaluation - Plaisant, Catherine; Grinstein,G.; Scholtz,J. (Computer Graphics and Applications, IEEE, 2009)
Visual analytics (VA) is the science of analytical reasoning facilitated by interactive visual interfaces. Assessing VA technology's effectiveness is challenging because VA tools combine several disparate components, both low and high level, integrated in complex interactive systems used by analysts, emergency responders, and others. These components include analytical reasoning, visual representations, computer-human interaction techniques, data representations and transformations, collaboration tools, and especially tools for communicating the results of their use. VA tool users' activities can be exploratory and can take place over days, weeks, or months. Users might not follow a predefined or even linear work flow. They might work alone or in groups. To understand these complex behaviors, an evaluation can target the component level, the system level, or the work environment level, and requires realistic data and tasks. Traditional evaluation metrics such as task completion time, number of errors, or recall and precision are insufficient to quantify the utility of VA tools, and new research is needed to improve our VA evaluation methodology.
Keywords: analytic; analytics; evaluation; cognition; data; generation; user; interactive; interfaces; synthetic-data-set; reasoning; visual; systems; tools; visual; visual; visualisation; interactive

Web Monitoring 2.0: Crossing Streams to Satisfy Complex Data Needs - Roitman,H.; Gal,A.; Raschid, Louiqa (IEEE 25th International Conference on Data Engineering, 2009. ICDE '09, 2009)
Web monitoring 2.0 supports the complex information needs of clients who probe multiple information sources and generate mashups by integrating across these volatile streams. A proxy that aims at satisfying multiple customized client profiles will face a scalability challenge in trying to maximize the number of clients served while at the same time fully satisfying complex client needs. In this paper, we introduce an abstraction of complex execution intervals, a combination of time intervals and information streams, to capture complex client needs. Given some budgetary constraints (e.g., bandwidth), we present offline algorithmic solutions for the problem of maximizing completeness of capturing complex profiles.
Keywords: Bandwidth; complex client information need; Data Delivery; Data engineering; database management systems; Educational institutions; Internet; Mashups; mashups generation; Monitoring; multiple information source; offline algorithmic solution; Portals; PROBES; Profiles; Query processing; scalability; scheduling; volatile information stream; Web 2.0; Web Monitoring

Wideband fast multipole accelerated boundary element methods for the three-dimensional Helmholtz equation. - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2009)
The development of a fast multipole method (FMM) accelerated iterative solution of the boundary element method (BEM) for the Helmholtz equations in three dimensions is described. The FMM for the Helmholtz equation is significantly different for problems with low and high kD, where k is the wave number and D the domain size, and for large problems, the method must be switched between levels of the hierarchy. The BEM requires several approximate computations: numerical quadrature and approximations of the boundary shapes using elements. These errors must be balanced against approximations introduced by the FMM and the convergence criterion for an iterative solution. These different errors must all be chosen in a way that, on the one hand, excess work is not done and, on the other, that the error achieved by the overall computation is acceptable. Details of translation operators for low and high kD choice of representations and BEM quadrature schemes, all consistent with these approximations, are described. A novel preconditioner using a low accuracy FMM accelerated solver as a right preconditioner is also described. Results of the developed solvers for large boundary value problems with 0.0001⩽kD⩽500 are presented and shown to perform close to theoretical expectations.

The acl anthology reference corpus: A reference dataset for bibliographic research in computational linguistics - Bird,S.; Dale,R.; Dorr, Bonnie J; Gibson,B.; Joseph,M.T.; Kan,M.Y.; Lee,D.; Powley,B.; Radev,D.R.; Tan,Y.F. (Proc. of the 6th International Conference on Language Resources and Evaluation Conference (LREC’08), 2008)
The ACL Anthology is a digital archive of conference and journal papers in natural language processing and computational linguistics.Its primary purpose is to serve as a reference repository of research results, but we believe that it can also be an object of study and a platform for research in its own right. We describe an enriched and standardized reference corpus derived from the ACL Anthology that can be used for research in scholarly document processing. This corpus, which we call the ACL Anthology Reference Corpus (ACL ARC), brings together the recent activities of a number of research groups around the world. Our goal is to make the corpus widely available, and to encourage other researchers to use it as a standard testbed for experiments in both bibliographic and bibliometric research.

Active logic semantics for a single agent in a static world - Anderson,Michael L.; Gomaa,Walid; Grant,John; Perlis, Don (Artificial Intelligence, 2008)
For some time we have been developing, and have had significant practical success with, a time-sensitive, contradiction-tolerant logical reasoning engine called the active logic machine (ALMA). The current paper details a semantics for a general version of the underlying logical formalism, active logic. Central to active logic are special rules controlling the inheritance of beliefs in general (and of beliefs about the current time in particular), very tight controls on what can be derived from direct contradictions (P&¬P), and mechanisms allowing an agent to represent and reason about its own beliefs and past reasoning. Furthermore, inspired by the notion that until an agent notices that a set of beliefs is contradictory, that set seems consistent (and the agent therefore reasons with it as if it were consistent), we introduce an "apperception function" that represents an agent's limited awareness of its own beliefs, and serves to modify inconsistent belief sets so as to yield consistent sets. Using these ideas, we introduce a new definition of logical consequence in the context of active logic, as well as a new definition of soundness such that, when reasoning with consistent premises, all classically sound rules remain sound in our new sense. However, not everything that is classically sound remains sound in our sense, for by classical definitions, all rules with contradictory premises are vacuously sound, whereas in active logic not everything follows from a contradiction.
Keywords: Active logic; Autonomous agents; Brittleness; Logic; Nonmonotonic logic; Paraconsistent logic; semantics; Soundness; TIME

An AGM-based belief revision mechanism for probabilistic spatio-temporal logics - Parker,A.; Infantes,G.; V.S. Subrahmanian; Grant,J. (Proceedings of the 23rd national conference on Artificial intelligence, 2008)

Algorithms for Generating Adaptive Projection Patterns for 3D Shape Measurement - Peng,T.; Gupta,S.K. (Journal of Computing and Information Science in Engineering, 2008)

An assessment of systems and software engineering scholars and institutions (2001–2005) - Wong,W. Eric; Tse,T.H.; Glass,Robert L.; Basili, Victor R.; Chen,T.Y. (Journal of Systems and Software, 2008)
This paper presents the findings of a five-year study of the top scholars and institutions in the systems and software engineering field, as measured by the quantity of papers published in the journals of the field in 2001–2005. The top scholar is Magne Jørgensen of Simula Research Laboratory, Norway, and the top institution is Korea Advanced Institute of Science and Technology, Korea.This paper is part of an ongoing study, conducted annually, that identifies the top 15 scholars and institutions in the most recent five-year period.
Keywords: Research publications; Systems and software engineering; Top institutions; Top scholars

Athos: Efficient Authentication of Outsourced File Systems: Information Security - Triandopoulos, Nikolaos; Goodrich, Michael T.; Charalampos Papamanthou; Tamassia, Roberto (Lecture Notes in Computer Science, 2008)

Audio Camera Using Microphone Arrays for Real Time Capture of Audio Images ... - Duraiswami, Ramani; O'donovan,Adam; Neumann, Jan; Gumerov, Nail A. (2008)
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 are generated at a high frame rate to achieve a video image if the data capture and intensity computations can be performed sufficiently quickly, thereby creating a frame-rate audio camera. A description is provided herein regarding how such a camera is built and the processing done sufficiently quickly using graphics processors. The joint processing of and captured frame-rate audio and video images enables applications such as visual identification of noise sources, beamforming and noise-suppression in video conferenceing and others, by accounting 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, such joint analysis can be performed.

Automated design of distributed control rules for the self-assembly of prespecified artificial structures - Grushin,Alexander; Reggia, James A. (Robotics and Autonomous Systems, 2008)
The self-assembly problem involves the design of agent-level control rules that will cause the agents to form some desired, target structure, subject to environmental constraints. This paper describes a fully automated rule generation procedure that allows structures to successfully self-assemble in a simulated environment with constrained, continuous motion. This environment implicitly imposes ordering constraints on the self-assembly process, where certain parts of the target structure must be assembled before others, and where it may be necessary to assemble (and subsequently disassemble) temporary structures such as staircases. A provably correct methodology is presented for computing a partial order on the self-assembly process, and for generating rules that enforce this order at runtime. The assembly and disassembly of structures is achieved by generating another set of rules, which are inspired by construction behavior among certain species of social insects. Computational experiments verify the effectiveness of the approach on a diverse set of target structures.
Keywords: Collective problem solving; Coordination; Self-assembly; Stigmergy; Swarm intelligence

Beyond nouns: Exploiting prepositions and comparative adjectives for learning visual classifiers - Gupta,A.; Davis, Larry S. (Computer Vision–ECCV 2008, 2008)
Learning visual classifiers for object recognition from weakly labeled data requires determining correspondence between image regions and semantic object classes. Most approaches use co-occurrence of “nouns” and image features over large datasets to determine the correspondence, but many correspondence ambiguities remain. We further constrain the correspondence problem by exploiting additional language constructs to improve the learning process from weakly labeled data. We consider both “prepositions” and “comparative adjectives” which are used to express relationships between objects. If the models of such relationships can be determined, they help resolve correspondence ambiguities. However, learning models of these relationships requires solving the correspondence problem. We simultaneously learn the visual features defining “nouns” and the differential visual features defining such “binary-relationships” using an EM-based approach.

Biofilms in water, its role and impact in human disease transmission - Huq,Anwar; Whitehouse,Chris A.; Grim,Christopher J.; Alam,Munirul; Rita R Colwell (Current Opinion in Biotechnology, 2008)
Understanding the mechanism of biofilm formation is the first step in determining its function and, thereby, its impact and role in the environment. Extensive studies accomplished during the past few years have elucidated the genetics and biochemistry of biofilm formation. Cell-to-cell communication, that is, quorum sensing, is a key factor in the initiation of biofilm. Occurrence of viable but nonculturable bacteria, including Vibrio cholerae in biofilms has been reported and most likely such cells were overlooked previously because appropriate methods of detection were not employed. For this reason discovery and investigation of this important bacterial ecological niche in the environment were impeded.

Budgeted Allocations in the Full-Information Setting - Srinivasan, Aravind (Approximation, Randomization and Combinatorial Optimization. Algorithms and TechniquesApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 2008)
We build on the work of Andelman & Mansour and Azar, Birnbaum, Karlin, Mathieu & Thach Nguyen to show that the full-information (i.e., offline) budgeted-allocation problem can be approximated to within 4/3: we conduct a rounding of the natural LP relaxation, for which our algorithm matches the known lower-bound on the integrality gap.

Can great research be taught?: independent research with cross-disciplinary thinking and broader impact - Feamster, Nick; Gray,Alexander (Proceedings of the 39th SIGCSE technical symposium on Computer science education, 2008)
This paper describes a course we have developed for preparing new Ph.D. students in computer science for a career in research. The course is intended to teach the skills needed for research and independent work, prepare students psychologically and socially for years lying before them, and help them find a good Ph.D. topic by providing principles and examples. In this course, we emphasize and encourage impact through cross-disciplinary research and broader societal outreach. To our knowledge, the course represents a first-of-its-kind systematic introduction to a graduate research career. This paper describes our high-level goals for this curricular initiative, the structure of the course (including lecture components and assignments), and the challenges we faced in developing this course. As we continue to develop this course, which is now in its second year, we hope it will serve as a model "introduction of Ph.D. research" course for other computer science departments.
Keywords: graduate education; ph.d.; research

Capturing Approximated Data Delivery Tradeoffs - Roitman,H.; Gal,A.; Raschid, Louiqa (Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on, 2008)
This paper presents a middleware data delivery setting with a proxy that is required to maximize the completeness of captured updates, specified in its clients' profiles, while minimizing at the same time the delay in delivering the updates to clients. The two objectives may conflict when the monitoring budget is limited. Therefore, any solution should consider this tradeoff in satisfying both objectives. We term this problem the "proxy dilemma" and formalize it as a biobjective optimization problem. Such problem occurs in many contemporary applications, such as mobile and sensor networks, and poses scalability challenges in delivering up-to-date data from remote resources to meet client specifications. We present a Pareto set as a formal solution to the proxy dilemma. We discuss the complexity of generating a Pareto set for the proxy dilemma and suggest an approximation scheme to this problem.
Keywords: approximation scheme; approximation theory; biobjective optimization problem; Middleware; middleware data delivery tradeoffs; mobile networks; Pareto optimisation; Pareto set; proxy dilemma problem; sensor networks

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

Collective Classification in Network Data - Sen,Prithviraj; Namata,Galileo; Bilgic,Mustafa; Getoor, Lise; Galligher,Brian; Eliassi-Rad,Tina (AI Magazine, 2008)
Collective Classification in Network Data

Combining Domain-Independent Planning and HTN Planning: The Duet Planner - Gerevini,Alfonso; Kuter,Ugur; Nau, Dana S.; Saetti,Alessandro; Waisbrot,Nathaniel (IOS Press, 2008)
Despite the recent advances in planning for classical domains, the question of how to use domain knowledge in planning is yet to be completely and clearly answered. Some of the existing planners use domain-independent search heuristics, and some others depend on intensively-engineered domain-specific knowledge to guide the planning process. In this paper, we describe an approach to combine ideas from both of the above schools of thought. We present Duet, our planning system that incorporates the ability of using hierarchical domain knowledge in the form of Hierarchical Task Networks (HTNs) as in SHOP2 [14] and using domain-independent local search techniques as in LPG [8]. In our experiments, Duet was able to solve much larger problems than LPG could solve, with only minimal domain knowledge encoded in HTNs (much less domain knowledge than SHOP2 needed to solve those problems by itself).

Community response grid (CRG) for a university campus: Design requirements and implications - Wu,P.F.; Qu,Y.; Preece,J.; Fleischmann,K.; Golbeck,J.; Jaeger,P.; Shneiderman, Ben (Proceedings of the 5th International ISCRAM Conference, 2008)
This paper describes the initial stages of the participatory design of a community-oriented emergency responsesystem for a university campus. After reviewing related work and the current University emergency response system, this paper describes our participatory design process, discusses initial findings from a design requirement survey and from our interactions with different stakeholders, and proposes a Web interface design for a community response grid system. The prototyping of the system demonstrates the possibility of fostering a social-network-based community participation in emergency response, and also identifies concerns raised by potential users and by the professional responder community.

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

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

Content-based assembly search: A step towards assembly reuse - Deshmukh,Abhijit S.; Banerjee,Ashis Gopal; Gupta, Satyandra K.; Sriram,Ram D. (Computer-Aided Design, 2008)
The increased use of CAD systems by product development organizations has resulted in the creation of large databases of assemblies. This explosion of assembly data is likely to continue in the future. In many situations, a text-based search alone may not be sufficient to search for assemblies and it may be desirable to search for assemblies based on the content of the assembly models. The ability to perform content-based searches on these databases is expected to help the designers in the following two ways. First, it can facilitate the reuse of existing assembly designs, thereby reducing the design time. Second, a lot of useful designs for manufacturing, and assembly knowledge are implicitly embedded in existing assemblies. Therefore a capability to locate existing assemblies and examine them can be used as a learning tool by designers to learn from the existing assembly designs. This paper describes a system for performing content-based searches on assembly databases. We identify templates for comprehensive search definitions and describe algorithms to perform content-based searches for mechanical assemblies. We also illustrate the capabilities of our system through several examples.
Keywords: Assembly characteristics; Assembly mating conditions; Content-based assembly search; Graph compatibility

Context and observation driven latent variable model for human pose estimation - Gupta,A.; Chen,T.; Chen,F.; Kimber,D.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, 2008)
Current approaches to pose estimation and tracking can be classified into two categories: generative and discriminative. While generative approaches can accurately determine human pose from image observations, they are computationally expensive due to search in the high dimensional human pose space. On the other hand, discriminative approaches do not generalize well, but are computationally efficient. We present a hybrid model that combines the strengths of the two in an integrated learning and inference framework. We extend the Gaussian process latent variable model (GPLVM) to include an embedding from observation space (the space of image features) to the latent space. GPLVM is a generative model, but the inclusion of this mapping provides a discriminative component, making the model observation driven. Observation Driven GPLVM (OD-GPLVM) not only provides a faster inference approach, but also more accurate estimates (compared to GPLVM) in cases where dynamics are not sufficient for the initialization of search in the latent space. We also extend OD-GPLVM to learn and estimate poses from parameterized actions/gestures. Parameterized gestures are actions which exhibit large systematic variation in joint angle space for different instances due to difference in contextual variables. For example, the joint angles in a forehand tennis shot are function of the height of the ball (Figure 2). We learn these systematic variations as a function of the contextual variables. We then present an approach to use information from scene/objects to provide context for human pose estimation for such parameterized actions.
Keywords: estimation; estimation; image; Gaussian; gestures; pose; latent; learning; parameterized; model; human; observations; integrated; pose; process; processes; gesture; processing; pose; recognition; image; tracking; Gaussian; variable

Cost-Sharing Mechanisms for Network Design - Gupta,Anupam; Srinivasan, Aravind; Tardos,Éva (Algorithmica, 2008)
We consider a single-source network design problem from a game-theoretic perspective. Gupta, Kumar and Roughgarden (Proc. 35th Annual ACM STOC, pp. 365–372, 2003 ) developed a simple method for a single-source rent-or-buy problem that also yields the best-known approximation ratio for the problem. We show how to use a variant of this method to develop an approximately budget-balanced and group strategyproof cost-sharing method for the problem. The novelty of our approach stems from our obtaining the cost-sharing methods for the rent-or-buy problem by carefully combining cost-shares for the simpler Steiner tree problem. Our algorithm is conceptually simpler than the previous such cost-sharing method due to Pál and Tardos (Proc. 44th Annual FOCS, pp. 584–593, 2003 ), and improves the previously-known approximation factor of 15 to 4.6.

Delegating Capabilities in Predicate Encryption Systems - Elaine Shi; Waters,Brent (Automata, Languages and Programming, 2008)
In predicate encryption systems, given a capability, one can evaluate one or more predicates on the plaintext encrypted, while all other information about the plaintext remains hidden. We consider the role of delegation in such predicate encryption systems. Suppose Alice has a capability, and she wishes to delegate to Bob a more restrictive capability allowing the decryption of a subset of the information Alice can learn about the plaintext encrypted. We formally define delegation in predicate encryption systems, propose a new security definition for delegation, and give an efficient construction supporting conjunctive queries. The security of our construction can be reduced to the general 3-party Bilinear Diffie-Hellman assumption, and the Bilinear Decisional Diffie-Hellman assumption in composite order bilinear groups.
Keywords: Computer science

Design and implementation of blackboard-based system for human detection - Zhuolin Jiang; Li,S.F.; Gao,D.F. (Jisuanji Gongcheng/ Computer Engineering, 2008)

Designing community-based emergency communication system: A preliminary study - Fei Wu,P.; Qu,Y.; Fleischmann,K.; Golbeck,J.; Jaeger,P.; Preece,J.; Shneiderman, Ben (Proceedings of the American Society for Information Science and Technology, 2008)

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

Dual role colonization factors connecting Vibrio cholerae's lifestyles in human and aquatic environments open new perspectives for combating infectious diseases - Vezzulli,Luigi; Guzmán,Carlos A; Rita R Colwell; Pruzzo,Carla (Current Opinion in Biotechnology, 2008)
Vibrio cholerae exhibits two distinctive lifestyles, one inside the milieu of the human intestine and the other in the aquatic environment. Recently, the existence of V. cholerae ligands involved in colonization of both human intestine and environmental chitin surfaces via the same binding specificity has been shown. Such molecules, here named ‘dual role colonization factors (DRCFs)’, are example of a tight connection between the two V. cholerae's lifestyles. It is suggested that DRCFs and, more generally, bacterial factors and pathways having roles in pathogenesis and in the out of the human body life may be promising targets for development of novel prophylactic or therapeutic interventions that may also affect V. cholerae fitness in its environmental reservoirs.

THE EFFECT OF NETWORK STRUCTURE ON DYNAMIC TEAM FORMATION IN MULTI‐AGENT SYSTEMS - Gaston,Matthew E.; desJardins, Marie (Computational Intelligence, 2008)
Previous studies of team formation in multi-agent systems have typically assumed that the agent social network underlying the agent organization is either not explicitly described or the social network is assumed to take on some regular structure such as a fully connected network or a hierarchy. However, recent studies have shown that real-world networks have a rich and purposeful structure, with common properties being observed in many different types of networks. As multi-agent systems continue to grow in size and complexity, the network structure of such systems will become increasing important for designing efficient, effective agent communities.We present a simple agent-based computational model of team formation, and analyze the theoretical performance of team formation in two simple classes of networks (ring and star topologies). We then give empirical results for team formation in more complex networks under a variety of conditions. From these experiments, we conclude that a key factor in effective team formation is the underlying agent interaction topology that determines the direct interconnections among agents. Specifically, we identify the property of diversity support as a key factor in the effectiveness of network structures for team formation. Scale-free networks, which were developed as a way to model real-world networks, exhibit short average path lengths and hub-like structures. We show that these properties, in turn, result in higher diversity support; as a result, scale-free networks yield higher organizational efficiency than the other classes of networks we have studied.
Keywords: dynamics of networked systems; multi‐agent systems; network structure; team formation

Effective label acquisition for collective classification - Bilgic,Mustafa; Getoor, Lise (Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, 2008)
Information diffusion, viral marketing, and collective classification all attempt to model and exploit the relationships in a network to make inferences about the labels of nodes. A variety of techniques have been introduced and methods that combine attribute information and neighboring label information have been shown to be effective for collective labeling of the nodes in a network. However, in part because of the correlation between node labels that the techniques exploit, it is easy to find cases in which, once a misclassification is made, incorrect information propagates throughout the network. This problem can be mitigated if the system is allowed to judiciously acquire the labels for a small number of nodes. Unfortunately, under relatively general assumptions, determining the optimal set of labels to acquire is intractable. Here we propose an acquisition method that learns the cases when a given collective classification algorithm makes mistakes, and suggests acquisitions to correct those mistakes. We empirically show on both real and synthetic datasets that this method significantly outperforms a greedy approximate inference approach, a viral marketing approach, and approaches based on network structural measures such as node degree and network clustering. In addition to significantly improving accuracy with just a small amount of labeled data, our method is tractable on large networks.
Keywords: active inference; collective classification; label acquisition

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

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

Evaluating Visual Analytics at the 2007 VAST Symposium Contest - Plaisant, Catherine; Grinstein,G.; Scholtz,J.; Whiting,M.; O'Connell,T.; Laskowski,S.; Chien,L.; Tat,A.; Wright,W.; Gorg,C.; Zhicheng Liu; Parekh,N.; et al. (Computer Graphics and Applications, IEEE, 2008)
In this article, we report on the contest's data set and tasks, the judging criteria, the winning tools, and the overall lessons learned in the competition. We believe that by organizing these contests, we're creating useful resources for researchers and are beginning to understand how to better evaluate VA tools. Competitions encourage the community to work on difficult problems, improve their tools, and develop baselines for others to build or improve upon. We continue to evolve a collection of data sets, scenarios, and evaluation methodologies that reflect the richness of the many VA tasks and applications.
Keywords: 2007; analytics; analytics; data; and; Contest; Visual; Science; Symposium; Technology; data; VAST; visualisation; visualization; visual

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

Exploiting shared correlations in probabilistic databases - Sen,Prithviraj; Deshpande, Amol; Getoor, Lise (Proceedings of the VLDB Endowment, 2008)
There has been a recent surge in work in probabilistic databases, propelled in large part by the huge increase in noisy data sources --- from sensor data, experimental data, data from uncurated sources, and many others. There is a growing need for database management systems that can efficiently represent and query such data. In this work, we show how data characteristics can be leveraged to make the query evaluation process more efficient. In particular, we exploit what we refer to as shared correlations where the same uncertainties and correlations occur repeatedly in the data. Shared correlations occur mainly due to two reasons: (1) Uncertainty and correlations usually come from general statistics and rarely vary on a tuple-to-tuple basis; (2) The query evaluation procedure itself tends to re-introduce the same correlations. Prior work has shown that the query evaluation problem on probabilistic databases is equivalent to a probabilistic inference problem on an appropriately constructed probabilistic graphical model (PGM). We leverage this by introducing a new data structure, called the random variable elimination graph (rv-elim graph) that can be built from the PGM obtained from query evaluation. We develop techniques based on bisimulation that can be used to compress the rv-elim graph exploiting the presence of shared correlations in the PGM, the compressed rv-elim graph can then be used to run inference. We validate our methods by evaluating them empirically and show that even with a few shared correlations significant speed-ups are possible.

Fast multipole accelerated boundary element method (FMBEM) for solution of 3D scattering problems - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2008)
Wideband FMBEM codes are challenging to implement since there are problems at both very low and high frequencies. Substantially different schemes for function representation and translation are efficient for low and high frequency ranges. We present a method which is suitable for solution both high and low frequency problems since it implements a switch between different representations and uses fast translation methods appropriate to each representation. For a high frequency problem the switch between representations may occur at some intermediate levels of hierarchical space subdivision of the FMM. We also present an FMM‐based preconditioner used in the flexible GMRES iterative solver for scattering problems and discuss example problems computed in range 0.001<kD<200, where k is the wave number and D is the size of the computational domain. The theoretical and experimental computational complexity of our algorithm is approximately O((kD)3) at large kD with relatively small asymptotic constant and the algorithm allows to solve problems with up to million nodes used for surface discretization in the range tested on a conventional personal computer.

Fast Multipole Accelerated Boundary Element Methods for the 3D Helmholtz Equation - Gumerov, Nail A.; Duraiswami, Ramani (Technical Reports from UMIACS UMIACS-TR-2008-03, 2008)
The development of a fast multipole method accelerated iterativesolution of the boundary element equations for large problems involving hundreds of thousands elements for the Helmholtz equations in 3D is described. The BEM requires several approximate computations (numerical quadrature, approximations of the boundary shapes using elements) and the convergence criterion for iterative computation. When accelerated using the FMM, these different errors must all be chosen in a way that on the one hand excess work is not done and on the other that the error achieved by the overall computation is acceptable. Details of translation operators used, choices of representations, and boundary element integration consistent with these approximations are described. A novel preconditioner for accelerating convergence, using a low accuracy FMM accelerated solver as a right preconditioner is also described. Results of the developed and tested solvers for boundary value problems for the Helmholtz equations using the solver are presented for the number of unknowns N <= 106 and product of wavenumber k times domain size D, kD <= 200 and show good performance close to theoretical expectations.
Keywords: Technical Report

Fast multipole methods on graphics processors - Gumerov, Nail A.; Duraiswami, Ramani (Journal of Computational Physics, 2008)
The fast multipole method allows the rapid approximate evaluation of sums of radial basis functions. For a specified accuracy, ϵ , the method scales as O ( N ) in both time and memory compared to the direct method with complexity O ( N 2 ) , which allows the solution of larger problems with given resources. Graphical processing units (GPU) are now increasingly viewed as data parallel compute coprocessors that can provide significant computational performance at low price. We describe acceleration of the FMM using the data parallel GPU architecture.The FMM has a complex hierarchical (adaptive) structure, which is not easily implemented on data-parallel processors. We described strategies for parallelization of all components of the FMM, develop a model to explain the performance of the algorithm on the GPU architecture; and determined optimal settings for the FMM on the GPU. These optimal settings are different from those on usual CPUs. Some innovations in the FMM algorithm, including the use of modified stencils, real polynomial basis functions for the Laplace kernel, and decompositions of the translation operators, are also described. We obtained accelerations of the Laplace kernel FMM on a single NVIDIA GeForce 8800 GTX GPU in the range of 30–60 compared to a serial CPU FMM implementation. For a problem with a million sources, the summations involved are performed in approximately one second. This performance is equivalent to solving of the same problem at a 43 Teraflop rate if we use straightforward summation.

A Feature Generation Algorithm with Applications to Biological Sequence Classification - Dogan,R. I; Getoor, Lise; Wilbur,W. J (Computational Methods, 2008)

Genome-Wide Analysis of Natural Selection on Human Cis-Elements - Sethupathy,Praveen; Giang,Hoa; Plotkin,Joshua B.; Hannenhalli, Sridhar (PLoS ONEPLoS ONE, 2008)
It has been speculated that the polymorphisms in the non-coding portion of the human genome underlie much of the phenotypic variability among humans and between humans and other primates. If so, these genomic regions may be undergoing rapid evolutionary change, due in part to natural selection. However, the non-coding region is a heterogeneous mix of functional and non-functional regions. Furthermore, the functional regions are comprised of a variety of different types of elements, each under potentially different selection regimes.Using the HapMap and Perlegen polymorphism data that map to a stringent set of putative binding sites in human proximal promoters, we apply the Derived Allele Frequency distribution test of neutrality to provide evidence that many human-specific and primate-specific binding sites are likely evolving under positive selection. We also discuss inherent limitations of publicly available human SNP datasets that complicate the inference of selection pressures. Finally, we show that the genes whose proximal binding sites contain high frequency derived alleles are enriched for positive regulation of protein metabolism and developmental processes. Thus our genome-scale investigation provides evidence for positive selection on putative transcription factor binding sites in human proximal promoters.

Getting to Green: Understanding Resource Consumption in the Home - Marshini Chetty; Tran, David; Grinter, Rebecca E. (UbiComp '08, 2008)
Rising global energy demands, increasing costs and limited natural resources mean that householders are more conscious about managing their domestic resource consumption. Yet, the question of what tools Ubicomp researchers can create for residential resource management remains open. To begin to address this omission, we present a qualitative study of 15 households and their current management practices around the water, electricity and natural gas systems in the home. We find that in-the-moment resource consumption is mostly invisible to householders and that they desire more real-time information to help them save money, keep their homes comfortable and be environmentally friendly. Designing for domestic sustainability therefore turns on improving the visibility of resource production and consumption costs as well as supporting both individuals and collectives in behavior change. Domestic sustainability also highlights the caveat of potentially creating a green divide by making resource management available only to those who can afford the technologies to support being green. Finally, we suggest that the Ubicomp community can contribute to the domestic and broader sustainability agenda by incorporating green values in designs and highlight the challenge of collecting data on being green.
Keywords: domestic conservation; residential resource consumption; Sustainability

Group proximity measure for recommending groups in online social networks - Saha,B.; Getoor, Lise (networks, 2008)
There are currently, thousands of online social networks (OSN)available, each of which hosts millions of users. Users make new friendship links, join groups on diverse topics, share opinions and thus help in building a big knowledge repository. In this paper we study the problem of defining proximity measure between groups (communities) of OSN. Understanding the proximity among the groups in OSN can reveal new insights into the structure of the network. We use this proximity measure in a novel way with other structural features of online groups to predict the evolving state of the network. One of the important task in the sphere of OSN is helping users in selecting groups of their interest, by making rec- ommendations. We utilize group proximity measure to propose a new framework for recommending groups to users of OSN. Finally we investigate the effectiveness of our methods in three real OSN: Flickr, Live Journal and You Tube. Our methods give promising results.

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

Guest Editors' Introduction to the Special Section on Algorithms in Bioinformatics - Giancarlo,Raffaele; Hannenhalli, Sridhar (IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2008)
Keywords: Abstracts; Algorithm design and analysis; Bioinformatics; Biological system modeling; biology computing; Computational Biology; Computational modeling; Computer science; Genomics; sequences

How friendship links and group memberships affect the privacy of individuals in social networks - Zheleva,Elena; Getoor, Lise (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2008)
In order to address privacy concerns, many social media websites allow users to hide their personal profiles from the public. In this work, we show how an adversary can exploit a social network with a mixture of public and private user profiles to predict the private attributes of users. We map this problem to a relational classification problem and we propose a simple yet powerful model that uses group features and group memberships of users to perform multi-value classification. We compare its efficacy against several other classification approaches. Our results show that even in the case when there is an option for making profile attributes private, if links and group affiliations are known, users' privacy in social networks may be compromised. On a dataset from a well-known social-media website, we could easily recover the sensitive attributes for half of the private-profile users with a high accuracy when as much as half of the profiles are private. To the best of our knowledge, this is the first work that uses link-based and group-based classification to study privacy implications in social networks. We conclude with a discussion of our findings and the broader applicability of our proposed model.
Keywords: Technical Report

Identification of Form Features in Non-Manifold Shapes Through a Decomposition Approach - De Floriani, Leila; Hui,Annie; Giannini,Franca (ASME Conference Proceedings, 2008)
In Computer-Aided Design (CAD), the idealization process reduces the complexity of the model of a solid object, thus resulting in a simplified representation which captures only the essential elements of its shape. Form features extraction is a relevant issue in order to recover semantic information from an idealized object model, since such information is typically lost during the idealization process. An idealized model is usually composed of non-manifold parts, whose topology carries significant structural information about the object shape. To this aim, we define form features for non-manifold object by extending the taxonomy of form features provided by STEP [19]. We describe an approach for the identification of features, which interact with non-manifold singularities in the object, based on a decomposition of a non-manifold object into nearly manifold components and on the properties of the graph representing such decomposition.

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

Interactive Entity Resolution in Relational Data: A Visual Analytic Tool and Its Evaluation - Kang,Hyunmo; Getoor, Lise; Shneiderman, Ben; Bilgic,M.; Licamele,L. (IEEE Transactions on Visualization and Computer Graphics, 2008)
Databases often contain uncertain and imprecise references to real-world entities. Entity resolution, the process of reconciling multiple references to underlying real-world entities, is an important data cleaning process required before accurate visualization or analysis of the data is possible. In many cases, in addition to noisy data describing entities, there is data describing the relationships among the entities. This relational data is important during the entity resolution process; it is useful both for the algorithms which determine likely database references to be resolved and for visual analytic tools which support the entity resolution process. In this paper, we introduce a novel user interface, D-Dupe, for interactive entity resolution in relational data. D-Dupe effectively combines relational entity resolution algorithms with a novel network visualization that enables users to make use of an entity's relational context for making resolution decisions. Since resolution decisions often are interdependent, D-Dupe facilitates understanding this complex process through animations which highlight combined inferences and a history mechanism which allows users to inspect chains of resolution decisions. An empirical study with 12 users confirmed the benefits of the relational context visualization on the performance of entity resolution tasks in relational data in terms of time as well as users' confidence and satisfaction.
Keywords: algorithms; Computer Graphics; D-Dupe; data visualisation; database management systems; Databases, Factual; graphical user interface; Graphical user interfaces; human-centered computing; Image Interpretation, Computer-Assisted; Information Storage and Retrieval; Information Visualization; interactive entity resolution; relational context visualization; Relational databases; relational entity resolution algorithm; User interfaces; user-centered design; User-Computer Interface; visual analytic tool

LEARNING STRUCTURED BAYESIAN NETWORKS: COMBINING ABSTRACTION HIERARCHIES AND TREE‐STRUCTURED CONDITIONAL PROBABILITY TABLES - desJardins, Marie; Rathod,Priyang; Getoor, Lise (Computational Intelligence, 2008)
Context-specific independence representations, such as tree-structured conditional probability distributions, capture local independence relationships among the random variables in a Bayesian network (BN). Local independence relationships among the random variables can also be captured by using attribute-value hierarchies to find an appropriate abstraction level for the values used to describe the conditional probability distributions. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models. In this paper, we introduce Tree-Abstraction-Based Search (TABS), an approach for learning a data distribution by inducing the graph structure and parameters of a BN from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. To construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. We present empirical results for three real-world domains, finding that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies.
Keywords: abstraction hierarchies; background knowledge; Bayesian networks; clustering; machine learning; MDL

Learning To Predict Bad Behavior - Ahmed Syed,N.; Feamster, Nick; Gray,A. (NIPS 2007 Workshop on Machine Learning in Adversarial Environments for Computer Security, 2008)

Leveraging social context for searching social media - Smith,Marc; Barash,Vladimir; Getoor, Lise; Lauw,Hady W. (Proceedings of the 2008 ACM workshop on Search in social media, 2008)
The ability to utilize and benefit from today's explosion of social media sites depends on providing tools that allow users to productively participate. In order to participate, users must be able to find resources (both people and information) that they find valuable. Here, we argue that in order to do this effectively, we should make use of a user's "social context". A user's social context includes both their personal social context (their friends and the communities to which they belong) and their community social context (their role and identity in different communities).
Keywords: social context; social media; social search

Methods to directly measure the trapping potential in optical tweezers - Balijepalli,A.; LeBrun,T. W.; Gorman,J. J.; Gupta,S.K. (2008)
Techniques to measure the trapping force in an optical tweezers without any prior assumptions about the trapshape have been developed. The response of a trapped micro or nanoparticle to a step input is measured and then used to calculate the trapping force experienced by the particle as a function of it’s position in the trap. This method will provide new insight into the trapping behavior of nanoparticles, which are more weakly bound than microparticles and thereby explore larger regions of the trapping potential due to Brownian motion. Langevin dynamics simulations are presented to model the system and are used to demonstrate this technique. Preliminary experimental results are then presented to validate the simulations. Finally, the measured trapping forces, from simulations and laboratory experiments, are integrated to recover the trapping potential.

Modeling Transfer Relationships Between Learning Tasks for Improved Inductive Transfer - Eaton,Eric; desJardins, Marie; Lane,Terran (Machine Learning and Knowledge Discovery in DatabasesMachine Learning and Knowledge Discovery in Databases, 2008)
In this paper, we propose a novel graph-based method for knowledge transfer. We model the transfer relationships between source tasks by embedding the set of learned source models in a graph using transferability as the metric. Transfer to a new problem proceeds by mapping the problem into the graph, then learning a function on this graph that automatically determines the parameters to transfer to the new learning task. This method is analogous to inductive transfer along a manifold that captures the transfer relationships between the tasks. We demonstrate improved transfer performance using this method against existing approaches in several real-world domains.

More Than Meets the Eye: Transforming the User Experience of Home Network Management - Poole, Erika Shehan; Marshini Chetty; Grinter, Rebecca E.; Edwards, W. Keith (Proceedings of the 7th ACM conference on Designing interactive systems, 2008)
As computing migrates from the workplace to the home, householders must tackle problems of home network maintenance. Often they lack the technical knowledge or motivation to complete these tasks, making the user experience of home network maintenance frustrating. In response to these difficulties, many householders rely on handwritten reminders or interactive networking tools that are ill-suited for the home environment. In this paper, we seek to understand how to design better home network management tools through a study of sketches created by 40 people in 18 households. In our study, we obtained information about householders' knowledge, practices and needs with respect to home networking. Based on our results, we present guidelines for transforming the user experience of home network management.
Keywords: home networks; sketching; troubleshooting

Navigating information spaces: A case study of related article search in PubMed - Jimmy Lin; DiCuccio,Michael; Grigoryan,Vahan; Wilbur,W. John (Information Processing & Management, 2008)
The concept of an â€œinformation spaceâ€ provides a powerful metaphor for guiding the design of interactive retrieval systems. We present a case study of related article search, a browsing tool designed to help users navigate the information space defined by results of the PubMedÂ® search engine. This feature leverages content-similarity links that tie MEDLINEÂ® citations together in a vast document network. We examine the effectiveness of related article search from two perspectives: a topological analysis of networks generated from information needs represented in the TREC 2005 genomics track and a query log analysis of real PubMed users. Together, data suggest that related article search is a useful feature and that browsing related articles has become an integral part of how users interact with PubMed.
Keywords: Browsing; Interactive IR; MEDLINE; TREC genomics

A New Approach of Dynamic Background Modeling for Surveillance Information - Gao,Dongfa; Zhuolin Jiang; Ye,Ming (Computer Science and Software Engineering, 2008 International Conference on, 2008)
This paper presents a new approach of best background modeling for surveillance information. The approach makes orthogonal non-separable wavelet transformation of information frames used for background modeling, extracts the approximate information to reconstruct information frames, filters out the disturbance, shadow and noise from the reconstructed frames, constructs basic background with the method of binary mask images, uses multi-frame combination of non-uniform noise to filter noise in basic background, applies mutual information to detect the situation of adjacent changes. If the background has a gradual change, weighted superposition of multi background modeling images with time will be applied to update the background. If the background has a major or sudden change, the background will remodel from this frame.
Keywords: approximate information extraction; binary mask images; disturbance filtering; dynamic background modeling; Feature extraction; filtering theory; Image reconstruction; information frame reconstruction; NOISE; noise filtering; orthogonal nonseparable wavelet transformation; Surveillance; surveillance information; Wavelet transforms

Occurrence and Expression of Luminescence in Vibrio Cholerae - Grim,Christopher J.; Taviani,Elisa; Alam,Munirul; Huq,Anwar; Sack,R. Bradley; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2008)
Several species of the genus Vibrio, including Vibrio cholerae, are bioluminescent or contain bioluminescent strains. Previous studies have reported that only 10% of V. cholerae strains are luminescent. Analysis of 224 isolates of non-O1/non-O139 V. cholerae collected from Chesapeake Bay, MD, revealed that 52% (116/224) were luminescent when an improved assay method was employed and 58% (130/224) of isolates harbored the luxA gene. In contrast, 334 non-O1/non-O139 V. cholerae strains isolated from two rural provinces in Bangladesh yielded only 21 (6.3%) luminescent and 35 (10.5%) luxA+ isolates. An additional 270 clinical and environmental isolates of V. cholerae serogroups O1 and O139 were tested, and none were luminescent or harbored luxA. These results indicate that bioluminescence may be a trait specific for non-O1/non-O139 V. cholerae strains that frequently occur in certain environments. Luminescence expression patterns of V. cholerae were also investigated, and isolates could be grouped based on expression level. Several strains with defective expression of the lux operon, including natural K variants, were identified.