COMPUTATIONAL BIOLOGY - Leparc,GG; Mitra,RD; Vardhanabhuti,S.; Wang,J.; Hannenhalli, Sridhar; Smit,S.; Widmann,J.; Knight,R.; Wu,S.; Zhang,Y.; others (Nucleic acids research, 2007)

Computing most probable worlds of action probabilistic logic programs: scalable estimation for 10^30,000 worlds - Khuller, Samir; Martinez,M.; Nau, Dana S.; Sliva,Amy; Simari,Gerardo; Subrahmanian,V. (Annals of Mathematics and Artificial Intelligence, 2007)
The semantics of probabilistic logic programs (PLPs) is usually given through a possible worlds semantics. We propose a variant of PLPs called action probabilistic logic programs or -programs that use a two-sorted alphabet to describe the conditions under which certain real-world entities take certain actions. In such applications, worlds correspond to sets of actions these entities might take. Thus, there is a need to find the most probable world (MPW) for -programs. In contrast, past work on PLPs has primarily focused on the problem of entailment. This paper quickly presents the syntax and semantics of -programs and then shows a naive algorithm to solve the MPW problem using the linear program formulation commonly used for PLPs. As such linear programs have an exponential number of variables, we present two important new algorithms, called and to solve the MPW problem exactly. Both these algorithms can significantly reduce the number of variables in the linear programs. Subsequently, we present a “binary” algorithm that applies a binary search style heuristic in conjunction with the Naive, and algorithms to quickly find worlds that may not be “most probable.” We experimentally evaluate these algorithms both for accuracy (how much worse is the solution found by these heuristics in comparison to the exact solution) and for scalability (how long does it take to compute). We show that the results of are very accurate and also very fast: more than 10 30,000 worlds can be handled in a few minutes. Subsequently, we develop parallel versions of these algorithms and show that they provide further speedups.
Keywords: Computer science

Concept disambiguation for improved subject access using multiple knowledge sources - Sidhu,T.; Klavans,J.; Jimmy Lin (Proceedings of the Workshop on Language Technology for Cultural Heritage Data (LaTeCH 2007), 2007)
We address the problem of mining text forrelevant image metadata. Our work is situ- ated in the art and architecture domain, where highly specialized technical vocabu- lary presents challenges for NLP tech- niques. To extract high quality metadata, the problem of word sense disambiguation must be addressed in order to avoid leading the searcher to the wrong image as a result of ambiguous—and thus faulty—meta- data. In this paper, we present a disam- biguation algorithm that attempts to select the correct sense of nouns in textual de- scriptions of art objects, with respect to a rich domain-specific thesaurus, the Art and Architecture Thesaurus (AAT). We per- formed a series of intrinsic evaluations us- ing a data set of 600 subject terms ex- tracted from an online National Gallery of Art (NGA) collection of images and text. Our results showed that the use of external knowledge sources shows an improvement over a baseline.

Concurrently-secure blind signatures without random oracles or setup assumptions - Hazay,C.; Katz, Jonathan; Koo,C. Y; Lindell,Y. (Theory of Cryptography, 2007)
We show a new protocol for blind signatures in which security is preserved even under arbitrarily-many concurrent executions. The protocol can be based on standard cryptographic assumptions and is the first to be proven secure in a concurrent setting (under any assumptions) without random oracles or a trusted setup assumption such as a common reference string. Along the way, we also introduce new definitions of security for blind signature schemes.This research was supported by US-Israel Binational Science Foundation grant #2004240. Work of the first author was also supported by an Eshkol fellowship from the Israel Ministry of Science and Technology. Work of the second author was also supported by NSF CAREER award #0447075.

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

Creating a Robust Desktop Grid using Peer-to-Peer Services - Kim,J.-S.; Nam,B.; Marsh,M.; Keleher,P.; Bhattacharjee, Bobby; Richardson,D.; Wellnitz,D.; Sussman, Alan (Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International, 2007)
The goal of the work described in this paper is to design and build a scalable infrastructure for executing grid applications on a widely distributed set of resources. Such grid infrastructure must be decentralized, robust, highly available, and scalable, while efficiently mapping application instances to available resources in the system. However, current desktop grid computing platforms are typically based on a client-server architecture, which has inherent shortcomings with respect to robustness, reliability and scalability. Fortunately, these problems can be addressed through the capabilities promised by new techniques and approaches in peer-to-peer (P2P) systems. By employing P2P services, our system allows users to submit jobs to be run in the system and to run jobs submitted by other users on any resources available in the system, essentially allowing a group of users to form an ad-hoc set of shared resources. The initial target application areas for the desktop grid system are in astronomy and space science simulation and data analysis.
Keywords: allocation; architecture; load; balancing; peer-to-peer; client-server; computing; peer-to-peer; computing; resource; desktop; grid; scalable; infrastructure; client-server; system; robust; systems; grid

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

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

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

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

Efficient cryptographic protocols based on the hardness of learning parity with noise - Katz, Jonathan (Proceedings of the 11th IMA international conference on Cryptography and coding, 2007)
The problem of learning parity with noise (The LPN problem), which can be re-cast as the problem of decoding a random linear code, has attracted attention recently as a possible tool for developing highly-efficient cryptographic primitives suitable for resource-constrained devices such as RFID tags. This article surveys recent work aimed at designing efficient authentication protocols based on the conjectured hardness of this problem.

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

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

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

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

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

Exploiting approximate transitivity of trust - Morselli,Ruggero; Bhattacharjee, Bobby; Katz, Jonathan; Marsh,Michael (Broadband Communications, Networks and Systems, 2007. BROADNETS 2007. Fourth International Conference on, 2007)
Social networks, of which webs of trust are a particular type, have been shown to be effective ways of moving information with minimal external configuration, setup, or management. For applications requiring information assurance, a web of trust is an appealing system architecture, since trust is an inherent component of both the network design and assurance. The trust in a typical web of trust is not transitive, however, making the construction of an application with strong assurance difficult or impossible. Instead, in this paper we examine a notion of weak assurance that can be provided by a web of trust, and might be #x201C;good enough #x201D; for many applications. As a motivating example, and to provide a more concrete basis for exposition, we present KeyChains, a peer-to-peer system that operates over a distributed web of trust to provide fully decentralized public key publishing and retrieval. In addition to weak assurance guarantees, KeyChains also provides an audit trail for public keys retrieved. Our analysis and simulations show that the resulting system is both efficient and secure.

A fast algorithm for learning large scale preference relations - Raykar,V.C.; Duraiswami, Ramani; Krishnapuram,B. (Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics (AISTATS 2007), 2007)
We consider the problem of learning the rank-ing function that maximizes a generalization of the Wilcoxon-Mann-Whitney statistic on training data. Relying on an ϵ-exact approx- imation for the error-function, we reduce the computational complexity of each iteration of a conjugate gradient algorithm for learn- ing ranking functions from O(m2), to O(m), where m is the size of the training data. Experiments on public benchmarks for ordi- nal regression and collaborative filtering show that the proposed algorithm is as accurate as the best available methods in terms of rank- ing accuracy, when trained on the same data, and is several orders of magnitude faster.

Fast weighted summation of erfc functions - Raykar,Vikas C.; Duraiswami, Ramani; Krishnapuram,B. (Technical Reports from UMIACS UMIACS-TR-2007-03, 2007)
Abstract: Direct computation of the weighted sum of N complementaryerror functions at M points scales as O(MN). We present a O(M + N) $ε$-exact approximation algorithm to compute the same.
Keywords: Technical Report

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

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

A forward-secure public-key encryption scheme - Canetti,R.; Halevi,S.; Katz, Jonathan (Journal of Cryptology, 2007)
Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious concern. Forward security allows one to mitigate the damage caused by exposure of secret keys. In a forward-secure scheme, secret keys are updated at regular periods of time; exposure of the 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. We present the first constructions of (non-interactive) forward-secure public-key encryption schemes. Our main construction achieves security against chosen-plaintext attacks in the standard model, and all parameters of the scheme are poly-logarithmic in the total number of time periods. Some variants and extensions of this scheme are also given. We also introduce the notion of binary tree encryption and construct a binary tree encryption scheme in the standard model. Our construction implies the first hierarchical identity-based encryption scheme in the standard model. (The notion of security we achieve, however, is slightly weaker than that achieved by some previous constructions in the random oracle model.)

GATA and Nkx factors synergistically regulate tissue-specific gene expression and development in vivo - Zhang,Yuzhen; Rath,Nibedita; Hannenhalli, Sridhar; Wang,Zhishan; Cappola,Thomas; Kimura,Shioko; Atochina-Vasserman,Elena; Lu,Min Min; Beers,Michael F.; Morrisey,Edward E. (Development, 2007)
In vitro studies have suggested that members of the GATA and Nkx transcription factor families physically interact, and synergistically activate pulmonary epithelial- and cardiac-gene promoters. However, the relevance of this synergy has not been demonstrated in vivo. We show that Gata6-Titf1 (Gata6-Nkx2.1) double heterozygous (G6-Nkx DH) embryos and mice have severe defects in pulmonary epithelial differentiation and distal airway development, as well as reduced phospholipid production. The defects in G6-Nkx DH embryos and mice are similar to those observed in human neonates with respiratory distress syndromes, including bronchopulmonary dysplasia, and differential gene expression analysis reveals essential developmental pathways requiring synergistic regulation by both Gata6 and Titf1 (Nkx2.1). These studies indicate that Gata6 and Nkx2.1 act in a synergistic manner to direct pulmonary epithelial differentiation and development in vivo, providing direct evidence that interactions between these two transcription factor families are crucial for the development of the tissues in which they are co-expressed.

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

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

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

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

Guest Editorial: Special Issue on Human Detection and Recognition - Bhanu, B.; Ratha,N. K; Kumar, V.; Chellapa, Rama; Bigun, J. (Information Forensics and Security, IEEE Transactions on, 2007)
The 12 regular papers and three correspondences in this special issue focus on human detection and recognition. The papers represent gait, face (3-D, 2-D, video), iris, palmprint, cardiac sounds, and vulnerability of biometrics and protection against the spoof attacks.

Holding the Internet Accountable - Andersen,David; Balakrishnan,Hari; Feamster, Nick; Koponen,Teemu; Moon,Daekyong; Shenker,Scott (Proc. 6th ACM Workshop on Hot Topics in Networks (Hotnets-VI), 2007)
Today’s IP network layer provides little to no protection against misconfiguration or malice. Despite some progress in improving the robustness and security of the IP layer, misconfigurations and attacks still occur frequently. We show how a network layer that provides accountability, i.e., the ability to associate each action with the responsible entity, provides a firm foundation for defenses against misconfiguration and malice. We present the design of a network layer that incorporates accountability called AIP (Accountable Internet Protocol) and show how its features—notably, its use of self-certifying addresses— can improve both source accountability (the ability to trace actions to a particular end host and stop that host from misbehaving) and control-plane accountability (the ability to pinpoint and prevent attacks on routing).

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

Human Identification using Gait and Face - Chellapa, Rama; Roy-Chowdhury, A.K.; Kale, A. (Computer Vision and Pattern Recognition, 2007. CVPR '07. IEEE Conference on, 2007)
In general the visual-hull approach for performing integrated face and gait recognition requires at least two cameras. In this paper we present experimental results for fusion of face and gait for the single camera case. We considered the NIST database which contains outdoor face and gait data for 30 subjects. In the NIST database, subjects walk along an inverted Sigma pattern. In (A. Kale, et al., 2003), we presented a view-invariant gait recognition algorithm for the single camera case along with some experimental evaluations. In this chapter we present the results of our view-invariant gait recognition algorithm in (A. Kale, et al., 2003) on the NIST database. The algorithm is based on the planar approximation of the person which is valid when the person walks far away from the camera. In (S. Zhou et al., 2003), an algorithm for probabilistic recognition of human faces from video was proposed and the results were demonstrated on the NIST database. Details of these methods can be found in the respective papers. We give an outline of the fusion strategy here.
Keywords: algorithm; visual-hull; analysis; image; approach; cameras; face; approximation; probabilistic; database; camera; face; databases; fusion; face; fusion; human; fusion; probability; video; Gait; identification; planar; NIST; processing; visual; recognition; recognition; gait; recognition; view-invariant; signal

Information-Aware 2^ n-Tree for Efficient Out-of-Core Indexing of Very Large Multidimensional Volumetric Data - Kim,J.; JaJa, Joseph F. (Scientific and Statistical Database Management, 2007. SSBDM'07. 19th International Conference on, 2007)

Large-scale byzantine fault tolerance: safe but not always live - Rodrigues,Rodrigo; Kouznetsov,Petr; Bhattacharjee, Bobby (Proceedings of the 3rd workshop on on Hot Topics in System Dependability, 2007)
The overall correctness of large-scale systems composed of many groups of replicas executing BFT protocols scales poorly with the number of groups. This is because the probability of at least one group being compromised (more than 1/3 faulty replicas) increases rapidly as the number of groups increases. In this paper we address this problem with a simple modification to Castro and Liskov's BFT replication that allows for arbitrary choice of n (number of replicas) and f (failure threshold). The price to pay is a more restrictive liveness requirement, and we present the design of a large-scale BFT replicated system that obviates this problem.

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

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

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

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

New records of phytoplankton for Bangladesh. 3. Volvocales - Khondker,Moniruzzaman; Bhuiyan,Rauf Ahmed; Yeasmin,Jenat; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Bangladesh Journal of Plant Taxonomy, 2007)
This study presents 21 species of Chlamydomonas, four species of Carteria, two species of each of Nephroselmis, Pyramidomonas and Scherffelia, and Collodictyon triciliatum, Polytoma minus, Tetrachloridium ? allorgei and Tetraselmis cordiformis. These species have been reported from some ponds of Mathbaria of Pirojpur and Bakerganj of Barisal districts in Bangladesh.

New records of phytoplankton for Bangladesh. 4. Chlorococcales - Khondker,Moniruzzaman; Bhuiyan,Rauf Ahmed; Yeasim,Jenat; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Bangladesh Journal of Plant Taxonomy, 2007)
This study presents three species from each of Schroederia, Monoraphidium and Ankistrodesmus, two species and one variety of Dictyosphaerium, two varieties of Pediastrum, and Tetraedron arthrodesmiforme var. contorta, Chlorotetraedron polymorphum, Myrmecia aquatica, Oocystis tainoensis, Nephrocytium spirale, Kirchneriella irregularis, Coelastrum indicum and Scenedesmus similagineus. These taxa have been reported from some ponds of Mathbaria of Pirojpur and Bakerganj of Barisal Districts in Bangladesh.

