The Genome Sequence of Trypanosoma Cruzi, Etiologic Agent of Chagas Disease - El‐Sayed, Najib M.; Myler,Peter J.; Bartholomeu,Daniella C.; Nilsson,Daniel; Aggarwal,Gautam; Tran,Anh-Nhi; Ghedin,Elodie; Worthey,Elizabeth A.; Delcher,Arthur L.; Blandin,Gaëlle; Westenberger,Scott J.; Caler,Elisabet; et al. (ScienceScience, 2005)
Whole-genome sequencing of the protozoan pathogen Trypanosoma cruzi revealed that the diploid genome contains a predicted 22,570 proteins encoded by genes, of which 12,570 represent allelic pairs. Over 50% of the genome consists of repeated sequences, such as retrotransposons and genes for large families of surface molecules, which include trans-sialidases, mucins, gp63s, and a large novel family (>1300 copies) of mucin-associated surface protein (MASP) genes. Analyses of the T. cruzi, T. brucei, and Leishmania major (Tritryp) genomes imply differences from other eukaryotes in DNA repair and initiation of replication and reflect their unusual mitochondrial DNA. Although the Tritryp lack several classes of signaling molecules, their kinomes contain a large and diverse set of protein kinases and phosphatases; their size and diversity imply previously unknown interactions and regulatory processes, which may be targets for intervention.

The Genome Sequence of Trypanosoma cruzi, Etiologic Agent of Chagas Disease - El‐Sayed, Najib M.; Myler,Peter J.; Bartholomeu,Daniella C.; Nilsson,Daniel; Aggarwal,Gautam; Tran,Anh-Nhi; Ghedin,Elodie; Worthey,Elizabeth A.; Delcher,Arthur L.; Blandin,Gaëlle; Westenberger,Scott J.; Caler,Elisabet; et al. (Science, 2005)
Whole-genome sequencing of the protozoan pathogen Trypanosoma cruzi revealed that the diploid genome contains a predicted 22,570 proteins encoded by genes, of which 12,570 represent allelic pairs. Over 50% of the genome consists of repeated sequences, such as retrotransposons and genes for large families of surface molecules, which include trans-sialidases, mucins, gp63s, and a large novel family (>1300 copies) of mucin-associated surface protein (MASP) genes. Analyses of the T. cruzi, T. brucei, and Leishmania major (Tritryp) genomes imply differences from other eukaryotes in DNA repair and initiation of replication and reflect their unusual mitochondrial DNA. Although the Tritryp lack several classes of signaling molecules, their kinomes contain a large and diverse set of protein kinases and phosphatases; their size and diversity imply previously unknown interactions and regulatory processes, which may be targets for intervention.

Geometric algorithms for containment analysis of rotational parts - Karnik,Mukul; Gupta, Satyandra K.; Magrab,Edward B. (Computer-Aided Design, 2005)
This paper describes a system and underlying algorithms to perform geometric containment analysis to determine if a newly designed rotational part can be manufactured from a part in an existing database of rotational parts. Only material removal of the database part is considered in order to obtain the newly designed part from the database part. The system uses a three-step algorithm to test for containment. The first step analyzes feasibility of containment using bounding cylinders. If the bounding cylinder of the query part is bigger than the part in the database, then the database part cannot contain the query part and it is eliminated from consideration. The second step analyzes feasibility of containment by ignoring off-axis features. Any part that fails to satisfy containment at this stage is eliminated from consideration. The third step analyzes the remaining parts from the database for feasibility of containment by including the off-axis features. Finally, the system rank-orders all the database parts that can contain the query part based on their volume differences with the query part. The system described in this paper can be used by designers and process planners to find an existing part that can be used as a stock to manufacture a newly designed part. This capability is expected to significantly reduce proliferation of parts, to improve manufacturing responsiveness, and to reduce the cost of new products.
Keywords: COMPUTER AIDED DESIGN; geometric reasoning; Part containment; Shape signatures; Shape similarity

A hierarchical task-network planner based on symbolic model checking - Kuter,U.; Nau, Dana S.; Pistore,M.; Traverso,P. (2005)
Although several approaches have been developed for planning in nondeterministic domains, solving large planning problems is still quite difficult. In this work, we present a novel algorithm, called YoYo, for planning in nondeterministic domains under the assumption of full observability. This algorithm enables us to combine the power of search-control strategies as in Planning with Hierarchical Task Networks (HTNs) with tech- niques from the Planning via Symbolic Model-Checking (SMC). Our experimental evaluation confirms the po- tentialities of our approach, demonstrating that it com- bines the advantages of these paradigms.

HOPE: A Homotopy Optimization Method for Protein Structure Prediction - Dunlavy,Daniel M.; O'Leary, Dianne P.; Klimov,Dmitri; Thirumalai,D. (Journal of Computational Biology, 2005)
We use a homotopy optimization method, HOPE, to minimize the potential energy associated with a protein model. The method uses the minimum energy conformation of one protein as a template to predict the lowest energy structure of a query sequence. This objective is achieved by following a path of conformations determined by a homotopy between the potential energy functions for the two proteins. Ensembles of solutions are produced by perturbing conformations along the path, increasing the likelihood of predicting correct structures. Successful results are presented for pairs of homologous proteins, where HOPE is compared to a variant of Newton's method and to simulated annealing.

Identity-based zero-knowledge - Katz, Jonathan; Ostrovsky,R.; Rabin,M. (Security in Communication Networks, 2005)
We introduce and define the notion of identity-based zero-knowledge, concentrating on the non-interactive setting. In this setting, our notion allows any prover to widely disseminate a proof of a statement while protecting the prover from plagiarism in the following sense: although proofs are transferable (i.e., publicly verifiable), they are also bound to the identity of the prover in a way which is recognizable to any verifier. Furthermore, an adversary is unable to change this identity (i.e., to claim the proof as his own, or to otherwise change the authorship), unless he could have proved the statement on his own.While we view the primary contribution of this work as a formal definition of the above notion, we also explore the relation of this notion to that of non-malleable (non-interactive) zero-knowledge. On the one hand, we show that these two notions are incomparable: that is, there are proof systems which are non-malleable but not identity-based, and vice versa. On the other hand, we show that a proof system of either type essentially implies a proof system of the other type.

Immediate Usability: A Case Study of Public Access Design for a Community Photo Library (2003) - Kules,Bill; Kang,Hyunmo; Plaisant, Catherine; Rose,Anne; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
This paper describes a novel instantiation of a digital photo library in a public access system. It demonstrates how designers can utilize characteristics of a target user community (social constraints, trust, and a lack of anonymity) to provide capabilities that would be impractical in other types of public access systems. It also presents a compact set of design principles and guidelines for ensuring the immediate usability of public access information systems. These principles and guidelines were derived from our experience developing PhotoFinder Kiosk, a community photo library. Attendees of a major HCI conference (CHI 2001 Conference on Human Factors in Computing Systems) successfully used the tool to browse and annotate collections of photographs spanning 20 years of HCI-related conferences, producing a richly annotated photo history of the field of human-computer interaction. Observations and log data were used to evaluate the tool and develop the guidelines. They provide specific guidance for practitioners, as well as a useful framework for additional research in public access interfaces.
Keywords: Technical Report

Immediate Usability: Kiosk design principles from the CHI 2001 Photo Library (2001) - Kules,Bill; Kang,Hyunmo; Plaisant, Catherine; Rose,Anne; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
This paper describes a novel set of design principles and guidelines for ensuring the immediate usability of public access systems. These principles and guidelines were formulated while developing PhotoFinder Kiosk, a community photo library. Attendees of CHI 2001 successfully used the tool to browse and annotate collections of photographs spanning 20 years of CHI and related conferences, producing a richly annotated photo history of the field of human-computer interaction. We used observations and log data to evaluate the tool and refine the guidelines. They provide specific guidance for practitioners, as well as a useful framework for additional research in public access interfaces.
Keywords: Technical Report

Improved efficiency for CCA-secure cryptosystems built using identity-based encryption - Boneh,D.; Katz, Jonathan (Topics in Cryptology–CT-RSA 2005, 2005)
Recently, Canetti, Halevi, and Katz showed a general method for constructing CCA-secure encryption schemes from identity-based encryption schemes in the standard model. We improve the efficiency of their construction, and show two specific instantiations of our resulting scheme which offer the most efficient encryption (and, in one case, key generation) of any CCA-secure encryption scheme to date.

Information gathering during planning for Web Service composition - Kuter,Ugur; Sirin,Evren; Parsia,Bijan; Nau, Dana S.; Hendler,James (Web Semantics: Science, Services and Agents on the World Wide Web, 2005)
Hierarchical task network (HTN) based planning techniques have been applied to the problem of composing Web Services, especially when described using the OWL-S service ontologies. Many of the existing Web Services are either exclusively information providing or crucially depend on information-providing services. Thus, many interesting service compositions involve collecting information either during execution or during the composition process itself. In this paper, we focus on the latter issue. In particular, we present ENQUIRER , an HTN-planning algorithm designed for planning domains in which the information about the initial state of the world may not be complete, but it is discoverable through plan-time information-gathering queries. We have shown that ENQUIRER is sound and complete, and derived several mathematical relationships among the amount of available information, the likelihood of the planner finding a plan, and the quality of the plan found. We have performed experimental tests that confirmed our theoretical results and that demonstrated how ENQUIRER can be used for Web Service composition.
Keywords: HTN planning; Information gathering; Web Service composition

Information Visualization and the Challenge of Universal Usability - Plaisant, Catherine (Exploring GeovisualizationExploring Geovisualization, 2005)
Information Visualization aims to provide compact graphical presentations and user interfaces for interactively manipulating large numbers of items. We present a simple “data by tasks taxonomy” then discuss the challenges of providing universal usability, with example applications using geo-referenced data. Information Visualization has been shown to be a powerful visual thinking or decision tool but it is becoming important for services to reach and empower every citizen. Technological advances are needed to deal with user diversity (age, language, disabilities, etc.) but also with the variety of technology used (screen size, network speed, etc.) and the gaps in user's knowledge (general knowledge, knowledge of the application domain, of the interface syntax or semantic). We present examples that illustrate how those challenges can be addressed.

Interactive pattern search in time series - Buono,Paolo; Aris,Aleks; Plaisant, Catherine; Khella,Amir; Shneiderman, Ben (Proceedings of SPIE, 2005)
The need for pattern discovery in long time series data led researchers to develop algorithms for similarity search. Most of the literature about time series focuses on algorithms that index time series and bring the data into the main storage, thus providing fast information retrieval on large time series. This paper reviews the state of the art in visualizing time series, and focuses on techniques that enable users to visually and interactively query time series. Then, it presents TimeSearcher 2, a tool that enables users to explore multidimensional data using synchronized tables and graphs with overview+detail, filter the time series data to reduce the scope of the search, select an existing pattern to find similar occurrences, and interactively adjust similarity parameters to narrow the result set. This tool is an extension of previous work, TimeSearcher 1, which uses graphical timeboxes to interactively query time series data.

Interactive Pattern Search in Time Series (2004) - Buono,Paolo; Aris,Aleks; Plaisant, Catherine; Khella,Amir; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
The need for pattern discovery in long time series data led researchers to develop algorithms for similarity search. Most of the literature about time series focuses on algorithms that index time series and bring the data into the main storage, thus providing fast information retrieval on large time series. This paper reviews the state of the art in visualizing time series, and focuses on techniques that enable users to interactively query time series. Then it presents TimeSearcher 2, a tool that enables users to explore multidimensional data using coordinated tables and graphs with overview+detail, filter the time series data to reduce the scope of the search, select an existing pattern to find similar occurrences, and interactively adjust similarity parameters to narrow the result set. This tool is an extension of previous work, TimeSearcher 1, which uses graphical timeboxes to interactively query time series data.
Keywords: Technical Report

Johns Hopkins summer workshop final report on parsing and spoken structural event detection - Harper,MP; Dorr, Bonnie J; Hale,J.; Roark,B.; Shafran,I.; Lease,M.; Liu,Y.; Snover,M.; Yung,L.; Krasnyanskaya,A. (Johns Hopkins University, Tech. Rep, 2005)
This report describes research conducted by the Parsing and Spoken Structural Event Detection(PaSSED) team as part of the 2005 Johns Hopkins Summer Workshop on Language Engineering. This project investigated the interaction between parsing and the detection of structural metadata in conversational speech, including sentence boundaries, edits (the reparandum portion of speech repairs), and fillers. In terms of parsing, we explored alternative methods of exploiting metadata information in parsing models and measured how varying accuracy in transcription and metadata information affects parsing accuracy. In the other direction, we similarly considered how syntactic and prosodic knowledge could be leveraged in metadata detection, measuring how this knowledge impacts metadata detection accuracy. As part of this work, we investigated metrics for evaluating parse accuracy in the presence of tran- scription and metadata detection errors, and we report on our experience using these metrics with several parsers and across varying experimental conditions. A range of methods for handling edits during pars- ing were evaluated in this research (excision, addition of markups to the input string, and grammar modification). We also developed a ToBI (a prosodic structure annotation scheme [SBP+92]) prosodic event classifier and describe its evaluation. Finally, we present methods for effective n-best sentence boundary candidate generation and reranking using syntactic, prosodic, and other features. These stud- ies are complemented by a second set of reranking investigations wherein we optimize sentence boundary detection explicitly to improve parse accuracy. The PaSSED project has: • investigated various techniques to enhance parsing of speech given metadata detection on conver- sational speech; • defined metrics for evaluating speech parsing accuracy, implemented them in the publically avail- able SParseval software package, and evaluated them under a wide variety of conditions; • recast SU detection as an n-best reranking problem with a relatively small n. Using this approach, we demonstrated significant improvements over a very strong baseline SU detection system. • reported on the interaction between parsing and metadata detection and their synergy; • fostered new collaborations and identified a number of interesting avenues for future work.

A logic-based model of intention formation and action for multi-agent subcontracting - Grant,John; Kraus,Sarit; Perlis, Don (Artificial Intelligence, 2005)
We present a formalism for representing the formation of intentions by agents engaged in cooperative activity. We use a syntactic approach presenting a formal logical calculus that can be regarded as a meta-logic that describes the reasoning and activities of the agents. Our central focus is on the evolving intentions of agents over time, and the conditions under which an agent can adopt and maintain an intention. In particular, the reasoning time and the time taken to subcontract are modeled explicitly in the logic. We axiomatize the concept of agent interactions in the meta-language, show that the meta-theory is consistent and describe the unique intended model of the meta-theory. In this context we deal both with subcontracting between agents and the presence of multiple recipes, that is, multiple ways of accomplishing tasks. We show that under various initial conditions and known facts about agent beliefs and abilities, the meta-theory representation yields good results.
Keywords: Cooperative agents; intentions; Minimal model semantics; Subcontracting; Syntactic logic