Oblivious routing on node-capacitated and directed graphs - Hajiaghayi, Mohammad T.; Kleinberg,R. D; R\äcke,H.; Leighton,T. (ACM Transactions on Algorithms (TALG), 2007)

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

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

Photometric stereo with general, unknown lighting - Basri,R.; Jacobs, David W.; Kemelmacher,I. (International Journal of Computer Vision, 2007)
Work on photometric stereo has shown how to recover the shape and reflectance properties of an object using multiple images taken with a fixed viewpoint and variable lighting conditions. This work has primarily relied on known lighting conditions or the presence of a single point source of light in each image. In this paper we show how to perform photometric stereo assuming that all lights in a scene are distant from the object but otherwise unconstrained. Lighting in each image may be an unknown and may include arbitrary combination of diffuse, point and extended sources. Our work is based on recent results showing that for Lambertian objects, general lighting conditions can be represented using low order spherical harmonics. Using this representation we can recover shape by performing a simple optimization in a low-dimensional space. We also analyze the shape ambiguities that arise in such a representation. We demonstrate our method by reconstructing the shape of objects from images obtained under a variety of lightings. We further compare the reconstructed shapes against shapes obtained with a laser scanner.

Principles for designing data-/compute-intensive distributed applications and middleware systems for heterogeneous environments - Kim,Jik-Soo; Andrade,Henrique; Sussman, Alan (Journal of Parallel and Distributed Computing, 2007)
The nature of distributed systems is constantly and steadily changing as the hardware and software landscape evolves. Porting applications and adapting existing middleware systems to ever changing computational platforms has become increasingly complex and expensive. Therefore, the design of applications, as well as the design of next generation middleware systems, must follow a set of guiding principles in order to insure long-term “survivability” without costly re-engineering. From our practical experience, the key determinants to success in this endeavor are adherence to the following principles: (1) Design for change; (2) Provide for storage subsystem I/O coordination; (3) Employ workload partitioning and load balancing techniques; (4) Employ caching; (5) Schedule the workload; and (6) Understand the workload. In order to support these principles, we have collected extensive experimental results comparing three middleware systems targeted at data- and compute-intensive applications implemented by our research group during the course of the last decade, on a single data- and compute-intensive application. The main contribution of this work is the analysis of a level playing field, where we discuss and quantify how adherence to these guiding principles impacts overall system throughput and response time.
Keywords: Computational science applications; Data-/compute-intensive applications; Heterogeneous environments; Middleware systems

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

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

Randomized Algorithms and Probabilistic Analysis in Wireless Networking - Srinivasan, Aravind (Stochastic Algorithms: Foundations and ApplicationsStochastic Algorithms: Foundations and Applications, 2007)
Devices connected wirelessly, in various forms including computers, hand-held devices, ad hoc networks, and embedded systems, are expected to become ubiquitous all around us. Wireless networks pose interesting new challenges, some of which do not arise in standard (wired) networks. This survey discusses some key probabilistic notions – both randomized algorithms and probabilistic analysis – in wireless networking.

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

Review of "Probability and Computing: Randomized Algorithms and Probabilitic Analysis by Michael Mitzenmacher and Eli Upfal", Cambridge University Press, 2005 - Katz, Jonathan (SIGACT News, 2007)

Robust Routing with Unknown Traffic Matrices - Tabatabaee,V.; Kashyap,A.; Bhattacharjee, Bobby; La,R.J.; Shayman,M.A. (INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, 2007)
In this paper, we present an algorithm for intra-domain traffic engineering. We assume that the traffic matrix, which specifies traffic load between every source-destination pair in the network, is unknown and varies with time, but that always lies inside an explicitly defined region. Our goal is to compute a fixed robust routing with best worst case performance for all traffic matrices inside the bounding region. We formulate this problem as a semi-infinite programming problem. Then, we focus on a special case with practical merits, where (1) the traffic matrix region is assumed to be a polytope specified by a finite set of linear inequalities, and (2) our objective is to find the routing that minimizes the maximum link utilization. Under these assumptions, the problem can be formulated as a polynomial size linear programming (LP) problem with finite number of constraints. We further consider two specific set of constraints for the traffic matrix region. The first set is based on the hose model and limits the total traffic rate of network point of presence (PoP) nodes. The second set is based on the pipe model and limits the traffic between source-destination pairs. We study the effectiveness of each set of constraints using extensive simulations.
Keywords: engineering; linear; inequalities; maximum; intradomain; linear; link; matrices; linear; matrix; network; nodes; polynomial; of; point; presence; problem; traffic; Programming; programming; semiinfinite; programming; telecommunication; region; unknown; routing; telecommunication; size; traffic; traffic; utilization; network

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

Round-efficient secure computation in point-to-point networks - Katz, Jonathan; Koo,C. Y (Advances in Cryptology-EUROCRYPT 2007, 2007)
Essentially all work studying the round complexity of secure computation assume broadcast as an atomic primitive. Protocols constructed under this assumption tend to have very poor round complexity when compiled for a point-to-point network due to the high overhead of emulating each invocation of broadcast. This problem is compounded when broadcast is used in more than one round of the original protocol due to the complexity of handling sequential composition (when using round-efficient emulation of broadcast).We argue that if the goal is to optimize round complexity in point-to-point networks, then it is preferable to design protocols — assuming a broadcast channel — minimizing the number of rounds in which broadcast is used rather than minimizing the total number of rounds. With this in mind, we present protocols for secure computation in a number of settings that use only a single round of broadcast. In all cases, we achieve optimal security threshold for adaptive adversaries, and obtain protocols whose round complexity (in a point-to-point network) improves on prior work.

Scalable protocols for authenticated group key exchange - Katz, Jonathan; Yung,M. (Journal of Cryptology, 2007)
We consider the problem of authenticated group key exchange among n parties communicating over an insecure public network. A number of solutions to this problem have been proposed; however, all prior provably secure solutions do not scale well and, in particular, require O(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) "full" modular exponentiations per user. Toward this goal (and adapting work of Bellare, Canetti, and Krawczyk), we first present an efficient 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.

Secure lookup without (constrained) flooding - Bhattacharjee, Bobby; Rodrigues,R.; Kouznetsov,P. (WRAITS 2007, 2007)

System for 802.11 connectivity at high speed - Frangiadakis,Nikolaos; Kuklov,Danila; Roussopoulos, Nick (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2007)
Measurements and ongoing research have shown that WLANconnection for moving vehicles is feasible. However none of the previous work suggests a solution addressing a complete array of the challenges in vehicular WLAN communications. To amend this we designed a system that provides wireless connection roaming at high velocities transparent to user level applications, and does not impose additional requirements to existing infrastructures. It offers simple deployment, security, and scalability. It remains efficient under intermittent connectivity conditions and supports heterogeneous network mediums for increased robustness.
Keywords: Technical Report

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

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

Thumbspace: Generalized one-handed input for touchscreen-based mobile devices - Karlson,A.K.; Bederson, Benjamin B. (Proceedings of the 11th IFIP TC 13 international conference on Human-computer interaction, 2007)

To fill or not to fill: the gas station problem - Khuller, Samir; Malekian,A.; Mestre,J. (Algorithms–ESA 2007, 2007)
In this paper we study several routing problems that generalize shortest paths and the Traveling Salesman Problem. We consider a more general model that incorporates the actual cost in terms of gas prices. We have a vehicle with a given tank capacity. We assume that at each vertex gas may be purchased at a certain price. The objective is to find the cheapest route to go from s to t, or the cheapest tour visiting a given set of locations. Surprisingly, the problem of find the cheapest way to go from s to t can be solved in polynomial time and is not NP-complete. For most other versions however, the problem is NP-complete and we develop polynomial time approximation algorithms for these versions.

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

A unified model explaining the offsets of overlapping and near-overlapping prokaryotic genes - Kingsford, Carl; Delcher,A. L; Salzberg,S. L (Molecular biology and evolution, 2007)

Universally composable multi-party computation using tamper-proof hardware - Katz, Jonathan (Advances in Cryptology-EUROCRYPT 2007, 2007)
Protocols proven secure within the universal composability (UC) framework satisfy strong and desirable security properties. Unfortunately, it is known that within the “plain” model, secure computation of general functionalities without an honest majority is impossible. This has prompted researchers to propose various “setup assumptions” with which to augment the bare UC framework in order to bypass this severe negative result. Existing setup assumptions seem to inherently require some trusted party (or parties) to initialize the setup in the real world.We propose a new setup assumption — more along the lines of a physical assumption regarding the existence of tamper-proof hardware — which also suffices to circumvent the impossibility result mentioned above. We suggest this assumption as potentially leading to an approach that might alleviate the need for trusted parties, and compare our assumption to those proposed previously.

Universally-composable two-party computation in two rounds - Horvitz,Omer; Katz, Jonathan (Proceedings of the 27th annual international cryptology conference on Advances in cryptology, 2007)
Round complexity is a central measure of efficiency, and characterizing the round complexity of various cryptographic tasks is of both theoretical and practical importance. We show here a universally-composable (UC) protocol (in the common reference string model) for two-party computation of any functionality, where both parties receive output, using only two rounds. (This assumes honest parties are allowed to transmit messages simultaneously in any given round; we obtain a three-round protocol when parties are required to alternate messages.) Our results match the obvious lower bounds for the round complexity of secure two-party computation under any reasonable definition of security, regardless of what setup is used. Thus, our results establish that secure two-party computation can be obtained under a commonly-used setup assumption with maximal security (i.e., security under general composition) in a minimal number of rounds. To give but one example of the power of our general result, we observe that as an almost immediate corollary we obtain a two-round UC blind signature scheme, matching a result by Fischlin at Crypto 2006 (though, in contrast to Fischlin, we use specific number-theoretic assumptions).

Usage-based dhcp lease time optimization - Khadilkar,Manas; Feamster, Nick; Sanders,Matt; Clark,Russ (Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, 2007)
The Dynamic Host Configuration Protocol (DHCP) is used to dynamically allocate address space to hosts on a local area network. Despite its widespread usage, few studies exist on DHCP usage patterns, and even less is known about the importance of setting the lease time (the time that a client retains ownership over some IP address) to an appropriate value. Lease time can greatly affect the tradeoff between address space utilization and the number of both renewal messages and client session expirations. In this paper, using a DHCP trace for 5 weekdays from the Georgia Tech campus network, we present the largest known study of DHCP utilization. We also explore how various strategies for setting lease times can dramatically reduce the number of renewals and expirations without prohibitively increasing address space utilization.
Keywords: dhcp; network management; OPTIMIZATION; usage

Using Content-Addressable Networks for Load Balancing in Desktop Grids - Kim,Jik-Soo; Keleher,Peter; Marsh,Michael; Bhattacharjee, Bobby; Sussman, Alan (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2007)
Desktop grids combine Peer-to-Peer and Grid computing techniques to improvethe robustness, reliability and scalability of job execution infrastructures. However, efficiently matching incoming jobs to available system resources and achieving good load balance in a fully decentralized and heterogeneous computing environment is a challenging problem. In this paper, we extend our prior work with a new decentralized algorithm for maintaining approximate global load information, and a job pushing mechanism that uses the global information to push jobs towards underutilized portions of the system. The resulting system more effectively balances load and improves overall system throughput. Through a comparative analysis of experimental results across different system configurations and job profiles, performed via simulation, we show that our system can reliably execute Grid applications on a distributed set of resources both with low cost and with good load balance.
Keywords: Technical Report

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

View-invariant modeling and recognition of human actions using grammars - Ogale, A.; Karapurkar, A.; Aloimonos, J. (Dynamical Vision, 2007)

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

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

Adaptive Transformation-based Learning for Improving Dictionary Tagging - Karagol-Ayan,Burcu; Doermann, David; Weinberg, Amy (Proceedings of the 11th Conference on European Chapter of the Association for Computational Linguistics, 2006)
We present an adaptive technique that enables users to produce a high quality dictionary parsed into its lexicographic components (headwords, parts of speech, translations, etc.) using an extremely small amount of user provided training data. We use transformation-based learning (TBL) as a postprocessor at two points in the system to improve performance. The results show that the tagging accuracy is increased from 83% and 91% to 93% and 94% for individual words or tokens , and from 64% and 83% to 90% and 93% for contiguous phrases such as definitions or examples of usage.

Algorithms for non-uniform size data placement on parallel disks - Kashyap,Srinivas; Khuller, Samir (Journal of Algorithms, 2006)
We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of M multimedia objects (data items) that need to be assigned to a storage system consisting of N disks d 1 , d 2 , … , d N . We are also given sets U 1 , U 2 , … , U M such that U i is the set of clients seeking the ith data item. Data item i has size s i . Each disk d j is characterized by two parameters, namely, its storage capacity C j which indicates the maximum total size of data items that may be assigned to it, and a load capacity L j which indicates the maximum number of clients that it can serve. The goal is to find a placement of data items to disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system.We study this data placement problem for homogeneous storage systems where all the disks are identical. We assume that all disks have a storage capacity of k and a load capacity of L. Previous work on this problem has assumed that all data items have unit size, in other words s i = 1 for all i. Even for this case, the problem is NP-hard. For the case where s i ∈ { 1 , … , Δ } for some constant Δ, we develop a polynomial time approximation scheme (PTAS). This result is obtained by developing two algorithms, one that works for constant k and one that works for arbitrary k. The algorithm for arbitrary k guarantees that a solution where at least ( ( k − Δ ) ( k + Δ ) ) ( 1 − 1 ( 1 + k ( 2 Δ ) ) 2 ) -fraction of all clients are assigned to a disk (under certain assumptions). In addition we develop an algorithm for which we can prove tight bounds when s i ∈ { 1 , 2 } . In fact, we can show that a ( 1 − 1 ( 1 + ⌊ k / 2 ⌋ ) 2 ) -fraction of all clients can be assigned (under certain natural assumptions), regardless of the input distribution.

Algorithms for Structured Total Least Squares Problems with Applications to Blind Image Deblurring - Kalsi,Anoop; O'Leary, Dianne P. (Journal of Research of the National Institute of Standards and Technology, 2006)
Mastronardi, Lemmerling, and van Huel presented an algorithm for solving a total least squares problem when the matrix and its perturbations are Toeplitz. A Toeplitz matrix is a special kind of matrix with small displacement rank. Here we generalize the fast algorithm to any matrix with small displacement rank. In particular, we show how to efficiently construct the generators whenever M has small displacement rank and show that in many important cases the Cholesky factorization of the matrix M M can also be determined fast. We further extend this problem to Tikhonov regularization of ill-posed problems and illustrate the use of the algorithm on an image deblurring problem.

Analyzing the HB and HB+ protocols in the “large error” case - Katz, Jonathan; Smith,A. (IACR ePrint report, 2006)
HB and HB+ are two shared-key, unidirectional authentication protocols whose extremelylow computational cost makes them potentially well-suited for severely resource-constrained devices. Security of these protocols is based on the conjectured hardness of learning parity with noise; that is, learning a secret s given “noisy” dot products of s that are incorrect with probability ε. Although the problem of learning parity with noise is meaningful for any constant ε < 1/2, existing proofs of security for HB and HB+ only imply security when ε < 1/4. In this note, we show how to extend these proofs to the case of arbitrary ε < 1/2.

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

Approximating the minimal sensor selection for supervisory control - Rohloff,K. R; Khuller, Samir; Kortsarz,G. (Discrete Event Dynamic Systems, 2006)
This paper discusses the problem of selecting a set of sensors of minimum cost that can be used for the synthesis of a supervisory controller. It is shown how this sensor selection problem is related to a type of directed graph st-cut problem that has not been previously discussed in the literature. Approximation algorithms to solve the sensor selection problem can be used to solve the graph cutting problem and vice-versa. Polynomial time algorithms to find good approximate solutions to either problem most likely do not exist (under certain complexity assumptions), but a time efficient approximation algorithm is shown that solves a special case of these problems. It is also shown how to convert the sensor selection problem into an integer programming problem.

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

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

Automatic identification of confusable drug names - Kondrak,Grzegorz; Dorr, Bonnie J (Artificial Intelligence in Medicine, 2006)
SummaryObjectiveMany hundreds of drugs have names that either look or sound so much alike that doctors, nurses and pharmacists can get them confused, dispensing the wrong one in errors that can injure or even kill patients. Methods and material We propose to address the problem through the application of two new methods—one based on orthographic similarity (“look-alike”), and the other based on phonetic similarity (“sound-alike”). In order to compare the effectiveness of the new methods for identifying confusable drug names with other known similarity measures, we developed a novel evaluation methodology. Results 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 a new feature-based phonetic approach (ALINE) outperforms orthographic approaches on a test set containing solely sound-alike pairs. However, an approach that combines several different measures achieves the best results on two test sets. Conclusion Our system is currently used as the basis of a system developed for the U.S. Food and Drug Administration for detection of confusable drug names.
Keywords: Drug names; Evaluation methodology; Lexical similarity; Medical errors

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