Main effects screening - Yilmaz,Cemal; Krishna,Arvind S.; Memon, Atif M.; Porter, Adam; Schmidt,Douglas C.; Gokhale,Aniruddha; Natarajan,Balachandran (Proceedings of the 27th international conference on Software engineering - ICSE '05, 2005)

Main effects screening: a distributed continuous quality assurance process for monitoring performance degradation in evolving software systems - Yilmaz,Cemal; Krishna,Arvind S.; Memon, Atif M.; Porter, Adam; Schmidt,Douglas C.; Gokhale,Aniruddha; Natarajan,Balachandran (Proceedings of the 27th international conference on Software engineering, 2005)
Developers of highly configurable performance-intensive software systems often use a type of in-house performance-oriented "regression testing" to ensure that their modifications have not adversely affected their software's performance across its large configuration space. Unfortunately, time and resource constraints often limit developers to in-house testing of a small number of configurations and unreliable extrapolation from these results to the entire configuration space, which allows many performance bottlenecks and sources of QoS degradation to escape detection until systems are fielded. To improve performance assessment of evolving systems across large configuration spaces, we have developed a distributed continuous quality assurance (DCQA) process called main effects screening that uses in-the-field resources to execute formally designed experiments to help reduce the configuration space, thereby allowing developers to perform more targeted in-house QA. We have evaluated this process via several feasibility studies on several large, widely-used performance-intensive software systems. Our results indicate that main effects screening can detect key sources of performance degradation in large-scale systems with significantly less effort than conventional techniques.
Keywords: design of experiment theory; distributed continuous quality assurance; performance-oriented regression testing

Making Computer and Internet Usability a Priority (2000) - Kreitzberg,Charles B; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
As usability professionals, we are all too aware of the productivity losses, frustration, and lost business that results from poorly designed user interfaces. And we are uncomfortable with the risks created by poorly designed computer systems in life-critical applications such as air travel, medical care, and military applications. Yet despite the common sense of our approach, we still find it difficult to convince the technical and managerial communities that usability is a critical business parameter. While senior managers may support the concept of usability, project mangers and developers, coping with too tight schedules, often see it as a nicety that can be eliminated.
Keywords: Technical Report

MCMC-based particle filtering for tracking a variable number of interacting targets - Zia Khan; Balch, T.; Dellaert, F. (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005)
We describe a particle filter that effectively deals with interacting targets, targets that are influenced by the proximity and/or behavior of other targets. The particle filter includes a Markov random field (MRF) motion prior that helps maintain the identity of targets throughout an interaction, significantly reducing tracker failures. We show that this MRF prior can be easily implemented by including an additional interaction factor in the importance weights of the particle filter. However, the computational requirements of the resulting multitarget filter render it unusable for large numbers of targets. Consequently, we replace the traditional importance sampling step in the particle filter with a novel Markov chain Monte Carlo (MCMC) sampling step to obtain a more efficient MCMC-based multitarget filter. We also show how to extend this MCMC-based filter to address a variable number of interacting targets. Finally, we present both qualitative and quantitative experimental results, demonstrating that the resulting particle filters deal efficiently and effectively with complicated target interactions.
Keywords: algorithms; Animals; Artificial intelligence; Computer simulation; Computer vision; Filtering; filtering theory; HUMANS; Image Enhancement; Image Interpretation, Computer-Assisted; Index Terms- Particle filters; Information Storage and Retrieval; Insects; interacting targets; Markov chain Monte Carlo sampling step; Markov chain Monte Carlo.; Markov chains; Markov processes; Markov random field motion; Markov random fields; Models, Biological; Models, Statistical; Monte Carlo Method; Monte Carlo methods; MOTION; Movement; multitarget filter; multitarget tracking; particle filtering; Particle filters; Particle tracking; Pattern Recognition, Automated; Sampling methods; Subtraction Technique; target tracking; Video Recording

Meaningful presentations of photo libraries: rationale and applications of bi-level radial quantum layouts - Kustanowitz,J.; Shneiderman, Ben (Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries, 2005. JCDL '05, 2005)
Searching photo libraries can be made more satisfying and successful if search results are presented in a way that allows users to gain an overview of the photo categories. Since photo layouts on computer displays are the primary way that users get an overview, we propose a novel approach to show more photos in meaningful groupings. Photo layouts can be linear strips, or zoomable three dimensional arrangements, but the most common form is the two-dimensional grid. This paper introduces a novel bi-level hierarchical layout with motivating examples. In a bilevel hierarchy, one region is designated for primary content - an image, text, or combination. Adjacent to that region, groups of photos are placed radially in an ordered fashion, such that the relationship of the single primary region to its many secondary regions is apparent. A compelling aspect is the interactive experience in which the layout is dynamically resized, allowing users to rapidly, incrementally, and reversibly alter the dimensions and content. It can accommodate hundreds of photos in dozens of regions, can be customized in a corner or center layout, and can scale from an element on a web page to a large poster size. On typical displays (1024 times 1280 or 1200 times 1600 pixels), bi-level radial quantum layouts can conveniently accommodate 2-20 regions with tens or hundreds of photos per region
Keywords: 1024 pixel; 1200 pixel; 1280 pixel; 1310720 pixel; 1600 pixel; 1920000 pixel; Application software; bi-level radial quantum layouts; Computer displays; Computer science; digital libraries; Educational institutions; Image retrieval; Layout; layout generation; Lifting equipment; linear strips; Permission; photo layouts; photo library searching; photo management; Photography; Quantum computing; software libraries; Strips; two-dimensional grid; User interfaces; visual databases; visual presentation; zoomable three dimensional arrangements

MediaFinder: An Interface for Dynamic Personal Media Management with Semantic Regions (2003) - Kang,Hyunmo; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Computer users deal with large amounts of personal media often face problems in managing and exploring it. This paper presents Semantic Regions, rectangular regions that enable users to specify their semantics or mental models, and the MediaFinder application, which uses Semantic Regions as the basis of a personal media management tool.
Keywords: Technical Report

Modeling insider attacks on group key-exchange protocols - Katz, Jonathan; Shin,Ji Sun (Proceedings of the 12th ACM conference on Computer and communications security, 2005)
Protocols for authenticated key exchange (AKE) allow parties within an insecure network to establish a common session key which can then be used to secure their future communication. It is fair to say that group AKE is currently less well understood than the case of two-party AKE; in particular, attacks by malicious insiders --- a concern specific to the group setting --- have so far been considered only in a relatively "ad-hoc" fashion. The main contribution of this work is to address this deficiency by providing a formal, comprehensive model and definition of security for group AKE which automatically encompasses insider attacks. We do so by defining an appropriate ideal functionality for group AKE within the universal composability (UC) framework. As a side benefit, any protocol secure with respect to our definition is secure even when run concurrently with other protocols, and the key generated by any such protocol may be used securely in any subsequent application.In addition to proposing this definition, we show that the resulting notion of security is strictly stronger than the one proposed by Bresson, et al. (termed "AKE-security"), and that our definition implies all previously-suggested notions of security against insider attacks. We also show a simple technique for converting any AKE-secure protocol into one secure with respect to our definition.
Keywords: group key exchange; insider attacks; universal composability

Modeling of block-based DSP systems - Ko,D. I; Bhattacharyya, Shuvra S. (The Journal of VLSI Signal Processing, 2005)

Motivating annotation for personal digital photo libraries: Lowering barriers while raising incentives - Kustanowitz,J.; Shneiderman, Ben (University of Marlyand, 2005)
The value of personal digital photo libraries grows immensely when users invest effort to annotate their photos. Frameworksfor understanding annotation requirements could guide improved strategies that would motivate more users to invest the necessary effort. We propose one framework for annotation techniques along with the strengths and weaknesses of each one, and a second framework for target user groups and their motivations. Several applications are described that provide useful and information-rich representations, but which require good annotations, in the hope of providing incentives for high quality annotation. We describe how annotations make possible four novel presentations of personal photo collections: (1) Birthday Collage to show growth of a child over several years, (2) FamiliarFace to show family trees of photos, (3) Kaleidoscope to show photos of related people in an appealing tableau, and (4) TripPics to show photos from a sequential story such as a vacation trip.

Multimedia fingerprinting forensics for traitor tracing - KJR Liu, W. Trappe, Z.J. Wang, M. Wu,H Zhao (Hindawi Pub Corp, 2005)

Multitarget tracking with split and merged measurements - Zia Khan; Balch, T.; Dellaert, F. (IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005. CVPR 2005, 2005)
In many multitarget tracking applications in computer vision, a detection algorithm provides locations of potential targets. Subsequently, the measurements are associated with previously estimated target trajectories in a data association step. The output of the detector is often imperfect and the detection data may include multiple, split measurements from a single target or a single merged measurement from several targets. To address this problem, we introduce a multiple hypothesis tracker for interacting targets that generate split and merged measurements. The tracker is based on an efficient Markov chain Monte Carlo (MCMC) based auxiliary variable particle filter. The particle filter is Rao-Blackwellized such that the continuous target state parameters are estimated analytically, and an MCMC sampler generates samples from the large discrete space of data associations. In addition, we include experimental results in a scenario where we track several interacting targets that generate these split and merged measurements.
Keywords: Application software; Computer vision; Detection algorithms; Detectors; filtering theory; Markov chain Monte Carlo based auxiliary variable particle filter; Markov processes; merged measurements; Monte Carlo methods; multiple hypothesis tracker; multitarget tracking; parameter estimation; Particle filters; Particle tracking; Rao-Blackwellized filter; split measurements; target tracking; Trajectory

OCR post-processing for low density languages - Kolak,O.; Resnik, Philip (Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005)

An outdoor 3-D visual tracking system for the study of spatial navigation and memory in rhesus monkeys - Zia Khan; Herman, Rebecca A.; Wallen, Kim; Balch, Tucker (Behavior Research Methods, 2005)
Previous studies of the navigational abilities of nonhuman primates have largely been limited to what could be described by a human observer with a pen and paper. Consequently, we have developed a system that uses a pair of cameras to automatically obtain the three-dimensional trajectory of rhesus monkeys performing an outdoor spatial navigation and memory task. The system provides trajectories, path length, speed, and other variables that would be impossible for an unaided observer to note. From trajectory data, we computed and validated a path-length measurement. We use this measurement to compare the navigation abilities of several animals. In addition, we provide quantitative data on the accuracy of a method for automatic behavior detection. Currently, the system is being used to examine the sex differences in spatial navigation of rhesus monkeys. We expect that measures derived from the trajectory data will reveal strategies used by animals to solve spatial problems.
Keywords: cognitive psychology

A pairwise key predistribution scheme for wireless sensor networks - Du,Wenliang; Deng,Jing; Han,Yunghsiang S.; Varshney,Pramod K.; Katz, Jonathan; Khalili,Aram (ACM Trans. Inf. Syst. Secur., 2005)
To achieve security in wireless sensor networks, it is important to be able to encrypt and authenticate messages sent between sensor nodes. Before doing so, keys for performing encryption and authentication must be agreed upon by the communicating parties. Due to resource constraints, however, achieving key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and other public-key based schemes, are not suitable for wireless sensor networks due to the limited computational abilities of the sensor nodes. Predistribution of secret keys for all pairs of nodes is not viable due to the large amount of memory this requires when the network size is large.In this paper, we provide a framework in which to study the security of key predistribution schemes, propose a new key predistribution scheme which substantially improves the resilience of the network compared to previous schemes, and give an in-depth analysis of our scheme in terms of network resilience and associated overhead. Our scheme exhibits a nice threshold property: when the number of compromised nodes is less than the threshold, the probability that communications between any additional nodes are compromised is close to zero. This desirable property lowers the initial payoff of smaller-scale network breaches to an adversary, and makes it necessary for the adversary to attack a large fraction of the network before it can achieve any significant gain.
Keywords: key predistribution; Security; Wireless sensor networks

Pioneer: verifying code integrity and enforcing untampered code execution on legacy systems - Seshadri, Arvind; Luk, Mark; Elaine Shi; Perrig, Adrian; van Doorn, Leendert; Khosla, Pradeep (ACM SIGOPS Operating Systems Review, 2005)
We propose a primitive, called Pioneer, as a first step towards verifiable code execution on untrusted legacy hosts. Pioneer does not require any hardware support such as secure co-processors or CPU-architecture extensions. We implement Pioneer on an Intel Pentium IV Xeon processor. Pioneer can be used as a basic building block to build security systems. We demonstrate this by building a kernel rootkit detector.
Keywords: dynamic root of trust; rootkit detection; self-check-summing code; software-based code attestation; verifiable code execution

Real-time foreground-background segmentation using codebook model - Kim,K.; Chalidabhongse,T.H.; Harwood,D.; Davis, Larry S. (Real-time imaging, 2005)

Reducing complexity assumptions for statistically-hiding commitment - Haitner,I.; Horvitz,O.; Katz, Jonathan; Koo,C. Y; Morselli,R.; Shaltiel,R. (Advances in Cryptology–EUROCRYPT 2005, 2005)
Determining the minimal assumptions needed to construct various cryptographic building blocks has been a focal point of research in theoretical cryptography. Here, we revisit the following question: what are the minimal assumptions needed to construct statistically-hiding commitment schemes? Previously, it was known how to construct such schemes based on one-way permutations. We improve upon this by constructing statistically-hiding commitment schemes based on approximable-preimage-size one-way functions. These are one-way functions for which there is an efficient way to approximate the number of preimages of a given output. A special case (for which we show a somewhat simpler construction) is that of regular one-way functions where all outputs have the same number of preimages.We utilize two different approaches in constructing statistically-hiding commitment schemes. Our first approach proceeds by showing that the scheme of Naor et al. can be implemented using any one-way function having an output distribution which is “sufficiently similar” to uniform. We then construct one-way functions with this property from approximable-preimage-size one-way functions. Our second approach begins by constructing a commitment scheme which is statistically hiding against an honest-but-curious receiver. We then demonstrate a compiler which transforms any such commitment scheme into one which is statistically hiding even against a malicious receiver. This compiler and its analysis may be of independent interest.

Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints - Kumar, V.; Marathe,Madhav; Parthasarathy,Srinivasan; Srinivasan, Aravind (Approximation, Randomization and Combinatorial Optimization. Algorithms and TechniquesApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 2005)
We present polylogarithmic approximations for the R | prec | C max and R | prec |∑ j w j C j problems, when the precedence constraints are “treelike” – i.e., when the undirected graph underlying the precedences is a forest. We also obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment – this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion+dilation”, as in other job shop scheduling approaches. The first step in our algorithm for the R | prec | C max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random delays technique of Leighton, Maggs and Rao to the case of trees. For the weighted completion time, we show a certain type of reduction to the makespan problem, which dovetails well with the lower bound we employ for the makespan problem. For the special case of chains, we show a dependent rounding technique which leads to improved bounds on the weighted completion time and new bicriteria bounds for the flow time.

Secure remote authentication using biometric data - Boyen,X.; Dodis,Y.; Katz, Jonathan; Ostrovsky,R.; Smith,A. (Advances in Cryptology–EUROCRYPT 2005, 2005)
Biometric data offer a potential source of high-entropy, secret information that can be used in cryptographic protocols provided two issues are addressed: (1) biometric data are not uniformly distributed; and (2) they are not exactly reproducible. Recent work, most notably that of Dodis, Reyzin, and Smith, has shown how these obstacles may be overcome by allowing some auxiliary public information to be reliably sent from a server to the human user. Subsequent work of Boyen has shown how to extend these techniques, in the random oracle model, to enable unidirectional authentication from the user to the server without the assumption of a reliable communication channel.We show two efficient techniques enabling the use of biometric data to achieve mutual authentication or authenticated key exchange over a completely insecure (i.e., adversarially controlled) channel. In addition to achieving stronger security guarantees than the work of Boyen, we improve upon his solution in a number of other respects: we tolerate a broader class of errors and, in one case, improve upon the parameters of his solution and give a proof of security in the standard model.

A simulation and data analysis system for large-scale, data-driven oil reservoir simulation studies - Kurc, T.; Catalyurek,U.; Zhang,X.; Saltz, J.; Martino,R.; Wheeler,M.; Peszyńska,M.; Sussman, Alan; Hansen,C.; Sen,M.; others (Concurrency and Computation: Practice and Experience, 2005)

Simulation and Secure Computation-Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs - Katz, Jonathan; Lindell,Y. (Lecture Notes in Computer Science, 2005)

Software synthesis from the dataflow interchange format - Hsu,C. J; Ko,M. Y; Bhattacharyya, Shuvra S. (Proceedings of the 2005 workshop on Software and compilers for embedded systems, 2005)

Statistical geometry representation for efficient transmission and rendering - Kalaiah,Aravind; Varshney, Amitabh (ACM Transactions on Graphics, 2005)
Traditional geometry representations have focused on representing the details of the geometry in a deterministic fashion. In this article we propose a statistical representation of the geometry that leverages local coherence for very large datasets. We show how the statistical analysis of a densely sampled point model can be used to improve the geometry bandwidth bottleneck, both on the system bus and over the network as well as for randomized rendering, without sacrificing visual realism. Our statistical representation is built using a clustering-based hierarchical principal component analysis (PCA) of the point geometry. It gives us a hierarchical partitioning of the geometry into compact local nodes representing attributes such as spatial coordinates, normal, and color. We pack this information into a few bytes using classification and quantization. This allows our representation to directly render from compressed format for efficient remote as well as local rendering. Our representation supports both view-dependent and on-demand rendering. Our approach renders each node using quasi-random sampling utilizing the probability distribution derived from the PCA analysis. We show many benefits of our approach: (1) several-fold improvement in the storage and transmission complexity of point geometry; (2) direct rendering from compressed data; and (3) support for local and remote rendering on a variety of rendering platforms such as CPUs, GPUs, and PDAs.
Keywords: network graphics; Point-based rendering; Principal component analysis; programmable GPU; progressive transmission; quasi-random numbers; view-dependent rendering

Structural metadata and parsing speech - Harper,M.; Dorr, Bonnie J; Hale,J.; Roark,B.; Shafran,I.; Lease,M.; Liu,Y.; Snover,M.; Yung,L.; Krasnyanskaya,A.; others (JHU Language Engineering Workshop, 2005)

Stub Domain DDoS Detection - Kommareddy,C.; Levin,D.; Bhattacharjee, Bobby; La,R.J.; Shayman,M. (Technical Report of the Department of Computer Science, University of Maryland, College Park, 2005)

A system for performing content-based searches on a database of mechanical assemblies - Deshmukh,A. S.; Gupta,S.K.; Karnik,M. V.; Sriram,R.D. (2005)
The increased use of 3D CAD systems by productdevelopment organizations has resulted in large databases of assemblies; this explosion of assembly data will continue in the future. Currently, there are no effective content-based techniques to search these databases. Ability to perform content-based searches on these databases is expected to help the designers in the following two ways. First, it can facilitate reuse of existing assembly designs, and thereby reducing the design time. Second, a lot of useful Design for Manufacturing and Assembly (DFMA) knowledge is embedded in existing assemblies. Therefore a capability to locate existing assemblies and examine them can be used as a learning tool by the designers to learn from the existing assembly designs and hence transfer the best DFMA practices to new designers. 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 capabilities of our system through several examples.

Two-server password-only authenticated key exchange - Katz, Jonathan; MacKenzie,P.; Taban,G.; Gligor,V. (Applied Cryptography and Network Security, 2005)
Typical protocols for password-based authentication assume a single server which stores all the information (e.g.), the password necessary to authenticate a user. Unfortunately, an inherent limitation of this approach (assuming low-entropy passwords are used) is that the user’s password is exposed if this server is ever compromised. To address this issue, a number of schemes have been proposed in which a user’s password information is shared among multiple servers, and these servers cooperate in a threshold manner when the user wants to authenticate.We show here a two-server protocol for this task assuming public parameters available to everyone in the system (as well as the adversary). Ours is the first provably-secure two-server protocol for the important password-only setting (in which the user need remember only a password, and not the servers’ public keys), and is the first two-server protocol (in any setting) with a proof of security in the standard model.

Universally composable password-based key exchange - Canetti,R.; Halevi,S.; Katz, Jonathan; Lindell,Y.; MacKenzie,P. (Advances in Cryptology–Eurocrypt 2005, 2005)
We propose and realize a definition of security for password-based key exchange within the framework of universally composable (UC) security, thus providing security guarantees under arbitrary composition with other protocols. In addition, our definition captures some aspects of the problem that were not adequately addressed by most prior notions. For instance, it does not assume any underlying probability distribution on passwords, nor does it assume independence between passwords chosen by different parties. We also formulate a definition of password-based secure channels, and show that such a definition is achievable given password-based key exchange.Our protocol realizing the new definition of password-based key exchange is in the common reference string model and relies on standard number-theoretic assumptions. The components of our protocol can be instantiated to give a relatively efficient solution which is conceivably usable in practice. We also show that it is impossible to satisfy our definition in the “plain” model (e.g., without a common reference string).

Unsupervised learning applied to progressive compression of time-dependent geometry - Baby,Thomas; Kim,Youngmin; Varshney, Amitabh (Computers & Graphics, 2005)
We propose a new approach to progressively compress time-dependent geometry. Our approach exploits correlations in motion vectors to achieve better compression. We use unsupervised learning techniques to detect good clusters of motion vectors. For each detected cluster, we build a hierarchy of motion vectors using pairwise agglomerative clustering, and succinctly encode the hierarchy using entropy encoding. We demonstrate our approach on a client–server system that we have built for downloading time-dependent geometry.
Keywords: Clustering algorithms; Distributed/network graphics; pattern recognition

Using domain-configurable search control for probabilistic planning - Kuter,U.; Nau, Dana S. (2005)
We describe how to improve the performance of MDP planning algorithms by modifying them to use the search-control mechanisms of planners such as TLPlan, SHOP2, and TALplanner. In our experiments, modified versions of RTDP, LRTDP, and Value Iteration were ex- ponentially faster than the original algorithms. On the largest problems the original algorithms could solve, the modified ones were about 10,000 times faster. On another set of problems whose state spaces were more than 14,000 times larger than the original algorithms could solve, the modified algorithms took only about 1/3 second.

Visualization Methods for Personal Photo Collections: Browsing and Searching in the PhotoFinder (2000) - Kang,Hyunmo; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Software tools for personal photo collection management are proliferating, but they usually have limited searching and browsing functions. We implemented the PhotoFinder prototype to enable non-technical users of personal photo collections to search and browse easily. PhotoFinder provides a set of visual Boolean query interfaces, coupled with dynamic query and query preview features. It gives users powerful search capabilities. Using a scatter plot thumbnail display and drag-and-drop interface, PhotoFinder is designed to be easy to use for searching and browsing photos.
Keywords: Technical Report

Web Service Composition with Volatile Information - Au,Tsz-Chiu; Kuter,Ugur; Nau, Dana S. (The Semantic Web – ISWC 2005, 2005)
In many Web service composition problems, information may be needed from Web services during the composition process. Existing research on Web service composition (WSC) procedures has generally assumed that this information will not change. We describe two ways to take such WSC procedures and systematically modify them to deal with volatile information. The black-box approach requires no knowledge of the WSC procedure’s internals: it places a wrapper around the WSC procedure to deal with volatile information. The gray-box approach requires partial information of those internals, in order to insert coding to perform certain bookkeeping operations. We show theoretically that both approaches work correctly. We present experimental results showing that the WSC procedures produced by the gray-box approach can run much faster than the ones produced by the black-box approach.
Keywords: Computer science

What Are the Ants Doing? Vision-Based Tracking and Reconstruction of Control Programs - Egerstedt, M.; Balch, T.; Dellaert, F.; Delmotte, F.; Zia Khan (Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 2005. ICRA 2005, 2005)
In this paper, we study the problem of going from a real-world, multi-agent system to the generation of control programs in an automatic fashion. In particular, a computer vision system is presented, capable of simultaneously tracking multiple agents, such as social insects. Moreover, the data obtained from this system is fed into a mode-reconstruction module that generates low-complexity control programs, i.e. strings of symbolic descriptions of control-interrupt pairs, consistent with the empirical data. The result is a mechanism for going from the real system to an executable implementation that can be used for controlling multiple mobile robots.
Keywords: Animals; Automatic generation control; Biological information theory; Computer vision; Control systems; Mobile robots; Probability distribution; Robot control; target tracking; Trajectory

Adaptive limited-supply online auctions - Hajiaghayi, Mohammad T.; Kleinberg,R.; Parkes,D. C (Proceedings of the 5th ACM Conference on Electronic Commerce, 2004)

Adaptive replication in peer-to-peer systems - Gopalakrishnan,V.; Silaghi,B.; Bhattacharjee, Bobby; Keleher,P. (Distributed Computing Systems, 2004. Proceedings. 24th International Conference on, 2004)
Peer-to-peer systems can be used to form a low-latency decentralized data delivery system. Structured peer-to-peer systems provide both low latency and excellent load balance with uniform query and data distributions. Under the more common skewed access distributions, however, individual nodes are easily overloaded, resulting in poor global performance and lost messages. This paper describes a lightweight, adaptive, and system-neutral replication protocol, called LAR, that maintains low access latencies and good load balance even under highly skewed demand. We apply LAR to Chord and show that it has lower overhead and better performance than existing replication strategies.
Keywords: adaptive; allocation; data; databases; decentralized; delivery; distributed; LAR; low-latency; peer-to-peer; processing; protocol; replicated; replication; resource; strategies; structured; system-neutral; system; systems

Adaptively-Secure, Non-Interactive Public-Key Encryption - Canetti,R.; Halevi,S.; Katz, Jonathan (Model reduction methods for vector autoregressive processes, 2004)

Applying Model-based Distributed Continuous Quality Assurance Processes to Enhance Persistent Software Attributes - Krishna,A. S; Yilmaz,C.; Memon, Atif M.; Porter, Adam; Schmidt,D. C; Gokhale,A.; Natarajan,B. (IEEE Software, 2004)
Time and resource constraints often force developers of highlyconfigurable quality of service (QoS)-intensive software sys- tems to guarantee their system’s persistent software attributes (PSAs) (e.g., functional correctness, portability, efficiency, and QoS) on very few platform configurations and to extrapolate from these configurations to the entire configuration space, which allows many sources of degradation to escape detec- tion until systems are fielded. This article illustrates how distributed continuous quality assurance (DCQA) processes help improve the assessment of these PSAs across large QoS- intensive software system configuration spaces. We also il- lustrate how model-based DCQA processes enable developers to run formally-designed screening experiments that isolate the most significant configuration options, such as different workload parameters, operating system, compiler flags, fea- ture sets, and/or run-time optimization controls. Our empir- ical results show that DCQA processes can be used monitor, safeguard, and enforce PSAs at an acceptable level of cost and effort.

Approximation algorithms for partial covering problems - Gandhi,Rajiv; Khuller, Samir; Srinivasan, Aravind (Journal of Algorithms, 2004)
We study a generalization of covering problems called partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-partial set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-partial set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-partial vertex cover) in polynomial time. Without making any assumption about the number of sets an element is in, for instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-partial vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-partial vertex cover on planar graphs, and for covering k points in Rd by disks.
Keywords: Approximation algorithms; Partial covering; Primal-dual methods; Randomized rounding; Set cover; Vertex cover

Background modeling and subtraction by codebook construction - Kim,Kyungnam; Chalidabhongse,T.H.; Harwood,D.; Davis, Larry S. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
We present a new fast algorithm for background modeling and subtraction. Sample background values at each pixel are quantized into codebooks which represent a compressed form of background model for a long image sequence. This allows us to capture structural background variation due to periodic-like motion over a long period of time under limited memory. Our method can handle scenes containing moving backgrounds or illumination variations (shadows and highlights), and it achieves robust detection for compressed videos. We compared our method with other multimode modeling techniques.
Keywords: (signal); analysis; background; codebook; coding; colour; compression; construction; data; image; modeling; modeling; MOTION; multimode; quantisation; representation; sequence; sequences; subtraction; technique; video

Binary tree encryption: Constructions and applications - Katz, Jonathan (Information Security and Cryptology-ICISC 2003, 2004)

Building an information retrieval test collection for spontaneous conversational speech - Oard, Douglas; Soergel,Dagobert; David Doermann; Huang,Xiaoli; Murray,G. Craig; Wang,Jianqiang; Ramabhadran,Bhuvana; Franz,Martin; Gustman,Samuel; Mayfield,James; Kharevych,Liliya; Strassel,Stephanie (Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, 2004)
Test collections model use cases in ways that facilitate evaluation of information retrieval systems. This paper describes the use of search-guided relevance assessment to create a test collection for retrieval of spontaneous conversational speech. Approximately 10,000 thematically coherent segments were manually identified in 625 hours of oral history interviews with 246 individuals. Automatic speech recognition results, manually prepared summaries, controlled vocabulary indexing, and name authority control are available for every segment. Those features were leveraged by a team of four relevance assessors to identify topically relevant segments for 28 topics developed from actual user requests. Search-guided assessment yielded sufficient inter-annotator agreement to support formative evaluation during system development. Baseline results for ranked retrieval are presented to illustrate use of the collection.
Keywords: assessment; Automatic speech recognition; oral history; search-guided relevance

CHARMED: A multi-objective co-synthesis framework for multi-mode embedded systems - Kianzad,V.; Bhattacharyya, Shuvra S. (Application-Specific Systems, Architectures and Processors, 2004. Proceedings. 15th IEEE International Conference on, 2004)

Chosen-ciphertext security from identity-based encryption - Canetti,R.; Halevi,S.; Katz, Jonathan (Advances in Cryptology-Eurocrypt 2004, 2004)
We propose a simple and efficient construction of a CCA-secure public-key encryption scheme from any CPA-secure identity-based encryption (IBE) scheme. Our construction requires the underlying IBE scheme to satisfy only a relatively “weak” notion of security which is known to be achievable without random oracles; thus, our results provide a new approach for constructing CCA-secure encryption schemes in the standard model. Our approach is quite different from existing ones; in particular, it avoids non-interactive proofs of “well-formedness” which were shown to underlie most previous constructions. Furthermore, applying our conversion to some recently-proposed IBE schemes results in CCA-secure schemes whose efficiency makes them quite practical.Our technique extends to give a simple and reasonably efficient method for securing any binary tree encryption (BTE) scheme against adaptive chosen-ciphertext attacks. This, in turn, yields more efficient CCA-secure hierarchical identity-based and forward-secure encryption schemes in the standard model.

Compact procedural implementation in DSP software synthesis through recursive graph decomposition - Ko,M. Y; Murthy,P. K; Bhattacharyya, Shuvra S. (Software and compilers for embedded systems: 8th international workshop, SCOPES 2004, Amsterdam, The Netherlands, September 2-3, 2004: proceedings, 2004)

Compressing historical information in sensor networks - Deligiannakis,Antonios; Kotidis,Yannis; Roussopoulos, Nick (Proceedings of the 2004 ACM SIGMOD international conference on Management of data - SIGMOD '04, 2004)

Data migration on parallel disks - Golubchik,L.; Khuller, Samir; Kim,Y. A; Shargorodskaya,S.; Wan,Y. C (Algorithms–ESA 2004, 2004)
Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such storage servers are used as web servers or multimedia servers, for handling high demand for data. As the system is running, it needs to dynamically respond to changes in demand for different data items. There are known algorithms for mapping demand to a layout. When the demand changes, a new layout is computed. In this work we study the data migration problem, which arises when we need to quickly change one layout to another. This problem has been studied earlier when for each disk the new layout has been prescribed. However, to apply these algorithms effectively, we identify another problem that we refer to as the correspondence problem, whose solution has a significant impact on the solution for the data migration problem. We study algorithms for the data migration problem in more detail and identify variations of the basic algorithm that seem to improve performance in practice, even though some of the variations have poor worst case behavior.

Data sciences technology for homeland security information management and knowledge discovery - Kolda,T.; Brown,D; Corones,J.; Critchlow,T.; Eliassi-Rad,T.; Getoor, Lise; Hendrickson,B.; Kumar, V.; Lambert,D.; Matarazzo,C. (Report of the DHS Workshop Data Sciences, Jointly Released by Sandia National Laboratories and Lawrence Livermore National Laboratory, Alexandria, Va, 2004)

DIF: An interchange format for dataflow-based design tools - Hsu,C. J; Keceli,F.; Ko,M. Y; Shahparnia,S.; Bhattacharyya, Shuvra S. (Computer Systems: Architectures, Modeling, and Simulation, 2004)

Distortion management of real-time MPEG-4 video over downlink multicode CDMA networks - Su,Guan-Ming; Han,Zhu; Kwasinski,A.; M. Wu; Liu,K. J.R; Farvardin,N. (Communications, 2004 IEEE International Conference on, 2004)
In this paper, a protocol is designed to manage source rate/channel coding rate adaptation, code allocation, and power control to transmit real-time MPEG-4 FGS video over downlink multicode CDMA networks. We develop a fast adaptive scheme of distortion management to reduce the overall distortion received by all users subject, to the limited number of codes and maximal transmitted power. Compared with a modified greedy method in literature, our proposed algorithm can reduce the overall system's distortion by at least 45%.
Keywords: access; adaptation; allocation; CDMA; channel; code; coding; coding; combined; communication; compression; control; data; distortion; division; downlink; links; management; MPEG-4; multicode; multiple; networks; power; radio; rate; real-time; resource; source; source-channel; video; video; visual

A distributed continuous quality assurance process to manage variability in performance-intensive software - Krishna,A.; Yilmaz,C.; Memon, Atif M.; Porter, Adam; Schmidt,D. C; Gokhale,A.; Natarajan,B. (19th ACM OOPSLA Workshop on Component and Middleware Performance, 2004)

Efficient Execution of Multi-Query Data Analysis Batches Using Compiler Optimization Strategies - Andrade,H.; Aryangat,S.; Kurc, T.; Saltz, J.; Sussman, Alan (Languages and Compilers for Parallel Computing, 2004)
This work investigates the leverage that can be obtained from compiler optimization techniques for efficient execution of multi-query workloads in data analysis applications. Our approach is to address multi-query optimization at the algorithmic level, by transforming a declarative specification of scientific data analysis queries into a high-level imperative program that can be made more efficient by applying compiler optimization techniques. These techniques – including loop fusion, common subexpression elimination and dead code elimination – are employed to allow data and computation reuse across queries. We describe a preliminary experimental analysis on a real remote sensing application that analyzes very large quantities of satellite data. The results show our techniques achieve sizable reductions in the amount of computation and I/O necessary for executing query batches and in average execution times for the individual queries in a given batch.

Efficient peer location on the Internet - Banerjee,Suman; Kommareddy,Chris; Bhattacharjee, Bobby (Computer Networks, 2004)
We consider the problem of locating nearby application peers over the Internet. We define a new peer-location scheme (called Tiers), that scales to large application peer groups. Tiers creates a hierarchy of peers, and provides an efficient and scalable solution to the peer-location problem. Tiers can be implemented entirely in the application-layer and does not require the deployment of either any additional measurement services, or well-known reference points in the network.We have evaluated the performance of Tiers through detailed experiments. Our results show that Tiers is able to locate the nearest peers quickly (≪1 s) and accurately on wide-area Internet-like topologies. We have also compared the performance of Tiers with two other schemes, Beaconing and Distributed Binning, both of which are known to have good performance. Both these techniques are reference-points based schemes and are efficient for overlays with a small number of peers (e.g. ⩽32). Our results show that Tiers significantly outperforms both these schemes. Tiers is particularly efficient for large overlay networks, has an order of magnitude lower control overhead for overlays with 512 peers and still achieves greater accuracy in locating the nearest peers.
Keywords: Group communication; hierarchy; overlays; Peer location; triangle inequality

Efficient peer-to-peer namespace searches - Gopalakrishnan,V.; Bhattacharjee, Bobby; Chawathe,S.; Keleher,P. (University of Maryland, College Park, MD, Tech. Rep. CSTR-4568, 2004)
In this paper we describe new methods for efficient and exact search (keyword and full-text) in distributed namespaces. Our methods can be used in conjunction with existing distributed lookup schemes, such as Distributed Hash Tables, and distributed directories. We describe how indexes for implementing distributed searches can be efficiently created, located, and stored. We describe techniques for creating approximate indexes that can be used to bound the space requirement at individual hosts; such techniques are particularly useful for full-text searches that may require a very large number of individual indexes to be created and maintained. Our methods use a new distributed data structure called the view tree. View trees can be used to efficiently cache and locate results from prior queries. We describe how view trees are created, and maintained. We present experimental results, using large namespaces and realistic data, showing that the techniques introduced in this paper can reduce search overheads (both network and processing costs) by more than an order of magnitude.

Efficient Serial and Parallel Algorithms for Querying Large Scale Multidimensional Time Series Data - JaJa, Joseph F.; Kim,J.; Wang,Q. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2004)
We consider the problem of querying large scale multidimensional time series data to discover events of interest,test and validate hypotheses, or to associate temporal patterns with specific events. Multidimensional time series data is growing at an extremely fast rate due to a number of trends including a recent strong interest in collecting and analyzing time series of business, scientific, demographic, and simulation data. The ability to explore such collections interactively, even at a coarse level, will be critical to the process of extracting some of the information and knowledge embedded in such collections. We develop indexing techniques and search algorithms to efficiently handle temporal range value querying of multidimensional time series data. Our indexing uses linear space data structures that enable the handling of queries very efficiently, invoking in the worst case a logarithmic number of queries to single time steps. We also show that our algorithm is ideally suited for parallel implementation on clusters of processors achieving a linear speedup in the number of available processors. A particularly simple data structure with provably good bounds is also presented for the case when the number of multidimensional objects is relatively small. These techniques improve significantly over previous techniques for either the serial or the parallel case, and are evaluated by extensive experimental results that confirm their superior performance. In particular, we achieve query times in the order of hundreds of milliseconds on a (relatively outdated) cluster of 16 processors for 140GB of data consisting of 160, 000 distinct time series of 16-dimensional points, each time series being of length 10, 000.

Enabling On-chip Diversity Through Architectural Communication Design - Tudor Dumitras; Kerner, Sam; Marculescu, Radu (ASP-DAC '04 Proceedings of the 2004 Asia and South Pacific Design Automation Conference, 2004)
In this paper, we explore a new concept, called on-chip diversity, and introduce a design methodology for such emerging systems. Simply speaking, on-chip diversity means mixing different architectures and/or technologies in a multiple voltage/frequency island setup in order to achieve the highest levels of performance, fault-tolerance and the needed flexibility in SoC design. As the main contribution, we present the challenges in implementing an efficient communication architecture for on-chip diversity and outline a unified framework which addresses some of these issues. We then provide comparative experimental results and make a qualitative analysis of different architectural choices in the design of the on-chip communication. Having the acoustic beamforming as driver application, we show that an efficient communication infrastructure can be constructed by carefully analyzing the characteristics of the application and the required levels of power, performance and fault-tolerance.

End-to-end packet-scheduling in wireless ad-hoc networks - Kumar,V. S. Anil; Marathe,Madhav V.; Parthasarathy,Srinivasan; Srinivasan, Aravind (Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, 2004)
Packet-scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we study packet routing and scheduling under this model. The main focus of our work is the development of fully-distributed (decentralized) protocols. We present polylogarithmic/constant factor approximation algorithms for various families of disk graphs (which capture the geometric nature of wireless-signal propagation), as well as near-optimal approximation algorithms for general graphs. The packet-scheduling work by L eighton, Maggs and Rao (Combinatorica, 1994) and a basic distributed coloring procedure, originally due to Luby (J. Computer and System Sciences, 1993), underlie many of our algorithms. Experimental work of Finocchi, Panconesi, and Silvestri (SODA 2002) showed that a natural modification of Luby's algorithm leads to improved performance, and a rigorous explanation of this was left as an open question; we prove that the modified algorithm is provably better in the worst-case. Finally, using simulations, we study the impact of the routing strategy and the choice of parameters on the performance of our distributed algorithm for unit disk graphs.

Equivalence of two linear programming relaxations for broadcast scheduling - Khuller, Samir; Kim,Yoo-Ah (Operations Research Letters, 2004)
A server needs to compute a broadcast schedule for n pages whose request times are known in advance. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. In this paper, we show the equivalence of two apparently different relaxations that have been considered for this problem.
Keywords: Approximation algorithms; Broadcasting; Linear programming; scheduling

A fine-structure image/video quality measure using local statistics - Kim,Kyungnam; Davis, Larry S. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
An objective no-reference measure is presented to assess line-structure image/video quality. It was designed to measure image/video quality for video surveillance applications, especially for background modeling and foreground object detection. The proposed measure using local statistics reflects image degradation well in terms of noise and blur. The experimental results on a background subtraction algorithm validate the usefulness of the proposed measure, by showing its correlation with the algorithm's performance.
Keywords: algorithm; background; degradation; detection; foreground; image; line-structure; local; measure; modeling; no-reference; object; objective; processing; QUALITY; signal; statistics; subtraction; surveillance; video

Forward-chaining planning in nondeterministic domains - Kuter,U.; Nau, Dana S. (2004)
In this paper, we present a general technique for tak- ing forward-chaining planners for deterministic do- mains (e.g., HSP, TLPlan, TALplanner, and SHOP2) and adapting them to work in nondeterministic do- mains. Our results suggest that our technique pre- serves many of the desirable properties of these plan- ners, such as the ability to use heuristic techniques to achieve highly efficient planning.In our experimental studies on two problem domains, the well-known MBP algorithm took exponential time, confirming prior results by others. A nondeterminized version of SHOP2 took only polynomial time. The polynomial-time figures are confirmed by a complex- ity analysis, and a similar complexity analysis shows that a nondeterminized version of TLPlan would per- form similarly.

Fusion of gait and face for human identification - Kale, A.; Roy Chowdhury, A.K.; Chellapa, Rama (Acoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP '04). IEEE International Conference on, 2004)
Identification of humans from arbitrary view points is an important requirement for different tasks including perceptual interfaces for intelligent environments, covert security and access control etc. For optimal performance, the system must use as many cues as possible and combine them in meaningful ways. In this paper, we discuss fusion of face and gait cues for the single camera case. We present a view invariant gait recognition algorithm for gait recognition. We employ decision fusion to combine the results of our gait recognition algorithm and a face recognition algorithm based on sequential importance sampling. We consider two fusion scenarios: hierarchical and holistic. The first involves using the gait recognition algorithm as a filter to pass on a smaller set of candidates to the face recognition algorithm. The second involves combining the similarity scores obtained individually from the face and gait recognition algorithms. Simple rules like the SUM, MIN and PRODUCT are used for combining the scores. The results of fusion experiments are demonstrated on the NIST database which has outdoor gait and face data of 30 subjects.
Keywords: access; algorithm; analysis; combining; control; covert; cues; data; decision; Environment; Face; fusion; Gait; hierarchical; holistic; human; identification; importance; intelligent; interfaces; invariant; perceptual; recognition; recognition; rules; sampling; score; scores; security; sensor; sequential; similarity; view

Gait-based human identification from a monocular video sequence - Kale, A.; Sundaresan, A.; Roy Chowdhury, A.K.; Chellapa, Rama (Handbook on Pattern Recognition and Computer Vision, 2004)
Human gait is a spatio-temporal phenomenon that characterizes the motion char-acteristics of an individual. It is possible to detect and measure gait even in low- resolution video. In this chapter, we discuss algorithms for identifying people by their gait from a monocular video sequence. Human identification using gait, sim- ilar to text-based speaker identification, involves different individuals performing the same task and a template-matching approach is suitable for such problems. In situations where the amount of training data is limited, we demonstrate the utility of a simple width feature for gait recognition. By virtue of their determin- istic nature, template matching methods have limited noise resilience. In order to deal with noise we introduce a systematic approach to gait recognition by building representations for the structural and dynamic components of gait using exemplars and hidden Markov models (HMMs). The above methods assume that an exact side-view of the subject is available in the probe sequence. For the case when the person walks at an arbitrary angle far away from the camera we present a view invariant gait recognition algorithm which is based on synthesizing a side view of a person from an arbitrary monocular view.

A game-theoretic framework for analyzing trust-inference protocols - Morselli,R.; Katz, Jonathan; Bhattacharjee, Bobby (Workshop on Economics of Peer-to-Peer Systems, 2004)
We propose a novel game-theoretic framework foranalyzing the robustness of trust-inference protocols in the presence of adversarial (but rational) users. To the best of our knowledge, this is the first such framework which simultaneously (1) admits a rigor- ous and precise definition, thereby enabling formal proofs of security (in various adversarial settings) for specific trust-inference protocols; (2) is flexible enough to accommodate a full range of (realistic) ad- versarial behavior and network models; and (3) is ap- propriate for decentralized networks, and in particu- lar does not posit a trusted, centralized party with complete knowledge of the system history. We also show some preliminary results regarding the design of trust-inference protocols which can be rigorously proven secure within our model. In addition to establishing a solid foundation for future work, our framework also enables a rigorous and objective comparison among existing trust inference protocols.

A generic construction for intrusion-resilient public-key encryption - Dodis,Y.; Franklin,M.; Katz, Jonathan; Miyaji,A.; Yung,M. (Topics in Cryptology–CT-RSA 2004, 2004)
In an intrusion-resilient cryptosystem [10], two entities (a user and a base) jointly evolve a secret decryption key; this provides very strong protection against an active attacker who can break into the user and base repeatedly and even simultaneously. Recently, a construction of an intrusion-resilient public-key encryption scheme based on specific algebraic assumptions has been shown [6]. We generalize this previous work and present a more generic construction for intrusion-resilient public-key encryption from any forward-secure public-key encryption scheme satisfying a certain homomorphic property.

Geometric Containment Analysis for Rotational Parts - Karnik,M.; Gupta,S.K.; Magrab,E. B. (2004)
This paper describes a system and underlying algorithms toperform geometric containment analysis to determine if a newly designed rotational part can be manufactured from a part in an existing database of rotational parts. Only material removal of the database part is considered in order to obtain the newly designed part from the database part. The system uses a three-step algorithm to test for containment. The first step analyzes feasibility of containment using bounding cylinders. If the bounding cylinder of the query part is bigger than the part in the database, then the database part cannot contain the query part and it is eliminated from consideration. The second step analyzes feasibility of containment by ignoring off-axis features. Any part that fails to satisfy containment at this stage is eliminated from consideration. The third step analyzes the remaining parts from the database for feasibility of containment by including the off-axis features. Finally, the system rank- orders all the database parts that can contain the query part based on their volume differences with the query part. The system described in this paper can be used to find an existing part from which to manufacture a newly designed part. This capability is expected to significantly reduce proliferation of parts, to improve manufacturing responsiveness, and to reduce the cost of new products.

Guest editors' foreword: special issue: 35th annual ACM symposium on theory of computing - Khanna,S.; Srinivasan, Aravind (Journal of Computer and System Sciences, 2004)

Hierarchical in-network data aggregation with quality guarantees - Deligiannakis,A.; Kotidis,Y.; Roussopoulos, Nick (Advances in Database Technology-EDBT 2004, 2004)

Hierarchical routing with soft-state replicas in TerraDir - Silaghi,B.; Gopalakrishnan,Vijay; Bhattacharjee, Bobby; Kelcher,P. (Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International, 2004)
Summary form only given. Recent work on peer-to-peer systems has demonstrated the ability to deliver low latencies and good load balance when demand for data is relatively uniform. We describe an adaptive replication protocol that delivers low latencies, good load balance even when demand is heavily skewed. The protocol can withstand arbitrary and instantaneous changes in demand distribution. Our approach also addresses classical concerns related to topological constraints of asymmetrical namespaces, such as hierarchical bottlenecks in the context of hierarchical namespaces. The protocol replicates routing state in an ad-hoc manner based on profiled information, is lightweight, scalable, and requires no replica consistency guarantees.
Keywords: ad-hoc; adaptive; allocation; asymmetrical; balancing; bottlenecks; consistency; constraints; delivering; demand; distribution; guarantees; hierarchical; latency; load; low; namespaces; peer-to-peer; protocol; protocols; replica; replicas; replication; resource; routing; soft-state; systems; TerraDir; topological

Hierarchical Scaffolding With Bambus - Pop, Mihai; Kosack,Daniel S.; Salzberg,Steven L. (Genome Research, 2004)
The output of a genome assembler generally comprises a collection of contiguous DNA sequences (contigs) whose relative placement along the genome is not defined. A procedure called scaffolding is commonly used to order and orient these contigs using paired read information. This ordering of contigs is an essential step when finishing and analyzing the data from a whole-genome shotgun project. Most recent assemblers include a scaffolding module; however, users have little control over the scaffolding algorithm or the information produced. We thus developed a general-purpose scaffolder, called Bambus, which affords users significant flexibility in controlling the scaffolding parameters. Bambus was used recently to scaffold the low-coverage draft dog genome data. Most significantly, Bambus enables the use of linking data other than that inferred from mate-pair information. For example, the sequence of a completed genome can be used to guide the scaffolding of a related organism. We present several applications of Bambus: support for finishing, comparative genomics, analysis of the haplotype structure of genomes, and scaffolding of a mammalian genome at low coverage. Bambus is available as an open-source package from our Web site.

iCLEF 2003 at Maryland: Translation Selection and Document Selection - Dorr, Bonnie J; He,Daqing; Luo,Jun; Oard, Douglas; Schwartz,Richard; Wang,Jianqiang; Zajic, David (Comparative Evaluation of Multilingual Information Access SystemsComparative Evaluation of Multilingual Information Access Systems, 2004)
Maryland performed two sets of experiments for the 2003 Cross-Language Evaluation Forum’s interactive track, one focused on interactive selection of appropriate translations for query terms, the second focused on interactive selection of relevant documents. Translation selection was supported using possible synonyms discovered through back translation and two techniques for generating KeyWord In Context (KWIC) examples of usage. The results indicate that searchers typically achieved a similar search effectiveness using fewer query iterations when interactive translation selection was available. For document selection, a complete extract of the first 40 words of each news story was compared to a compressed extract generated using an automated parse-and-trim approach that approximates one way in which people can produce headlines. The results indicate that compressed “headlines” result in faster assessment, but with a 20% relative reduction in the F α = 0.8 search effectiveness measure.

Identification of confusable drug names: a new approach and evaluation methodology - Kondrak,Grzegorz; Dorr, Bonnie J (Proceedings of the 20th international conference on Computational Linguistics, 2004)
This paper addresses the mitigation of medical errors due to the confusion of sound-alike and look-alike drug names. Our approach involves application of two new methods---one based on orthographic similarity ("look-alike") and the other based on phonetic similarity ("sound-alike"). We present a new recall-based evaluation methodology for determining the effectiveness of different similarity measures on drug names. We show that the new orthographic measure (BI-SIM) outperforms other commonly used measures of similarity on a set containing both look-alike and sound-alike pairs, and that the feature-based phonetic approach (ALINE) outperforms orthographic approaches on a test set containing solely sound-alike confusion pairs. However, an approach that combines several different measures achieves the best results on both test sets.

Identification of humans using gait - Kale, A.; Sundaresan, A.; Rajagopalan, AN; Cuntoor, N.P.; Roy-Chowdhury, A.K.; Kruger, V.; Chellapa, Rama (Image Processing, IEEE Transactions on, 2004)
We propose a view-based approach to recognize humans from their gait. Two different image features have been considered: the width of the outer contour of the binarized silhouette of the walking person and the entire binary silhouette itself. To obtain the observation vector from the image features, we employ two different methods. In the first method, referred to as the indirect approach, the high-dimensional image feature is transformed to a lower dimensional space by generating what we call the frame to exemplar (FED) distance. The FED vector captures both structural and dynamic traits of each individual. For compact and effective gait representation and recognition, the gait information in the FED vector sequences is captured in a hidden Markov model (HMM). In the second method, referred to as the direct approach, we work with the feature vector directly (as opposed to computing the FED) and train an HMM. We estimate the HMM parameters (specifically the observation probability B) based on the distance between the exemplars and the image features. In this way, we avoid learning high-dimensional probability density functions. The statistical nature of the HMM lends overall robustness to representation and recognition. The performance of the methods is illustrated using several databases.
Keywords: Automated; Reproducibility of Results; Sensitivity and Specificity; Signal Processing; binary silhouette; frame to exemplar distance; gait databases; gait recognition; hidden Markov model; human identification; image features; observation probability; observation vector; hidden Markov models; image recognition; image representation; image sequences; pro; Biological; Models; Computer-Assisted; Models; Computer-Assisted; Subtraction Technique; Task Performance and Analysis; Video Recording; Statistical; Pattern Recognition

Identifying similar parts for assisting cost estimation of prismatic machined parts - Cardone, Antonio; Gupta,S.K.; Karnik,M. (ASME Design for Manufacturing Conference, Salt Lake City, Utah, 2004)

Immediate usability: a case study of public access design for a community photo library - Kules,Bill; Kang,Hyunmo; Plaisant, Catherine; Rose,Anne; Shneiderman, Ben (Interacting with Computers, 2004)
This paper describes a novel instantiation of a digital photo library in a public access system. It demonstrates how designers can utilize characteristics of a target user community (social constraints, trust, and a lack of anonymity) to provide capabilities, such as unrestricted annotation and uploading of photos, which would be impractical in other types of public access systems. It also presents a compact set of design principles and guidelines for ensuring the immediate usability of public access information systems. These principles and guidelines were derived from our experience developing PhotoFinder Kiosk, a community photo library. Attendees of a major HCI conference (CHI 2001 Conference on Human Factors in Computing Systems) successfully used the tool to browse and annotate collections of photographs spanning 20 years of HCI-related conferences, producing a richly annotated photo history of the field of human–computer interaction. Observations and usage log data were used to evaluate the tool and develop the guidelines. They provide specific guidance for practitioners, as well as a useful framework for additional research in public access interfaces.
Keywords: Casual use; Community photo library; direct annotation; direct manipulation; Drag-and-drop; Group annotation; Immediate usability; Photo collection; Public access system; Walk-up-and-use; Zero-trial learning

Implementation of the regularized structured total least squares algorithms for blind image deblurring - Mastronardi,N.; Lemmerling,P.; Kalsi,A.; O’Leary,D. P; Huffel,S. Van (Linear Algebra and its Applications, 2004)
The structured total least squares (STLS) problem has been introduced to handle problems involving structured matrices corrupted by noise. Often the problem is ill-posed. Recently, regularization has been proposed in the STLS framework to solve ill-posed blind deconvolution problems encountered in image deblurring when both the image and the blurring function have uncertainty. The kernel of the regularized STLS (RSTLS) problem is a least squares problem involving Block–Toeplitz–Toeplitz–Block matrices.In this paper an algorithm is described to solve this problem, based on a particular implementation of the generalized Schur Algorithm (GSA). It is shown that this new implementation improves the computational efficiency of the straightforward implementation of GSA from O(N2.5) to O(N2), where N is the number of pixels in the image.
Keywords: Block Toeplitz matrix; Displacement rank; Generalized Schur algorithm; Image deblurring; Structured total least squares; Tikhonov regularization

Improving the Quality of Performance-intensive Software via Model-integrated Distributed Continuous Quality Assurance - Krishna,A. S; Schmidt,D. C; Porter, Adam; Memon, Atif M.; Sevilla-Ruiz,D. (Proceedings of the 8th International Conference on Software Reuse, 2004)

Information Gathering During Planning for Web Service Composition - Kuter,Ugur; Sirin,Evren; Nau, Dana S.; Parsia,Bijan; Hendler,James (The Semantic Web – ISWC 2004, 2004)
Hierarchical Task-Network (HTN) based planning techniques have been applied to the problem of composing Web Services, especially when described using the OWL − S service ontologies. Many of the existing Web Services are either exclusively information providing or crucially depend on information-providing services. Thus, many interesting service compositions involve collecting information either during execution or during the composition process itself. In this paper, we focus on the latter issue. In particular, we present ENQUIRER , an HTN-planning algorithm designed for planning domains in which the information about the initial state of the world may not be complete, but it is discoverable through plan-time information-gathering queries. We have shown that ENQUIRER is sound and complete, and derived several mathematical relationships among the amount of available information, the likelihood of the planner finding a plan, and the quality of the plan found. We have performed experimental tests that confirmed our theoretical results and that demonstrated how ENQUIRER can be used in Web Service composition.
Keywords: Computer science

Mandarin-English Information (MEI): investigating translingual speech retrieval - Meng,Helen M.; Chen,Berlin; Khudanpur,Sanjeev; Levow,Gina-Anne; Lo,Wai-Kit; Oard, Douglas; Schone,Patrick; Tang,Karen; Wang,Hsin-Min; Wang,Jianqiang (Computer Speech & Language, 2004)
This paper describes the Mandarin–English Information (MEI) project, where we investigated the problem of cross-language spoken document retrieval (CL-SDR), and developed one of the first English–Chinese CL-SDR systems. Our system accepts an entire English news story (text) as query, and retrieves relevant Chinese broadcast news stories (audio) from the document collection. Hence, this is a cross-language and cross-media retrieval task. We applied a multi-scale approach to our problem, which unifies the use of phrases, words and subwords in retrieval. The English queries are translated into Chinese by means of a dictionary-based approach, where we have integrated phrase-based translation with word-by-word translation. Untranslatable named entities are transliterated by a novel subword translation technique. The multi-scale approach can be divided into three subtasks – multi-scale query formulation, multi-scale audio indexing (by speech recognition) and multi-scale retrieval. Experimental results demonstrate that the use of phrase-based translation and subword translation gave performance gains, and multi-scale retrieval outperforms word-based retrieval.
Keywords: English–Chinese cross-language spoken document retrieval; Multi-scale spoken document retrieval

An MCMC-Based Particle Filter for Tracking Multiple Interacting Targets - Zia Khan; Balch, Tucker; Dellaert, Frank (Computer Vision - ECCV 2004, 2004)
We describe a Markov chain Monte Carlo based particle filter that effectively deals with interacting targets, i.e., targets that are influenced by the proximity and/or behavior of other targets. Such interactions cause problems for traditional approaches to the data association problem. In response, we developed a joint tracker that includes a more sophisticated motion model to maintain the identity of targets throughout an interaction, drastically reducing tracker failures. The paper presents two main contributions: (1) we show how a Markov random field (MRF) motion prior, built on the fly at each time step, can substantially improve tracking when targets interact, and (2) we show how this can be done efficiently using Markov chain Monte Carlo (MCMC) sampling. We prove that incorporating an MRF to model interactions is equivalent to adding an additional interaction factor to the importance weights in a joint particle filter. Since a joint particle filter suffers from exponential complexity in the number of tracked targets, we replace the traditional importance sampling step in the particle filter with an MCMC sampling step. The resulting filter deals efficiently and effectively with complicated interactions when targets approach each other. We present both qualitative and quantitative results to substantiate the claims made in the paper, including a large scale experiment on a video-sequence of over 10,000 frames in length.
Keywords: Artificial Intelligence (incl. Robotics); Computer Graphics; Image Processing and Computer Vision; pattern recognition

Measurement based optimal multi-path routing - Guven,T.; Kommareddy,C.; La,R.J.; Shayman,M.A.; Bhattacharjee, Bobby (INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 2004)
We propose a new architecture for efficient network monitoring and measurements in a traditional IP network. This new architecture enables establishment of multiple paths (tunnels) between source-destination pairs without having to modify the underlying routing protocol(s). Based on the proposed architecture we propose a measurement-based multipath routing algorithm derived from simultaneous perturbation stochastic approximation. The proposed algorithm does not assume that the gradient of analytical cost function is known to the algorithm, but rather relies on noisy estimates from measurements. Using the analytical model presented in the paper we prove the convergence of the algorithm to the optimal solution. Simulation results are presented to demonstrate the advantages of the proposed algorithm under a variety of network scenarios. A comparative study with an existing optimal routing algorithm, MATE, is also provided
Keywords: algorithm; network; approximation; routing; IP; measurement; network; monitoring; optimization; perturbation; multipath; network; measurement-based; networks; Internet; optimisation; routing; processes; protocol; IP; protocols; stochastic; Routing; Stochastic

Method of designing signaling networks for internet telephony - Aravamudan,Murali; Kumaran,Krishnan; Ramakrishnan,Kajamalai Gopalaswamy; Srinivasan, Aravind (2004)
A method is disclosed for designing a signaling network of call coordinators (CCs) for internet telephony. The new method can be used to design a CC network of arbitrary size that satisfies, with high probability, limitations on the maximum number of sockets per CC and on the maximum number of hops between an arbitrary pair of switches in the network. According to the disclosed method, the network of CCs is treated initially as a collection of isolated points, one point for each CC. Then, links are added between pairs of CCs, excluding pairs lying within the same switch. The links are added randomly, but with a particular probability p, which may be different for different pairs. Thus, whether a given link is added depends, in effect, upon the outcome of a loaded coin toss in which the probability of a positive outcome is p.

Model-Based Approaches-Validating Quality of Service for Reusable Software Via Model-Integrated Distributed Continuous Quality Assurance - Krishna,A. S; Schmidt,D. C; Memon, Atif M.; Porter, Adam; Sevilla,D. (Lecture Notes in Computer Science, 2004)

A Model-based Distributed Continuous Quality Assurance Process to Enhance the Quality of Service of Evolving Performance-intensive Software Systems - Yilmaz,C.; Krishna,A. S; Memon, Atif M.; Porter, Adam; Schmidt,D. C; Gokhale,A.; Natarajan,B. (Proceedings of the 2nd ICSE Workshop on Remote Analysis and Measurement of Software Systems (RAMSS), Edinburgh, Scotland, UK, 2004)
Performance-intensive software, such as that found in high-perfo-rmance computing systems and distributed real-time and embedded systems, increasingly executes on a multitude of platforms and user contexts. To ensure that performance-intensive software meets its quality of service (QoS) requirements, it must often be fine-tuned to specific platforms/contexts by adjusting many (in some cases hun- dreds of) configuration options. Developers who write these types of systems must therefore try to ensure that their additions and mod- ifications work across this large configuration space. In practice, however, time and resource constraints often force developers to assess performance on very few configurations and to extrapolate from these to the entire configuration space, which allows many performance bottlenecks and sources of QoS degradation to escape detection until systems are fielded. To improve the assessment of performance across large config- uration spaces, we present a model-based approach to develop- ing and deploying a new distributed continuous quality assurance (DCQA) process. Our approach builds upon and extends the Skoll environment, which is developing and validating novel software QA processes and tools that leverage the extensive computing resources of worldwide user communities in a distributed, continuous man- ner to significantly and rapidly improve software quality. This pa- per describes how our new DCQA performance assessment process enables developers to run formally-designed screening experiments that isolate the most significant options. After that, exhaustive ex- periments (on the now much smaller configuration space) are con- ducted. We implemented this process using model-based software tools and executed it in the Skoll environment to demonstrate its ef- fectiveness via two experiments on widely used QoS-enabled mid- dleware. Our results show that model-based DCQA processes im- proves developer insight into the effect of system changes on per- formance at an acceptable cost.

Modelling disease outbreaks in realistic urban social networks - Eubank,Stephen; Guclu,Hasan; Kumar,V. S. Anil; Marathe,Madhav V.; Srinivasan, Aravind; Toroczkai,Zolt|[aacute]|n; Wang,Nan (Nature, 2004)
Most mathematical models for the spread of disease use differential equations based on uniform mixing assumptions1 or ad hoc models for the contact process2, 3, 4. Here we explore the use of dynamic bipartite graphs to model the physical contact patterns that result from movements of individuals between specific locations. The graphs are generated by large-scale individual-based urban traffic simulations built on actual census, land-use and population-mobility data. We find that the contact network among people is a strongly connected small-world-like5 graph with a well-defined scale for the degree distribution. However, the locations graph is scale-free6, which allows highly efficient outbreak detection by placing sensors in the hubs of the locations network. Within this large-scale simulation framework, we then analyse the relative merits of several proposed mitigation strategies for smallpox spread. Our results suggest that outbreaks can be contained by a strategy of targeted vaccination combined with early detection without resorting to mass vaccination of a population.

Motivating annotation for digital photographs: Lowering barriers while raising incentives - Kustanowitz,J.; Shneiderman, Ben (HCIL-2004-18, 2004)
Frameworks for understanding annotation requirements could guide improved strategies that would motivate more users to invest the necessary effort. We propose one framework for annotation techniques along with the st rengths and weaknesses of each one, and a second framework for target user groups and their motivations. Several applications are described that provide useful and information-rich representations, but which require good annotations, in the hope of providing incentives for high quality annotation. We describe how annotations make possible four novel presentations of photo collections: (1) Birthday Collage to show growth of a child over several years, (2) FamiliarFace to show family trees of photos, (3) Kaleidoscope to show photos of related people in an appeal tableau, and (4) TripPics to show photos from a sequential story such as a vacation trip.

Multi-dimensional quorum sets for read-few write-many replica control protocols - Silaghi,B.; Keleher,P.; Bhattacharjee, Bobby (Cluster Computing and the Grid, 2004. CCGrid 2004. IEEE International Symposium on, 2004)
We describe d-spaces, a replica control protocol defined in terms of quorum sets on multi-dimensional logical structures. Our work is motivated by asymmetrical access patterns, where the number of read accesses to data are dominant relative to update accesses, i.e. where the protocols should be read-few write-many. D-spaces are optimal with respect to quorum group sizes. The quality of the tradeoff between read efficiency and update availability is not matched by existing quorum protocols. We also propose a novel scheme for implementing d-spaces that combines caching and local information to provide a best-effort form of global views. This allows quorum reconfiguration to be lightweight without impacting access latencies, even when the rate of membership changes is very high.
Keywords: accesses; availability; cache; caching; Communication; complexity; CONTROL; d-spaces; distributed; efficiency; lightweight; logical; multi-dimensional; processing; protocols; quorum; read; read-few; reconfiguration; replica; sets; storage; structures; update; write-many

New directions in design for manufacturing - Herrmann,J.W.; Cooper,J.; Gupta,S.K.; Hayes,C. C.; Ishii,K.; Kazmer,D.; Sandborn,P. A.; Wood,W. H. (2004)
This paper gives an overview of research that is expandingthe domain of design for manufacturing (DFM) into new and important areas. This paper covers DFM and concurrent engineering, DFM for conceptual design, DFM for embodiment design, DFM for detailed design, design for production, platform design for reducing time-to-market, design for system quality, design for life cycle costs, and design for environment. The paper concludes with some general guidelines that suggest how manufacturing firms can develop useful, effective DFM tools.

A novel approach to removing intersymbol interference from spin-stand images - Mayergoyz, Issak D; Tse,C.; Krafft,C.; McAvoy,P. (Magnetics, IEEE Transactions on, 2004)
A novel intersymbol interference (ISI) removal technique based on the "response function" characterization of giant-magnetoresistive heads is presented. It is demonstrated that the ISI-free readback image that corresponds to the actual underlying magnetization patterns can be extracted from the ISI-distorted readback signal through deconvolution. A new image deconvolution algorithm has been implemented, and it has been shown that it effectively removes the ISI distortions.
Keywords: algorithm; characterization; Deconvolution; function; function; giant; giant-magnetoresistive; Head; heads; image; image; imaging; Interference; interference; intersymbol; ISI-distorted; ISI-free; magnetic; magnetization; magnetoresistance; patterns; readback; removal; response; signal; spin-stand; suppression

One-round protocols for two-party authenticated key exchange - Jeong,I. R; Katz, Jonathan; Lee,D. H (Applied Cryptography and Network Security, 2004)

Pandemic strains of O3:K6 Vibrio parahaemolyticus in the aquatic environment of Bangladesh - Islam,M. S.; Tasmin,Rizwana; Khan,Sirajul I. s l a m; Bakht,Habibul B. M.; Mahmood,Zahid H. a y a t; Rahman,M. Z. i a u r; Bhuiyan,Nurul A. m i n; Nishibuchi,Mitsuaki; Nair,G. B. a l a k r i s h; Sack,R. B. r a d l e y; Huq,Anwar; Rita R Colwell; et al. (Canadian Journal of Microbiology, 2004)
A total of 1500 environmental strains of Vibrio parahaemolyticus, isolated from the aquatic environment of Bangladesh, were screened for the presence of a major V. parahaemolyticus virulence factor, the thermostable direct haemolysin (tdh) gene, by the colony blot hybridization method using a digoxigenin-labeled tdh gene probe. Of 1500 strains, 5 carried the tdh sequence, which was further confirmed by PCR using primers specific for the tdh gene. Examination by PCR confirmed that the 5 strains were V. parahamolyticus and lacked the thermostable direct haemolysin-related haemolysin (trh) gene, the alternative major virulence gene known to be absent in pandemic strains. All 5 strains gave positive Kanagawa phenomenon reaction with characteristic beta-haemolysis on Wagatsuma agar medium. Southern blot analysis of the HindIII-digested chromosomal DNA demonstrated, in all 5 strains, the presence of 2 tdh genes common to strains positive for Kanagawa phenomenon. However, the 5 strains were found to belong to 3 different serotypes (O3:K29, O4:K37, and O3:K6). The 2 with pandemic serotype O3:K6 gave positive results in group-specific PCR and ORF8 PCR assays, characteristics unique to the pandemic clone. Clonal variations among the 5 isolates were analyzed by comparing RAPD and ribotyping patterns. Results showed different patterns for the 3 serotypes, but the pattern was identical among the O3:K6 strains. This is the first report on the isolation of pandemic O3:K6 strains of V. parahaemolyticus from the aquatic environment of Bangladesh.

Pocket PhotoMesa: a Zoomable image browser for PDAs - Khella,A.; Bederson, Benjamin B. (Proceedings of the 3rd international conference on Mobile and ubiquitous multimedia, 2004)

PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness - Vishkin, Uzi (Mathematical Foundations of Computer Science 2004Mathematical Foundations of Computer Science 2004, 2004)
Consider situations where once you were told about a new technical idea you reacted by saying: “but this is so obvious, I wonder how I missed it”. I found out recently that the US patent law has a nice formal way of characterizing such a situation. The US patent law protects inventions that meet three requirements: utility, novelty and non-obviousness. Non-obviousness is considered the most challenging of the three to establish. The talk will try to argue that a possible virtue for a technical contribution is when, in restrospect, its non-obviousness is not too obvious; and since hindsight is always 20/20, one may often need to resort to various types of circumstantial evidence in order to establish non-obviousness. There are two reasons for bringing this issue up in my talk: (i) seeking such a virtue has been an objective of my work over the years, and (ii) issues of taste in research are more legitimate for invited talks; there might be merit in reminding younger researchers that not every “result” is necessarily also a “contribution”; perhaps the criterion of not-so-obvious non-obviousness could be helpful in some cases to help recognize a contribution. The focus of the second focal point for my talk, the PRAM-On-Chip approach, meets at least one of the standard legal ways to support non-obviousness: “Expressions of disbelief by experts constitute strong evidence of non-obviousness”. It is well documented that the whole PRAM algorithmic theory was considered “unrealistic” by numerous experts in the field, prior to the PRAM-On-Chip project. In fact, I needed recently to use this documentation in a reply to the U.S. patent office. An introduction of the PRAM-On-Chip approach follows. Many parallel computer systems architectures have been proposed and built over the last several decades. The outreach of the few that survived has been severely limited due to their programmability problems. The question of how to think algorithmically in parallel has been the fundamental problem for which these architectures did not have an adequate answer. A computational model, the Parallel Random Access Model (PRAM), has been developed by numerous (theoretical computer science) algorithm researchers to address this question during the 1980s and 1990s and is considered by many as the easiest known approach to parallel programming. Despite the broad interest the PRAM generated, it had not been possible to build parallel machines that adequately support it using multi-chip multiprocessors, the only multiprocessors that were buildable in the 1990s since low-overhead coordination was not possible. Our main insight is that this is becoming possible with the increasing amounts of hardware that can be placed on a single chip. From the PRAM, as a starting point, a highly parallel explicit multi-threaded (XMT) on-chip processor architecture that relies on new low-overhead coordination mechanisms and whose performance objective is reducing single task completion time has been conceived and developed. Simulated program executions have shown dramatic performance gains over conventional processor architectures. Namely, in addition to the unique parallel programmability features, which set XMT apart from any other current approach, XMT also provides very competitive performance. If XMT will meet expectations, its introduction would greatly enhance the normal rate of improvement of conventional processor architectures leading to new applications.
Keywords: Computer; Science

Preserving distributed systems critical properties: a model-driven approach - Yilmaz,C.; Memon, Atif M.; Porter, Adam; Krishna,A. S; Schmidt,D. C; Gokhale,A.; Natarajan,B. (Software, IEEE, 2004)
The need for creating predictability in distributed systems is most often specified in terms of quality-of-service (QoS) requirements, which help define the acceptable levels of dependability with which capabilities such as processing capacity, data throughput, or service availability reach users. For longer-term properties such as scalability, maintainability, adaptability, and system security, we can similarly use persistent software attributes (PSAs) to specify how and to what degree such properties must remain intact as a network expands and evolves over time. The Skoll distributed continuous software quality assurance process helps to identify viable system and software configurations for meeting stringent QOS and PSA requirements by coordinating the use of distributed computing resources. The authors tested their process using the large, rapidly evolving ACE+TAO middleware suite.
Keywords: configuration management; formal verification; Middleware; middleware suite; model-driven approach; persistent software attributes; QoS requirements; Quality assurance; quality of service; quality-of-service; Skoll distributed computing resources; software configuration; Software maintenance; Software quality; software quality assurance process; system dependability

Product approximation by minimizing the upper bound of Bayes error rate for Bayesian combination of classifiers - Kang,Hee-Joong; David Doermann (Pattern Recognition, 2004. ICPR 2004. Proceedings of the 17th International Conference on, 2004)
In combining multiple classifiers using a Bayesian formalism, a high dimensional probability distribution is composed of a class and decisions of classifiers. In order to do product approximation of the probability distribution, the upper bound of Bayes error rate, bounded by the conditional entropy of a class and decisions, should be minimized. A second-order dependency-based product approximation is proposed in this paper by considering the second-order dependency between the class and decisions. The proposed method is evaluated by combining the classifiers recognizing unconstrained handwritten numerals.
Keywords: approximation; Bayes; Bayesian; bound; character; classification; classifiers; conditional; distribution; entropy; error; formalism; handwritten; methods; minimisation; multiple; numerals; pattern; probability; probability; Product; rate; recognition; statistics; unconstrained; upper

Querying structured data in an unstructured P2P system - Kantere,Verena; Tsoumakos,Dimitrios; Roussopoulos, Nick (Proceedings of the 6th annual ACM international workshop on Web information and data management - WIDM '04, 2004)

A Rao-Blackwellized particle filter for EigenTracking - Zia Khan; Balch, T.; Dellaert, F. (Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004, 2004)
Subspace representations have been a popular way to model appearance in computer vision. In Jepson and Black's influential paper on EigenTracking, they were successfully applied in tracking. For noisy targets, optimization-based algorithms (including EigenTracking) often fail catastrophically after losing track. Particle filters have recently emerged as a robust method for tracking in the presence of multi-modal distributions. To use subspace representations in a particle filter, the number of samples increases exponentially as the state vector includes the subspace coefficients. We introduce an efficient method for using subspace representations in a particle filter by applying Rao-Blackwellization to integrate out the subspace coefficients in the state vector. Fewer samples are needed since part of the posterior over the state vector is analytically calculated. We use probabilistic principal component analysis to obtain analytically tractable integrals. We show experimental results in a scenario in which we track a target in clutter.
Keywords: analytically tractable integrals; Computer vision; EigenTracking; Filters; Gaussian processes; modal analysis; multi-modal distributions; NOISE; noisy targets; optimisation; optimization-based algorithms; Particle filters; Particle measurements; Particle tracking; Principal component analysis; probabilistic principal component analysis; Rao-Blackwellized particle filter; Robustness; SHAPE; State estimation; state vector; subspace coefficients; Subspace representations; target tracking; vectors

Reducing complexity assumptions for statistically-hiding commitment - Horvitz,O.; Katz, Jonathan; Koo,C. Y; Morselli,R. (In EUROCRYPT, 2004)
Determining the minimal assumptions needed to construct various cryptographic buildingblocks has been a focal point of research in theoretical cryptography. For most — but not all! — cryptographic primitives, complexity assumptions both necessary and sufficient for their existence are known. Here, we revisit the following, decade-old question: what are the minimal assumptions needed to construct a statistically-hiding bit commitment scheme? Previously, it was known how to construct such schemes based on any one-way permutation. In this work, we show that regular one-way functions suffice. We show two constructions of statistically-hiding commitment schemes from regular one-way functions. Our first construction is more direct, and serves as a “stepping-stone” for our second construction which has improved round complexity. Of independent interest, as part of our work we show a compiler transforming any commitment scheme which is statistically-hiding against an honest-but-curious receiver to one which is statistically-hiding against a malicious receiver. This demonstrates the equivalence of these two formulations of the problem.

Round-optimal secure two-party computation - Katz, Jonathan; Ostrovsky,R. (Advances in Cryptology–CRYPTO 2004, 2004)
We consider the central cryptographic task of secure two-party computation: two parties wish to compute some function of their private inputs (each receiving possibly different outputs) where security should hold with respect to arbitrarily-malicious behavior of either of the participants. Despite extensive research in this area, the exact round-complexity of this fundamental problem (i.e., the number of rounds required to compute an arbitrary poly-time functionality) was not previously known.Here, we establish the exact round complexity of secure two-party computation with respect to black-box proofs of security. We first show a lower bound establishing (unconditionally) that four rounds are not sufficient to securely compute the coin-tossing functionality for any super-logarithmic number of coins; this rules out 4-round protocols for other natural functionalities as well. Next, we construct protocols for securely computing any (randomized) functionality using only five rounds. Our protocols may be based either on certified trapdoor permutations or homomorphic encryption schemes satisfying certain additional properties. The former assumption is implied by, e.g., the RSA assumption for large public exponents, while the latter is implied by, e.g., the DDH assumption. Finally, we show how our protocols may be modified – without increasing their round complexity and without requiring erasures – to tolerate an adaptive malicious adversary.

Secure routing in ad hoc networks - Katz, Jonathan (Workshop on Security of ad hoc and Sensor Networks: Proceedings of the 2 nd ACM workshop on Security of ad hoc and sensor networks, 2004)

A semidefinite programming approach to side chain positioning with new rounding strategies - Chazelle,B.; Kingsford, Carl; Singh,M. (INFORMS Journal on Computing, 2004)

Special issue: 35th Annual ACM Symposium on Theory of Computing - Khanna,Sanjeev; Srinivasan, Aravind (Journal of Computer and System Sciences, 2004)

Structural and algorithmic aspects of massive social networks - Eubank,Stephen; Kumar,V. S. Anil; Marathe,Madhav V.; Srinivasan, Aravind; Wang,Nan (Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, 2004)
We study the algorithmic and structural properties of very large, realistic social contact networks. We consider the social network for the city of Portland, Oregon, USA, developed as a part of the TRANSIMS/EpiSims project at the Los Alamos National Laboratory. The most expressive social contact network is a bipartite graph, with two types of nodes: people and locations; edges represent people visiting locations on a typical day. Three types of results are presented. (i) Our empirical results show that many basic characteristics of the dataset are well-modeled by a random graph approach suggested by Fan Chung Graham and Lincoln Lu (the CL-model), with a power-law degree distribution. (ii) We obtain fast approximation algorithms for computing basic structural properties such as clustering coefficients and shortest paths distribution. We also study the dominating set problem for such networks; this problem arose in connection with optimal sensor-placement for disease-detection. We present a fast approximation algorithm for computing near-optimal dominating sets. (iii) Given the close approximations provided by the CL-model to our original dataset and the large data-volume, we investigate fast methods for generating such random graphs. We present methods that can generate such a random network in near-linear time, and show that these variants asymptotically share many key features of the CL-model, and also match the Portland social network.The structural results have been used to study the impact of policy decisions for controlling large-scale epidemics in urban environments.

Temporal range exploration of large scale multidimensional time series data - JaJa, Joseph F.; Kim,J.; Wang,Q. (Proceedings of SSDBM, 2004)
We consider the problem of querying largescale multidimensional time series data to discover events of interest, test and validate hypotheses, or to associate temporal patterns with specific events. This type of data currently dominate most other types of available data, and will very likely become even more prevalent in the future given the current trends in collecting time series of business, scientific, demographic, and simulation data. The ability to explore such collections interactively, even at a coarse level, will be critical in discovering the information and knowledge embedded in such collections. We develop indexing techniques and search algorithms to efficiently handle temporal range value querying of multidimensional time series data. Our indexing uses linear space data structures that enable the handling of queries in I/O time that is essentially the same as that of handling a single time slice, assuming the availability of a logarithmic number of processors as a function of size of the temporal window. A data structure with provably good bounds is also presented for the case when the number of multidimensional objects is relatively small. These techniques improve significantly over standard techniques for either serial or parallel processing, and are evaluated by extensive experimental results that confirm their superior performance.

Trust-preserving set operations - Morselli,R.; Bhattacharjee, Bobby; Katz, Jonathan; Keleher,P. (INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 2004)
We describe a method for performing trust-preserving set operations by untrusted parties. Our motivation for this is the problem of securely reusing content-based search results in peer-to-peer networks. We model search results and indexes as data sets. Such sets have value for answering a new query only if they are trusted. In the absence of any system-wide security mechanism, a data set is trusted by a node a only if it was generated by some node which is trusted by a. Our main contributions are a formal definition of the problem as well as an efficient scheme that solves this problem by allowing untrusted peers to perform set operations on trusted data sets while also producing unforgeable proofs of correctness. This is accomplished by requiring trusted nodes to sign appropriately-defined digests of generated sets; each such digest consists of an RSA accumulator and a Bloom filter. The scheme is general, and has other applications as well. We give an analysis demonstrating the low overhead of the scheme, and we include experimental data which confirm the analysis.
Keywords: accumulator; Bloom; computing; filter; mechanism; network; operation; peer-to-peer; RSA; Security; security; set; system-wide; Telecommunication; theory; trust-preserving

Ubistatins Inhibit Proteasome-Dependent Degradation by Binding the Ubiquitin Chain - Verma,Rati; Peters,Noel R.; D'Onofrio,Mariapina; Tochtrop,Gregory P.; Sakamoto,Kathleen M.; Varadan,Ranjani; Zhang,Mingsheng; Coffino,Philip; Fushman, David; Deshaies,Raymond J.; King,Randall W. (Science, 2004)
To identify previously unknown small molecules that inhibit cell cycle machinery, we performed a chemical genetic screen in Xenopus extracts. One class of inhibitors, termed ubistatins, blocked cell cycle progression by inhibiting cyclin B proteolysis and inhibited degradation of ubiquitinated Sic1 by purified proteasomes. Ubistatins blocked the binding of ubiquitinated substrates to the proteasome by targeting the ubiquitin-ubiquitin interface of Lys48-linked chains. The same interface is recognized by ubiquitin-chain receptors of the proteasome, indicating that ubistatins act by disrupting a critical protein-protein interaction in the ubiquitin-proteasome system.

Understanding tuberculosis epidemiology using structured statistical models - Getoor, Lise; Rhee,Jeanne T; Koller,Daphne; Small,Peter (Artificial Intelligence in Medicine, 2004)
Molecular epidemiological studies can provide novel insights into the transmission of infectious diseases such as tuberculosis. Typically, risk factors for transmission are identified using traditional hypothesis-driven statistical methods such as logistic regression. However, limitations become apparent in these approaches as the scope of these studies expand to include additional epidemiological and bacterial genomic data. Here we examine the use of Bayesian models to analyze tuberculosis epidemiology. We begin by exploring the use of Bayesian networks (BNs) to identify the distribution of tuberculosis patient attributes (including demographic and clinical attributes). Using existing algorithms for constructing BNs from observational data, we learned a BN from data about tuberculosis patients collected in San Francisco from 1991 to 1999. We verified that the resulting probabilistic models did in fact capture known statistical relationships. Next, we examine the use of newly introduced methods for representing and automatically constructing probabilistic models in structured domains. We use statistical relational models (SRMs) to model distributions over relational domains. SRMs are ideally suited to richly structured epidemiological data. We use a data-driven method to construct a statistical relational model directly from data stored in a relational database. The resulting model reveals the relationships between variables in the data and describes their distribution. We applied this procedure to the data on tuberculosis patients in San Francisco from 1991 to 1999, their Mycobacterium tuberculosis strains, and data on contact investigations. The resulting statistical relational model corroborated previously reported findings and revealed several novel associations. These models illustrate the potential for this approach to reveal relationships within richly structured data that may not be apparent using conventional statistical approaches. We show that Bayesian methods, in particular statistical relational models, are an important tool for understanding infectious disease epidemiology.
Keywords: Bayesian networks; epidemiology; Probabilistic and statistical relational models; Tuberculosis

Using the structure of Web sites for automatic segmentation of tables - Lerman,Kristina; Getoor, Lise; Minton,Steven; Knoblock,Craig (Proceedings of the 2004 ACM SIGMOD international conference on Management of data, 2004)
Many Web sites, especially those that dynamically generate HTML pages to display the results of a user's query, present information in the form of list or tables. Current tools that allow applications to programmatically extract this information rely heavily on user input, often in the form of labeled extracted records. The sheer size and rate of growth of the Web make any solution that relies primarily on user input is infeasible in the long term. Fortunately, many Web sites contain much explicit and implicit structure, both in layout and content, that we can exploit for the purpose of information extraction. This paper describes an approach to automatic extraction and segmentation of records from Web tables. Automatic methods do not require any user input, but rely solely on the layout and content of the Web source. Our approach relies on the common structure of many Web sites, which present information as a list or a table, with a link in each entry leading to a detail page containing additional information about that item. We describe two algorithms that use redundancies in the content of table and detail pages to aid in information extraction. The first algorithm encodes additional information provided by detail pages as constraints and finds the segmentation by solving a constraint satisfaction problem. The second algorithm uses probabilistic inference to find the record segmentation. We show how each approach can exploit the web site structure in a general, domain-independent manner, and we demonstrate the effectiveness of each algorithm on a set of twelve Web sites.

Using the TIGR Assembler in Shotgun Sequencing Projects - Pop, Mihai; Kosack,Dan (Bacterial Artificial Chromosomes, 2004)
The TIGR Assembler (TA) ( 1 ) is the sequence assembly program used in sequencing projects at The Institute for Genomic Research (TIGR). Development of the TA was based on the experience obtained in more than 20 sequencing projects completed at TIGR ( see http://www.tigr.org ). This extensive experience led to a sequence assembler that produces few misassemblies ( 2 , 3 ) and has been used successfully in whole-genome shotgun sequencing of prokaryotic and eukaryotic organisms, bacterial artificial chromosome-based sequencing of eukaryotic organisms, and expressed sequence tag assembly.

Validating quality of service for reusable software via model-integrated distributed continuous quality assurance - Krishna,A.; Schmidt,D.; Memon, Atif M.; Porter, Adam; Sevilla,D. (Software Reuse: Methods, Techniques, and Tools, 2004)
Quality assurance (QA) tasks, such as testing, profiling, and performance evaluation, have historically been done in-house on developer-generated workloads and regression suites. Performance-intensive systems software, such as that found in the scientific computing grid and distributed real-time and embedded (DRE) domains, increasingly run on heterogeneous combinations of OS, compiler, and hardware platforms. Such software has stringent quality of service (QoS) requirements and often provides a variety of configuration options to optimize QoS. As a result, QA performed solely in-house is inadequate since it is hard to manage software variability, i.e., ensuring software quality on all supported target platforms across all desired configuration options. This paper describes how the Skoll project is addressing these issues by developing advanced QA processes and tools that leverage the extensive computing resources of user communities in a distributed, continuous manner to improve key software quality attributes.

Variation of toxigenic Vibrio cholerae O1 in the aquatic environment of Bangladesh and its correlation with the clinical strains - Islam,M. S.; Talukder,K. A.; Khan,N. H.; Mahmud,Z. H.; Rahman,M. Z.; Nair,G. B.; Siddique,A. K. M.; Yunus,M.; Sack,D. A.; Sack,R. B.; Rita R Colwell (Microbiology and immunology, 2004)

What works better for question answering: Stemming or morphological query expansion - Bilotti,M. W; Katz,B.; Jimmy Lin (Proceedings of the Information Retrieval for Question Answering (IR4QA) Workshop at SIGIR 2004, 2004)
How do different information retrieval techniques affect theperformance of document retrieval in the context of question answering? An exploration of this question is our overall re- search goal. In this paper, we specifically examine strategies for coping with morphological variation. This work quanti- tatively compares two different approaches to handling term variation: applying a stemming algorithm at indexing time, and performing morphological query expansion at retrieval time. We discovered that, compared to the no-stemming baseline, stemming results in lower recall, and morphologi- cal expansion yields higher recall. By separately weighting different term variants, we were able to achieve even higher recall, which opens the door to interesting question analy- sis algorithms for sophisticated query generation. Another significant contribution of our work is the development of a reusable question answering test collection to support our experiments.

Wide baseline image registration with application to 3-D face modeling - Roy-Chowdhury, A.K.; Chellapa, Rama; Keaton, T. (Multimedia, IEEE Transactions on, 2004)
Establishing correspondence between features in two images of the same scene taken from different viewing angles is a challenging problem in image processing and computer vision. However, its solution is an important step in many applications like wide baseline stereo, three-dimensional (3-D) model alignment, creation of panoramic views, etc. In this paper, we propose a technique for registration of two images of a face obtained from different viewing angles. We show that prior information about the general characteristics of a face obtained from video sequences of different faces can be used to design a robust correspondence algorithm. The method works by matching two-dimensional (2-D) shapes of the different features of the face (e.g., eyes, nose etc.). A doubly stochastic matrix, representing the probability of match between the features, is derived using the Sinkhorn normalization procedure. The final correspondence is obtained by minimizing the probability of error of a match between the entire constellation of features in the two sets, thus taking into account the global spatial configuration of the features. The method is applied for creating holistic 3-D models of a face from partial representations. Although this paper focuses primarily on faces, the algorithm can also be used for other objects with small modifications.
Keywords: 2D; 3D; algorithm; baseline; biometrics; Computer; configuration; correspondence; doubly; error; extraction; Face; feature; holistic; image; matching; matrix; minimization; modeling; models; normalization; probability; probability; procedure; processes; processing; recognition; registration; representation; sequences; shapes; Sinkhorn; spatial; statistics; Stochastic; video; vision; wide

Acquisition of bilingual MT lexicons from OCRed dictionaries - Karagol-Ayan,B.; David Doermann; Dorr, Bonnie J (Proceedings of the 9th MT Summit, 2003)
This paper describes an approach to analyzing the lexical structure of OCRed bilingual dictionaries to construct re-sources suited for machine translation of low-density languages, where online resources are limited. A rule-based, an HMM-based, and a post-processed HMM-based method are used for rapid construction of MT lexicons based on sys- tematic structural clues provided in the original dictionary. We evaluate the effectiveness of our techniques, concluding that: (1) the rule-based method performs better with dictionaries where the font is not an important distinguishing fea- ture for determining information types; (2) the post-processed stochastic method improves the results of the stochastic method for phrasal entries; and (3) Our resulting bilingual lexicons are comprehensive enough to provide the basis for reasonable translation results when compared to human translations.

Acquisition of Bilingual MTLexicons from OCRed Dictionaries - Karagol-Ayan,B.; David Doermann; Dorr, Bonnie J (Proceedings of the Ninth Machine Translation Summit, 2003)

An adaptive quality of service aware middleware for replicated services - Krishnamurthy,Sudha; Sanders,W. H.; Michel Cukier (Parallel and Distributed Systems, IEEE Transactions on, 2003)
A dependable middleware should be able to adaptively share the distributed resources it manages in order to meet diverse application requirements, even when the quality of service (QoS) is degraded due to uncertain variations in load and unanticipated failures. We have addressed this issue in the context of a dependable middleware that adaptively manages replicated servers to deliver a timely and consistent response to time-sensitive client applications. These applications have specific temporal and consistency requirements, and can tolerate a certain degree of relaxed consistency in exchange for better response time. We propose a flexible QoS model that allows clients to specify their timeliness and consistency constraints. We also propose an adaptive framework that dynamically selects replicas to service a client's request based on the prediction made by probabilistic models. These models use the feedback from online performance monitoring of the replicas to provide probabilistic guarantees for meeting a client's QoS specification. The experimental results we have obtained demonstrate the role of feedback and the efficacy of simple analytical models for adaptively sharing the available replicas among the users under different workload scenarios.
Keywords: distributed resource sharing; Middleware; online performance monitoring; probabilistic modeling; QoS specification; quality of service; replica consistency; replicated services; resource allocation; time-sensitive client applications; timeliness constraints

Airborne Video Registration for Activity Monitoring - Shekhar,Chandra; Chellapa, Rama (Video RegistrationVideo Registration, 2003)
The analysis of ground activities involving vehicles and humans is of interest in airborne surveillance applications. The high spatiotemporal resolution of a video camera makes it the sensor of choice for such applications. In the past, video sensors were not preferred, precisely because of the high volume of data generated, which had to be processed manually for the most part. Further, the moving platform gives rise to numerous false alarms.

Approximating the domatic number - Feige,U.; Halldórsson,M.M.; Kortsarz,G.; Srinivasan, Aravind (SIAM Journal on Computing, 2003)
A set of vertices in a graph is a dominating set if every vertex outside the set hasa neighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices, δ the minimum degree, and ∆ the maximum degree. We show that every graph has a domatic partition with (1 − o(1))(δ + 1)/ ln n dominating sets and, moreover, that such a domatic partition can be found in polynomial-time. This implies a (1 + o(1)) ln n-approximation algorithm for domatic number, since the domatic number is always at most δ+1. We also show this to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every ϵ > 0, a (1 − ϵ) ln n-approximation implies that NP ⊆ DTIME(nO(log log n)). This makes domatic number the first natural maximization problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better. We also show that every graph has a domatic partition with (1 − o(1))(δ + 1)/ ln ∆ dominating sets, where the “o(1)” term goes to zero as ∆ increases. This can be turned into an efficient algorithm that produces a domatic partition of Ω(δ/ ln ∆) sets.

Approximation Algorithms for Channel Allocation Problems in Broadcast Networks - Gandhi,Rajiv; Khuller, Samir; Srinivasan, Aravind; Wang,Nan (Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 2003)
We study two packing problems that arise in the area of dissemination-based information systems; a second theme is the study of distributed approximation algorithms. The problems considered have the property that the space occupied by a collection of objects together could be significantly less than the sum of the sizes of the individual objects. In the Channel Allocation Problem , there are users who request subsets of items. There are a fixed number of channels that can carry an arbitrary amount of information. Each user must get all of the requested items from one channel, i.e., all the data items of each request must be broadcast on some channel. The load on any channel is the number of items that are broadcast on that channel; the objective is to minimize the maximum load on any channel. We present approximation algorithms for this problem and also show that the problem is MAX-SNP hard. The second problem is the Edge Partitioning Problem addressed by Goldschmidt, Hochbaum, Levin, and Olinick ( Networks, 41:13-23, 2003 ). Each channel here can deliver information to at most k users, and we aim to minimize the total load on all channels. We present an O ( n⅓ )–approximation algorithm and also show that the algorithm can be made fully distributed with the same approximation guarantee; we also generalize to the case of hypergraphs.

AQuA: an adaptive architecture that provides dependable distributed objects - Ren,Yansong; Bakken,D. E.; Courtney,T.; Michel Cukier; Karr,D. A.; Rubel,P.; Sabnis,C.; Sanders,W. H.; Schantz,R.E.; Seri,M. (Computers, IEEE Transactions on, 2003)
Building dependable distributed systems from commercial off-the-shelf components is of growing practical importance. For both cost and production reasons, there is interest in approaches and architectures that facilitate building such systems. The AQuA architecture is one such approach; its goal is to provide adaptive fault tolerance to CORBA applications by replicating objects. The AQuA architecture allows application programmers to request desired levels of dependability during applications' runtimes. It provides fault tolerance mechanisms to ensure that a CORBA client can always obtain reliable services, even if the CORBA server object that provides the desired services suffers from crash failures and value faults. AQuA includes a replicated dependability manager that provides dependability management by configuring the system in response to applications' requests and changes in system resources due to faults. It uses Maestro/Ensemble to provide group communication services. It contains a gateway to intercept standard CORBA IIOP messages to allow any standard CORBA application to use AQuA. It provides different types of replication schemes to forward messages reliably to the remote replicated objects. All of the replication schemes ensure strong, data consistency among replicas. This paper describes the AQuA architecture and presents, in detail, the active replication pass-first scheme. In addition, the interface to the dependability manager and the design of the dependability manager replication are also described. Finally, we describe performance measurements that were conducted for the active replication pass-first scheme, and we present results from our study of fault detection, recovery, and blocking times.
Keywords: active replication pass-first scheme; adaptive architecture; adaptive fault tolerance; AQuA; CORBA; data consistency; data integrity; dependable distributed objects; distributed object management; performance measurements; quality of service; replicated dependability manager; replication schemes; software fault tolerance; system resources

Bistro: a scalable and secure data transfer service for digital government applications - Golubchik,Leana; Cheng,William C.; Chou,Cheng-Fu; Khuller, Samir; Samet, Hanan; Wan,C. Justin (Communications of the ACM, 2003)
Government at all levels is a major collector and provider of data.Our project focuses on the collection of data over wide-area networks (WANs) and addresses the scalability issues that arise in the context of Internet-based massive data collection applications. Furthermore, security, due to the need for privacy and integrity of the data, is a central issue for data collection applications that use a public infrastructure such as the Internet. Numerous digital government applications require data collection over WANs [5].One compelling example of such an application is the Internal Revenue Service's electronic submission of income tax forms. Other digital government applications include collecting census data, federal statistics, and surveys; gathering and tallying of electronic votes; collecting crime data for the U.S. Justice department; collecting data from sensors for disaster response applications; collecting data from geological surveys; collecting electronic filings of patents, permits, and securities (for SEC) applications; grant proposals and contract bids submissions; and so on. All these applications have scalability and security needs in common.The poor performance that may be experienced by current digital government users, given the existing state of technology (as in Figure 1a), is largely due to how (independent) data transfers using TCP/IP work over the Internet. TCP/IP is good at equally sharing bandwidth between data streams, which in large-scale applications can lead to poor performance for individual clients (as they receive only a very small share of this bandwidth). Given that TCP/IP is here to stay for the foreseeable future, what is needed is a scalable yet cost- effective solution that can be easily deployed over the existing Internet technology.We are designing and developing a system called Bistro, which addresses the scalability needs of digital government data collection applications while allowing them to share the same infrastructure and resources efficiently, cost-effectively, and securely [1]. Bistro's basic approach is to introduce intermediate hosts---bistros---which allow replacement of a traditionally "synchronized client push" approach with a "nonsynchronized combination of client-push and server-pull" approach (as depicted in Figure 1b). This in turn allows spreading of the workload on the destination server and the network over time, with subsequent elimination of hot spots as well as significant improvements in performance for both clients and servers. Our ongoing research [2, 4] indicates that orders of magnitude of improvement can be achieved with the Bistro architecture and the corresponding data collection algorithms it affords.Bistro's design allows for a gradual deployment and experimentation over the Internet (by simply downloading Bistro server software and installing it on public servers). Bistro's security protocol and trust structure [3] are designed such that only encrypted data travels through (not necessarily trusted) bistros. This means a government agency does not need to trust bistros installed by other agencies or commercial institutions. At the same time, these (untrusted) bistros can significantly improve the agency's data collection performance. Each application (within each agency) can have its own scalability, security, fault tolerance, and other data collection needs, and these applications and agencies can still share available resources, if so desired, across all Bistro servers.We believe an appropriately designed single infrastructure such as Bistro can address all digital government wide-area data collection needs in a scalable, secure, and cost-effective manner. (For more information, see bourbon.usc.edu/iml/bistro/.

Bistro: a scalable and secure data transfer service for digital government applications - Golubchik,Leana; Cheng,William C.; Chou,Cheng-Fu; Khuller, Samir; Samet, Hanan; Wan,C. Justin (Commun. ACM, 2003)
Government at all levels is a major collector and provider of data.Our project focuses on the collection of data over wide-area networks (WANs) and addresses the scalability issues that arise in the context of Internet-based massive data collection applications. Furthermore, security, due to the need for privacy and integrity of the data, is a central issue for data collection applications that use a public infrastructure such as the Internet. Numerous digital government applications require data collection over WANs [5].One compelling example of such an application is the Internal Revenue Service's electronic submission of income tax forms. Other digital government applications include collecting census data, federal statistics, and surveys; gathering and tallying of electronic votes; collecting crime data for the U.S. Justice department; collecting data from sensors for disaster response applications; collecting data from geological surveys; collecting electronic filings of patents, permits, and securities (for SEC) applications; grant proposals and contract bids submissions; and so on. All these applications have scalability and security needs in common.The poor performance that may be experienced by current digital government users, given the existing state of technology (as in Figure 1a), is largely due to how (independent) data transfers using TCP/IP work over the Internet. TCP/IP is good at equally sharing bandwidth between data streams, which in large-scale applications can lead to poor performance for individual clients (as they receive only a very small share of this bandwidth). Given that TCP/IP is here to stay for the foreseeable future, what is needed is a scalable yet cost- effective solution that can be easily deployed over the existing Internet technology.We are designing and developing a system called Bistro, which addresses the scalability needs of digital government data collection applications while allowing them to share the same infrastructure and resources efficiently, cost-effectively, and securely [1]. Bistro's basic approach is to introduce intermediate hosts---bistros---which allow replacement of a traditionally "synchronized client push" approach with a "nonsynchronized combination of client-push and server-pull" approach (as depicted in Figure 1b). This in turn allows spreading of the workload on the destination server and the network over time, with subsequent elimination of hot spots as well as significant improvements in performance for both clients and servers. Our ongoing research [2, 4] indicates that orders of magnitude of improvement can be achieved with the Bistro architecture and the corresponding data collection algorithms it affords.Bistro's design allows for a gradual deployment and experimentation over the Internet (by simply downloading Bistro server software and installing it on public servers). Bistro's security protocol and trust structure [3] are designed such that only encrypted data travels through (not necessarily trusted) bistros. This means a government agency does not need to trust bistros installed by other agencies or commercial institutions. At the same time, these (untrusted) bistros can significantly improve the agency's data collection performance. Each application (within each agency) can have its own scalability, security, fault tolerance, and other data collection needs, and these applications and agencies can still share available resources, if so desired, across all Bistro servers.We believe an appropriately designed single infrastructure such as Bistro can address all digital government wide-area data collection needs in a scalable, secure, and cost-effective manner. (For more information, see bourbon.usc.edu/iml/bistro/.

Bringing Treasures to the Surface: Previews and Overviews in a Prototype for the Library of Congress National Digital Library - Marchionini,A.S.; Nation,D.; Karasik,S.; Cronnell,T.; Shneiderman, Ben; Spotfire,V.D.M.U.; Bederson, Benjamin B.; Data,T.S.; Hochheiser,H.; Shneiderman, Ben; others (The craft of information visualization: readings and reflections, 2003)

Characterization of a Vibrio cholerae phage isolated from the coastal water of Peru - Talledo,Miguel; Rivera,Irma N. G.; Lipp,Erin K.; Neale,Angela; Karaolis,David; Huq,Anwar; Rita R Colwell (Environmental Microbiology, 2003)
A Vibrio cholerae bacteriophage, family Myoviridae, was isolated from seawater collected from the coastal water of Lima, Peru. Genome size was estimated to be 29 kbp. The temperate phage was specific to V. cholerae and infected 12/13 V. cholerae O1 strains and half of the four non-O1/non-O139 strains tested in this study. Vibrio cholerae O139 strains were resistant to infection and highest infection rates were obtained in low nutrient media amended with NaCl or prepared using seawater as diluent.

Checking and inferring local non-aliasing - Aiken,A.; Foster, Jeffrey S.; Kodumal,J.; Terauchi,T. (ACM SIGPLAN Notices, 2003)

Combining multiple evidences for gait recognition - Cuntoor, N.; Kale, A.; Chellapa, Rama (Acoustics, Speech, and Signal Processing, 2003. Proceedings. (ICASSP '03). 2003 IEEE International Conference on, 2003)
In this paper, we systematically analyze different components of human gait, for the purpose of human identification. We investigate dynamic features such as the swing of the hands/legs, the sway of the upper body and static features like height, in both frontal and side views. Both probabilistic and non-probabilistic techniques are used for matching the features. Various combination strategies may be used depending upon the gait features being combined. We discuss three simple rules: the Sum, Product and MIN rules that are relevant to our feature sets. Experiments using four different datasets demonstrate that fusion can be used as an effective strategy in recognition.
Keywords: analysis; dynamic; evidences; extraction; feature; features; frontal; Gait; height; human; identification; image; MIN; multiple; nonprobabilistic; probabilistic; Product; recognition; rules; sets; side; static; Sum; sway; swing; techniques; views

Construction of an efficient overlay multicast infrastructure for real-time applications - Banerjee,S.; Kommareddy,C.; Kar,K.; Bhattacharjee, Bobby; Khuller, Samir (INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies, 2003)
This paper presents an overlay architecture where service providers deploy a set of service nodes (called MSNs) in the network to efficiently implement media-streaming applications. These MSNs are organized into an overlay and act as application-layer multicast forwarding entities for a set of clients. We present a decentralized scheme that organizes the MSNs into an appropriate overlay structure that is particularly beneficial for real-time applications. We formulate our optimization criterion as a "degree-constrained minimum average-latency problem" which is known to be NP-hard. A key feature of this formulation is that it gives a dynamic priority to different MSNs based on the size of its service set. Our proposed approach iteratively modifies the overlay tree using localized transformations to adapt with changing distribution of MSNs, clients, as well as network conditions. We show that a centralized greedy approach to this problem does not perform quite as well, while our distributed iterative scheme efficiently converges to near-optimal solutions.
Keywords: application-layer; applications; communication; criterion; decentralized; distributed; entities; forwarding; infrastructure; Internet; iterative; media-streaming; methods; MSN; Multicast; nodes; NP-hard; OPTIMIZATION; overlay; real; real-time; scheme; service; systems; TIME

Data exploration with paired hierarchical visualizations: initial designs of PairTrees - Kules,Bill; Shneiderman, Ben; Plaisant, Catherine (Proceedings of the 2003 annual national conference on Digital government research, 2003)
Paired hierarchical visualizations (PairTrees) integrate treemaps, node-link diagrams, choropleth maps and other information visualization techniques to support exploration of hierarchical data sets at multiple levels of abstraction. This paper describes several novel applications of PairTrees in the econometric and health statistics domains, as well as some challenges and trade-offs inherent in the technique.

Data partitioning for DSP software synthesis - Ko,M. Y; Bhattacharyya, Shuvra S. (Lecture Notes in Computer Science, 2003)

Defeating Web censorship with untrusted messenger discovery - Feamster, Nick; Balazinska,M.; Wang,W.; Balakrishnan,H.; Karger,D. (Workshop on Privacy Enhancing Technologies, 2003)

Deno: a decentralized, peer-to-peer object-replication system for weakly connected environments - Cetintemel,U.; Keleher,P. J; Bhattacharjee, Bobby; Franklin,M.J. (Computers, IEEE Transactions on, 2003)
This paper presents the design, implementation, and evaluation of the replication framework of Deno, a decentralized, peer-to-peer object-replication system targeted for weakly connected environments. Deno uses weighted voting for availability and pair-wise, epidemic information flow for flexibility. This combination allows the protocols to operate with less than full connectivity, to easily adapt to changes in group membership, and to make few assumptions about the underlying network topology. We present two versions of Deno's protocol that differ in the consistency levels they support. We also propose security extensions to handle a class of malicious actions that involve misrepresentation of protocol information. Deno has been implemented and runs on top of Linux and Win32 platforms. We use the Deno prototype to characterize the performance of the Deno protocols and extensions. Our study reveals several interesting results that provide fundamental insight into the benefits of decentralization and the mechanics of epidemic protocols.
Keywords: actions; connected; consistency; data; data; databases; decentralized; Deno; distributed; environments; epidemic; group; levels; Linux; malicious; management; membership; network; object; object-replication; of; operating; peer-to-peer; protocols; replicated; replication; Security; security; synchronisation; system; systems; topology; Unix; voting; weakly; weighted; Win32

Designing a metadata-driven visual information browser for federal statistics - Kules,Bill; Shneiderman, Ben (Proceedings of the 2003 annual national conference on Digital government research, 2003)
When looking for federal statistics, finding the right table, chart or report can be a daunting task for anyone not thoroughly familiar with the federal statistical system. Search tools help, but differing terminologies within the statistical agencies and a lack of familiarity of terms by information seekers limit their effectiveness. The FedStats Browser is a design for visually browsing federal agency statistical products and publications, using techniques that allow users to reformulate queries and iteratively refine results via simple, reversible actions with immediate feedback. This paper also discusses the characteristics of metadata needed for such a browser and the challenges inherent in acquiring that metadata.

Desparately seeking cebuano - Oard, Douglas; David Doermann; Dorr, Bonnie J; He,D.; Resnik, Philip; Weinberg, Amy; Byrne,W.; Khudanpur,S.; Yarowsky,D.; Leuski,A.; others (Third Conference on Human Language Technologies, 2003)
This paper describes an effort to rapidly de-velop language resources and component tech- nology to support searching Cebuano news sto- ries using English queries. Results from the first 60 hours of the exercise are presented.

Deterministic Resource Discovery in Distributed Networks - Kutten,Shay; Peleg,David; Vishkin, Uzi (Theory of Computing Systems, 2003)
The resource discovery problem was introduced by Harchol-Balter, Leighton, and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is a directed logical graph that represents the vertices’ knowledge about the topology of the underlying communication network. The current paper proposes a deterministic algorithm for the problem in the same model, with improved time, message, and communication complexities. Each previous algorithm had a complexity that was higher at least in one of the measures. Specifically, previous deterministic solutions required either time linear in the diameter of the initial network, or communication complexity $O(n^3)$ (with message complexity $O(n^2)$), or message complexity $O(|E_0| łog n)$ (where $E_0$ is the arc set of the initial graph $G_0$). Compared with the main randomized algorithm of Harchol-Balter, Leighton, and Lewin, the time complexity is reduced from $O(łog^2n)$ to\pagebreak[4] $O(łog n )$, the message complexity from $O(n łog^2 n)$ to $O(n łog n )$, and the communication complexity from $O(n^2 łog^3 n)$ to $O(|E_0|łog ^2 n )$. \par Our work significantly extends the connectivity algorithm of Shiloach and Vishkin which was originally given for a parallel model of computation. Our result also confirms a conjecture of Harchol-Balter, Leighton, and Lewin, and addresses an open question due to Lipton.
Keywords: Computer; Science

Digital Government-Bistro: A Scalable and Secure Data Transfer Service for Digital Government Applications - Golubchik,L.; Cheng,W. C; Chou,C. F; Khuller, Samir; Samet, Hanan; Wan,Y. C.J (Communications of the ACM-Association for Computing Machinery-CACM, 2003)

The dog genome: survey sequencing and comparative analysis - Kirkness,E. F; Bafna,V.; Halpern,A. L; Levy,S.; Remington,K.; Rusch,D. B; Delcher,A. L; Pop, Mihai; Wang,W.; Fraser,C. M; others (Science, 2003)

The Dog Genome: Survey Sequencing and Comparative Analysis - Kirkness,Ewen F.; Bafna,Vineet; Halpern,Aaron L.; Levy,Samuel; Remington,Karin; Rusch,Douglas B; Delcher,Arthur L.; Pop, Mihai; Wang,Wei; Fraser,Claire M.; Venter,J. Craig (ScienceScience, 2003)
A survey of the dog genome sequence (6.22 million sequence reads; 1.5× coverage) demonstrates the power of sample sequencing for comparative analysis of mammalian genomes and the generation of species-specific resources. More than 650 million base pairs (>25%) of dog sequence align uniquely to the human genome, including fragments of putative orthologs for 18,473 of 24,567 annotated human genes. Mutation rates, conserved synteny, repeat content, and phylogeny can be compared among human, mouse, and dog. A variety of polymorphic elements are identified that will be valuable for mapping the genetic basis of diseases and traits in the dog.

Domain Tuning of Bilingual Lexicons for MT - Ayan,Necip F; Dorr, Bonnie J; Kolak,Okan (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2003)
Our overall objective is to translate a domain-specific document in a foreign language (in this case, Chinese) to English. Using automatically induced domain-specific, comparable documents and language-independent clustering, we apply domain-tuning techniques to a bilingual lexicon for downstream translation of the input document to English. We will describe our domain-tuning technique and demonstrate its effectiveness by comparing our results to manually constructed domain-specific vocabulary. Our coverage/accuracy experiments indicate that domain-tuned lexicons achieve 88/% precision and 66/% recall. We also ran a Bleu experiment to compare our domain-tuned version to its un-tuned counterpart in an IR Ni-style NIT system. Our domain-tuned lexicons brought about an improvement in the Blen scores: 9.4/% higher than a system trained on a uniformly- weighted dictionary and 275/% higher than a system trained on no dictionary at all.
Keywords: *DICTIONARIES; *FOREIGN LANGUAGES; accuracy; BILINGUAL LEXICONS; DOCUMENTS; linguistics; Vocabulary

Driving scientific applications by data in distributed environments - Saltz, J.; Catalyurek,U.; Kurc, T.; Gray,M.; Hastings,S.; Langella,S.; Narayanan,S.; Martino,R.; Bryant,S.; Peszynska,M.; others (Computational Science—ICCS 2003, 2003)

Efficiency improvements for signature schemes with tight security reductions - Katz, Jonathan; Wang,Nan (Proceedings of the 10th ACM conference on Computer and communications security, 2003)
Much recent work has focused on constructing efficient digital signature schemes whose security is tightly related to the hardness of some underlying cryptographic assumption. With this motivation in mind, we show here two approaches which improve both the computational efficiency and signature length of some recently-proposed schemes:Diffie-Hellman signatures. Goh and Jarecki [18] recently analyzed a signature scheme which has a tight security reduction to the computational Diffie-Hellman problem. Unfortunately, their scheme is less efficient in both computation and bandwidth than previous schemes relying on the (related) discrete logarithm assumption. We present a modification of their scheme in which signing is 33% more efficient and signatures are 75% shorter; the security of this scheme is tightly related to the decisional Diffie-Hellman problem.PSS. The probabilistic signature scheme (PSS) designed by Bellare and Rogaway [3] uses a random salt to enable a tight security reduction to, e.g., the RSA problem. Coron [12] subsequently showed that a shorter random salt can be used without impacting the security of the scheme. We show a variant of PSS which avoids the random salt altogether yet has an equally-tight security reduction. This furthermore yields a version of PSS-R (PSS with message recovery) with optimal message length. Our technique may also be used to improve the efficiency of a number of other schemes.
Keywords: digital; SIGNATURES

Efficient and non-malleable proofs of plaintext knowledge and applications - Katz, Jonathan (Proceedings of the 22nd international conference on Theory and applications of cryptographic techniques, 2003)
We describe efficient protocols for non-malleable (interactive) proofs of plaintext knowledge for the RSA, Rabin, Paillier, and El Gamal encryption schemes. We also highlight some important applications of these protocols: - Chosen-ciphertext-secure, interactive encryption. In settings where both parties are on-line, an interactive encryption protocol may be used. We construct chosen-ciphertext-secure interactive encryption schemes based on any of the schemes above. In each case, the improved scheme requires only a small overhead beyond the original, semantically-secure scheme. - Password-based authenticated key exchange. We derive efficient protocols for password-based key exchange in the public-key model [28, 5] whose security may be based on any of the cryptosystems mentioned above. - Deniable authentication. Our techniques give the first efficient constructions of deniable authentication protocols based on, e.g., the RSA or computational Diffie-Hellman assumption. Of independent interest, we consider the concurrent composition of proofs of knowledge; this is essential to prove security of our protocols when run in an asynchronous, concurrent environment.

Efficient particle filter-based tracking of multiple interacting targets using an MRF-based motion model - Zia Khan; Balch, T.; Dellaert, F. (2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003. (IROS 2003). Proceedings, 2003)
We describe a multiple hypothesis particle filter for tracking targets that are influenced by the proximity and/or behavior of other targets. Our contribution is to show how a Markov random field motion prior, built on the fly at each time step, can model these interactions to enable more accurate tracking. We present results for a social insect tracking application, where we model the domain knowledge that two targets cannot occupy the same space, and targets actively avoid collisions. We show that using this model improves track quality and efficiency. Unfortunately, the joint particle tracker we propose suffers from exponential complexity in the number of tracked targets. An approximation to the joint filter, however, consisting of multiple nearly independent particle filters can provide similar track quality at substantially lower computational cost.
Keywords: collision avoidance; computational cost; Computational efficiency; Educational institutions; exponential complexity; Filtering; filtering theory; Insects; joint particle tracker; Markov processes; Markov random field motion; Markov random fields; multiple interacting targets; particle filter-based tracking; Particle filters; Particle tracking; Radar tracking; social insect tracking application; target tracking; Trajectory

Efficient peer-to-peer searches using result-caching - Bhattacharjee, Bobby; Chawathe,S.; Gopalakrishnan,V.; Keleher,P.; Silaghi,B. (Peer-to-Peer Systems II, 2003)
Existing peer-to-peer systems implement a single function well: data lookup. There is now a wealth of research describing how to reliably disseminate, and to later retrieve, data in a scalable and load-balanced manner.

Evaluating Translational Correspondence using Annotation Projection - Hwa,R.; Resnik, Philip; Weinberg, Amy; Kolak,O. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2003)
Recently, statistical machine translation models have begun to take advantage of higherlevel linguistic structures such as syntactic dependencies. Underlying these models is an assumption about the directness of translational correspondence between sentences in the two languages; however, the extent to which this assumption is valid and useful is not well understood. In this paper, we present an empirical study that quantifies the degree to which syntactic dependencies are preserved when parses are projected directly from En- glish to Chinese. Our results show that although the direct correspondence assumption is often too restrictive, a small set of principled, elementary linguistic transformations can boost the quality of the projected Chinese parses by 76% relative to the unimproved baseline.

Evaluation Techniques Applied to Domain Tuning of MT Lexicons - Ayan,N.F.; Dorr, Bonnie J; Kolak,O. (Proceedings of the Workshop “Towards Systematizing MT Evaluation, 2003)
We describe a set of evaluation techniques applied to domain tuning of bilingual lexicons for machine translation.Our overall objective is to translate a domain-specific document in a foreign language (in this case, Chinese) to En- glish. First, we perform an intrinsic evaluation of the effectiveness of our domain-tuning techniques by comparing our domain-tuned lexicon to a manually constructed domain-specific bilingual termlist. Our results indicate that we achieve 66% recall and 95% precision with respect to a human-derived gold standard. Next, an extrinsic evaluation demonstrates that our domain-tuned lexicon improves the Bleu scores 50% over a statistical system—with a smaller improvement when the system is trained on a uniformly-weighted dictionary.

Exploiting Functional Decomposition for Efficient Parallel Processing of Multiple Data Analysis Queries - Andrade,Henrique; Kurc,Tahsin; Sussman, Alan; Saltz,Joel (Parallel and Distributed Processing Symposium, International, 2003)
Reuse is a powerful method for increasing system performance. In this paper, we examine functional decomposition for improving data and computation reuse and, therefore, overall query execution performance in the context of data analysis applications. Additionally, we look at the performance effects of using various projection primitives that make it possible to transform intermediate results generated by a query so that they can be reused by a new query. A satellite data analysis application is used to experimentally show the performance benefits achieved using functional decomposition and projection primitives.

Extracting structural paraphrases from aligned monolingual corpora - Ibrahim,Ali; Katz,Boris; Jimmy Lin (Proceedings of the second international workshop on Paraphrasing - Volume 16, 2003)
We present an approach for automatically learning paraphrases from aligned monolingual corpora. Our algorithm works by generalizing the syntactic paths between corresponding anchors in aligned sentence pairs. Compared to previous work, structural paraphrases generated by our algorithm tend to be much longer on average, and are capable of capturing long-distance dependencies. In addition to a standalone evaluation of our paraphrases, we also describe a question answering application currently under development that could immensely benefit from automatically-learned structural paraphrases.

Forward secrecy in password-only key exchange protocols - Katz, Jonathan; Ostrovsky,Rafail; Yung,Moti (Proceedings of the 3rd international conference on Security in communication networks, 2003)
Password-only authenticated key exchange (PAKE) protocols are designed to be secure even when users choose short, easily-guessed passwords. Security requires, in particular, that the protocol cannot be broken by an off-line dictionary attack in which an adversary enumerates all possible passwords in an attempt to determine the correct one based on previously-viewed transcripts. Recently, provably-secure protocols for PAKE were given in the idealized random oracle/ideal cipher models [2,8,19] and in the standard model based on general assumptions [11] or the DDH assumption [14]. The latter protocol (the KOY protocol) is currently the only known practical solution based on standard assumptions. However, only a proof of basic security for this protocol has appeared. In the basic setting the adversary is assumed not to corrupt clients (thereby learning their passwords) or servers (thereby modifying the value of stored passwords). Simplifying and unifying previous work, we present a natural definition of security which incorporates the more challenging requirement of forward secrecy. We then demonstrate via an explicit attack that the KOY protocol as originally presented is not secure under this definition. This provides the first natural example showing that forward secrecy is a strictly stronger requirement for PAKE protocols. Finally, we present a slight modification of the KOY protocol which prevents the attack and - as the main technical contribution of this paper - rigorously prove that the modified protocol achieves forward secrecy.

A forward-secure public-key encryption scheme - Canetti,R.; Halevi,S.; Katz, Jonathan (Advances in Cryptology—Eurocrypt 2003, 2003)
Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an effort to mitigate the damage caused by exposure of secret data (e.g., keys) stored on such devices, the paradigm of forward security was introduced. In a forward-secure scheme, secret keys are updated at regular periods of time; furthermore, exposure of a secret key corresponding to a given time period does not enable an adversary to “break” the scheme (in the appropriate sense) for any prior time period. A number of constructions of forward-secure digital signature schemes, key-exchange protocols, and symmetric-key schemes are known.We present the first constructions of a (non-interactive) forward-secure public-key encryption scheme. Our main construction achieves security against chosen plaintext attacks under the decisional bilinear Diffie-Hellman assumption in the standard model. It is practical, and all complexity parameters grow at most logarithmically with the total number of time periods. The scheme can also be extended to achieve security against chosen ciphertext attacks.

Gait Analysis for Human Identification - Kale, A.; Cuntoor, N.; Yegnanarayana,B.; Rajagopalan, AN; Chellapa, Rama (Audio- and Video-Based Biometric Person AuthenticationAudio- and Video-Based Biometric Person Authentication, 2003)
Human gait is an attractive modality for recognizing people at a distance. In this paper we adopt an appearance-based approach to the problem of gait recognition. The width of the outer contour of the binarized silhouette of a walking person is chosen as the basic image feature. Different gait features are extracted from the width vector such as the dowsampled, smoothed width vectors, the velocity profile etc. and sequences of such temporally ordered feature vectors are used for representing a person’s gait. We use the dynamic time-warping (DTW) approach for matching so that non-linear time normalization may be used to deal with the naturally-occuring changes in walking speed. The performance of the proposed method is tested using different gait databases.

A generative probabilistic OCR model for NLP applications - Kolak,O.; Byrne,W.; Resnik, Philip (Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology-Volume 1, 2003)

The genome sequence of Bacillus anthracis Ames and comparison to closely related bacteria - Read,Timothy D.; Peterson,Scott N.; Tourasse,Nicolas; Baillie,Les W.; Paulsen,Ian T.; Nelson,Karen E.; Tettelin,Herv|[eacute]|; Fouts,Derrick E.; Eisen,Jonathan A.; Gill,Steven R.; Holtzapple,Erik K.; |[Oslash]|kstad,Ole Andreas; et al. (Nature, 2003)
Bacillus anthracis is an endospore-forming bacterium that causes inhalational anthrax1. Key virulence genes are found on plasmids (extra-chromosomal, circular, double-stranded DNA molecules) pXO1 (ref. 2) and pXO2 (ref. 3). To identify additional genes that might contribute to virulence, we analysed the complete sequence of the chromosome of B. anthracis Ames (about 5.23 megabases). We found several chromosomally encoded proteins that may contribute to pathogenicity—including haemolysins, phospholipases and iron acquisition functions—and identified numerous surface proteins that might be important targets for vaccines and drugs. Almost all these putative chromosomal virulence and surface proteins have homologues in Bacillus cereus, highlighting the similarity of B. anthracis to near-neighbours that are not associated with anthrax4. By performing a comparative genome hybridization of 19 B. cereus and Bacillus thuringiensis strains against a B. anthracis DNA microarray, we confirmed the general similarity of chromosomal genes among this group of close relatives. However, we found that the gene sequences of pXO1 and pXO2 were more variable between strains, suggesting plasmid mobility in the group. The complete sequence of B. anthracis is a step towards a better understanding of anthrax pathogenesis.

HCIL Technical Report Listing (1993-2002) - Ceaparu,I.; Druin, Allison; Guimbretiere,F.; Manipulation,D.; Shneiderman, Ben; Westerlurid,B.; Keogh,E.; Hochheiser,H.; Shrieidemian,B.; Shneidemiari,B.; others (The craft of information visualization: readings and reflections, 2003)

Helping users get started with visual interfaces: multi-layered interfaces, integrated initial guidance and video demonstrations - Kang,Hyunmo; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the 2003 annual national conference on Digital government research, 2003)
We are investigating new ways to help users learn to use public access interactive tools, in particular for the visual exploration of government statistics. Our work led to a series of interfaces using multi-layered design, a new help method called Integrated Initial Guidance, and video demonstrations. Multi-layer designs structure an interface so that a simpler interface is available for users to get started and more complex features are accessed as users move through the more advanced layers. Integrated Initial Guidance provides help within the working interface, right at the start of the application. Using the metaphor of "sticky notes" overlaid on top of the functional interface locates the main widgets, demonstrates their manipulation, and explains the resulting actions using preset activations of the interface.

Hierarchical dwarfs for the rollup cube - Sismanis,Yannis; Deligiannakis,Antonios; Kotidis,Yannis; Roussopoulos, Nick (Proceedings of the 6th ACM international workshop on Data warehousing and OLAP - DOLAP '03, 2003)

Immediate Usability: Kiosk design principles from the CHI 2001 Photo Library - Kules,Bill; Kang,Hyunmo; Plaisant, Catherine; Rose,Anne; Shneiderman, Ben (Technical Reports from UMIACS, 2003)
This paper describes a novel set of design principles and guidelines forensuring the immediate usability of public access systems. These principles and guidelines were formulated while developing PhotoFinder Kiosk, a community photo library. Attendees of CHI 2001 successfully used the tool to browse and annotate collections of photographs spanning 20 years of CHI and related conferences, producing a richly annotated photo history of the field of human-computer interaction. We used observations and log data to evaluate the tool and refine the guidelines. They provide specific guidance for practitioners, as well as a useful framework for additional research in public access interfaces. Keywords Photo collection, community photo library, group annotation, public access system, direct annotation, direct manipulation, drag-and-drop, immediate usability, zero-trial learning, walk-up-and-use, casual use. (UMIACS-TR-2001-71) (HCIL-TR-2001-23)
Keywords: Technical Report

Integrality ratio for group Steiner trees and directed steiner trees - Halperin,Eran; Kortsarz,Guy; Krauthgamer,Robert; Srinivasan, Aravind; Wang,Nan (Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, 2003)
We present an Ω(log2k) lower bound on the integrality ratio of the flow-based relaxation for the Group Steiner Tree problem, where k denotes the number of groups; this holds even for input graphs that are Hierarchically Well-Separated Trees, introduced by Bartal [Symp. Foundations of Computer Science, pp. 184--193, 1996], in which case this lower bound is tight. This relaxation appears to be the only one that have been studied for the problem, as well as for its generalization, the Directed Steiner Tree problem. For the latter problem, our results imply an Ω(log2n/(log logn)2) integrality ratio, where n is the number of vertices in the graph. For both problems, this is the first known lower bound on the integrality ratio that is superlogarithmic in the input size. We also show algorithmically that the integrality ratio for Group Steiner Tree is much better for certain families of instances, which helps pinpoint the types of instances that appear to be most difficult to approximate.

Intradomain Overlays: Architecture and Applications - Kommareddy,Christopher; Guven,Tuna; Bhattacharjee, Bobby; La,Richard; Shayman,Mark (Technical Reports from UMIACS, UMIACS-TR-2003-70, 2003)
We introduce an architecture for ``Intradomain Overlays'', where a subset of routers within a domain is augmented with a dedicated host. These strategically placed hosts form an overlay network, and we describe a number of applications for such overlays. These applications include efficient network monitoring, policy- and load-based packet re-routing, and network resource accounting. In this paper, we elaborate on the network monitoring application and describe a distributed protocol for monitoring routers within an AS which has been augmented with a few overlay nodes. The routers and other infrastructure are unaware of the overlay nodes, and the monitoring of individual elements is conducted using plain SNMP. We describe techniques for efficiently synthesizing and transporting the monitored SNMP data, and present results using trace data collected from an AS with 400+ routers. Our results show that the overlay-based monitoring reduces overheads by 2--4 orders of magnitude, and thus enables much finer grained monitoring and traffic engineering than is otherwise possible. (UMIACS-TR-2003-70)
Keywords: Technical Report

Intrusion-resilient public-key encryption - Dodis,Y.; Franklin,M.; Katz, Jonathan; Miyaji,A.; Yung,M. (Topics in Cryptology—CT-RSA 2003, 2003)
Exposure of secret keys seems to be inevitable, and may in practice represent the most likely point of failure in a cryptographic system. Recently, the notion of intrusion-resilience [17] (which extends both the notions of forward security [3], [5] and key insulation [11]) was proposed as a means of mitigating the harmful effects that key exposure can have. In this model, time is divided into distinct periods; the public key remains fixed throughout the lifetime of the protocol but the secret key is periodically updated. Secret information is stored by both a user and a base; the user performs all cryptographic operations during a given time period, while the base helps the user periodically update his key. Intrusion-resilient schemes remain secure in the face of multiple compromises of both the user and the base, as long as they are not both compromised simultaneously. Furthermore, in case the user and base are compromised simultaneously, prior time periods remain secure (as in forward-secure schemes). Intrusion-resilient signature schemes have been previously constructed [17], [15]. Here, we give the first construction of an intrusion-resilient publickey encryption scheme, based on the recently-constructed forwardsecure encryption scheme of [8]. We also consider generic transformations for securing intrusion-resilient encryption schemes against chosenciphertext attacks.

IrisNet: an architecture for internet-scale sensing services - Nath,Suman; Deshpande, Amol; Ke,Yan; Gibbons,Phillip B.; Karp,Brad; Seshan,Srinivasan (Proceedings of the 29th international conference on Very large data bases - Volume 29, 2003)
We demonstrate the design and an early prototype of IrisNet (Internet-scale Resource-Intensive Sensor Network services), a common, scalable networked infrastructure for deploying wide area sensing services. IrisNet is a potentially global network of smart sensing nodes, with webcams or other monitoring devices, and organizing nodes that provide the means to query recent and historical sensor-based data. IrisNet exploits the fact that high-volume sensor feeds are typically attached to devices with significant computing power and storage, and running a standard operating system. It uses aggressive filtering, smart query routing, and semantic caching to dramatically reduce network bandwidth utilization and improve query response times, as we demonstrate. Our demo will present two services built on Iris-Net, from two very different application domains. The first one, a parking space finder, utilizes webcams that monitor parking spaces to answer queries such as the availability of parking spaces near a user's destination. The second one, a distributed infrastructure monitor, uses measurement tools installed in individual nodes of a large distributed infrastructure to answer queries such as average network bandwidth usage of a set of nodes.

Lower bounds on the efficiency of encryption and digital signature schemes - Gennaro,Rosario; Gertner,Yael; Katz, Jonathan (Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 2003)
A central focus of modern cryptography is to investigate the weakest possible assumptions under which various cryptographic algorithms exist. Typically, a proof that a "weak" primitive (e.g., a one-way function) implies the existence of a "strong" algorithm (e.g., a private-key encryption scheme) proceeds by giving an explicit construction of the latter from the former. In addition to showing the existence of such a construction, an equally important research direction is to explore the efficiency of such constructions.Among the most fundamental cryptographic algorithms are digital signature schemes and schemes for public- or private-key encryption. Here, we show the first lower bounds on the efficiency of any encryption or signature construction based on black-box access to one-way or trapdoor one-way permutations. If S is the assumed security of the permutation π (i.e., no adversary of size S can invert π on a fraction larger than 1/S of its inputs), our results show that:Any public-key encryption scheme for m-bit messages must query π at least Ω(m log S) times.Any private-key encryption scheme for m-bit messages (with k-bit keys) must query π at least Ω(m-k/log S) times.Any signature verification algorithm for m-bit messages must query π at least Ω(m log S) times.Our bounds match known upper bounds for the case of encryption.We prove our results in an extension of the Impagliazzo-Rudich model. That is, we show that any black-box construction beating our lower bounds would imply the unconditional existence of a one-way function.
Keywords: black-box; digital signatures; encryption; lower bounds

Making miracles: Interactive translingual search for cebuano and hindi - He,D.; Oard, Douglas; Wang,J.; Luo,J.; Demner-Fushman,D.; Darwish,K.; Resnik, Philip; Khudanpur,S.; Nossal,M.; Subotin,M.; others (ACM Transactions on Asian Language Information Processing (TALIP), 2003)

Measuring the effects of internet path faults on reactive routing - Feamster, Nick; Andersen,David G.; Balakrishnan,Hari; Kaashoek,M. Frans (SIGMETRICS Perform. Eval. Rev., 2003)
Empirical evidence suggests that reactive routing systems improve resilience to Internet path failures. They detect and route around faulty paths based on measurements of path performance. This paper seeks to understand why and under what circumstances these techniques are effective.To do so, this paper correlates end-to-end active probing experiments, loss-triggered traceroutes of Internet paths, and BGP routing messages. These correlations shed light on three questions about Internet path failures: (1) Where do failures appear? (2) How long do they last? (3) How do they correlate with BGP routing instability?Data collected over 13 months from an Internet testbed of 31 topologically diverse hosts suggests that most path failures last less than fifteen minutes. Failures that appear in the network core correlate better with BGP instability than failures that appear close to end hosts. On average, most failures precede BGP messages by about four minutes, but there is often increased BGP traffic both before and after failures. Our findings suggest that reactive routing is most effective between hosts that have multiple connections to the Internet. The data set also suggests that passive observations of BGP routing messages could be used to predict about 20% of impending failures, allowing re-routing systems to react more quickly to failures.

MediaFinder: an interface for dynamic personal media management with semantic regions - Kang,Hyunmo; Shneiderman, Ben (CHI '03 extended abstracts on Human factors in computing systems, 2003)
Computer users deal with large amounts of personal media often face problems in managing and exploring it. This paper presents Semantic Regions, rectangular regions that enable users to specify their semantics or mental models, and the MediaFinder application, which uses Semantic Regions as the basis of a personal media management tool.
Keywords: dynamic queries; Fling-and-flock; Personal media management; spatial information organization; User interfaces

Modeling and Rendering of Points with Local Geometry - Kalaiah,Aravind; Varshney, Amitabh (IEEE Transactions on Visualization and Computer Graphics, 2003)
We present a novel rendering primitive that combines the modeling brevity of points with the rasterization efficiency of polygons. The surface is represented by a sampled collection of Differential Points (DP), each with embedded curvature information that captures the local differential geometry in the vicinity of that point. This is a more general point representation that, for the cost of a few additional bytes, packs much more information per point than the traditional point-based models. This information is used to efficiently render the surface as a collection of local geometries. To use the hardware acceleration, the DPs are quantized into $\big. 256\bigr.$ different types and each sampled point is approximated by the closest quantized DP and is rendered as a normal-mapped rectangle. The advantages to this representation are: 1) The surface can be represented more sparsely compared to other point primitives, 2) it achieves a robust hardware accelerated per-pixel shading—even with no connectivity information, and 3) it offers a novel point-based simplification technique that factors in the complexity of the local geometry. The number of primitives being equal, DPs produce a much better quality of rendering than a pure splat-based approach. Visual appearances being similar, DPs are about two times faster and require about 75 percent less disk space in comparison to splatting primitives.
Keywords: differential geometry; per-pixel shading.; point sample rendering; simplification

New approaches to help users get started with visual interfaces: multi-layered interfaces and integrated initial guidance - Kang,Hyunmo; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the 2003 annual national conference on Digital government research, 2003)
We are investigating new ways to help users learn to use public access interactive tools, in particular for the visual exploration of government statistics. Our work led to a series of interfaces using multi-layered design and a new help method called Integrated Initial Guidance. Multi-layer designs structure an interface so that a simpler interface is available for users to get started and more complex features are accessed as users move through the more advanced layers. Integrated Initial Guidance provides help within the working interface, right at the start of the application. Using the metaphor of "sticky notes" overlaid on top of the functional interface locates the main widgets, demonstrates their manipulation, and explains the resulting actions using preset animation of the interface. Usability testing with 12 participants led to refined designs and guidelines for the design of Integrated Initial Guidance interfaces.

The Opsis project: materialized views for data warehouses and the web - Roussopoulos, Nick; Kotidis,Y.; Labrinidis,A.; Sismanis,Y. (Advances in Informatics, 2003)

Parsing and Tagging of Bilingual Dictionaries - Ma,Huanfeng; Karagol-Ayan,Burcu; David Doermann; Oard, Douglas; Wang,Jianqiang (TALTraitement Automatique Des Langues, 2003)
Bilingual dictionaries hold great potential as a source of lexical resources for training and testing automated systems for optical character recognition, machine translation, and cross-language information retrieval. In this paper, we describe a system for extracting term lexicons from printed bilingual dictionaries. Our work was divided into three phases - dictionary segmentation, entry tagging, and generation. In segmentation, pages are divided into logical entries based on structural features learned from selected examples. The extracted entries are associated with functional labels and passed to a tagging module which associates linguistic labels with each word or phrase in the entry. The output of the system is a structure that represents the entries from the dictionary. We have used this approach to parse a variety of dictionaries with both Latin and non-Latin alphabets, and demonstrate the results of term lexicon generation for retrieval from a collection of French news stories using English queries.

Pathogenic Potential of Environmental Vibrio Cholerae Strains Carrying Genetic Variants of the Toxin-Coregulated Pilus Pathogenicity Island - Faruque,Shah M.; Kamruzzaman,M.; Meraj,Ismail M.; Chowdhury,Nityananda; Nair,G. Balakrish; Sack,R. Bradley; Rita R Colwell; Sack,David A. (Infection and ImmunityInfect. Immun., 2003)
The major virulence factors of toxigenic Vibrio cholerae are cholera toxin (CT), which is encoded by a lysogenic bacteriophage (CTXΦ), and toxin-coregulated pilus (TCP), an essential colonization factor which is also the receptor for CTXΦ. The genes for the biosynthesis of TCP are part of a larger genetic element known as the TCP pathogenicity island. To assess their pathogenic potential, we analyzed environmental strains of V. cholerae carrying genetic variants of the TCP pathogenicity island for colonization of infant mice, susceptibility to CTXΦ, and diarrheagenicity in adult rabbits. Analysis of 14 environmental strains, including 3 strains carrying a new allele of the tcpA gene, 9 strains carrying a new allele of the toxT gene, and 2 strains carrying conventional tcpA and toxT genes, showed that all strains colonized infant mice with various efficiencies in competition with a control El Tor biotype strain of V. cholerae O1. Five of the 14 strains were susceptible to CTXΦ, and these transductants produced CT and caused diarrhea in adult rabbits. These results suggested that the new alleles of the tcpA and toxT genes found in environmental strains of V. cholerae encode biologically active gene products. Detection of functional homologs of the TCP island genes in environmental strains may have implications for understanding the origin and evolution of virulence genes of V. cholerae.

The people in digital libraries: Multifaceted approaches to assessing needs and impact - Marchionini,G.; Plaisant, Catherine; Komlodi,A. (Digital library use: Social practice in design and evaluationDigital library use: Social practice in design and evaluation, 2003)

A perturbation method for evaluating background subtraction algorithms - Chalidabhongse,T.H.; Kim,K.; Harwood,D.; Davis, Larry S. (Joint IEEE International Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance (VS-PETS), 2003)
We introduce a performance evaluation methodology calledPerturbation Detection Rate (PDR) analysis, for measuring performance of background subtraction (BGS) algorithms. It has some advantages over the commonly used Receiver Operation Characteristics (ROC) analysis. Specifically, it does not require foreground targets or knowledge of fore- ground distributions. It measures the sensitivity of a BGS algorithm in detecting low contrast targets against back- ground as a function of contrast, also depending on how well the model captures mixed (moving) background events. We compare four algorithms having similarities and differ- ences. Three are in [2, 3, 5] while the fourth is recently de- veloped, called Codebook BGS. The latter algorithm quan- tizes sample background values at each pixel into code- books which represent a compressed form of background model for a long image sequence.

Planning in Answer Set Programming Using Ordered Task Decomposition - Dix,Jürgen; Kuter,Ugur; Nau, Dana S. (KI 2003: Advances in Artificial Intelligence, 2003)
In this paper we introduce a formalism for solving Hierarchical Task Network ( HTN ) Planning using Answer Set Programming ( ASP ). We consider the formulation of HTN planning as described in the SHOP planning system and define a systematic translation method from SHOP ’s representation of the planning problem into logic programs with negation. We show that our translation is sound and complete : answer sets of the logic program obtained by our translation correspond exactly to the solutions of the planning problem. We compare our method to (1) similar approaches based on non- HTN planning and (2) SHOP , a dedicated planning system. We show that our approach outperforms non- HTN methods and that its performance is better with ASP systems that allow for nonground programs than with ASP systems that require ground programs.
Keywords: Computer science

Probabilistic recognition of human faces from video - Zhou,Shaohua; Krueger,Volker; Chellapa, Rama (Computer Vision and Image Understanding, 2003)
Recognition of human faces using a gallery of still or video images and a probe set of videos is systematically investigated using a probabilistic framework. In still-to-video recognition, where the gallery consists of still images, a time series state space model is proposed to fuse temporal information in a probe video, which simultaneously characterizes the kinematics and identity using a motion vector and an identity variable, respectively. The joint posterior distribution of the motion vector and the identity variable is estimated at each time instant and then propagated to the next time instant. Marginalization over the motion vector yields a robust estimate of the posterior distribution of the identity variable. A computationally efficient sequential importance sampling (SIS) algorithm is developed to estimate the posterior distribution. Empirical results demonstrate that, due to the propagation of the identity variable over time, a degeneracy in posterior probability of the identity variable is achieved to give improved recognition. The gallery is generalized to videos in order to realize video-to-video recognition. An exemplar-based learning strategy is adopted to automatically select video representatives from the gallery, serving as mixture centers in an updated likelihood measure. The SIS algorithm is applied to approximate the posterior distribution of the motion vector, the identity variable, and the exemplar index, whose marginal distribution of the identity variable produces the recognition result. The model formulation is very general and it allows a variety of image representations and transformations. Experimental results using images/videos collected at UMD, NIST/USF, and CMU with pose/illumination variations illustrate the effectiveness of this approach for both still-to-video and video-to-video scenarios with appropriate model choices.
Keywords: Exemplar-based learning; face recognition; sequential importance sampling; Still-to-video; Time series state space model; Video-to-video

Probabilistically survivable mass - Kraus,S.; V.S. Subrahmanian; Tas,N. C (INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2003)
Multiagent systems (MAS) can "go down" for alarge number of reasons, ranging from system mal- functions and power failures to malicious attacks. The placement of agents on nodes is called a de- ployment of the MAS. We develop a probabilis- tic model of survivability of a deployed MAS and provide two algorithms to compute the probability of survival of a deployed MAS. Our probabilistic model docs not make independence assumptions though such assumptions can be added if so de- sired. An optimal deployment of a MAS is one that maximizes its survival probability. We provide a mathematical answerto this question, an algorithm that computes an exact solution to this problem, as well as several algorithms that quickly compute approximate solutions to the problem. We have implemented our algorithms - our implementation demonstrates that computing deployments can be done scalably.

Question answering from the web using knowledge annotation and knowledge mining techniques - Jimmy Lin; Katz,Boris (Proceedings of the twelfth international conference on Information and knowledge management, 2003)
We present a strategy for answering fact-based natural language questions that is guided by a characterization of real-world user queries. Our approach, implemented in a system called Aranea, extracts answers from the Web using two different techniques: knowledge annotation and knowledge mining. Knowledge annotation is an approach to answering large classes of frequently occurring questions by utilizing semi\-structured and structured Web sources. Knowledge mining is a statistical approach that leverages massive amounts of Web data to overcome many natural language processing challenges. We have integrated these two different paradigms into a question answering system capable of providing users with concise answers that directly address their information needs.
Keywords: data-redundancy; semistructured data

Question answering techniques for the World Wide Web - Jimmy Lin; Katz,B. (Tutorial presentation at The 11th Conference of the European Chapter of the Association of Computational Linguistics (EACL-2003), 2003)
Question answering systems have become increasingly popular because they deliverusers short, succinct answers instead of overloading them with a large number of irrelevant documents. The vast amount of information readily available on the World Wide Web presents new opportunities and challenges for question answering. In order for question answering systems to benefit from this vast store of useful knowledge, they must cope with large volumes of useless data. Many characteristics of the World Wide Web distinguish Web-based question answering from question answering on closed corpora such as newspaper texts. The Web is vastly larger in size and boasts incredible “data redundancy,” which renders it amenable to statistical techniques for answer extraction. A data-driven approach can yield high levels of performance and nicely complements traditional question answering techniques driven by information extraction. In addition to enormous amounts of unstructured text, the Web also contains pockets of structured and semistructured knowledge that can serve as a valuable resource for question answering. By organizing these resources and annotating them with natural language, we can successfully incorporate Web knowledge into question answering systems. This tutorial surveys recent Web-based question answering technology, focusing on two separate paradigms: knowledge mining using statistical tools and knowledge annotation using database concepts. Both approaches can employ a wide spectrum of techniques ranging in linguistic sophistication from simple “bag-of-words” treatments to full syntactic parsing.

Reduction of Cholera in Bangladeshi Villages by Simple Filtration - Rita R Colwell; Huq,Anwar; M. Sirajul Islam; K. M. A. Aziz; Yunus,M.; N. Huda Khan; A. Mahmud; Sack,R. Bradley; Nair,G. B.; J. Chakraborty; Sack,David A.; E. Russek-Cohen (Proceedings of the National Academy of SciencesPNAS, 2003)
Based on results of ecological studies demonstrating that Vibrio cholerae, the etiological agent of epidemic cholera, is commensal to zooplankton, notably copepods, a simple filtration procedure was developed whereby zooplankton, most phytoplankton, and particulates >20 μm were removed from water before use. Effective deployment of this filtration procedure, from September 1999 through July 2002 in 65 villages of rural Bangladesh, of which the total population for the entire study comprised ≈133,000 individuals, yielded a 48% reduction in cholera (P < 0.005) compared with the control.

Robust Face Recognition in the Presence of Clutter - Rajagopalan, AN; Chellapa, Rama; Koterba,Nathan (Audio- and Video-Based Biometric Person AuthenticationAudio- and Video-Based Biometric Person Authentication, 2003)
We propose a new method within the framework of principal component analysis to robustly recognize faces in the presence of clutter. The traditional eigenface recognition method performs poorly when confronted with the more general task of recognizing faces appearing against a background. It misses faces completely or throws up many false alarms. We argue in favor of learning the distribution of background patterns and show how this can be done for a given test image. An eigenbackground space is constructed and this space in conjunction with the eigenface space is used to impart robustness in the presence of background. A suitable classifier is derived to distinguish non-face patterns from faces. When tested on real images, the performance of the proposed method is found to be quite good.

Round efficiency of multi-party computation with a dishonest majority - Katz, Jonathan; Ostrovsky,Rafail; Smith,Adam (Proceedings of the 22nd international conference on Theory and applications of cryptographic techniques, 2003)
We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some functionality and up to n - 1 of these players may be arbitrarily malicious. Previous protocols for this setting (when a broadcast channel is available) require O(n) rounds. We present two protocols with improved round complexity: The first assumes only the existence of trapdoor permutations and dense cryptosystems, and achieves round complexity O(log n) based on a proof scheduling technique of Chor and Rabin [13]; the second requires a stronger hardness assumption (along with the non-black-box techniques of Barak [2]) and achieves O(1) round complexity.

Scalable protocols for authenticated group key exchange - Katz, Jonathan; Yung,M. (Advances in Cryptology-CRYPTO 2003, 2003)
We consider the fundamental problem of authenticated group key exchange among n parties within a larger and insecure public network. A number of solutions to this problem have been proposed; however, all provably-secure solutions thus far are not scalable and, in particular, require n rounds. Our main contribution is the first scalable protocol for this problem along with a rigorous proof of security in the standard model under the DDH assumption; our protocol uses a constant number of rounds and requires only O(1) modular exponentiations per user (for key derivation). Toward this goal and of independent interest, we first present a scalable compiler that transforms any group key-exchange protocol secure against a passive eavesdropper to an authenticated protocol which is secure against an active adversary who controls all communication in the network. This compiler adds only one round and O(1) communication (per user) to the original scheme. We then prove secure — against a passive adversary — a variant of the two-round group key-exchange protocol of Burmester and Desmedt. Applying our compiler to this protocol results in a provably-secure three-round protocol for authenticated group key exchange which also achieves forward secrecy.

A search engine for 3D models - Funkhouser,Thomas; Min,Patrick; Kazhdan,Michael; Chen,Joyce; Halderman,Alex; Dobkin,David; Jacobs, David W. (ACM Trans. Graph., 2003)
As the number of 3D models available on the Web grows, there is an increasing need for a search engine to help people find them. Unfortunately, traditional text-based search techniques are not always effective for 3D data. In this article, we investigate new shape-based search methods. The key challenges are to develop query methods simple enough for novice users and matching algorithms robust enough to work for arbitrary polygonal models. We present a Web-based search engine system that supports queries based on 3D sketches, 2D sketches, 3D models, and/or text keywords. For the shape-based queries, we have developed a new matching algorithm that uses spherical harmonics to compute discriminating similarity measures without requiring repair of model degeneracies or alignment of orientations. It provides 46 to 245% better performance than related shape-matching methods during precision--recall experiments, and it is fast enough to return query results from a repository of 20,000 models in under a second. The net result is a growing interactive index of 3D models available on the Web (i.e., a Google for 3D models).
Keywords: Search engine; shape matching; shape representation; shape retrieval

Searching large collections of recorded speech: A preliminary study - Kim,J.; Oard, Douglas; Soergel,D. (Proceedings of the American Society for Information Science and Technology, 2003)

Secure agents - Bonatti,P. A; Kraus,S.; V.S. Subrahmanian (Annals of Mathematics and Artificial Intelligence, 2003)
With the rapid proliferation of software agents, there comes an increased need for agents to ensure that they do not provide data and/or services to unauthorized users. We first develop an abstract definition of what it means for an agent to preserve data/action security. Most often, this requires an agent to have knowledge that is impossible to acquire – hence, we then develop approximate security checks that take into account, the fact that an agent usually has incomplete/approximate beliefs about other agents. We develop two types of security checks – static ones that can be checked prior to deploying the agent, and dynamic ones that are executed at run time. We prove that a number of these problems are undecidable, but under certain conditions, they are decidable and (our definition of) security can be guaranteed. Finally, we propose a language within which the developer of an agent can specify her security needs, and present provably correct algorithms for static/dynamic security verification.

A secure PLAN - Hicks, Michael W.; Keromytis,A. D; Smith,J. M (IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2003)
Active networks, being programmable, promise greater flexibility than current networks. Programmability, however, may introduce safety and security risks. This correspondence describes the design and implementation of a security architecture for the active network PLANet. Security is obtained with a two-level architecture that combines a functionally restricted packet language, PLAN, with an environment of general-purpose service routines governed by trust management. In particular, a technique is used which expands or contracts a packet's service environment based on its level of privilege, termed namespace-based security. The design and implementation of an active-network firewall and virtual private network is used as an application of the security architecture. Measurements of the system show that the addition of the firewall imposes an approximately 34% latency overhead and as little as a 6.7% space overhead to incoming packets.
Keywords: active networks; active-network firewall; Authentication; Authorization; Contracts; cryptography; Environmental management; Extraterrestrial measurements; functionally restricted packet language; general-purpose service routines; Internet; latency overhead; namespace-based security; packet switching; PLANet; Planets; privilege level; programmable networks; Safety; safety risks; secure PLAN; security of data; security risks; trust management; two-level architecture; virtual private network; Virtual private networks; Web and internet services

Seeing the World Through Image Libraries - North,C.; Shneiderman, Ben; Plaisant, Catherine; Kang,H.; Bederson, Benjamin B. (The craft of information visualization: readings and reflectionsThe craft of information visualization: readings and reflections, 2003)

SHOP2: An HTN planning system - Nau, Dana S.; Au,T. C; Ilghami,O.; Kuter,U.; Murdock,J. W.; Wu,D.; Yaman,F. (J. Artif. Intell. Res. (JAIR), 2003)
The SHOP2 planning system received one of the awards for distinguished performance in the 2002 International Planning Competition. This paper describes the features of SHOP2 which enabled it to excel in the competition, especially those aspects of SHOP2 that deal with temporal and metric planning domains.

Starting an intergenerational technology design team: a case study - Knudtzon,Kendra; Druin, Allison; Kaplan,Nancy; Summers,Kathryn; Chisik,Yoram; Kulkarni,Rahul; Moulthrop,Stuart; Weeks,Holly; Bederson, Benjamin B. (Proceedings of the 2003 conference on Interaction design and children, 2003)
This paper presents a case study of the first three months of a new intergenerational design team with children ages 10--13. It discusses the research and design methods used for working with children of this age group, the challenges and opportunities of starting a new team, and the lessons learned.
Keywords: children; cooperative inquiry; design methods; educational applications; intergenerational design teams; participatory design