CAM04-6: Single-Path Routing of Time-varying Traffic - Kashyap,A.; Bhattacharjee, Bobby; La,R.; Shayman,M.; Tabatabaee,V. (Global Telecommunications Conference, 2006. GLOBECOM '06. IEEE, 2006)
We consider the problem of finding a single-path intra-domain routing for time-varying traffic. We characterize the traffic variations by a finite set of traffic profiles with given non-zero fractions of occurrence. Our goal is to optimize the average performance over all of these traffic profiles. We solve the optimal multi-path version of this problem using linear programming and develop heuristic single-path solutions using randomized rounding and iterated rounding. We analyze our single-path heuristic (finding the optimal single-path routing is NP-hard), and prove that the randomized rounding algorithm has a worst case performance bound of O(log(KN)/log(log(KN))) compared to the optimal multi-path routing with a high probability, where K is the number of traffic profiles, and N the number of nodes in the network. Further, our simulations show the iterated rounding heuristics perform close to the optimal multi-path routing on a wide range of measured ISP topologies, in both the average and the worst-case. Overall, these results are extremely positive since they show that in a wide-range of practical situations, it is not necessary to deploy multi-path routing; instead, an appropriately computed single-path routing is sufficient to provide good performance.
Keywords: algorithm; linear; algorithm; time-varying; algorithms; telecommunication; bound; IP; case; complexity; iterative; intra-domain; IP; methods; linear; multipath; network; network; ISP; networks; Internet; computational; optimal; performance; problem; heuristic; profile; worst; programming; optimal; programming; probability; randomised; rounding; routing; iterated; routing; probability; randomized; routing; telecommunication; single-path; topology; NP-hard; topology; telecommunication; traffic; traffic

Categorizing web search results into meaningful and stable categories using fast-feature techniques - Kules,Bill; Kustanowitz,Jack; Shneiderman, Ben (Proceedings of the 6th ACM/IEEE-CS joint conference on Digital libraries, 2006)
When search results against digital libraries and web resources have limited metadata, augmenting them with meaningful and stable category information can enable better overviews and support user exploration. This paper proposes six fast-feature techniques that use only features available in the search result list, such as title, snippet, and URL, to categorize results into meaningful categories. They use credible knowledge resources, including a US government organizational hierarchy, a thematic hierarchy from the Open Directory Project (ODP) web directory, and personal browse histories, to add valuable metadata to search results. In three tests the percent of results categorized for five representative queries was high enough to suggest practical benefits: general web search (76-90%), government web search (39-100%), and the Bureau of Labor Statistics website (48-94%). An additional test submitted 250 TREC queries to a search engine and successfully categorized 66% of the top 100 using the ODP and 61% of the top 350. Fast-feature techniques have been implemented in a prototype search engine. We propose research directions to improve categorization rates and make suggestions about how web site designers could re-organize their sites to support fast categorization of search results.
Keywords: Browsing; categorization; classification; metadata; open directory; taxonomies

Characterization of security notions for probabilistic private-key encryption - Katz, Jonathan; Yung,M. (Journal of Cryptology, 2006)
The development of precise definitions of security for encryption, as well as a detailed understanding of their relationships, has been a major area of research in modern cryptography. Here, we focus on the case of private-key encryption. Extending security notions from the public-key setting, we define security in the sense of both indistinguishability and non-malleability against chosen-plaintext and chosen-ciphertext attacks, considering both non-adaptive (i.e., ``lunchtime'') and adaptive oracle access (adaptive here refers to an adversary's ability to interact with a given oracle even after viewing the challenge ciphertext). We then characterize the 18 resulting security notions in two ways. First, we construct a complete hierarchy of security notions; that is, for every pair of definitions we show whether one definition is stronger than the other, whether the definitions are equivalent, or whether they are incomparable. Second, we partition these notions of security into two classes (computational or information-theoretic) depending on whether one-way functions are necessary in order for encryption schemes satisfying the definition to exist. Perhaps our most surprising result is that security against adaptive chosen-plaintext attack is (polynomially) equivalent to security against non-adaptive chosen-plaintext attack. On the other hand, the ability of an adversary to mount a (non-adaptive) chosen-plaintext attack is the key feature distinguishing computational and information-theoretic notions of security. These results hold for all security notions considered here.

A compact mathematical programming formulation for DNA motif finding - Kingsford, Carl; Zaslavsky,E.; Singh,M. (Combinatorial Pattern Matching, 2006)

Contention-conscious transaction ordering in multiprocessor DSP systems - Khandelia,M.; Bambha,N. K; Bhattacharyya, Shuvra S. (IEEE Transactions on Signal Processing, 2006)
This paper explores the problem of efficiently ordering interprocessor communication (IPC) operations in statically scheduled multiprocessors for iterative dataflow graphs. In most digital signal processing (DSP) applications, the throughput of the system is significantly affected by communication costs. By explicitly modeling these costs within an effective graph-theoretic analysis framework, we show that ordered transaction schedules can significantly outperform self-timed schedules even when synchronization costs are low. However, we also show that when communication latencies are nonnegligible, finding an optimal transaction order given a static schedule is an NP-complete problem, and that this intractability holds both under iterative and noniterative execution. We develop new heuristics for finding efficient transaction orders, and perform an extensive experimental comparison to gauge the performance of these heuristics.
Keywords: contention-conscious transaction ordering; Costs; data flow graphs; Dataflow; Delay; Digital signal processing; digital signal processing chips; Embedded system; graph-theoretic analysis; Instruments; Internet telephony; interprocessor communication; iterative dataflow graphs; iterative methods; Message passing; multiprocessor; multiprocessor DSP systems; NP-complete problem; Processor scheduling; scheduling; Signal processing; synchronization; Throughput

Controlled search over compact state representations, in nondeterministic planning domains and beyond - Kuter,U.; Nau, Dana S. (2006)
Two of the most efficient planners for planning in nondeter- ministic domains are MBP and ND-SHOP2. MBP achieves its efficiency by using Binary Decision Diagrams (BDDs) to represent sets of states that share some common properties, so it can plan for all of these states simultaneously. ND-SHOP2 achieves its efficiency by using HTN task decomposition to focus the search. In some environments, ND-SHOP2 runs exponentially faster than MBP, and in others the reverse is true. In this paper, we discuss the following:• We describe how to combine ND-SHOP2’s HTNs with MBP’s BDDs. Our new planning algorithm, YoYo, per- forms task decompositions over classes of states that are represented as BDDs. In our experiments, YoYo easily outperformed both MBP and ND-SHOP2, often by sev- eral orders of magnitude. • HTNsarejustoneofseveraltechniquesthatareoriginally developed for classical planning domains and that can be adapted to work in nondeterministic domains. By combin- ing those techniques with a BDD representation, it should be possible to get great speedups just as we did here. • We discuss how these same ideas can be generalized for use in several other research areas, such as planning with Markov Decision Processes, synthesizing controllers for hybrid systems, and composing Semantic Web Services.

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

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

Data redistribution and remote method invocation for coupled components - Bertrand,Felipe; Bramley,Randall; Bernholdt,David E.; Kohl,James A.; Sussman, Alan; Larson,Jay W.; Damevski,Kostadin B. (Journal of Parallel and Distributed Computing, 2006)
With the increasing availability of high-performance massively parallel computer systems, the prevalence of sophisticated scientific simulation has grown rapidly. The complexity of the scientific models being simulated has also evolved, leading to a variety of coupled multi-physics simulation codes. Such cooperating parallel programs require fundamentally new interaction capabilities, to efficiently exchange parallel data structures and collectively invoke methods across programs. So-called “ M × N ” research, as part of the common component architecture (CCA) effort, addresses these special and challenging needs, to provide generalized interfaces and tools that support flexible parallel data redistribution and parallel remote method invocation. Using this technology, distinct simulation codes with disparate distributed data decompositions can work together to achieve greater scientific discoveries.
Keywords: Common component architecture; Model coupling; Parallel data redistribution; Parallel remote method invocation

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

Differential Transcriptional Response to Nonassociative and Associative Components of Classical Fear Conditioning in the Amygdala and Hippocampus - Keeley,Michael B; Wood,Marcelo A; Isiegas,Carolina; Stein,Joel; Hellman,Kevin; Hannenhalli, Sridhar; Abel,Ted (Learning & MemoryLearn. Mem., 2006)
Classical fear conditioning requires the recognition of conditioned stimuli (CS) and the association of the CS with an aversive stimulus. We used Affymetrix oligonucleotide microarrays to characterize changes in gene expression compared to naive mice in both the amygdala and the hippocampus 30 min after classical fear conditioning and 30 min after exposure to the CS in the absence of an aversive stimulus. We found that in the hippocampus, levels of gene regulation induced by classical fear conditioning were not significantly greater than those induced by CS alone, whereas in the amygdala, classical fear conditioning did induce significantly greater levels of gene regulation compared to the CS. Computational studies suggest that transcriptional changes in the hippocampus and amygdala are mediated by large and overlapping but distinct combinations of molecular events. Our results demonstrate that an increase in gene regulation in the amygdala was partially correlated to associative learning and partially correlated to nonassociative components of the task, while gene regulation in the hippocampus was correlated to nonassociative components of classical fear conditioning, including configural learning.

Dissemination of compressed historical information in sensor networks - Deligiannakis,Antonios; Kotidis,Yannis; Roussopoulos, Nick (The VLDB JournalThe VLDB Journal, 2006)

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

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

Efficient techniques for clustering and scheduling onto embedded multiprocessors - Kianzad,V.; Bhattacharyya, Shuvra S. (IEEE Transactions on Parallel and Distributed Systems, 2006)

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

On expected constant-round protocols for Byzantine agreement - Katz, Jonathan; Koo,C. Y (Advances in Cryptology-CRYPTO 2006, 2006)
In a seminal paper, Feldman and Micali (STOC ’88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., t < n/2), and relying only on the existence of a secure signature scheme and a public-key infrastructure (PKI). Combined with existing results, this gives the first expected constant-round protocol for secure computation with honest majority in a point-to-point network assuming only one-way functions and a PKI. Our key technical tool — a new primitive we introduce called moderated VSS — also yields a simpler proof of the Feldman-Micali result.We also show a simple technique for sequential composition of protocols without simultaneous termination (something that is inherent for Byzantine agreement protocols using o(n) rounds) for the case of t<n/2.

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

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

Exploring personal media: A spatial interface supporting user-defined semantic regions - Kang,Hyunmo; Shneiderman, Ben (Journal of Visual Languages & Computing, 2006)
Graphical mechanisms for spatially organizing personal media data could enable users to fruitfully apply their conceptual models. This paper introduces Semantic regions, an innovative way for users to construct display representations of their conceptual models by drawing regions on 2D space and specifying the semantics for each region. Then users can apply personal categorizations to personal media data using the fling-and-flock metaphor. This allows personal media to be dragged to the spatially organized display and automatically grouped according to time, geography, family trees, groups of friends, or other spatially organized display representations of conceptual models. The prototype implementation for semantic regions, MediaFinder, was refined based on two small usability tests for usage and construction of user-defined conceptual models.
Keywords: dynamic queries; Fling-and-flock; Personal media management; Spatial information management; User interfaces

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

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

First Steps Toward an Electronic Field Guide for Plants - Haibin,Gaurav Agarwal; Agarwal,Gaurav; Ling,Haibin; Jacobs, David W.; Shirdhonkar,Sameer; Kress,W. John; Russell,Rusty; Belhumeur,Peter; Dixit,An; Feiner,Steve; Mahajan,Dhruv; Sunkavalli,Kalyan; et al. (Taxon, 2006)
this paper, we will describe our progress towards building a digital collection of the Smithsonian's type specimens, developing recognition algorithms that can match an image of a leaf to the species of plant from which it comes, and designing user interfaces for interacting with an electronic field guide. To start, we are developing a prototype electronic field guide for the flora of Plummers Island, a small, well-studied island in the Potomac River. This prototype system contains multiple images for each of about 130 species of plants on the island, and should soon grow to cover all 200+ species currently recorded (Shetler et al., 2005). Images of full specimens are available, as well as images of isolated leaves of each species. A zoomable user interface allows a user to browse these images, zooming in on ones of interest. Visual recognition algorithms assist a botanist in locating the specimens that are most relevant to identify the species of a plant. The system currently runs on a small hand-held computer. We will describe the components of this prototype, and also describe some of the future challenges we anticipate if we are to provide botanists in the field with all the resources that are now currently available in the world's museums and herbaria. Type Specimen Digital Collection The first challenge in producing our electronic field guide is to create a digital collection covering all of the Smithsonian's 85,000 vascular plant type specimens. For each type specimen, the database should eventually include systematically acquired high-resolution digital images of the specimen, textual descriptions, links to decision trees, images of live plants, and 3D models. Figure 1: On the left, our set-up at the Smithsonian for digitally photographing type specimens. On the...

Flow-insensitive type qualifiers - Foster, Jeffrey S.; Johnson,R.; Kodumal,J.; Aiken,A. (ACM Transactions on Programming Languages and Systems (TOPLAS), 2006)

Functional Analysis of Hes-1 in Preadipocytes - Ross,David A; Hannenhalli, Sridhar; Tobias,John W; Cooch,Neil; Shiekhattar,Ramin; Kadesch,Tom (Molecular EndocrinologyMolecular Endocrinology, 2006)
Notch signaling blocks differentiation of 3T3-L1 preadipocytes, and this can be mimicked by constitutive expression of the Notch target gene Hes-1. Although considered initially to function only as a repressor, recent evidence indicates that Hes-1 can also activate transcription. We show here that the domains of Hes-1 needed to block adipogenesis coincide with those necessary for transcriptional repression. HRT1, another basic-helix-loop-helix protein and potential Hes-1 partner, was also induced by Notch in 3T3-L1 cells but did not block adipogenesis, suggesting that Hes-1 functions primarily as a homodimer or possibly as a heterodimer with an unknown partner. Purification of Hes-1 identified the Groucho/transducin-like enhancer of split family of corepressors as the only significant Hes-1 interacting proteins in vivo. An evaluation of global gene expression in preadipocytes identified approximately 200 Hes-1-responsive genes comprising roughly equal numbers of up-regulated and down-regulated genes. However, promoter analyses indicated that the down-regulated genes were significantly more likely to contain Hes-1 binding sites, indicating that Hes-1 is more likely to repress transcription of its direct targets. We conclude that Notch most likely blocks adipogenesis through the induction of Hes-1 homodimers, which repress transcription of key target genes.

Hierarchical Layouts for Photo Libraries - Kustanowitz,J.; Shneiderman, Ben (IEEE Multimedia, 2006)
We use an annotated digital photo collection to demonstrate a two-level auto-layout technique consisting of a central primary region with secondary regions surrounding it. Because the object sizes within regions can only be changed in discrete units, we refer to them as quantum content. Our real-time algorithms enable a compelling interactive display as users resize the canvas, or move and resize the primary region
Keywords: annotated digital photo collection; auto-layout technique; bi-level hierarchies; Computer science; data visualisation; digital libraries; document image processing; Information Visualization; interactive algorithms; interactive displays; Libraries; Lifting equipment; Organization Charts; photo collections; photo layouts; photo library; Photography; quantum content; Silver; Springs; User interfaces; Web pages

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

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

Improved algorithms for data migration - Khuller, Samir; Kim,Y. A; Malekian,A. (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2006)
Our work is motivated by the need to manage data on a collection of storage devices to handle dynamically changing demand. As demand for data changes, the system needs to automatically respond to changes in demand for different data items. The problem of computing a migration plan among the storage devices is called the data migration problem. This problem was shown to be NP-hard, and an approximation algorithm achieving an approximation factor of 9.5 was presented for the half-duplex communication model in [Khuller, Kim and Wan: Algorithms for Data Migration with Cloning, SIAM J. on Computing, Vol. 33(2):448–461 (2004)]. In this paper we develop an improved approximation algorithm that gives a bound of 6.5+o(1) using various new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5. We also consider the full duplex communication model and develop an improved bound of 4 +o(1) for this model, with no external disks.

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

Improved lower and upper bounds for universal TSP in planar metrics - Hajiaghayi, Mohammad T.; Kleinberg,R.; Leighton,T. (Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006)

Information-aware HyperOctree for effective isosurface rendering of large scale time-varying data - Kim,J.; JaJa, Joseph F. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2006)
We develop a new indexing structure and a new out-of-core scheme to extract and render isosurfaces forlarge scale time-varying 3-D volume data. The new algorithm enables the fast visualization of arbitrary isosurfaces cut by a user-specified hyperplane along any of the four dimensions. Our data structure makes use of the entropy measure to establish the relative resolutions of the spatial and temporal dimensions rather than treating the temporal dimension just as any other dimension. The preprocessing is very efficient and the resulting indexing structure is very compact. We have tested our scheme on 40GB subset of the Richtmyer-Meshkov instability data set and obtained very good performance for a wide range of isosurface extraction queries.

Integrating Video Information over Time. Example: Face Recognition from Video - Krüger,Volker; Zhou,Shaohua; Chellapa, Rama (Cognitive Vision SystemsCognitive Vision Systems, 2006)
The ability to integrate information over time in order to come to a conclusion is a strength of cognitive systems. It allows the system, e.g., to 1 verify insecure observations: This is the case when data is noisy or of low-quality, or if conditions in general are non-optimal. 2 exploit general knowledge about spatio-temporal relations: This allows the system to exploit the specific dynamics of an object as an additional feature for, e.g., recognition, interpretation and prediction of actions of other agents. 3 In general, using dynamics allows the system to recursively generate and verify hypotheses for object and scene interpretation and to generate warnings when ‘implausible’ hypotheses occur or to circumvent them altogether. We have studied the effectiveness of temporal integration for recognition purposes by using the face recognition as an example study case. Face recognition is a prominent problem and has been studied more extensively than almost any other recognition problem. An observation is that face recognition works well in ideal conditions. If those conditions, however, are not met, then all present algorithms break down disgracefully. This problem appears to be general to all vision techniques that intend to extract visual information out of low-SNR image data. It is exactly a strength of cognitive systems that they are able to cope with non-ideal situations. In this chapter we will deal with this problem.

KeyChains: A Decentralized Public-Key Infrastructure - Morselli,Ruggero; Bhattacharjee, Bobby; Katz, Jonathan; Marsh,Michael A (Technical Reports from UMIACS, UMIACS-TR-2006-12, 2006)
A Certification Authority (CA) can be used to certify keys and build apublic-key infrastructure (PKI) when all users trust the same CA. A decentralized PKI trades off absolute assurance on keys for independence from central control and improved scalability and robustness. The PGP ``web of trust'' model has been suggested as a decentralized certification system, and has been used with great success for secure email. Although the PGP web of trust model allows anyone to issue certificates which can be used to form certificate chains, the discovery and construction of certificate chains relies on centralized keyservers to store certificates and respond to queries. In this paper, we design and implement KeyChains, a peer-to-peer system which incorporates a novel lookup mechanism specifically tailored to the task of generating and retrieving certificate chains in completely unstructured networks. By layering our system on top of the web of trust model, we thus obtain the first PKI which is truly decentralized in all respects. Our analysis and simulations show that the resulting system is both efficient and secure.
Keywords: Technical Report

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

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

Mapping Multimedia Applications Onto Configurable Hardware With Parameterized Cyclo-Static Dataflow Graphs - Haim,F.; Sen,M.; Ko,Dong-Ik; Bhattacharyya, Shuvra S.; Wolf,W. (Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on, 2006)
This paper develops methods for model-based design and implementation of image processing applications. We apply our previously developed meta-modeling technique of homogeneous parameterized dataflow (HPDF) (M. Sen et al., 2005) to the framework of cyclostatic dataflow (CSDF) (G. Bilsen et al., 1996), and demonstrate this integrated modeling methodology through hardware mapping of a gesture recognition application. We also provide a comparative study between HPDF/CSDF-based representation of the gesture recognition application, and a previously developed version based on applying HPDF in conjunction with conventional synchronous dataflow (SDF) semantics (M. Sen et al., 2005)
Keywords: configurable hardware; Data communication; Gesture recognition; gesture recognition application; graph theory; hardware mapping; image processing applications; mapping multimedia applications; meta-modeling technique; model-based design; Multimedia communication; parameterized cyclo-static dataflow graphs

Matching Jobs to Resources in Distributed Desktop Grid Environments - Kim,Jik-Soo; Bhattacharjee, Bobby; Keleher, Peter J.; Sussman, Alan (Technical Reports from UMIACS, UMIACS-TR-2006-15, 2006)
Desktop grids use opportunistic sharing to exploit large collectionsof personal computers and workstations across the Internet and can achieve tremendous computing power with low cost. However, current systems are typically based on a traditional client-server architecture, which has inherent shortcomings with respect to robustness, reliability and scalability. In this paper, we propose a decentralized, robust, highly available, and scalable infrastructure to match incoming jobs to available resources. The key idea behind our proposed system is to leverage information provided by an underlying peer-to-peer system to create a hierarchical Rendezvous Node Tree, which performs the matching efficiently. Our experimental results obtained via simulation show that we can effectively match jobs with varying levels of resource constraints to available nodes and maintain good load balance in a fully decentralized heterogeneous computational environment.
Keywords: Technical Report

MCMC Data Association and Sparse Factorization Updating for Real Time Multitarget Tracking with Merged and Multiple Measurements - Zia Khan; Balch, T.; Dellaert, F. (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006)
In several multitarget tracking applications, a target may return more than one measurement per target and interacting targets may return multiple merged measurements between targets. Existing algorithms for tracking and data association, initially applied to radar tracking, do not adequately address these types of measurements. Here, we introduce a probabilistic model for interacting targets that addresses both types of measurements simultaneously. We provide an algorithm for approximate inference in this model using a Markov chain Monte Carlo (MCMC)-based auxiliary variable particle filter. We Rao-Blackwellize the Markov chain to eliminate sampling over the continuous state space of the targets. A major contribution of this work is the use of sparse least squares updating and downdating techniques, which significantly reduce the computational cost per iteration of the Markov chain. Also, when combined with a simple heuristic, they enable the algorithm to correctly focus computation on interacting targets. We include experimental results on a challenging simulation sequence. We test the accuracy of the algorithm using two sensor modalities, video, and laser range data. We also show the algorithm exhibits real time performance on a conventional PC
Keywords: algorithms; approximate inference; Artificial intelligence; auxiliary variable particle filter; Computational efficiency; continuous state space; downdating; Image Enhancement; Image Interpretation, Computer-Assisted; Inference algorithms; Information Storage and Retrieval; laser range scanner; laser range scanner.; Least squares approximation; least squares approximations; Least squares methods; linear least squares; Markov chain Monte Carlo; Markov processes; MCMC data association; merged measurements; Monte Carlo methods; Movement; multiple merged measurements; multitarget tracking; particle filter; particle filtering (numerical methods); Particle filters; Pattern Recognition, Automated; probabilistic model; QR factorization; Radar tracking; Rao-Blackwellized; real time multitarget tracking; Reproducibility of results; Sampling methods; Sensitivity and Specificity; sensor fusion; sparse factorization updating; sparse least squares; State-space methods; Subtraction Technique; target tracking; updating

Memory-constrained block processing optimization for synthesis of DSP software - Ko,M. Y; Shen,C. C; Bhattacharyya, Shuvra S. (Embedded Computer Systems: Architectures, Modeling and Simulation, 2006. IC-SAMOS 2006. International Conference on, 2006)

Morphology Induction from Limited Noisy Data Using Approximate String Matching - Karagol-Ayan,Burcu; David Doermann; Weinberg, Amy (Proceedings of the Eighth Meeting of the ACL Special Interest Group in Computational Phonology (SIGPHON 2006), 2006)
For a language with limited resources, a dictionary may be one of the few available electronic resources. To make effective use of the dictionary for translation, however, users must be able to access it using the root form of morphologically deformed variant found in the text. Stemming and data driven methods, however, are not suitable when data is sparse. We present algorithms for discovering morphemes from limited, noisy data obtained by scanning a hard copy dictionary. Our approach is based on the novel application of the longest common substring and string edit distance metrics. Results show that these algorithms can in fact segment words into roots and affixes from the limited data contained in a dictionary, and extract affixes. This in turn allows non native speakers to perform multilingual tasks for applications where response must be rapid, and their knowledge is limited. In addition, this analysis can feed other NLP tools requiring lexicons.

Multi-camera tracking and segmentation of occluded people on ground plane using search-guided particle filtering - Kim,K.; Davis, Larry S. (Computer Vision–ECCV 2006, 2006)
A multi-view multi-hypothesis approach to segmenting and tracking multiple (possibly occluded) persons on a ground plane is proposed. During tracking, several iterations of segmentation are performed using information from human appearance models and ground plane homography. To more precisely locate the ground location of a person, all center vertical axes of the person across views are mapped to the top-view plane and their intersection point on the ground is estimated. To tackle the explosive state space due to multiple targets and views, iterative segmentation-searching is incorporated into a particle filtering framework. By searching for people’s ground point locations from segmentations, a set of a few good particles can be identified, resulting in low computational cost. In addition, even if all the particles are away from the true ground point, some of them move towards the true one through the iterated process as long as they are located nearby. We demonstrate the performance of the approach on several video sequences.

Multiuser distortion management of layered video over resource limited downlink multicode-CDMA - Han,Z.; Su,Guan-Ming; Kwasinski,A.; M. Wu; Liu,K. J.R (Wireless Communications, IEEE Transactions on, 2006)
Transmitting multiple real-time encoded videos to multiple users over wireless cellular networks is a key driving force for developing broadband technology. We propose a new framework to transmit multiple users' video programs encoded by MPEG-4 FGS codec over downlink multicode CDMA networks in real time. The proposed framework jointly manages the rate adaptation of source and channel coding, CDMA code allocation, and power control. Subject to the limited system resources, such as the number of pseudo-random codes and the maximal power for CDMA transmission, we develop an adaptive scheme of distortion management to ensure baseline video quality for each user and further reduce the overall distortion received by all users. To efficiently utilize system resources, the proposed scheme maintains a balanced ratio between the power and code usages. We also investigate three special scenarios where demand, power, or code is limited, respectively. Compared with existing methods in the literature, the proposed algorithm can reduce the overall system's distortion by 14% to 26%. In the demand-limited case and the code-limited but power-unlimited case, the proposed scheme achieves the optimal solutions. In the power-limited but code-unlimited case, the proposed scheme has a performance very close to a performance upper bound
Keywords: (mobile; access; combined; allocation; broadband; case; layered; CDMA; cellular; code; codes; radio; codes; real-time; codes; telecommunication; coding; mobility; coding; video; coding; wireless; communication; control; pseudo-random; control; pseudonoise; control; video; distortion; division; downlink; encoded; limited; links; random; management; management; power; multicode-CDMA; source-channel; multiple; networks; broadband; networks; cellular; radio); power; radio; code; source-channel; technology; code-unlimited; video; multiuser; videos; resource

New lower bounds for oblivious routing in undirected graphs - Hajiaghayi, Mohammad T.; Kleinberg,R. D; Leighton,T.; R\äcke,H. (Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006)

A Novel Information-Aware Octree for the Visualization of Large Scale Time-Varying Data - Kim,Jusub; JaJa, Joseph F. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2006)
Large scale scientific simulations are increasingly generatingvery large data sets that present substantial challenges to current visualization systems. In this paper, we develop a new scalable and efficient scheme for the visual exploration of 4-D isosurfaces of time varying data by rendering the 3-D isosurfaces obtained through an arbitrary axis-parallel hyperplane cut. The new scheme is based on: (i) a new 4-D hierarchical indexing structure, called Information-Aware Octree; (ii) a controllable delayed fetching technique; and (iii) an optimized data layout. Together, these techniques enable efficient and scalable out-of-core visualization of large scale time varying data sets. We introduce an entropy-based dimension integration technique by which the relative resolutions of the spatial and temporal dimensions are established, and use this information to design a compact size 4-D hierarchical indexing structure. We also present scalable and efficient techniques for out-of-core rendering. Compared with previous algorithms for constructing 4-D isosurfaces, our scheme is substantially faster and requires much less memory. Compared to the Temporal Branch-On-Need octree (T-BON), which can only handle a subset of our queries, our indexing structure is an order of magnitude smaller and is at least as effective in dealing with the queries that the T-BON can handle. We have tested our scheme on two large time-varying data sets and obtained very good performance for a wide range of isosurface extraction queries using an order of magnitude smaller indexing structures than previous techniques. In particular, we can generate isosurfaces at intermediate time steps very quickly.
Keywords: Technical Report

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

OMNI: An efficient overlay multicast infrastructure for real-time applications - Banerjee,Suman; Kommareddy,Christopher; Kar,Koushik; Bhattacharjee, Bobby; Khuller, Samir (Computer Networks, 2006)
We consider an overlay architecture (called OMNI) 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 and 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 multicast; Minimum latency problem; overlay multicast

Participatory design with proxies: developing a desktop-PDA system to support people with aphasia - Jordan Boyd-Graber; Nikolova,Sonya S.; Moffatt,Karyn A.; Kin,Kenrick C.; Lee,Joshua Y.; Mackey,Lester W.; Tremaine,Marilyn M.; Klawe,Maria M. (Proceedings of the SIGCHI conference on Human Factors in computing systems, 2006)
In this paper, we describe the design and preliminary evaluation of a hybrid desktop-handheld system developed to support individuals with aphasia, a disorder which impairs the ability to speak, read, write, or understand language. The system allows its users to develop speech communication through images and sound on a desktop computer and download this speech to a mobile device that can then support communication outside the home. Using a desktop computer for input addresses some of this population's difficulties interacting with handheld devices, while the mobile device addresses stigma and portability issues. A modified participatory design approach was used in which proxies, that is, speech-language pathologists who work with aphasic individuals, assumed the role normally filled by users. This was done because of the difficulties in communicating with the target population and the high variability in aphasic disorders. In addition, the paper presents a case study of the proxy-use participatory design process that illustrates how different interview techniques resulted in different user feedback.
Keywords: aphasia; assistive technology; multi-modal interfaces; participatory design

Patterns of sequence conservation in presynaptic neural genes - Hadley,Dexter; Murphy,Tara; Valladares,Otto; Hannenhalli, Sridhar; Ungar,Lyle; Kim,Junhyong; Bućan,Maja (Genome Biology, 2006)
The neuronal synapse is a fundamental functional unit in the central nervous system of animals. Because synaptic function is evolutionarily conserved, we reasoned that functional sequences of genes and related genomic elements known to play important roles in neurotransmitter release would also be conserved.

PCFGs with syntactic and prosodic indicators of speech repairs - Hale,John; Shafran,Izhak; Yung,Lisa; Dorr, Bonnie J; Harper,Mary; Krasnyanskaya,Anna; Lease,Matthew; Liu,Yang; Roark,Brian; Snover,Matthew; Stewart,Robin (Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, 2006)
A grammatical method of combining two kinds of speech repair cues is presented. One cue, prosodic disjuncture, is detected by a decision tree-based ensemble classifier that uses acoustic cues to identify where normal prosody seems to be interrupted (Lickley, 1996). The other cue, syntactic parallelism, codifies the expectation that repairs continue a syntactic category that was left unfinished in the reparandum (Levelt, 1983). The two cues are combined in a Treebank PCFG whose states are split using a few simple tree transformations. Parsing performance on the Switchboard and Fisher corpora suggests that these two cues help to locate speech repairs in a synergistic way.

PDR: A Performance Evaluation Method for Foreground-Background Segmentation Algorithms - Kim,K.; Chalidabhongse,T.H.; Harwood,D.; Davis, Larry S. (EURASIP Journal on Applied Signal Processing, 2006)
We introduce a performance evaluation methodologycalled Perturbation Detection Rate (PDR) analysis for measuring performance of foreground-background seg- mentation. It has some advantages over the commonly used Receiver Operation Characteristics (ROC) analy- sis. Specifically, it does not require foreground targets or knowledge of foreground distributions. It measures the sensitivity of a background subtraction algorithm in detecting possible low contrast targets against the background as a function of contrast, also depending on how well the model captures mixed (moving) back- ground events. We compare four background subtrac- tion algorithms using the methodology. The experimen- tal results show how PDR is used to measure perfor- mance with respect to detection sensitivity in interest- ing low contrast regions.

Processing approximate aggregate queries in wireless sensor networks - Deligiannakis,Antonios; Kotidis,Yannis; Roussopoulos, Nick (Information Systems, 2006)
In-network data aggregation has been recently proposed as an effective means to reduce the number of messages exchanged in wireless sensor networks. Nodes of the network form an aggregation tree, in which parent nodes aggregate the values received from their children and propagate the result to their own parents. However, this schema provides little flexibility for the end-user to control the operation of the nodes in a data sensitive manner. For large sensor networks with severe energy constraints, the reduction (in the number of messages exchanged) obtained through the aggregation tree might not be sufficient. In this paper, we present new algorithms for obtaining approximate aggregate statistics from large sensor networks. The user specifies the maximum error that he is willing to tolerate and, in turn, our algorithms program the nodes in a way that seeks to minimize the number of messages exchanged in the network, while always guaranteeing that the produced estimate lies within the specified error from the exact answer. A key ingredient to our framework is the notion of the residual mode of operation that is used to eliminate messages from sibling nodes when their cumulative change to the computed aggregate is small. We introduce two new algorithms, based on potential gains, which adaptively redistribute the error thresholds to those nodes that benefit the most and try to minimize the total number of transmitted messages in the network. Our techniques significantly reduce the number of messages, often by a factor of 10 for a modest 2% relative error bound, and consistently outperform previous techniques for computing approximate aggregates, which we have adapted for sensor networks.
Keywords: Aggregate queries; approximation; sensor networks

Query planning in the presence of overlapping sources - Bleiholder,J.; Khuller, Samir; Naumann,F.; Raschid, Louiqa; Wu,Y. (Advances in Database Technology-EDBT 2006, 2006)

Query planning in the presence of overlapping sources - Bleiholder,J.; Khuller, Samir; Naumann,F.; Raschid, Louiqa; Wu,Y. (Advances in Database Technology-EDBT 2006, 2006)
Navigational queries on Web-accessible life science sources pose unique query optimization challenges. The objects in these sources are interconnected to objects in other sources, forming a large and complex graph, and there is an overlap of objects in the sources. Answering a query requires the traversal of multiple alternate paths through these sources. Each path can be associated with the benefit or the cardinality of the target object set (TOS) of objects reached in the result. There is also an evaluation cost of reaching the TOS.We present dual problems in selecting the best set of paths. The first problem is to select a set of paths that satisfy a constraint on the evaluation cost while maximizing the benefit (number of distinct objects in the TOS). The dual problem is to select a set of paths that satisfies a threshold of the TOS benefit with minimal evaluation cost. The two problems can be mapped to the budgeted maximum coverage problem and the maximal set cover with a threshold. To solve these problems, we explore several solutions including greedy heuristics, a randomized search, and a traditional IP/LP formulation with bounds. We perform experiments on a real-world graph of life sciences objects from NCBI and report on the computational overhead of our solutions and their performance compared to the optimal solution.

Ranking search results in P2P systems - Gopalakrishnan,V.; Morselli,R.; Bhattacharjee, Bobby; Keleher,P.; Srinivasan, Aravind (Technical Report, CR-TR-4779, Department of Computer Science, University of Maryland, 2006)
P2P deployments are a natural infrastructure for buildingdistributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them. Users, however, are primarily interested in the most relevant, and not all possible results. Using random sampling, we extend a class of well- known information retrieval ranking algorithms such that they can be applied in this distributed setting. We analyze the overhead of our approach, and quantify exactly how our system scales with increasing number of documents, system size, document to node mapping (uniform versus non-uniform), and types of queries (rare versus popular terms). Our analysis and simulations show that a) these extensions are efficient, and can scale with little overhead to large systems, and b) the accuracy of the results ob- tained using distributed ranking is comparable to a cen- tralized implementation.

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

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

Relay Placement for Higher Order Connectivity in Wireless Sensor Networks - Kashyap,A.; Khuller, Samir; Shayman,M. (INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006)
Not available

Reliable broadcast in radio networks: the bounded collision case - Koo,Chiu-Yuen; Bhandari,Vartika; Katz, Jonathan; Vaidya,Nitin H. (Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, 2006)
We study the problem of achieving global broadcast in a radio network where a node can multicast messages to all of its neighbors (that is, nodes within some given distance r), and up to t nodes in any single neighborhood may be corrupted. Previous work assumes that corrupted nodes can neither cause collisions nor spoof addresses of honest nodes. In this work, we eliminate these assumptions and allow each faulty node to cause a (known) bounded number of collisions and spoof the addresses of arbitrary other nodes. We show that the maximum tolerable t in this case is identical to the maximum tolerable t when collisions and address spoofing are not allowed. Thus, by causing collisions and spoofing addresses an adversary may be able to degrade the efficiency of achieving broadcast, but it cannot affect the feasibility of this task.
Keywords: broadcast; byzantine failure; Fault tolerance; radio networks

Reranking for Sentence Boundary Detection in Conversational Speech - Roark,B.; Liu,Yang; Harper,M.; Stewart,R.; Lease,M.; Snover,M.; Shafran,I.; Dorr, Bonnie J; Hale,J.; Krasnyanskaya,A.; Yung,L. (2006 IEEE International Conference on Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings, 2006)
We present a reranking approach to sentence-like unit (SU) boundary detection, one of the EARS metadata extraction tasks. Techniques for generating relatively small n-best lists with high oracle accuracy are presented. For each candidate, features are derived from a range of information sources, including the output of a number of parsers. Our approach yields significant improvements over the best performing system from the NIST RT-04F community evaluation
Keywords: Automatic speech recognition; conversational speech; data mining; Ear; EARS metadata extraction tasks; Feature extraction; hidden Markov models; meta data; Model driven engineering; NIST; NIST RT-04F community evaluation; oracle accuracy; performance evaluation; reranking; sentence-like unit boundary detection; Speech processing; Speech recognition; Telephony

Resource Discovery Techniques in Distributed Desktop Grid Environments - Kim,Jik-Soo; Nam,Beomseok; Keleher,Peter; Marsh,Michael; Bhattacharjee, Bobby; Sussman, Alan (Proceedings of the 7th IEEE/ACM International Conference on Grid Computing, 2006)
Desktop grids use opportunistic sharing to exploit large collections of personal computers and workstations across the Internet, achieving tremendous computing power at low cost. Traditional desktop grid systems are typically based on a client-server architecture, which has inherent shortcomings with respect to robustness, reliability and scalability. In this paper, we propose a decentralized, robust, highly available, and scalable infrastructure to match incoming jobs to available resources. Through a comparative analysis on the experimental results obtained via simulation of three different types of matchmaking algorithms under different workload scenarios, we show the trade-offs between effcient matchmaking and good load balancing in a fully decentralized, heterogeneous computational environment.

Review of "A Computational Introduction to Number Theory and Algebra by Victor Shoup", Cambridge University Press, 2005 - Katz, Jonathan (SIGACT News, 2006)

Review of "Primality Testing in Polynomial Time by Martin Dietzfelbinger", Springer-Verlag, 2004 - Katz, Jonathan (SIGACT News, 2006)

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

Robust fuzzy extractors and authenticated key agreement from close secrets - Dodis,Y.; Katz, Jonathan; Reyzin,L.; Smith,A. (Advances in Cryptology-CRYPTO 2006, 2006)
Consider two parties holding correlated random variables W and W′, respectively, that are within distance t of each other in some metric space. These parties wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys R j using multiple pairs {(W j , W′ j )}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors.Our results improve upon previous work in several respects: – The best previous solution for the keyless case with no errors (i.e., t=0) requires the min-entropy of W to exceed 2|W|/3. We show a solution when the min-entropy of W exceeds the minimal threshold |W|/2. – Previous solutions for the keyless case in the presence of errors (i.e., t>0) required random oracles. We give the first constructions (for certain metrics) in the standard model. – Previous solutions for the keyed case were stateful. We give the first stateless solution.

A robust maximum completion time measure for scheduling - Charikar,Moses; Khuller, Samir (Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006)
One popular measure for evaluating the performance of scheduling algorithms, is the maximum response time of any job (makespan). Typically the objective is to find a schedule that minimizes the maximum response time over all jobs. One drawback of this measure is that a relatively small number of jobs in the request set could cause the maximum response time to be very high. Thus, this measure reflects local rather than global properties of the request set. In this paper we consider a robust generalization of this measure. Our goal is to minimize T, such that a given fraction of jobs can be scheduled with a response time of at most T. We demonstrate the applicability of this measure in the context of broadcast scheduling. We show that in the online setting no constant factor online approximation is possible for the problem of minimizing the maximum response time for a given fraction of jobs in the context of broadcast scheduling. We give a factor 5, polynomial time offline approximation algorithm for the problem of minimizing the maximum response time for a given fraction of jobs in the context of broadcast scheduling.

Saliency-guided Enhancement for Volume Visualization - Kim,Y.; Varshney, Amitabh (Visualization and Computer Graphics, IEEE Transactions on, 2006)
Recent research in visual saliency has established a computational measure of perceptual importance. In this paper we present a visual-saliency-based operator to enhance selected regions of a volume. We show how we use such an operator on a user-specified saliency field to compute an emphasis field. We further discuss how the emphasis field can be integrated into the visualization pipeline through its modifications of regional luminance and chrominance. Finally, we validate our work using an eye-tracking-based user study and show that our new saliency enhancement operator is more effective at eliciting viewer attention than the traditional Gaussian enhancement operator
Keywords: Computer-Assisted; Imaging; Ocular; Humans; Image Enhancement; Image Interpretation; saliency-guided enhancement; visual-saliency-based operator; volume rendering; volume visualization; data visualisation; rendering (computer graphics); Algorithms; Attention; Computer Graphics; Eye Movements; Fixation; Three-Dimensional; User-Computer Interface

SParseval: Evaluation metrics for parsing speech - Roark,B.; Harper,M.; Charniak,E.; Dorr, Bonnie J; Johnson,M.; Kahn,J.; Liu,Y.; Ostendorf,M.; Hale,J.; Krasnyanskaya,A.; others (Proc. LREC, 2006)
While both spoken and written language processing stand to benefit from parsing, the standard Parseval metrics (Black et al., 1991) andtheir canonical implementation (Sekine and Collins, 1997) are only useful for text. The Parseval metrics are undefined when the words input to the parser do not match the words in the gold standard parse tree exactly, and word errors are unavoidable with automatic speech recognition (ASR) systems. To fill this gap, we have developed a publicly available tool for scoring parses that implements a variety of metrics which can handle mismatches in words and segmentations, including: alignment-based bracket evaluation, alignment-based dependency evaluation, and a dependency evaluation that does not require alignment. We describe the different metrics, how to use the tool, and the outcome of an extensive set of experiments on the sensitivity of the metrics.

A Step Towards Automated Design of Side Actions in Injection Molding of Complex Parts - Banerjee,Ashis; Gupta, Satyandra K. (Geometric Modeling and Processing - GMP 2006, 2006)
Side actions contribute to mold cost by resulting in an additional manufacturing and assembly cost as well as by increasing the molding cycle time. Therefore, generating shapes of side actions requires solving a complex geometric optimization problem. Different objective functions may be needed depending upon different molding scenarios (e.g., prototyping versus large production runs). Manually designing side actions is a challenging task and requires considerable expertise. Automated design of side actions will significantly reduce mold design lead times. This paper describes algorithms for generating shapes of side actions to minimize a customizable molding cost function.
Keywords: Computer science

A structural approach to latency prediction - Madhyastha,Harsha V.; Anderson,Thomas; Krishnamurthy,Arvind; Spring, Neil; Venkataramani,Arun (Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, 2006)
Several models have been recently proposed for predicting the latency of end to end Internet paths. These models treat the Internet as a black-box, ignoring its internal structure. While these models are simple, they can often fail systematically; for example, the most widely used models use metric embeddings that predict no benefit to detour routes even though half of all Internet routes can benefit from detours.In this paper, we adopt a structural approach that predicts path latency based on measurements of the Internet's routing topology, PoP connectivity, and routing policy. We find that our approach outperforms Vivaldi, the most widely used black-box model. Furthermore, unlike metric embeddings, our approach successfully predicts 65% of detour routes in the Internet. The number of measurements used in our approach is comparable with that required by black box techniques, but using traceroutes instead of pings.
Keywords: internet topology; latency prediction; route measurements

Structure of social contact networks and their impact on epidemics - Eubank,S.; Kumar,V. S.A; Marathe,M. V; Srinivasan, Aravind; Wang,N. (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 2006)
Traditional epidemiological research has focused on rate-based differential-equation models on completely mixing populations. In this paper, we outline an approach based on a combination of net- work theory and discrete-event simulations to study epidemics in large urban areas. We survey some of our results published in Nature (2004) and the Proc. ACM-SIAM Symposium on Discrete Algorithms (2004), and present some new results on: (i) mathematical properties of large social contact networks, as well as (ii) simulation-based dynamic anal- ysis of disease-spread in such networks. We identify a number of new measures that are significant for understanding epidemics and for devel- oping new strategies in policy planning. We also perform a very detailed structural analysis of the social contact networks produced by TRAN- SIMS, a simulator for detailed transportation/traffic studies, and study two random graph models to generate realistic social networks: Chung- Lu’s model and the configuration model. We also develop combinatorial formulations and approximation algorithms for quarantining, vaccina- tion and sensor placement, as aids to decision-making.

Synthetic‐perturbation techniques for screening shared memory programs - Snelick,Robert; JaJa, Joseph F.; Kacker,Raghu; Lyon,Gordon (Software: Practice and Experience, 2006)
The synthetic-perturbation screening (SPS) methodology is based on an empirical approach; SPS introduces artificial perturbations into the MIMD program and captures the effects of such perturbations by using the modern branch of statistics called design of experiments. SPS can provide the basis of a powerful tool for screening MIMD programs for performance bottlenecks. This technique is portable across machines and architectures, and scales extremely well on massively parallel processors. The purpose of this paper is to explain the general approach and to extend it to address specific features that are the main source of poor performance on the shared memory programming model. These include performance degradation due to load imbalance and insufficient parallelism, and overhead introduced by synchronizations and by accessing shared data structures. We illustrate the practicality of SPS by demonstrating its use on two very different case studies: a large image understanding benchmark and a parallel quicksort.
Keywords: Design of experiments; parallel programs; performance; Shared memory programming model; Synthetic perturbation

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

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

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

Trusted declassification:: high-level policy for a security-typed language - Hicks,Boniface; King,Dave; McDaniel,Patrick; Hicks, Michael W. (Proceedings of the 2006 workshop on Programming languages and analysis for security, 2006)
Security-typed languages promise to be a powerful tool with which provably secure software applications may be developed. Programs written in these languages enforce a strong, global policy of noninterferencewhich ensures that high-security data will not be observable on low-security channels. Because noninterference is typically too strong a property, most programs use some form of declassification to selectively leak high security information, e.g. when performing a password check or data encryption. Unfortunately, such a declassification is often expressed as an operation within a given program, rather than as part of a global policy, making reasoning about the security implications of a policy more difficult.In this paper, we propose a simple idea we call trusted declassification in which special declassifier functions are specified as part of the global policy. In particular, individual principals declaratively specify which declassifiers they trust so that all information flows implied by the policy can be reasoned about in absence of a particular program. We formalize our approach for a Java-like language and prove a modified form of noninterference which we call noninterference modulo trusted methods. We have implemented our approach as an extension to Jif and provide some of our experience using it to build a secure e-mail client.
Keywords: noninterference modolo trusted methods; declassification; FJifP; information-flow control; Jif; security policy; security-typed languages; trusted declassification

Vertex–transformation streams - Kim,Youngmin; Lee,Chang Ha; Varshney, Amitabh (Graphical Models, 2006)
Recent trends in parallel computer architecture strongly suggest the need to improve the arithmetic intensity (the compute to bandwidth ratio) for greater performance in time-critical applications, such as interactive 3D graphics. At the same time, advances in stream programming abstraction for graphics processors (GPUs) have enabled us to use parallel algorithm design methods for GPU programming. Inspired by these developments, this paper explores the interactions between multiple data streams to improve arithmetic intensity and address the input geometry bandwidth bottleneck for interactive 3D graphics applications. We introduce the idea of creating vertex and transformation streams that represent large point datasets via their interaction. We discuss how to factor such point datasets into a set of source vertices and transformation streams by identifying the most common translations amongst vertices. We accomplish this by identifying peaks in the cross-power spectrum of the dataset in the Fourier domain. We validate our approach by integrating it with a view-dependent point rendering system and show significant improvements in input geometry bandwidth requirements as well as rendering frame rates.
Keywords: Arithmetic intensity; Geometry instancing; Stream programming; Streaming algorithms; Transformation encoding

A Visual Interface for Multivariate Temporal Data: Finding Patterns of Events across Multiple Histories - Fails,J. A; Karlson,A.; Shahamat,L.; Shneiderman, Ben (Visual Analytics Science And Technology, 2006 IEEE Symposium On, 2006)
Finding patterns of events over time is important in searching patient histories, Web logs, news stories, and criminal activities. This paper presents PatternFinder, an integrated interface for query and result-set visualization for search and discovery of temporal patterns within multivariate and categorical data sets. We define temporal patterns as sequences of events with inter-event time spans. PatternFinder allows users to specify the attributes of events and time spans to produce powerful pattern queries that are difficult to express with other formalisms. We characterize the range of queries PatternFinder supports as users vary the specificity at which events and time spans are defined. Pattern Finder's query capabilities together with coupled ball-and-chain and tabular visualizations enable users to effectively query, explore and analyze event patterns both within and across data entities (e.g. patient histories, terrorist groups, Web logs, etc.)
Keywords: ball-and-chain visualization; Chromium; Computer science; Data analysis; data visualisation; Data visualization; Database languages; event pattern discovery; Graphical user interfaces; History; Information Visualization; Medical treatment; multivariate temporal data; Pattern analysis; pattern recognition; PatternFinder integrated interface; Query processing; query visualization; result-set visualization; Spatial databases; tabular visualization; temporal pattern discovery; temporal pattern searching; Temporal query; user interface; User interfaces; visual databases; visual interface

Adaptively-secure, non-interactive public-key encryption - Canetti,R.; Halevi,S.; Katz, Jonathan (Theory of Cryptography, 2005)
Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of already-corrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure. Impossibility holds even if secure data erasure is possible.We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about the frequency of communication between parties. Using this approach, we construct adaptively-secure, completely non-interactive encryption schemes supporting secure encryption of arbitrarily-many messages from arbitrarily-many senders. Our schemes additionally provide forward security and security against chosen-ciphertext attacks.

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

Algorithmic graph minor theory: Decomposition, approximation, and coloring - Demaine,E. D; Hajiaghayi, Mohammad T.; Kawarabayashi,K. (Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, 2005)
At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.
Keywords: algorithmic graph minor theory; approximation algorithm; combinatorial polylogarithmic approximation; computational complexity; constant-factor approximation; graph algorithm; graph coloring; graph colouring; half-integral multicommodity flow; largest grid minor; maximization problem; minimization problem; polynomial-time algorithm; subexponential fixed-parameter algorithm; topological graph theory; treewidth

Applications of SHOP and SHOP2 - Nau, Dana S.; Au,T.-C.; Ilghami,O.; Kuter,U.; Wu,D.; Yaman,F.; Munoz-Avila,H.; Murdock,J. W. (Intelligent Systems, IEEE, 2005)
We design the simple hierarchical ordered planner (SHOP) and its successor, SHOP2, with two goals in mind: to investigate research issues in automated planning and to provide some simple, practical planning tools. SHOP and SHOP2 are based on a planning formalism called hierarchical task network planning. SHOP and SHOP2 use a search-control strategy called ordered task decomposition, which breaks tasks into subtasks and generates the plan's actions in the same order that the plan executor executes them. So, throughout the planning process, the planner can tell what the state of the world at each step of the plan.
Keywords: automated planning; hierarchical task network planning; ordered task decomposition; planning (artificial intelligence); problem solving; search-control strategy; simple hierarchical ordered planner; trees (mathematics); uncertainty handling

Approximation results for probabilistic survivability - Zhang,Y.; Manister,E.; Kraus,S.; V.S. Subrahmanian (Multi-Agent Security and Survivability, 2005 IEEE 2nd Symposium on, 2005)
As multiagent systems (MASs) are increasingly used in industrial applications, the need to make them more robust and resilient against disruption increases dramatically. The author has developed a probabilistic model (assuming complete ignorance of dependencies between node failures) of survivability based on deploying each agent in a MAS on one or more nodes. Finding a deployment that maximizes survivability is highly intractable for two reasons: firstly, computing the survivability of any deployment is intractable, and secondly, going through an exponential number of deployments to find the best one adds another layer of intractability. In this paper, we study what happens when node failures are independent. We show that computing survivability in this environment is still intractable. We propose various heuristics to compute the survivability of a given deployment. We have implemented and tested all these heuristics. We report on the advantages and disadvantages of different heuristics in different environmental settings.
Keywords: application; computing; failure; fault; heuristic; heuristics; industrial; model; multi-agent; multiagent; node; probabilistic; probability; programming; survivability; system; systems; testing; tolerant

An architectural level design methodology for embedded face detection - Kianzad,V.; Saha,S.; Schlessman,J.; Aggarwal,G.; Bhattacharyya, Shuvra S.; Wolf,W.; Chellapa, Rama (Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, 2005)
Face detection and recognition research has attracted great attention in recent years. Automatic face detection has great potential in a large array of application areas, including banking and security system access control, video surveillance, and multimedia information retrieval. In this paper, we discuss an architectural level design methodology for implementation of an embedded face detection system on a reconfigurable system on chip. We present models for performance estimation and validate these models with experimental values obtained from implementing our system on an FPGA platform. This modeling approach is shown to be efficient, accurate, and intuitive for designers to work with. Using this approach, we present several design options that trade-off various architectural features.
Keywords: design space exploration; Face detection; platforms; reconfigurable; system-level models

An Augmented Visual Query Mechanism for Finding Patterns in Time Series Data (2002) - Keogh,Eamonn; Hochheiser,Harry; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Relatively few query tools exist for data exploration and pattern identification in time series data sets. In previous work we introduced Timeboxes. Timeboxes are rectangular, direct-manipulation queries for studying time-series datasets. We demonstrated how Timeboxes can be used to support interactive exploration via dynamic queries, along with overviews of query results and drag-and-drop support for query-by-example. In this paper, we extend our work by introducing Variable Time Timeboxes (VTT). VTTs are a natural generalization of Timeboxes, which permit the specification of queries that allow a degree of uncertainty in the time axis. We carefully motivate the need for these more expressive queries, and demonstrate the utility of our approach on several data sets.
Keywords: Technical Report

Background learning for robust face recognition with PCA in the presence of clutter - Rajagopalan, AN; Chellapa, Rama; Koterba, N.T. (Image Processing, IEEE Transactions on, 2005)
We propose a new method within the framework of principal component analysis (PCA) to robustly recognize faces in the presence of clutter. The traditional eigenface recognition (EFR) method, which is based on PCA, works quite well when the input test patterns are faces. However, when confronted with the more general task of recognizing faces appearing against a background, the performance of the EFR method can be quite poor. It may miss faces completely or may wrongly associate many of the background image patterns to faces in the training set. In order to improve performance in the presence of background, 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 corresponding to the given test image and this space in conjunction with the eigenface space is used to impart robustness. A suitable classifier is derived to distinguish nonface patterns from faces. When tested on images depicting face recognition in real situations against cluttered background, the performance of the proposed method is quite good with fewer false alarms.
Keywords: Automated; Principal Component Analysis; Reproducibility of Results; Sensitivity and Specificity; Signal Processing; Biological; Models; Computer-Assisted; Information Storage and Retrieval; Models; Computer-Assisted; Subtraction Technique; PCA; background learning; clutter; eigenface recognition method; face recognition; linear discriminant; principal component analysis; clutter; eigenvalues and eigenfunctions; face recognition; learning (artificial intelligence); principal component analysis; Algorith; Statistical; Pattern Recognition

Background updating for visual surveillance - Kim,K.; Harwood,D.; Davis, Larry S. (Advances in Visual Computing, 2005)
Scene changes such as moved objects, parked vehicles, or opened/closed doors need to be carefully handled so that interesting foreground targets can be detected along with the short-term background layers created by those changes. A simple layered modeling technique is embedded into a codebook-based background subtraction algorithm to update a background model. In addition, important issues related to background updating for visual surveillance are discussed. Experimental results on surveillance examples, such as unloaded packages and unattended objects, are presented by showing those objects as short-term background layers.

The Bible and multilingual optical character recognition - Kanungo,T.; Resnik, Philip; Mao,S.; Kim,D.W.; Zheng,Q. (Communications of the ACM, 2005)

Bi-Level Hierarchical Layouts for Photo Libraries: Algorithms for Design Optimization with Quantum Content - Kustanowitz,Jack; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
A frequently-used layout for a collection of two-dimensional, fixed aspect-ratio objects, such as photo thumbnails, is the grid, in which rows and columns are configured to match the allowed space. However, in cases where these objects have some group relationship among them, it can be advantageous to show this relationship in the layout, rather than in textual captions. We use an annotated digital photo collection as a case study of an auto-layout technique in which a two-level hierarchy is generated, consisting of a primary, central region with secondary regions (typically 2-12 regions) surrounding it. We show that given specific requirements, this technique is also optimal, in the sense that it will generate the largest size for the objects. Since all objects are the same size we refer to them as quantum content. These algorithms are designed to be real-time, enabling a compelling interactive display as users resize the canvas, or move and resize the primary region. The interactive redisplay also occurs as users add regions or objects to a secondary region.
Keywords: Societal Infrastructure Systems

Bootstrapping parsers via syntactic projection across parallel texts - Hwa,Rebecca; Resnik, Philip; Weinberg, Amy; Cabezas,Clara; Kolak,Okan (Nat. Lang. Eng., 2005)
Broad coverage, high quality parsers are available for only a handful of languages. A prerequisite for developing broad coverage parsers for more languages is the annotation of text with the desired linguistic representations (also known as “treebanking”). However, syntactic annotation is a labor intensive and time-consuming process, and it is difficult to find linguistically annotated text in sufficient quantities. In this article, we explore using parallel text to help solving the problem of creating syntactic annotation in more languages. The central idea is to annotate the English side of a parallel corpus, project the analysis to the second language, and then train a stochastic analyzer on the resulting noisy annotations. We discuss our background assumptions, describe an initial study on the “projectability” of syntactic relations, and then present two experiments in which stochastic parsers are developed with minimal human intervention via projection from English.

Bounds on the efficiency of black-box commitment schemes - Horvitz,O.; Katz, Jonathan (Automata, Languages and Programming, 2005)
Constructions of cryptographic primitives based on general assumptions (e.g., the existence of one-way functions) tend to be less efficient than constructions based on specific (e.g., number-theoretic) assumptions. This has prompted a recent line of research aimed at investigating the best possible efficiency of (black-box) constructions based on general assumptions. Here, we present bounds on the efficiency of statistically-binding commitment schemes constructed using black-box access to one-way permutations; our bounds are tight for the case of perfectly-binding schemes. We present the bounds in an extension of the Impagliazzo-Rudich model; that is, we show that any construction beating our bounds would imply the unconditional existence of a one-way function (from which a commitment scheme could be constructed “from scratch”). Our analysis is the first in the area to pertain directly to an information-theoretic component of the security notion.

Bounds on the efficiency of generic cryptographic constructions - Gennaro,R.; Gertner,Y.; Katz, Jonathan; Trevisan,L. (SIAM Journal on Computing, 2005)
A central focus of modern cryptography is the construction of efficient, “high-level”cryptographic tools (e.g., encryption schemes) from weaker, “low-level” cryptographic primitives (e.g., one-way functions). Of interest are both the existence of such construc- tions, and their efficiency. Here, we show essentially-tight lower bounds on the best possible efficiency of any black-box construction of some fundamental cryptographic tools from the most basic and widely-used cryptographic primitives. Our results hold in an extension of the model introduced by Impagliazzo and Rudich, and improve and extend earlier results of Kim, Simon, and Tetali. We focus on constructions of pseudorandom generators, universal one-way hash functions, and digital signatures based on one-way permutations, as well as constructions of public- and private-key encryption schemes based on trapdoor permutations. In each case, we show that any black-box construction beating our efficiency bound would yield the unconditional existence of a one-way function and thus, in particular, prove P \= NP

Broadcasting on networks of workstations - Khuller, Samir; Kim,Yoo-Ah; Wan,Yung-Chun Justin (Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, 2005)
Broadcasting and multicasting are fundamental operations. In this work we develop algorithms for performing broadcast and multicast in clusters of workstations. In this model, sending a message from one machine to another machine in the same cluster takes 1 time unit, and sending a message to a machine in a different cluster takes C time units. Lowekamp and Beguelin proposed heuristics for this model, but their algorithms may produce broadcast times that are arbitrarily worse than optimal. We develop the first constant factor approximation algorithms for this model. Algorithm LCF (Largest Cluster First) for the basic model is simple, efficient and has a worst case approximation guarantee of 2. We then extend these models to more complex models where we remove the assumption that an unbounded amount of simultaneous communication may happen using the global network. The algorithms for these models build on the LCF method developed for the basic problem. Finally, we develop broadcasting algorithms for the postal model where the sending processor does not block for C time units when the message is in transit. Moreover, we assume that the messages are small and so the bottleneck is the latency.
Keywords: Approximation algorithms; Broadcasting; multicasting

CASPER: an integrated energy-driven approach for task graph scheduling on distributed embedded systems - Kianzad,V.; Bhattacharyya, Shuvra S.; Gang Qu (Application-Specific Systems, Architecture Processors, 2005. ASAP 2005. 16th IEEE International Conference on, 2005)
For multiprocessor embedded systems, the dynamic voltage scaling (DVS) technique can be applied to scheduled applications for energy reduction. DVS utilizes slack in the schedule to slow down processes and save energy. Therefore, it is generally believed that the maximal energy saving is achieved on a schedule with the minimum makespan (maximal slack). Most current approaches treat task assignment, scheduling, and DVS separately. In this paper, we present a framework called CASPER (combined assignment, scheduling, and power-management) that challenges this common belief by integrating task scheduling and DVS under a single iterative optimization loop via genetic algorithm. We have conducted extensive experiments to validate the energy efficiency of CASPER. For homogeneous multiprocessor systems (in which all processors are of the same type), we consider a recently proposed slack distribution algorithm (PDP-SPM) by S. Hua and G. Qu (2005): applying PDP-SPM on the schedule with the minimal makespan gives an average of 53.8% energy saving; CASPER finds schedules with slightly larger makespan but a 57.3% energy saving, a 7.8% improvement. For heterogeneous systems, we consider the power variation DVS (PV-DVS) algorithm by Schmitz et al. (2004), CASPER improves its energy efficiency by 8.2%. Finally, our results also show that the proposed single loop CASPER framework saves 23.3% more energy over GMA+EE-GLSA by Schmitz et al. (2002), the only other known integrated approach with a nested loop that combines scheduling and power management in the inner loop but leaves assignment in the outer loop.
Keywords: CASPER; combined-assignment-scheduling-and-power-management; computational complexity; distributed system; dynamic voltage scaling; embedded systems; energy reduction; genetic algorithm; Genetic algorithms; graph theory; homogeneous multiprocessor system; maximal energy saving; Multiprocessing systems; multiprocessor embedded system; optimization loop; power management; power variation; Processor scheduling; slack distribution algorithm; task assignment; task graph scheduling

Categorized Graphical Overviews for Web Search Results: An Exploratory Study using U.S. Government Agencies as a Meaningful and Stable Structure (2004) - Kules,Bill; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Search engines are very effective at generating long lists of results that are highly relevant to user-provided query terms . But the lack of effective overviews presents challenges to users who seek to understand these results, especially for a complex task such as learning about a topic area, which requires gaining overviews of and exploring large sets of search results, identifying unusual documents, and understanding their context. Categorizing the results into comprehensible visual displays using meaningful and stable classifications can support user exploration and understanding of large sets of search results. This extended abstract presents a set of principles that we are developing for search result visualization. It also describes an exploratory study that investigated categorized overviews of search results for complex search tasks within the domain of U. S. government web sites, using a hierarchy based on the federal government organization.
Keywords: Global Communication Systems

Catergorized Overviews for Web Search Results: Two Exploratory Studies in the US Government Domain - Kules,B.; Shneiderman, Ben (Technical Reports from UMIACS, 2005)
Search engines are very effective at generating extensive lists of results that are highly relevant to user-provided query terms. But the lack of effective overviews challenges users who seek to understand these results, especially for complex tasks such as learning about a new topic, which require gaining overviews of and exploring large sets of search results, identifying unusual documents, and understanding their context. Categorizing the results into comprehensible visual displays using meaningful and stable classifications can support user exploration and understanding of large sets of search results. We conducted two exploratory studies to investigate categorized overviews of search results for complex search tasks within the domain of U. S. government web sites, using a hierarchy based on the federal government organization and a hierarchy generated by automated clustering. First we compared two overview conditions vs. a control (N=18) and found that participants performed better with and preferred the overview conditions. Then we compared automated clustering vs. an overview based on a government hierarchy (N=12) for several task types, and found that several factors appeared to influence the preferred overview. The studies motivated new requirements for the organization of and interaction with web search results: user-selectable organization of results and a lightweight mechanism for customizing hierarchies. The results were also used to refine a set of principles that we are developing for categorized search result visualization.

Chosen-ciphertext security of multiple encryption - Dodis,Y.; Katz, Jonathan (Theory of Cryptography, 2005)
Encryption of data using multiple, independent encryption schemes (“multiple encryption”) has been suggested in a variety of contexts, and can be used, for example, to protect against partial key exposure or cryptanalysis, or to enforce threshold access to data. Most prior work on this subject has focused on the security of multiple encryption against chosen-plaintext attacks, and has shown constructions secure in this sense based on the chosen-plaintext security of the component schemes. Subsequent work has sometimes assumed that these solutions are also secure against chosen-ciphertext attacks when component schemes with stronger security properties are used. Unfortunately, this intuition is false for all existing multiple encryption schemes.Here, in addition to formalizing the problem of chosen-ciphertext security for multiple encryption, we give simple, efficient, and generic constructions of multiple encryption schemes secure against chosen-ciphertext attacks (based on any component schemes secure against such attacks) in the standard model. We also give a more efficient construction from any (hierarchical) identity-based encryption scheme secure against selective-identity chosen plaintext attacks. Finally, we discuss a wide range of applications for our proposed schemes.

Comparative book review: Cryptography: An Introduction by V. V. Yaschenko (American Mathematical Society, 2002); Cryptanalysis of Number Theoretic Ciphers by S.S. Wagstaff, Jr. (Chapman & Hall/CRC Press, 2003); RSA and Public-Key Cryptography by R. A. - Katz, Jonathan (SIGACT News, 2005)
With the growing interest in cryptography --- from students andresearchers as well as from the general public --- there has been a corresponding increase in the number of cryptography textbooks available. Many of these, however, remain somewhat mired in the past, and present cryptography from a pre-1980s point of view. Indeed, there are very few published books which even make an attempt (let alone a successful one) at covering modern cryptography. This unfortunate state of affairs results in a serious lack of books describing the fundamental advances in the field that have taken place since the mid-1980's; this is especially true at the undergraduate and beginning graduate levels, where there is a severe need for suitable texts in this area. The central contributions of modern (i.e., post-1980) cryptography include an emphasis on precise definitions, formalizations of cryptographic goals, and provably-secure constructions of higherlevel tasks (e.g., signatures) from lower-level primitives (e.g., one-way functions). Without precise definitions and rigorous proofs of security, cryptography is reduced to a "game" in which the goal is merely to design a scheme that one's friend or colleague cannot "break". Any exposition of cryptography failing to recognize and emphasize the diffierence between the former and the latter approaches misses a substantial fraction of what current cryptographic research is about, and is a disservice to the field. Sadly, however, almost all cryptography textbooks of which I am aware fall into this category. A classic example of the problems with an "ad-hoc" approach to cryptography is the following simple test I often use to discriminate "good" cryptography books from "poor" ones: flip to the section on digital signatures and see whether it is stated anywhere that "textbook RSA" signatures are completely insecure. It is a simple exercise to show that this is the case (the same holds for "textbook RSA" encryption, but it is somewhat more difficult to demonstrate), yet most books make no mention of this (central!) fact, and instead leave the reader with the impression that secure signature schemes based on the RSA problem are easy to design. Some might argue that there is no place for rigorous definitions and proofs in a book directed toward undergraduates, but I take this misconception as a thinly-guised insult to undergraduate computer science majors. Undergraduates in other majors are taught quantum mechanics, thermodynamics, analysis, and abstract algebra, to name a few, all difficult subjects that are taught rigorously (to varying degrees, perhaps). Why should an undergraduate course on cryptography be expected to be any less rigorous than these? Continuing the disappointing trend discussed above, neither of the first three books reviewed here qualify as (what I would consider) appropriate for introducing the interested reader to the field of cryptography. Cryptography: An Introduction gets a number of things right, but overall is a muddled, poorly written, and disorganized text whose intended audience is unclear. Cryptanalysis. . . is a useful book which I am glad to have on my shelf, but it fails at its stated goal of serving as a suitable text for an introductory cryptography course. It would serve better as a book on elementary number theory (with applications to cryptography, perhaps), and I wish it had been advertised and organized as such. A somewhat similar book, RSA and Public-Key Cryptography suffers from the same criticisms; furthermore, I found its treatment of number theory to be not quite on par with that in Wagstaff's book. In contrast to these, Foundations of Cryptography presents a clear and accurate picture of the foundations underlying modern cryptography; in fact, it is currently the only published book I am aware of which does so. Its primary drawback is that it is likely to be inaccessible to the beginning student; it is more appropriate for a researcher or an advanced graduate student who has previously been exposed to the basics of cryptography, either of whom would benefit from a careful reading of this book cover-to-cover.

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

Comparing the Performance of High-Level Middleware Systems in Shared and Distributed Memory Parallel Environments - Kim,Jik-Soo; Andrade,H.; Sussman, Alan (Parallel and Distributed Processing Symposium, 2005. Proceedings. 19th IEEE International, 2005)
The utilization of toolkits for writing parallel and/or distributed applications has been shown to greatly enhance developer's productivity. Such an approach hides many of the complexities associated with writing these applications, rather than relying solely on programming language aids and parallel library support, such as MPI or PVM. In this work, we evaluate three different middleware systems that have been used to implement a computation and I/O-intensive data analysis application from the domain of computer vision. This study shows the benefits and overheads associated with each of the middleware systems, in different homogeneous computational environments and with different workloads. Our results lead the way toward being able to make better decisions for tuning the application environment, for selecting the appropriate middleware, and also for designing more powerful middleware systems to efficiently build and run highly complex applications in both parallel and distributed computing environments.
Keywords: Application software; Computer science; Computer vision; Data analysis; Distributed computing; distributed computing environment; distributed memory parallel environment; distributed shared memory systems; Educational institutions; high-level middleware system; I/O-intensive data analysis application; Libraries; Middleware; parallel computing environment; parallel library support; parallel memories; programming language; programming languages; Runtime environment; shared memory parallel environment; Writing

A Comparison of Voice Controlled and Mouse Controlled Web Browsing (2000) - Christian,Kevin; Kules,Bill; Shneiderman, Ben; Youssef,Adel (Institute for Systems Research Technical Reports, 2005)
Voice controlled web browsers allow users to navigate by speaking the text of a link or an associated number instead of clicking with a mouse. One such browser is Conversa, by Conversational Computing. This within subjects study with 18 subjects compared voice browsing with traditional mouse-based browsing. It attempted to identify which of three common hypertext forms (linear slide show, grid/tiled map, and hierarchical menu) are well suited to voice navigation, and whether voice navigation is helped by numbering links. The study shows that voice control adds approximately 50 percent to the performance time for certain types of tasks. Subjective satisfaction measures indicate that for voice browsing, textual links are preferable to numbered links.
Keywords: Technical Report

On constructing universal one-way hash functions from arbitrary one-way functions - Katz, Jonathan; Koo,C. Y (Journal of Cryptology, 2005)
A fundamental result in cryptography is that a digital signature scheme can be constructedfrom an arbitrary one-way function. A proof of this somewhat surprising statement follows from two results: first, Naor and Yung defined the notion of universal one-way hash functions and showed that the existence of such hash functions implies the existence of secure digital signature schemes. Subsequently, Rompel showed that universal one-way hash functions could be constructed from arbitrary one-way functions. Unfortunately, despite the importance of the result, a complete proof of the latter claim has never been published. In fact, a careful reading of Rompel’s original conference publication reveals a number of errors in many of his arguments which have (seemingly) never been addressed. We provide here what is — as far as we know — the first complete write-up of Rompel’s proof that universal one-way hash functions can be constructed from arbitrary one-way functions.

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

Crisis and opportunity in computer science - Klawe,Maria; Shneiderman, Ben (Commun. ACM, 2005)
The future of the field depends on winning back student enrollment, public interest in technology, and government research funding.

Critical Factors Influencing the Occurrence of Vibrio Cholerae in the Environment of Bangladesh - Huq,Anwar; Sack,R. Bradley; Nizam,Azhar; Longini,Ira M.; Nair,G. Balakrish; Ali,Afsar; Morris,J. Glenn; Khan,M. N. Huda; Siddique,A. Kasem; Yunus,Mohammed; Albert,M. John; Sack,David A.; et al. (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2005)
The occurrence of outbreaks of cholera in Africa in 1970 and in Latin America in 1991, mainly in coastal communities, and the appearance of the new serotype Vibrio cholerae O139 in India and subsequently in Bangladesh have stimulated efforts to understand environmental factors influencing the growth and geographic distribution of epidemic Vibrio cholerae serotypes. Because of the severity of recent epidemics, cholera is now being considered by some infectious disease investigators as a “reemerging” disease, prompting new work on the ecology of vibrios. Epidemiological and ecological surveillance for cholera has been under way in four rural, geographically separated locations in Bangladesh for the past 4 years, during which both clinical and environmental samples were collected at biweekly intervals. The clinical epidemiology portion of the research has been published (Sack et al., J. Infect. Dis. 187:96-101, 2003). The results of environmental sampling and analysis of the environmental and clinical data have revealed significant correlations of water temperature, water depth, rainfall, conductivity, and copepod counts with the occurrence of cholera toxin-producing bacteria (presumably V. cholerae). The lag periods between increases or decreases in units of factors, such as temperature and salinity, and occurrence of cholera correlate with biological parameters, e.g., plankton population blooms. The new information on the ecology of V. cholerae is proving useful in developing environmental models for the prediction of cholera epidemics.

Data hiding in compiled program binaries for enhancing computer system performance - Swaminathan,A.; Mao,Y.; Wu,M.; Kailas,K. (Information Hiding, 2005)
Information hiding has been studied in many security applications such as authentication, copyright management and digital forensics. In this work, we introduce a new application where successful information hiding in compiled program binaries could bring system-wide performance improvements. Our goal is to enhance computer system performance by providing additional information to the processor, without changing the instruction set architecture. We first analyze the statistics of typical programs to demonstrate the feasibility of hiding data in them. We then propose several techniques to hide a large amount of data in the operand fields with very low computation and storage requirements during the extraction process. The data embedding is made reversible to recover the original instructions and to ensure the correct execution of the computer program. Our experiments on the SPEC CPU2000 benchmark programs show that up to 110K bits of information can be embedded in large programs with as little as 3K bits of additional run-time memory in the form of a simple look-up table.

Data Redistribution and Remote Method Invocation in Parallel Component Architectures - Bertrand,Felipe; Bramley,Randall; Sussman, Alan; Bernholdt,David E.; Kohl,James A.; Larson,Jay W.; Damevski,Kostadin B. (Parallel and Distributed Processing Symposium, International, 2005)
With the increasing availability of high-performance massively parallel computer systems, the prevalence of sophisticated scientific simulation has grown rapidly. The complexity of the scientific models being simulated has also evolved, leading to a variety of coupled multi-physics simulation codes. Such cooperating parallel programs require fundamentally new interaction capabilities, to efficiently exchange parallel data structures and collectively invoke methods across programs. So-called "M?N" research, as part of the Common Component Architecture (CCA) effort, addresses these special and challenging needs, to provide generalized interfaces and tools that support flexible parallel data redistribution and parallel remote method invocation. Using this technology, distinct simulation codes with disparate distributed data decompositions can work together to achieve greater scientific discoveries.

On degree constrained shortest paths - Khuller, Samir; Lee,K.; Shayman,M. (Algorithms–ESA 2005, 2005)
Traditional shortest path problems play a central role in both the design and use of communication networks and have been studied extensively. In this work, we consider a variant of the shortest path problem. The network has two kinds of edges, “actual” edges and “potential” edges. In addition, each vertex has a degree/interface constraint. We wish to compute a shortest path in the graph that maintains feasibility when we convert the potential edges on the shortest path to actual edges. The central difficulty is when a node has only one free interface, and the unconstrained shortest path chooses two potential edges incident on this node. We first show that this problem can be solved in polynomial time by reducing it to the minimum weighted perfect matching problem. The number of steps taken by this algorithm is O(|E|2 log |E|) for the single-source single-destination case. In other words, for each v we compute the shortest path P v such that converting the potential edges on P v to actual edges, does not violate any degree constraint. We then develop more efficient algorithms by extending Dijkstra’s shortest path algorithm. The number of steps taken by the latter algorithm is O(|E||V|), even for the single-source all destination case.

Designing a Metadata-Driven Visual Information Browser for Federal Statistics (2003) - Kules,Bill; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
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.
Keywords: Technical Report

Direct Annotation: A Drag-and-Drop Strategy for Labeling Photos (2000) - Shneiderman, Ben; Kang,Hyunmo (Institute for Systems Research Technical Reports, 2005)
Annotating photos is such a time-consuming, tedious and error-prone data entry task that it discourages most owners of personal photo libraries. By allowing users to drag labels such as personal names from a scrolling list and drop them on a photo, we believe we can make the task faster, easier and more appealing. Since the names are entered in a database, searching for all photos of a friend or family member is dramatically simplified. We describe the user interface design and the database schema to support direct annotation, as implemented in our PhotoFinder prototype.
Keywords: Technical Report

Distributed Algorithms for Dynamic Survivability of Multiagent Systems - Subrahmanian,V.; Kraus,Sarit; Zhang,Yingqian (Computational Logic in Multi-Agent SystemsComputational Logic in Multi-Agent Systems, 2005)
Though multiagent systems (MASs) are being increasingly used, few methods exist to ensure survivability of MASs. All existing methods suffer from two flaws. First, a centralized survivability algorithm (CSA) ensures survivability of the MAS – unfortunately, if the node on which the CSA exists goes down, the survivability of the MAS is questionable. Second, no mechanism exists to change how the MAS is deployed when external factors trigger a re-evaluation of the survivability of the MAS. In this paper, we present three algorithms to address these two important problems. Our algorithms can be built on top of any CSA. Our algorithms are completely distributed and can handle external triggers to compute a new deployment. We report on experiments assessing the efficiency of these algorithms.
Keywords: Computer; Science

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

Dynamic configuration of dataflow graph topology for DSP system design - Ko,D. I; Bhattacharyya, Shuvra S. (Proc. of the Int. Conf. on Acoustics, Speech, and Signal Processing, 2005)

Dynamic Layout Management in a Multimedia Bulletin Board (2002) - Kang,Hyunmo; Shneiderman, Ben; Wolff,Gregory J (Institute for Systems Research Technical Reports, 2005)
This paper proposes a novel user interface to manage the dynamic layout of multimedia objects in the Multimedia Bulletin Board (MBB) system. The MBB has been designed and implemented as a prototype of an asynchronous communication system that enables rich communication and collaboration among users of multimedia objects such as text, image, moving picture, sound, voice, web, office document, and other files. The layout properties of the multimedia objects on a board (e.g. x-y position, size, z-order, partial occlusion, explicit and implicit links, etc.) show important and useful information on the user dynamics occurring within a board. However, a fixed layout created and edited by multiple users may prevent users from recognizing and identifying useful information. This paper resolves this problem with a novel user-controlled layout strategy made visible with dynamic layout templates (DLT). Users can reorganize the objects to extract meaningful information related to time, source, geographic location, or topic.
Keywords: Technical Report

Dynamic network resource allocation using multimedia content features and ... - M. Wu; Joyce,Robert A.; Vetro,Anthony; Wong,Hau-San; Guan,Ling; Kung,Sun-Yuan (2005)
A method for dynamically allocating network resources while transferring multimedia at variable bit-rates in a network extracts first content features from the multimedia to determine renegotiation points and observation periods. Second content features and traffic features are extracted from the multimedia bit stream during the observation periods. The second content features and the traffic features are combined in a neural network to predict the network resources to be allocated at the renegotiation points.

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

Exploring Personal Media: A Spatial Interface Supporting User-Defined Semantic Regions (2004) - Kang,Hyunmo; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Graphical mechanisms for spatially organizing personal media data could enable users to fruitfully apply their mental models. This paper introduces Semantic Regions, an innovative way for users to construct mental models by drawing regions on 2D space and specifying the semantics for each region. Then users can apply personal ontologies to personal media data using the fling-and-flock metaphor. This allows photos (or other personal media) to be dragged to the display and automatically grouped according to time, geography, family trees, groups of friends, or other conceptual maps. The prototype implementation for Semantic Regions, MediaFinder, was validated with two usability tests for usage and construction of user-defined mental models. Applications and extensions are discussed.
Keywords: Technical Report

Finite-State Language resources and Language Processing - Hale,K.; Keyser,S.J.; Hutchins,W.J.; Habash,N.; Dorr, Bonnie J; Traum,D. (Machine Translation, 2005)

Forensic recovery of hard disk data by using the spin-stand imaging technique - Tse,Chun; Krafft,Charles; Mayergoyz, Issak D; McAvoy,Patrick; Tseng,Chun-Yang (Proceedings of SPIE, 2005)
An ex-situ technique for the drive-independent forensic recovery of data from failed hard drives has been developed.For drives which have suffered damage from a head crash or other mechanical problems and cannot be resuscitatedusing standard software, firmware, or part-replacement techniques, there is currently no commercially available meansto recover the data, even though the files are still stored on the magnetic disks. Here, we report on the results of a spinstandimaging based technology, where the failed disk is removed from its native drive, placed on a spin-stand, andscanned with a giant magnetoresistive head. After track centering, track following, signal detection, data decoding, errorcorrection, and sector mapping, the otherwise unrecoverable data can be retrieved to the computer operating system.Spin-stand based data imaging has the potential to provide recovery at data rates approaching those in the native driveand is a truly drive-independent method to recover hard disk data in a time-efficient manner.

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

Gait-based human identification using appearance matching - Kale, A.; Cuntoor, N.; Yegnanarayana,B.; Rajagopalan, A.; Chellapa, Rama (Optical and Digital Techniques for Information Security, 2005)
In this chapter, we present an appearance-based approach for recognizing human gait. Given the gait video of an individual, the images are binarized and the width of the outer contour of the silhouette of that individual is obtained for each image frame. Several gait features are derived from this basic width vector. Temporally ordered sequences of the feature vectors are then used to represent the gait of a person. While matching the feature templates for recognition, dynamic time-warping (DTW), which is a nonlinear time-normalization technique, is used to deal with naturally occurring changes in the walking speeds of individuals. The performance of the proposed method is tested on indoor as well as outdoor gait databases, and the efficacy of different gait features and their noise resilience is studied. The experiments also demonstrate the effect of change in the viewing angle and frame rate of data capture on the accuracy of gait recognition.