Statistical point geometry - Kalaiah,Aravind; Varshney, Amitabh (Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, 2003)
We propose a scheme for modeling point sample geometry with statistical analysis. In our scheme we depart from the current schemes that deterministically represent the attributes of each point sample. We show how the statistical analysis of a densely sampled point model can be used to improve the geometry bandwidth bottleneck and to do randomized rendering without sacrificing visual realism. We first carry out a hierarchical principal component analysis (PCA) of the model. This stage partitions the model into compact local geometries by exploiting local coherence. Our scheme handles vertex coordinates, normals, and color. The input model is reconstructed and rendered using a probability distribution derived from the PCA analysis. We demonstrate the benefits of this approach in all stages of the graphics pipeline: (1) orders of magnitude improvement in the storage and transmission complexity of point geometry, (2) direct rendering from compressed data, and (3) view-dependent randomized rendering.

A Survey of Shape Similarity Assessment Algorithms for Product Design and Manufacturing Applications - Cardone, Antonio; Gupta, Satyandra K.; Karnik,Mukul (Journal of Computing and Information Science in EngineeringJ. Comput. Inf. Sci. Eng., 2003)
Keywords: CAD; computational geometry; production engineering computing; spatial reasoning

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

TelegraphCQ: An architectural status report - Krishnamurthy, S.; Chandrasekaran,S.; Cooper,O.; Deshpande, Amol; Franklin,M.J.; Hellerstein,J. M; Hong,W.; Madden,S.; Reiss,F.; Shah,M. A (IEEE Data Engineering Bulletin, 2003)

TelegraphCQ: continuous dataflow processing - Chandrasekaran,Sirish; Cooper,Owen; Deshpande, Amol; Franklin,Michael J.; Hellerstein,Joseph M.; Wei Hong; Krishnamurthy,Sailesh; Madden,Samuel R.; Reiss,Fred; Shah,Mehul A. (Proceedings of the 2003 ACM SIGMOD international conference on Management of data, 2003)

Thwarting Web Censorship with Untrusted Messenger Discovery - Feamster, Nick; Balazinska,Magdalena; Wang,Winston; Balakrishnan,Hari; Karger,David (Privacy Enhancing TechnologiesPrivacy Enhancing Technologies, 2003)
All existing anti-censorship systems for the Web rely on proxies to grant clients access to censored information. Therefore, they face the proxy discovery problem : how can clients discover the proxies without having the censor discover and block these proxies? To avoid widespread discovery and blocking, proxies must not be widely published and should be discovered in-band. In this paper, we present a proxy discovery mechanism called keyspace hopping that meets this goal. Similar in spirit to frequency hopping in wireless networks, keyspace hopping ensures that each client discovers only a small fraction of the total number of proxies. However, requiring clients to independently discover proxies from a large set makes it practically impossible to verify the trustworthiness of every proxy and creates the possibility of having untrusted proxies. To address this, we propose separating the proxy into two distinct components—the messenger , which the client discovers using keyspace hopping and which simply acts as a gateway to the Internet; and the portal , whose identity is widely-published and whose responsibility it is to interpret and serve the client’s requests for censored content. We show how this separation, as well as in-band proxy discovery, can be applied to a variety of anti-censorship systems.
Keywords: Computer science

Toward secure key distribution in truly ad-hoc networks - Khalili,A.; Katz, Jonathan; Arbaugh, William A. (Applications and the Internet Workshops, 2003. Proceedings. 2003 Symposium on, 2003)
Ad-hoc networks - and in particular wireless mobile ad-hoc networks $have unique characteristics and constraints that make traditional cryptographic mechanisms and assumptions inappropriate. In particular it may not be warranted to assume pre-existing shared secrets between members of the network or the presence of a common PKI. Thus, the issue of key distribution in ad-hoc networks represents an important problem. Unfortunately, this issue has been largely ignored; as an example, most protocols for secure ad-hoc routing assume that key distribution has already taken place. Traditional key distribution schemes either do not apply in an ad-hoc scenario or are not efficient enough for small, resource-constrained devices. We propose to combine efficient techniques from identity-based (ID-based) and threshold cryptography to provide a mechanism that enables flexible and efficient key distribution while respecting the constraints of ad-hoc networks. We also discuss the available mechanisms and their suitability for the proposed task.
Keywords: ad; ad-hoc; cryptography; distribution; hoc; identity-based; key; mobile; network; networks; routing; secure; security; Telecommunication; threshold; wireless

Towards a view invariant gait recognition algorithm - Kale, A.; Chowdhury, A.K.R.; Chellapa, Rama (Proceedings. IEEE Conference on Advanced Video and Signal Based Surveillance, 2003., 2003)
Human gait is a spatio-temporal phenomenon and typifies the motion characteristics of an individual. The gait of a person is easily recognizable when extracted from a side-view of the person. Accordingly, gait-recognition algorithms work best when presented with images where the person walks parallel to the camera image plane. However, it is not realistic to expect this assumption to be valid in most real-life scenarios. Hence, it is important to develop methods whereby the side-view can be generated from any other arbitrary view in a simple, yet accurate, manner. This is the main theme of the paper. We show that if the person is far enough from the camera, it is possible to synthesize a side view (referred to as canonical view) from any other arbitrary view using a single camera. Two methods are proposed for doing this: (i) using the perspective projection model; (ii) using the optical flow based structure from motion equations. A simple camera calibration scheme for this method is also proposed. Examples of synthesized views are presented. Preliminary testing with gait recognition algorithms gives encouraging results. A by-product of this method is a simple algorithm for synthesizing novel views of a planar scene.
Keywords: (access; algorithm; analysis; Biometrics; biometrics; Calibration; calibration; camera; canonical; control); equations; flow; Gait; gait; human; image; invariant; model; MOTION; optical; perspective; phenomenon; projection; recognition; scheme; sequences; spatio-temporal; view; view

Towards On-chip Fault-tolerant Communication - Tudor Dumitras; Kerner, Sam; M\uarculescu, Radu (ASP-DAC '03 Proceedings of the 2003 Asia and South Pacific Design Automation Conference, 2003)
As CMOS technology scales down into the deep-submicron (DSM) domain, devices and interconnects are subject to new types of malfunctions and failures that are harder to predict and avoid with the current system-on-chip (SoC) design methodologies. Relaxing the requirement of 100% correctness in operation drastically reduces the costs of design but, at the same time, requires SoCs be designed with some degree of system-level fault-tolerance. In this paper, we introduce a high-level model of DSM failure patterns and propose a new communication paradigm for SoCs, namely stochastic communication. Specifically, for a generic tile-based architecture, we propose a randomized algorithm which not only separates computation from communication, but also provides the required fault-tolerance to on-chip failures. This new technique is easy and cheap to implement in SoCs that integrate a large number of communicating IP cores.

On the use of flow migration for handling short-term overloads - Kuo,Kuo-Tung; Phuvoravan,S.; Bhattacharjee, Bobby; Jun La,R.; Shayman,M.; Chang,Hyeong Soo (Global Telecommunications Conference, 2003. GLOBECOM '03. IEEE, 2003)
In this work, we investigate flow migration as a mechanism to sustain QoS to network users during short-term overloads in the context of an MPLS IP network. We experiment with three different control techniques: static long-term optimal mapping of flows to LSPs; on-line locally optimal mapping of flows to LSPs at flow set-up time; and dynamic flow migration in response to transient congestion. These techniques are applicable over different timescales, have different run-time overheads, and require different levels of monitoring and control software inside the network. We present results both from detailed simulations and a complete implementation using software IP routers. We use voice-over-IP as our test application, and show that if end-to-end quality is to be maintained during short unpredictable bursts of high load, then a fast-timescale control such as migration is required.
Keywords: computing; CONGESTION; congestion; CONTROL; control; dynamic; end-to-end; engineering; fast-timescale; flow; Internet; IP; label; long-term; mapping; migration; MPLS; multiprotocol; network; network; networks; of; optimal; overloads; protocol; QoS; QUALITY; quality; routers; routing; service; set-up; short-term; software; software; static; switching; Telecommunication; telephony; time; transient; voice-over-IP

Use of OCR for Rapid Construction of Bilingual Lexicons - Karagol-Ayan,Burcu; David Doermann; Dorr, Bonnie J (University of Maryland, College Park, 2003)
This paper describes an approach to analyzing the lexical structure of OCRed bilingual dictionaries to construct resources suited for machine translation of low-density languages, where online resources are limited. A rule-based and an HMM-based method are used for rapid construction of MT lexicons based on systematic structural clues provided in the original dictionary. We evaluate the effectiveness of our techniques, concluding that: (1) the rule-based method performs better on dictionaries with a simple structure; (2) the stochastic method performs better on dictionaries with an enriched structure; (3) regardless of the degree of dictionary richness, the rule-based method gives better results for phrasal entries than for single-word entries; and (4) Our resulting bilingual lexicons are comprehensive enough to provide reasonable MT results when compared to human-constructed lexicons.

User interface evaluation and empirically-based evolution of a prototype experience management tool - Seaman,C.B; Mendonca,M.G.; Basili, Victor R.; Kim,Y. M (Software Engineering, IEEE Transactions on, 2003)
Experience management refers to the capture, structuring, analysis, synthesis, and reuse of an organization's experience in the form of documents, plans, templates, processes, data, etc. The problem of managing experience effectively is not unique to software development, but the field of software engineering has had a high-level approach to this problem for some time. The Experience Factory is an organizational infrastructure whose goal is to produce, store, and reuse experiences gained in a software development organization. This paper describes The Q-Labs Experience Management System (Q-Labs EMS), which is based on the Experience Factory concept and was developed for use in a multinational software engineering consultancy. A critical aspect of the Q-Labs EMS project is its emphasis on empirical evaluation as a major driver of its development and evolution. The initial prototype requirements were grounded in the organizational needs and vision of Q-Labs, as were the goals and evaluation criteria later used to evaluate the prototype. However, the Q-Labs EMS architecture, data model, and user interface were designed to evolve, based on evolving user needs. This paper describes this approach, including the evaluation that was conducted of the initial prototype and its implications for the further development of systems to support software experience management.
Keywords: data; development; empirical; EMS; engineering; evaluation; experience; experience; Factory; interface; interfaces; knowledge; management; management; model; models; organization; performance; prototype; Q-Labs; re-engineering; reusability; reuse; software; system; systems; tool; user

Video Analysis for Pervasive Environments - David Doermann; Karunanidhi,A. (ICME, 2003)

Video based rendering of planar dynamic scenes - Kale, A.; Chowdhury, A.K.R.; Chellapa, Rama (Multimedia and Expo, 2003. ICME '03. Proceedings. 2003 International Conference on, 2003)
In this paper, we propose a method to synthesize arbitrary views of a planar scene from a monocular video sequence of it. The 3-D direction of motion of the object is robustly estimated from the video sequence. Given this direction any other view of the object can be synthesized through a perspective projection approach, under assumptions of planarity. If the distance of the object from the camera is large, a planar approximation is reasonable even for non-planar scenes. Such a method has many important applications, one of them being gait recognition where a side view of the person is required. Our method can be used to synthesize the side-view of the person in case he/she does not present a side view to the camera. Since the planarity assumption is often an approximation, the effects of non-planarity can lead to inaccuracies in rendering and needs to be corrected for. Regions where this happens are examined and a simple technique based on weak perspective approximation is proposed to offset rendering inaccuracies. Examples of synthesized views using our method and performance evaluation are presented.
Keywords: (computer; 3D; analysis; approximation; based; camera; cameras; direction; dynamic; graphics); image; monocular; MOTION; perspective; planar; processing; rendering; rendering; scenes; sequence; sequences; signal; video; weak

Video synthesis of arbitrary views for approximately planar scenes - Chowdhury, A.K.R.; Kale, A.; Chellapa, Rama (Acoustics, Speech, and Signal Processing, 2003. Proceedings. (ICASSP '03). 2003 IEEE International Conference on, 2003)
In this paper, we propose a method to synthesize arbitrary views of a planar scene, given a monocular video sequence. The method is based on the availability of knowledge of the angle between the original and synthesized views. Such a method has many important applications, one of them being gait recognition. Gait recognition algorithms rely on the availability of an approximate side-view of the person. From a realistic viewpoint, such an assumption is impractical in surveillance applications and it is of interest to develop methods to synthesize a side view of the person, given an arbitrary view. For large distances from the camera, a planar approximation for the individual can be assumed. In this paper, we propose a perspective projection approach for recovering the direction of motion of the person purely from the video data, followed by synthesis of a new video sequence at a different angle. The algorithm works purely in the image and video domain, though 3D structure plays an implicit role in its theoretical justification. Examples of synthesized views using our method and performance evaluation are presented.
Keywords: (access; 3D; applications; approach; approximately; approximation; arbitrary; Biometrics; control); data; direction; estimation; evaluation; Gait; image; monocular; MOTION; performance; perspective; planar; processing; projection; recognition; recovery; scenes; sequence; sequences; side; signal; structure; Surveillance; surveillance; synthesis; synthesized; video; view; views

VIDEO SYNTHESIS OF ARBITRARY VIEWS FOR APPROXIMATELY PLANAR SCENES - Chowdhury, A.R.; Kale, A.; Chellapa, Rama (IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 2003)

The virtual microscope - Catalyurek,U.; Beynon,M. D; Chang,Chialin; Kurc, T.; Sussman, Alan; Saltz, J. (IEEE Transactions on Information Technology in Biomedicine, 2003)
We present the design and implementation of the virtual microscope, a software system employing a client/server architecture to provide a realistic emulation of a high power light microscope. The system provides a form of completely digital telepathology, allowing simultaneous access to archived digital slide images by multiple clients. The main problem the system targets is storing and processing the extremely large quantities of data required to represent a collection of slides. The virtual microscope client software runs on the end user's PC or workstation, while database software for storing, retrieving and processing the microscope image data runs on a parallel computer or on a set of workstations at one or more potentially remote sites. We have designed and implemented two versions of the data server software. One implementation is a customization of a database system framework that is optimized for a tightly coupled parallel machine with attached local disks. The second implementation is component-based, and has been designed to accommodate access to and processing of data in a distributed, heterogeneous environment. We also have developed caching client software, implemented in Java, to achieve good response time and portability across different computer platforms. The performance results presented show that the Virtual Microscope systems scales well, so that many clients can be adequately serviced by an appropriately configured data server.
Keywords: biomedical optical imaging; client software; client/server architecture; Computer architecture; Computer Graphics; computer platforms; Computer simulation; Concurrent computing; configured data server; data server software; database management systems; database software; Database systems; digital slide images; digital telepathology; diseases; emulation; Environment; Equipment Design; Equipment Failure Analysis; high power light microscope; Image databases; Image Enhancement; Image Interpretation, Computer-Assisted; Image retrieval; Information retrieval; Information Storage and Retrieval; java; local disks; microscope image data; Microscopy; multiple clients; optical microscopy; PACS; software; Software design; software system; Software systems; Systems Integration; Telepathology; User-Computer Interface; virtual microscope design; Virtual reality; Workstations

Visual Information Management for Network Configuration - Kumar,Harsha; Plaisant, Catherine; Teittinen,Marko; Shneiderman, Ben (The Craft of Information VisualizationThe Craft of Information Visualization, 2003)
Current network management systems rely heavily on forms in their user interfaces. The interfaces reflect the intricacies of the network hardware components but provide little support for guiding users through tasks. There is a scarcity of useful graphical visualizations and decision-support tools.

Visualizing websites using a hierarchical table of contents browser: WebTOC - Plaisant, Catherine; Marchionini,G.; Komlodi,A. (The craft of information visualization: readings and reflectionsThe craft of information visualization: readings and reflections, 2003)

What makes a good answer? The role of context in question answering - Jimmy Lin; Quan,D.; Sinha,V.; Bakshi,K.; Huynh,D.; Katz,B.; Karger,D. R (Human-Computer Interaction, Interact '03, 2003)

Which comes first, usability or utility? - Grinstein,Georges; Kobsa,Alfred; Plaisant, Catherine; Shneiderman, Ben; Stasko,John T (Proceedings of the 14th IEEE Visualization 2003 (VIS'03), 2003)

The World's Information in Digital Libraries - Plaisant, Catherine; Marchimini,G.; Bruns,T.; Komlodi,A.; Campbell,L.; Rose,A.; Ding,G.M.; Beale Jr,J.; Nolet,V.; Shneiderman, Ben; others (The craft of information visualization: readings and reflectionsThe craft of information visualization: readings and reflections, 2003)

1.375-Approximation Algorithm for Sorting by Reversals - Berman,Piotr; Hannenhalli, Sridhar; Karpinski,Marek (Algorithms — ESA 2002Algorithms — ESA 2002, 2002)
Analysis of genomes evolving by inversions leads to a general combinatorial problem of Sorting by Reversals , MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. Following a series of preliminary results, Hannenhalli and Pevzner developed the first exact polynomial time algorithm for the problem of sorting signed permutations by reversals, and a polynomial time algorithm for a special case of unsigned permutations. The best known approximation algorithm for MIN-SBR, due to Christie, gives a performance ratio of 1.5. In this paper, by exploiting the polynomial time algorithm for sorting signed permutations and by developing a new approximation algorithm for maximum cycle decomposition of breakpoint graphs, we design a new 1.375-algorithm for the MIN-SBR problem.

3D face reconstruction from video using a generic model - Chowdhury, A.R.; Chellapa, Rama; Krishnamurthy, S.; Vo, T. (Multimedia and Expo, 2002. ICME '02. Proceedings. 2002 IEEE International Conference on, 2002)
Reconstructing a 3D model of a human face from a video sequence is an important problem in computer vision, with applications to recognition, surveillance, multimedia etc. However, the quality of 3D reconstructions using structure from motion (SfM) algorithms is often not satisfactory. One common method of overcoming this problem is to use a generic model of a face. Existing work using this approach initializes the reconstruction algorithm with this generic model. The problem with this approach is that the algorithm can converge to a solution very close to this initial value, resulting in a reconstruction which resembles the generic model rather than the particular face in the video which needs to be modeled. We propose a method of 3D reconstruction of a human face from video in which the 3D reconstruction algorithm and the generic model are handled separately. A 3D estimate is obtained purely from the video sequence using SfM algorithms without use of the generic model. The final 3D model is obtained after combining the SfM estimate and the generic model using an energy function that corrects for the errors in the estimate by comparing local regions in the two models. The optimization is done using a Markov chain Monte Carlo (MCMC) sampling strategy. The main advantage of our algorithm over others is that it is able to retain the specific features of the face in the video sequence even when these features are different from those of the generic model. The evolution of the 3D model through the various stages of the algorithm is presented.
Keywords: 3D; algorithm; algorithms; analysis; Carlo; chain; Computer; Face; from; function; generic; human; image; Markov; MCMC; methods; model; Monte; MOTION; optimisation; OPTIMIZATION; processes; processing; recognition; reconstruction; reconstruction; sampling; sequence; sequences; SfM; signal; structure; surveillance; video; vision

AAAI 2002 Workshops - Blake,Brian; Haigh,Karen; Hexmoor,Henry; Falcone,Rino; Soh,Leen-Kiat; Baral,Chitta; McIlraith,Sheila; Gmytrasiewicz,Piotr; Parsons,Simon; Malaka,Rainer; Krueger,Antonio; Bouquet,Paolo; et al. (AI Magazine, 2002)

Active Proxy-G: Optimizing the query execution process in the Grid - Andrade,H.; Kurc, T.; Sussman, Alan; Saltz, J. (Proceedings of the 2002 ACM/IEEE conference on Supercomputing, 2002)

AD (Attacker Defender) Game - Kochut,Andrzej; Agrawala, Ashok K.; Larsen,Ronald L; A. Udaya Shankar (Technical Reports from UMIACS, UMIACS-TR-2001-45, 2002)
Information Dynamics is a framework for agent-based systems that givesa central position to the role of information, time, and the value of information. We illustrate system design in the Information Dynamics Framework by developing an intelligence game called AD involving attackers, defenders and targets operating in some space of locations. The goal of the attackers is to destroy all targets. Target destruction takes place when the number of attackers in the target's neighborhood exceeds the number of defenders in this neighborhood by a value WINNING_DIFFERENCE. The goal of defenders is to prevent attackers from achieving their goal. (Also UMIACS-TR-2001-45)
Keywords: Technical Report

An adaptive framework for tunable consistency and timeliness using replication - Krishnamurthy, S.; Sanders,W. H.; Michel Cukier (2002)
One well-known challenge in using replication to service multiple clients concurrently is that of delivering a timely and consistent response to the clients. In this paper, we address this problem in the context of client applications that have specific temporal and consistency requirements. These applications can tolerate a certain degree of relaxed consistency, in exchange for better response time. We propose a flexible QoS model that allows these clients to specify their temporal and consistency constraints. In order to select replicas to serve these clients, we need to control of the inconsistency of the replicas, so that we have a large enough pool of replicas with the appropriate state to meet a client's timeliness, consistency, and dependability requirements. We describe an adaptive framework that uses lazy update propagation to control the replica inconsistency and employs a probabilistic approach to select replicas dynamically to service a client, based on its QoS specification. The probabilistic approach predicts the ability of a replica to meet a client's QoS specification by using the performance history collected by monitoring the replicas at runtime. We conclude with experimental results based on our implementation.
Keywords: adaptive framework; concurrent multiple client service; consistency requirements; dependability requirements; distributed object management; flexible QoS model; lazy update propagation; performance history; probabilistic approach; Protocols; quality of service; replication; temporal requirements; timely consistent response; tunable consistency; tunable timeliness

Agents dealing with time and uncertainty - Dix,Jürgen; Kraus,Sarit; V.S. Subrahmanian (Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, 2002)
Situated agents in the real world need to handle the fact that events occur frequently, as well as the fact that the agent typically has uncertain knowledge about what is true in the world. The ability to reason about both time and uncertainty is therefore very important. In this paper, we develop a formal theory of agents that can reason about both time and uncertainty. The theory extends the notion of agents described in [10, 21] and proposes the notion of temporal probabilistic (or TP) agents. A formal semantics for TP-agents is proposed - this semantics is described via structures called feasible TP-status interpretations (FTPSI's). TP-agents continuously evaluate changes (in the state of the environment they are situated in) and compute appropriate FTPSI's. For a class of TP-agents called positive TP-agents, we develop a provably sound and complete procedure to compute FTPSI's.
Keywords: formalisms and logics; logic programming; probabilistic/uncertain reasoning; temporal reasoning; theories of agency

Algorithmic issues in modeling motion - Agarwal,Pankaj K.; Guibas,Leonidas J.; Edelsbrunner,Herbert; Erickson,Jeff; Isard,Michael; Har-Peled,Sariel; Hershberger,John; Jensen,Christian; Kavraki,Lydia; Koehl,Patrice; Lin,Ming; Manocha,Dinesh; et al. (ACM Comput. Surv., 2002)
This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines.
Keywords: computational geometry; Computer vision; mobile networks; modeling; molecular biology; motion modeling; physical simulation; robotoics; spatio-temporal databases

Annotating the semantic web using natural language - Katz,Boris; Jimmy Lin (Proceedings of the 2nd workshop on NLP and XML - Volume 17, 2002)
Because the ultimate purpose of the Semantic Web is to help users better locate, organize, and process content, we believe that it should be grounded in the information access method humans are most comfortable with---natural language. However, the Resource Description Framework (RDF), the foundation of the Semantic Web, was designed to be easily processed by computers, not humans. To render RDF more friendly to humans, we propose to augment it with natural language annotations, or metadata written in everyday language. We argue that natural language annotations, parsed into computer-readable representations, are not only intuitive and effective, but can also accelerate the pace with which the Semantic Web is being adopted. We believe that our technology can facilitate a happy marriage between natural language technology and the Semantic Web vision.

Approximation algorithms for the covering Steiner problem - Konjevod,Goran; Ravi,R.; Srinivasan, Aravind (Random Structures & Algorithms, 2002)
The covering Steiner problem is a generalization of both the k-MST and the group Steiner problems: given an edge-weighted graph, with subsets of vertices called the groups, and a nonnegative integer value (called the requirement) for each group, the problem is to find a minimum-weight tree spanning at least the required number of vertices of every group. When all requirements are equal to 1, this becomes the group Steiner problem, while if there is only one group which contains all vertices of the graph the problem reduces to k-MST with k equal to the requirement of this unique group. We discuss two different (but equivalent) linear relaxations of the problem for the case when the given graph is a tree and construct polylogarithmic approximation algorithms based on randomized LP rounding of these relaxations. By using a probabilistic approximation of general metrics by tree metrics due to Bartal, our algorithms also solve the covering Steiner problem on general graphs with a further polylogarithmic worsening in the approximation ratio. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:465–483, 2002

Are virtualized overlay networks too much of a good thing? - Keleher,P.; Bhattacharjee, Bobby; Silaghi,B. (Peer-to-Peer Systems, 2002)
The majority of recent high-profile work in peer-to-peer networks has approached the problem of location by abstracting over object lookup services. Namespace virtualization in the overlay layer provides load balance and provable bounds on latency at low costs.We contend that namespace virtualization comes at a significant cost for applications that naturally describe their data sets in a hierarchical manner. Opportunities for enhancing browsing, prefetching and efficient attribute-based searches are lost. A hierarchy exposes relationships between items near to each other in the topology; virtualization of the namespace discards this information even if present at client, higherlevel protocols. We advocate encoding application hierarchies directly into the structure of the overlay network, and revisit this argument through a newly proposed distributed directory service.

An Augmented Visual Query Mechanism for Finding Patterns in Time Series Data - Keogh,Eamonn; Hochheiser,Harry; Shneiderman, Ben (Flexible Query Answering SystemsFlexible Query Answering Systems, 2002)
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.

Automated design of multi-stage molds for manufacturing multi-material objects - Kumar,M.; Gupta,S.K. (Journal of Mechanical Design, 2002)

Bounds on the efficiency of encryption and digital signatures - Gennaro,R.; Gertner,Y.; Katz, Jonathan (Rutgers University, 2002)
A central focus of modern cryptography is to investigate the weakest possible assumptionsunder which various cryptographic algorithms exist. Typically, a proof that a “weak” prim- itive (e.g., a one-way function) implies the existence of some “strong” algorithm (e.g., a private-key encryption scheme) proceeds by giving an explicit construction of the latter from the former. Beyond merely showing such a construction, an equally important research direction is to explore the efficiency of the construction. One might argue that this line of research has become even more important now that minimal assumptions are known for many (but not all) algorithms of interest. Protocols for encryption (in both the public- and private-key setting) and for digital signatures are fundamental to cryptography. In this work, we show the first lower bounds on the efficiency of constructions of these protocols based on black-box access to one-way or trapdoor one-way permutations. If S is the assumed security of the permutation π (i.e., no adversary of size S can “break” π in the appropriate sense on a fraction larger than 1/S of its inputs), our results show that: • Any public-key encryption algorithm for m-bit messages must query π at least Ω(m/log S) times. This matches the known upper bound. • Any private-key encryption algorithm for m-bit messages which uses a k-bit key must query π at least Ω(m−k logS ) times. This matches the known upper bound. • Any signature verification algorithm for m-bit messages must query π at least Ω(m/log S) times. We prove our results in an extension of the Impagliazzo-Rudich model. That is, we show that any black-box construction beating our lower bounds would imply the unconditional existence of a one-way function.

On cache replacement policies for servicing mixed data intensive query workloads - Andrade,H.; Kurc, T.; Sussman, Alan; Borovikov,E.; Saltz, J. (Proceedings of the 2nd Workshop on Caching, Coherence, and Consistency, held in conjunction with the 16th ACM International Conference on Supercomputing, 2002)
When data analysis applications are employed in a multi-client environment, a data server must service multiple si- multaneous queries, each of which may employ complex user-defined data structures and operations on the data. It is then necessary to harness inter- and intra-query com- monalities and system resources to improve the performance of the data server. We have developed a framework and customizable middleware to enable reuse of intermediate and final results among queries, through an in-memory ac- tive semantic cache and user-defined transformation func- tions. Since resources such as processing power and mem- ory space are limited on the machine hosting the server, ef- fective scheduling of incoming queries and efficient cache replacement policies are challenging issues that must be ad- dressed. We have worked on the scheduling problem in ear- lier work, and in this paper we describe and evaluate several cache replacement policies. We present experimental eval- uation of the policies on a shared-memory parallel system using two applications from different application domains.

Combinatorial Algorithms for Design of DNA Arrays - Hannenhalli, Sridhar; Hubbell,Earl; Lipshutz,Robert; Pevzner,Pavel (Chip TechnologyChip Technology, 2002)
Optimal design of DNA arrays requires the development of algorithms with two-fold goals: reducing the effects caused by unintended illumination ( border length minimization problem ) and reducing the complexity of masks ( mask decomposition problem ). We describe algorithms that reduce the number of rectangles in mask decomposition by 20–30% as compared to a standard array design under the assumption that the arrangement of oligonucleotides on the array is fixed. This algorithm produces provably optimal solution for all studied real instances of array design. We also address the difficult problem of finding an arrangement which minimizes the border length and come up with a new idea of threading that significantly reduces the border length as compared to standard designs.

Comparative Genome Sequencing for Discovery of Novel Polymorphisms in Bacillus Anthracis - Read,Timothy D.; Salzberg,Steven L.; Pop, Mihai; Shumway,Martin; Umayam,Lowell; Jiang,Lingxia; Holtzapple,Erik; Busch,Joseph D; Smith,Kimothy L; Schupp,James M; Solomon,Daniel; Keim,Paul; et al. (Science, 2002)
Comparison of the whole-genome sequence ofBacillus anthracis isolated from a victim of a recent bioterrorist anthrax attack with a reference reveals 60 new markers that include single nucleotide polymorphisms (SNPs), inserted or deleted sequences, and tandem repeats. Genome comparison detected four high-quality SNPs between the two sequenced B. anthracischromosomes and seven differences among different preparations of the reference genome. These markers have been tested on a collection of anthrax isolates and were found to divide these samples into distinct families. These results demonstrate that genome-based analysis of microbial pathogens will provide a powerful new tool for investigation of infectious disease outbreaks.

A configurable CORBA gateway for providing adaptable system properties - Seri,M.; Courtney,T.; Michel Cukier; Gupta,V.; Krishnmamurthy,S.; Lyons,J.; Ramasamy,H.; Ren,J.; Sanders,W. H. (2002)

COTS-based software development: Processes and open issues - Morisio,M; Seaman,C.B; Basili, Victor R.; Parra,A.T; Kraft,S.E; Condon,S.E (Journal of Systems and Software, 2002)
The work described in this paper is an investigation of the COTS-based software development within a particular NASA environment, with an emphasis on the processes used. Fifteen projects using a COTS-based approach were studied and their actual process was documented. This process is evaluated to identify essential differences in comparison to traditional software development. The main differences, and the activities for which projects require more guidance, are requirements definition and COTS selection, high level design, integration and testing. Starting from these empirical observations, a new process and set of guidelines for COTS-based development are developed and briefly presented.
Keywords: Commercial off-the-shelf; Component-based; COTS; empirical study; Software development process

Dependent rounding in bipartite graphs - Gandhi,R.; Khuller, Samir; Parthasarathy,S.; Srinivasan, Aravind (The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings, 2002)
We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to 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 the following applications: 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, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.
Keywords: Application software; Approximation algorithms; bipartite graph; bipartite graphs; broadcast channels; broadcast scheduling; Broadcasting; capacitated vertex cover; Character generation; computational complexity; Computer science; Delay; edge-sets; Educational institutions; fair scheduling; fractional vectors; graph theory; per-user fairness properties; pipage rounding technique; Processor scheduling; Random variables; random-graph models; randomized rounding approach; rounding method; scheduling; Scheduling algorithm; telecommunication computing; unrelated parallel machines

Dwarf - Sismanis,Yannis; Deligiannakis,Antonios; Roussopoulos, Nick; Kotidis,Yannis (Proceedings of the 2002 ACM SIGMOD international conference on Management of data - SIGMOD '02, 2002)

Dynamic layout management in a multimedia bulletin board - Kang,Hyunmo; Shneiderman, Ben; Wolff,G. J (IEEE 2002 Symposia on Human Centric Computing Languages and Environments, 2002. Proceedings, 2002)
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, 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 other 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: Asynchronous communication; asynchronous communication system; Collaboration; data mining; dynamic layout management; dynamic layout templates; groupware; Human computer interaction; image; Information services; Laboratories; moving picture; Multimedia Bulletin Board system; multimedia computing; Multimedia databases; multimedia objects; multimedia systems; office document; Prototypes; sound; text; user interface; User interfaces; user-controlled layout strategy; voice; Web; Web pages

Efficient Cryptographic Protocols Preventing “Man-in-the-Middle” Attacks - Katz, Jonathan (Columbia University, 2002)
In the analysis of many cryptographic protocols, it is useful to distinguish two classes of attacks:passive attacks in which an adversary eavesdrops on messages sent between honest users and active attacks (i.e., “man-in-the-middle” attacks) in which — in addition to eavesdropping — the adversary inserts, deletes, or arbitrarily modifies messages sent from one user to another. Passive attacks are well characterized (the adversary’s choices are inherently limited) and techniques for achieving security against passive attacks are relatively well understood. Indeed, cryptographers have long focused on methods for countering passive eavesdropping attacks, and much work in the 1970’s and 1980’s has dealt with formalizing notions of security and providing provably-secure solutions for this setting. On the other hand, active attacks are not well characterized and precise modeling has been difficult. Few techniques exist for dealing with active attacks, and designing practical protocols secure against such attacks remains a challenge. This dissertation considers active attacks in a variety of settings and provides new, provably- secure protocols preventing such attacks. Proofs of security are in the standard cryptographic model and rely on well-known cryptographic assumptions. The protocols presented here are efficient and practical, and may find application in real-world systems.

Efficient Data Processing using Cross Layer Hints - Banerjee,Suman; Agrawala, Ashok K.; Kramer,Michael J (Technical Reports from UMIACS, UMIACS-TR-2002-59, 2002)
Conventional network stacks define a layered architecture, whereeach layer implements a set of services and exports a well-defined interface to be used by its immediate upper layer. A key design choice of the layered architecture has been to provide isolation between the functional modules of distinct layers. While such an architecture provides an useful abstraction for system development, the strict isolation of this layered architecture limits the flexibility of tailoring the behavior of the lower layers of the stack to the needs of the application. In this paper we define a new architecture, called X-Tags, which allows flexible interaction between layers for cooperative data processing without impacting the isolation property. In this architecture, applications use special tags to provide semantic hints for data processing to lower layers. We motivate the usefulness of this architecture by describing ts applicability to some emerging applications. UMIACS-TR-2002-59
Keywords: Technical Report

An efficient k-means clustering algorithm: analysis and implementation - Kanungo,T.; Mount, Dave; Netanyahu,N. S; Piatko,C. D; Silverman,R.; Wu,A. Y (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2002)
In k-means clustering, we are given a set of n data points in d-dimensional space Rd and an integer k and the problem is to determine a set of k points in Rd, called centers, so as to minimize the mean squared distance from each data point to its nearest center. A popular heuristic for k-means clustering is Lloyd's (1982) algorithm. We present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm. This algorithm is easy to implement, requiring a kd-tree as the only major data structure. We establish the practical efficiency of the filtering algorithm in two ways. First, we present a data-sensitive analysis of the algorithm's running time, which shows that the algorithm runs faster as the separation between clusters increases. Second, we present a number of empirical studies both on synthetically generated data and on real data sets from applications in color quantization, data compression, and image segmentation
Keywords: algorithm; color; algorithm; image; algorithm; kd-tree; mean; analysis; filtering; clustering; clustering; compression; data; distance; covariance; Lloyd; matrices; filtering; quantization; data; segmentation; k-means; squared; structure; data-sensitive; theory; pattern

Efficient Manipulation of Large Datasets on Heterogeneous Storage Systems - Beynon,Michael D.; Sussman, Alan; Kurc,Tahsin; Catalyurek,Umit; Saltz,Joel (Parallel and Distributed Processing Symposium, International, 2002)
In this paper we are concerned with the efficient use of a collection of disk-based storage systems and computing platforms in a heterogeneous setting for retrieving and processing large scientific datasets. We demonstrate, in the context of a data-intensive visualization application, how heterogeneity affects performance and show a set of optimization techniques that can be used to improve performance in a component-based framework. In particular, we examine the application of parallelism via transparent copies of application components in the pipelined processing of data.
Keywords: component-based frameworks; data-intensive computing; load balancing

Error-Tolerant Agents - Eiter,Thomas; Mascardi,Viviana; Subrahmanian,V. (Computational Logic: Logic Programming and BeyondComputational Logic: Logic Programming and Beyond, 2002)
The use of agents in today’s Internet world is expanding rapidly. Yet, agent developers proceed largely under the optimistic assumption that agents will be error-free. Errors may arise in agents for numerous reasons — agents may share a workspace with other agents or humans and updates made by these other entities may cause an agent to face a situation that it was not explicitly programmed to deal with. Likewise, errors in coding agents may lead to inconsistent situations where it is unclear how the agent should act. In this paper, we define an agent execution model that allows agents to continue acting “reasonably” even when some errors of the above types occur. More importantly, in our framework, agents take “repair” actions automatically when confronted with such situations, but while taking such repair actions, they can often continue to engage in work and/or interactions with other agents that are unaffected by repairs.
Keywords: Computer; Science

Evaluating translational correspondence using annotation projection - Hwa,Rebecca; Resnik, Philip; Weinberg, Amy; Kolak,Okan (Association for Computational Linguistics, 2002)
Recently, statistical machine translation models have begun to take advantage of higher level linguistic structures such as syntactic dependencies. Underlying these models is an assumption about the directness of translational correspondence between sentences in the two languages; however, the extent to which this assumption is valid and useful is not well understood. In this paper, we present an empirical study that quantifies the degree to which syntactic dependencies are preserved when parses are projected directly from English to Chinese. Our results show that although the direct correspondence assumption is often too restrictive, a small set of principled, elementary linguistic transformations can boost the quality of the projected Chinese parses by 76% relative to the unimproved baseline.

Evaluating translational correspondence using annotation projection - Hwa,R.; Resnik, Philip; Weinberg, Amy; Kolak,O. (Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, 2002)

Executing Multiple Pipelined Data Analysis Operations in the Grid - Spencer,Matthew; Ferreira,Renato; Beynon,Michael; Kurc,Tahsin; Catalyurek,Umit; Sussman, Alan; Saltz,Joel (SC Conference, 2002)
Processing of data in many data analysis applications can be represented as an acyclic, coarse grain data flow, from data sources to the client. This paper is concerned with scheduling of multiple data analysis operations, each of which is represented as a pipelined chain of processing on data. We define the scheduling problem for effectively placing components onto Grid resources, and propose two scheduling algorithms. Experimental results are presented using a visualization application.

Experimental Construction of Very Large Scale DNA Databases with Associative Search - Reif,J. H; LaBean,T. H; Pirrung,M.; Rana,V. S; Guo,B.; Kingsford, Carl; Wickham,G. S (DNA computing: 7th International Workshop on DNA-Based Computers, DNA 7, Tampa, FL, USA, June 10-13, 2001: revised papers, 2002)

Extracting articulation models from CAD models of parts with curved surfaces - Sinha,R.; Gupta,S.K.; Paredis,C. J. J.; Khosla,P. K. (TRANSACTIONS-AMERICAN SOCIETY OF MECHANICAL ENGINEERS JOURNAL OF MECHANICAL DESIGN, 2002)
Degrees of freedom in an assembly are realized by creating mating features that permit relativemotion between parts. In complex assemblies, interactions between individual degrees of freedom may result in a behavior different from the intended behavior. In addition, current methods perform assembly reasoning by approximating curved surfaces as piecewise linear surfaces. Therefore, it is important to be able to: reason about assemblies using exact representations of curved surfaces; verify global motion behavior of parts in the assembly; and create motion simulations of the assembly by examination of the geometry. In this paper, we present a linear algebraic constraint method to automatically construct the space of allowed instantaneous motions of an assembly from the geometry of its constituent parts. Our work builds on previous work on linear contact mechanics and on our previous work on curved surface contact mechanics. We enumerate the conditions under which general curved surfaces can be represented using a finite number of constraints linear in the instantaneous velocities. We compose such constraints to build a space of allowed instantaneous velocities for the assembly. The space is then described as a set-theoretic sum of contact-preserving and contact-breaking motion sub-spaces. Analysis of each subspace provides feedback to the designer, which we demonstrate through the use of an example assembly – a 4-part arm. Finally, the results of the analysis of a 4-bar linkage are compared to those from mechanism theory.

Face recognition from video: a CONDENSATION approach - Zhou,Shaohua; Krueger, V.; Chellapa, Rama (Automatic Face and Gesture Recognition, 2002. Proceedings. Fifth IEEE International Conference on, 2002)
The aim of this work is to investigate how to exploit the temporal information in a video sequence for the task of face recognition. Following the approach in (Li and Chellappa, 2000), we propose a probabilistic model parameterized by a tracking state vector and a recognizing identity variable, simultaneously characterizing the kinematics and identity of humans. We then invoke a CONDENSATION (Isard and Blake, 1996) approach to provide a numerical solution to the model. Once the joint posterior distribution of the state vector and the identity variable is estimated, we marginalize it over the state vector to yield a robust estimate of the posterior distribution of the identity variable. Due to the propagation of identity and dynamics, a degeneracy in the posterior distribution of the identity variable is achieved to give improved recognition. This evolving behavior is characterized using changes in entropy. The effectiveness of this approach is illustrated using experimental results on low-resolution video data.
Keywords: algorithm; experimental; approach; Sequential; CONDENSATION; data; probabilistic; distribution; kinematics; low-resolution; importance; information; tracking; model; state; posterior; recognition; image; recognition; joint; resolution; image; results; face; sampling; sampling; probability; sequence; face; sequences; importance; state; vector; temporal; vector; video; video

A forward-secure public-key encryption scheme - Katz, Jonathan (Technical Report 2002/060, Cryptology ePrint Archive, 2002, 2002)

Genome sequence and comparative analysis of the model rodent malaria parasite Plasmodium yoelii yoelii - Carlton,Jane M.; Angiuoli,Samuel V; Suh,Bernard B.; Kooij,Taco W.; Pertea,Mihaela; Silva,Joana C.; Ermolaeva,Maria D.; Allen,Jonathan E; Jeremy D Selengut; Koo,Hean L.; Peterson,Jeremy D.; Pop, Mihai; et al. (Nature, 2002)
Species of malaria parasite that infect rodents have long been used as models for malaria disease research. Here we report the whole-genome shotgun sequence of one species, Plasmodium yoelii yoelii, and comparative studies with the genome of the human malaria parasite Plasmodium falciparum clone 3D7. A synteny map of 2,212 P. y. yoelii contiguous DNA sequences (contigs) aligned to 14 P. falciparum chromosomes reveals marked conservation of gene synteny within the body of each chromosome. Of about 5,300 P. falciparum genes, more than 3,300 P. y. yoelii orthologues of predominantly metabolic function were identified. Over 800 copies of a variant antigen gene located in subtelomeric regions were found. This is the first genome sequence of a model eukaryotic parasite, and it provides insight into the use of such systems in the modelling of Plasmodium biology and disease.

A history-based test prioritization technique for regression testing in resource constrained environments - Kim,Jung-Min; Porter, Adam (Proceedings of the 24th international conference on Software engineering - ICSE '02, 2002)

HTN Planning in Answer Set Programming - Dix,Jurgen; Kuter,Ugur; Nau, Dana S. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
In this paper we introduce a formalism for solving Hierarchical Task NEtwork(HTN) Planning using Answer Set Programming (ASP). The ASP paradigm evolved out of the stable semantics for logic programs in recent years and is strongly related to nonmonotonic logics. We consider the formulation of HTM planning as described in the SHOP planning system and define a systematic translation method from SHOP's representation of the planning problems into logic programs with negation. We show that our translation is sound and complete: answer sets of the logic programs obtained by our translation correspond exactly to the solutions of the planning problems. Our approach does not rly on a particular system for computing answer sets. It can therefore serve as a means to evaluate ASP systems by using well-established benchmarks from the planning community. We tested our method on various such benchmarks and used smodels and DLV for computing answer sets. We compared our method to (1) similar approaches based on non-HTN planning and (2) SHOP, a dedicated planning system. We show that our approach outperforms non-HTN methods and that its performance is closer to that of SHOP, when we are using ASP systems which allow for nonground programs. (Also UMIACS-TR-2002-18)
Keywords: Technical Report

Identification of humans using gait - Kale, A.; Rajagopalan, AN; Cuntoor, N.; Krueger, V.; Chellapa, Rama (IEEE Transactions on Image Processing, 2002)
We propose a view-based approach to recognize humans from their gait. Two different imagefeatures have been considered: the width of the outer contour of the binarized silhouette of the walking person and the entire binary silhouette itself. To obtain the observation vector from the image features we employ two different methods. In the first method referred to as the indirect approach, the high-dimensional image feature is transformed to a lower-dimensional space by generating what we call the Frame to Exemplar (FED) distance. The FED vector captures both structural and dynamic traits of each individual. For compact and effective gait representation and recognition, the gait information in the FED vector sequences is captured in a hidden Markov model (HMM). In the second method referred to as the direct approach, we work with the feature vector directly (as opposed to computing the FED) and train an HMM. We estimate the HMM parameters (specifically the observation probability B) based on the distance between the exemplars and the image features. In this way we avoid learning high-dimensional probability density functions. The statistical nature of the HMM lends overall robustness to representation and recognition. The performance of the methods is illustrated using several databases.

Implementation of chosen-ciphertext attacks against PGP and GnuPG - Jallad,K.; Katz, Jonathan; Schneier,B. (Information Security, 2002)
We recently noted [6] that PGP and other e-mail encryption protocols are, in theory, highly vulnerable to chosen-ciphertext attacks in which the recipient of the e-mail acts as an unwitting “decryption oracle”. We argued further that such attacks are quite feasible and therefore represent a serious concern. Here, we investigate these claims in more detail by attempting to implement the suggested attacks. On one hand, we are able to successfully implement the described attacks against PGP and GnuPG (two widely-used software packages) in a number of different settings. On the other hand, we show that the attacks largely fail when data is compressed before encryption.Interestingly, the attacks are unsuccessful for largely fortuitous reasons; resistance to these attacks does not seem due to any conscious effort made to prevent them. Based on our work, we discuss those instances in which chosen-ciphertext attacks do indeed represent an important threat and hence must be taken into account in order to maintain confidentiality. We also recommend changes in the OpenPGP standard [3] to reduce the effectiveness of our attacks in these settings.

The importance of lexicalized syntax models for natural language generation tasks - Daumé, Hal; Knight,K.; Langkilde-Geary,I.; Marcu,D.; Yamada,K. (Proc. of INLG, 2002)

Incremental unforgeable encryption - Buonanno,E.; Katz, Jonathan; Yung,M. (Fast Software Encryption, 2002)
The recent selection of the AES block cipher to replace DES has generated interest in developing new modes of operation to supplement the modes defined as part of the DES standard [1,16,23]. We initiate the study of modes of encryption which are both incremental and unforgeable, and point out a number of applications for modes meeting these requirements. We also propose three specific modes achieving these goals, and discuss the strengths and weaknesses of each.

Infranet: Circumventing web censorship and surveillance - Feamster, Nick; Balazinska,M.; Harfst,G.; Balakrishnan,H.; Karger,D. (Proceedings of the 11th USENIX Security Symposium, 2002)
An increasing number of countries and companies routinely block or monitor access to parts of the Internet. To counteract these measures, we propose Infranet, a system that enables clients to surreptitiously retrieve sensitive content via cooperating Web servers distributed across the global Internet. These Infranet servers provide clients access to censored sites while continuing to host normal uncensored content. Infranet uses a tunnel protocol that provides a covert communication channel between its clients and servers, modulated over standard HTTP transactions that resemble innocuous Web browsing. In the upstream direction, Infranet clients send covert messages to Infranet servers by associating meaning to the sequence of HTTP requests being made. In the downstream direction, Infranet servers return content by hiding censored data in uncensored images using steganographic techniques. We describe the design, a prototype implementation, security properties, and performance of Infranet. Our security analysis shows that Infranet can successfully circumvent several sophisticated censoring techniques.

Intermediate representations for design automation of multiprocessor DSP systems - Bambha,N.; Kianzad,V.; Khandelia,M.; Bhattacharyya, Shuvra S. (Design Automation for Embedded Systems, 2002)

Irisnet: An architecture for compute-intensive wide-area sensor network services - Nath,S.; Deshpande, Amol; Ke,Y.; Gibbons,P.; Karp,B.; Seshan,S. (Intel Corporation, Pittsburgh IRPTR-02, 2002)
Previous work on sensor networks has targeted adhoc wireless networks of closely-colocated, resource- constrained scalar sensor motes. Such work has over- looked richer sensor types such as webcams and mi- crophones, which are typically attached to Internet- connected machines with significant computing power and storage. In this paper, we describe IrisNet (Internet- scale Resource-Intensive Sensor Network services), an architecture for wide-area sensor networks based on these more capable sensing nodes. IrisNet provides a common, scalable software infrastructure that enables the flexible creation of sensor-based Internet services. It dramatically reduces network bandwidth utilization through the use of senselets, binary code fragments that perform intensive data filtering at the sensing nodes, leveraging the available processing power and mem- ory. IrisNet employs a two-tier hierarchy of sensing nodes and query processing nodes. Key features of IrisNet include flexible data partitioning, efficient and protected sharing of sensor nodes, low-latency queries, partial match caching, query-specified freshness toler- ances, and monitoring and logging support. This pa- per reports on experiments with a working IrisNet pro- totype running a parking space finder service, demon- strating the effectiveness of IrisNet’s features in achiev- ing scalability and reducing query response times.

Key-insulated public key cryptosystems - Dodis,Y.; Katz, Jonathan; Xu,S.; Yung,M. (Advances in Cryptology—Eurocrypt 2002, 2002)
Cryptographic computations (decryption, signature generation, etc.) are often performed on a relatively insecure device (e.g., a mobile device or an Internet-connected host) which cannot be trusted to maintain secrecy of the private key. We propose and investigate the notion of key-insulated security whose goal is to minimize the damage caused by secret-key exposures. In our model, the secret key(s) stored on the insecure device are refreshed at discrete time periods via inter-action with a physically-secure - but computationally-limited - device which stores a “master key”. All cryptographic computations are still done on the insecure device, and the public key remains unchanged. In a (t, N)-key-insulated scheme, an adversary who compromises the insecure device and obtains secret keys for up to t periods of his choice is unable to violate the security of the cryptosystem for any of the remaining N - t periods. Furthermore, the scheme remains secure (for all time periods) against an adversary who compromises only the physically-secure device. We focus primarily on key-insulated public-key encryption. We construct a (t, N)-key-insulated encryption scheme based on any (standard) public-key encryption scheme, and give a more efficient construction based on the DDH assumption. The latter construction is then extended to achieve chosen-ciphertext security.

Learning structured statistical models from relational data - Getoor, Lise; Friedman,N.; Koller,D. (Linköping Electronic Articles in Computer and Information Science, 2002)
Here we describe tools for constructing statistical models from relational data. Our goal is to learn structured probabilistic models that represent statistical correlations both between the properties of an entity and between the properties of related entities. These statistical models can then be used for a variety of tasks including knowledge discovery, exploratory data analysis, data summarization and anomaly detection. Unfortunately, most statistical learning methods work only with "flat" data representations. Thus, to apply these methods, we are forced to convert the data into a flat form, thereby not only losing its compact representation and structure but also potentially introducing statistical skew. These drawbacks severely limit the ability of current statistical methods to model relational databases. Here we describe two complementary approaches: one approach suited to making probabilistic statements about individuals and the second approach suited to making statements about frequencies in relational data. We describe algorithms for both learning and making inferences in these models, and give experimental results.

Lexicon Acquisition from Bilingual Dictionaries - David Doermann; Ma,H.; Karagol-Ayan,B.; Oard, Douglas (SPIEPhotonic West Electronic Imaging Conference, 2002)

A local search approximation algorithm for k-means clustering - Kanungo,Tapas; Mount, Dave; Netanyahu,Nathan S.; Piatko,Christine D.; Silverman,Ruth; Wu,Angela Y. (Proceedings of the eighteenth annual symposium on Computational geometry, 2002)
In k-means clustering we are given a set of n data points in d-dimensional space Rd and an integer k, and the problem is to determine a set of k points in ÓC;d, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+&egr;)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-&egr;). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.
Keywords: Approximation algorithms; clustering; computational geometry; k-means; local search

Method and apparatus for learning probabilistic relational models having attribute and link uncertainty and for performing selectivity estimation using probabilistic relational models - Koller,Daphne; Getoor, Lise; Pfeffer,Avi; Friedman,Nir; Taskar,Ben (2002)
The invention comprises a method and apparatus for learning probabilistic models (PRM's) with attribute uncertainty. A PRM with attribute uncertainty defines a probability distribution over instantiations of a database. A learned PRM is useful for discovering interesting patterns and dependencies in the data. Unlike many existing techniques, the process is data-driven rather than hypothesis driven. This makes the technique particularly well-suited for exploratory data analysis. In addition, the invention comprises a method and apparatus for handling link uncertainty in PRM's. Link uncertainty is uncertainty over which entities are related in our domain. The invention comprises of two mechanisms for modeling link uncertainty: reference uncertainty and existence uncertainty. The invention includes learning algorithms for each form of link uncertainty. The third component of the invention is a technique for performing database selectivity estimation using probabilistic relational...

Multiple Query Optimization for Data Analysis Applications on Clusters of SMPs - Andrade,H.; Kurc, T.; Sussman, Alan; Saltz, J. (2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, 2002, 2002)
This paper is concerned with the efficient execution of multiple query workloads on a cluster of SMPs. We target applications that access and manipulate large scientific datasets. Queries in these applications involve user-defined processing operations and distributed data structures to hold intermediate and final results. Our goal is to implement system components to leverage previously computed query results and to effectively utilize processing power and aggregated I/O bandwidth on SMP nodes so that both single queries and multi-query batches can be efficiently executed.
Keywords: Aggregates; Application software; Bandwidth; Data analysis; Data structures; Delay; Query processing; scheduling; Subcontracting; Switched-mode power supply

OCR error correction using a noisy channel model - Kolak,O.; Resnik, Philip (Proceedings of the second international conference on Human Language Technology Research, 2002)

Octree approximation and compression methods - Samet, Hanan; Kochut, A. (Proc. of the 1st Intl. Symp. on 3D Data Processing, Visualization, and Transmission, 2002)
Techniques are presented to progressively approximateand compress in a lossless manner two-colored (i.e. bi- nary) 3D objects (as well as objects of arbitrary dimen- sionality). The objects are represented by a region octree implemented using a pointerless representation based on locational codes. Approximation is achieved through the use of a forest. This method labels the internal nodes of the octree as GB or GW, depending on the number of chil- dren being of type GB or GW. In addition, all BLACK nodes are labeled GB, while all WHITE nodes are labeled GW. A number of different image approximation methods are dis- cussed that make use of a forest. The advantage of these methods is that they are progressive which means that as more of the object is transmitted, the better is the approx- imation. This makes these methods attractive for use on the worldwide web. Progressive transmission has the draw- back that there is an overhead in requiring extra storage. A progressive forest-based approximation and transmission method is presented where the total amount of data that is transmitted is not larger than MIN(B,W), where B and W are the number of BLACK and WHITE blocks, respectively, in the region octree of the set of objects.

Omnibase: Uniform access to heterogeneous data for question answering - Katz,B.; Felshin,S.; Yuret,D.; Ibrahim,A.; Jimmy Lin; Marton,G.; Jerome McFarland,A.; Temelkuran,B. (Natural Language Processing and Information Systems, 2002)
Although the World Wide Web contains a tremendous amount of information, the lack of uniform structure makes finding the right knowledge difficult. A solution is to turn the Web into a “virtual database” and to access it through natural language.We built Omnibase, a system that integrates heterogeneous data sources using an object- property-value model. With the help of Omnibase, our Start natural language system can now access numerous heterogeneous data sources on the Web in a uniform manner, and answers millions of user questions with high precision.

Optimizing execution of component-based applications using group instances - Beynon,Michael D.; Kurc,Tahsin; Sussman, Alan; Saltz,Joel (Future Generation Computer Systems, 2002)
Recent research on programming models for developing applications on the Grid has proposed component-based models as a viable approach, in which an application is composed of multiple interacting computational objects. We have been developing a framework, called filter-stream programming, for building data-intensive applications that query, analyze and manipulate very large datasets in a distributed environment. In this model, the processing structure of an application is represented as a set of processing units, referred to as filters. In this paper, we develop the problem of scheduling instances of a filter group. A filter group is a set of filters collectively performing a computation for an application. In particular, we seek the answer to the following question: should a new instance be created, or an existing one reused? We experimentally investigate the effects on performance of instantiating multiple filter groups under varying application characteristics.
Keywords: DataCutter; Grid; Wide-area network

Performance evaluation of a probabilistic replica selection algorithm - Krishnamurthy, S.; Sanders,W. H.; Michel Cukier (2002)
When executing time-sensitive distributed applications, a middleware that provides dependability and timeliness is faced with the important problem of preventing timing failures both under normal conditions and when the quality of service is degraded due to replica failures and transient overload on the server. To address this problem, we have designed a probabilistic model-based replica selection algorithm that allows a middleware to choose a set of replicas to service a client based on their ability to meet a client's timeliness requirements. This selection is done based on the prediction made by a probabilistic model that uses the performance history of replicas as inputs. In this paper, we describe the experiments we have conducted to evaluate the ability of this dynamic selection algorithm to meet a client's timing requirements, and compare it with that of a static and round-robin selection scheme under different scenarios
Keywords: client-server systems; Dependability; distributed object management; dynamic selection algorithm; Middleware; probabilistic model; probabilistic model-based replica selection algorithm; probability; quality of service; real-time systems; replica failures; round-robin selection scheme; static scheme; time-sensitive distributed applications; timeliness; timing failures; transient overload

Performance evaluation of a QoS-aware framework for providing tunable consistency and timeliness - Krishnamurthy, S.; Sanders,W. H.; Michel Cukier (2002)
Strong replica consistency models ensure that the data delivered by a replica always includes the latest updates, although this may result in poor response times. On the other hand, weak replica consistency models provide quicker access to information, but do not usually provide guarantees about the degree of staleness in the data they deliver. In order to support emerging distributed applications that are characterized by high concurrency demands, an increasing shift towards dynamic content, and timely delivery, we need quality of service models that allow us to explore the intermediate space between these two extreme approaches to replica consistency. Further, for better support of time-sensitive applications that can tolerate relaxed consistency in exchange for better responsiveness, we need to understand how the desired level of consistency affects the timeliness of a response. The QoS model we have developed to realize these objectives considers both timeliness and consistency, and treats consistency along two dimensions: order and staleness. We evaluate experimentally the framework we have developed to study the timeliness/consistency tradeoffs for replicated services and present experimental results that compare these tradeoffs in the context of sequential and FIFO ordering.
Keywords: client-server systems; Computer networks; CORBA-based middleware; distributed applications; distributed object management; Network servers; QoS; quality of service; replica consistency; replicated services; server replicas; timeliness

Performance evaluation of object detection algorithms - Mariano,V.Y.; Min,Junghye; Park,Jin-Hyeong; Kasturi,R.; Mihalcik,D.; Huiping Li; David Doermann; Drayer,T. (Pattern Recognition, 2002. Proceedings. 16th International Conference on, 2002)
The continuous development of object detection algorithms is ushering in the need for evaluation tools to quantify algorithm performance. In this paper a set of seven metrics are proposed for quantifying different aspects of a detection algorithm's performance. The strengths and weaknesses of these metrics are described. They are implemented in the Video Performance Evaluation Resource (ViPER) system and will be used to evaluate algorithms for detecting text, faces, moving people and vehicles. Results for running two previous text-detection algorithms on a common data set are presented.
Keywords: algorithms; common; data; DETECTION; detection; Evaluation; evaluation; image; object; performance; recognition; resource; set; system; text-detection; video

Persistent caching in a multiple query optimization framework - Andrade,H.; Kurc, T.; Catalyurek,U.; Sussman, Alan; Saltz, J. (Proceedings of the 6th Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, 2002)
This paper focuses on persistent caching in multi-client en-vironments, which aims to improve the performance of a data server by caching on disk query results that can be expensive to produce. We present and evaluate extensions to an existing multi-query optimization framework, called MQO, to incorporate persistent caching capabilities.

A photo history of SIGCHI: evolution of design from personal to public - Shneiderman, Ben; Kang,Hyunmo; Kules,Bill; Plaisant, Catherine; Rose,Anne; Rucheir,Richesh (interactions, 2002)
For 20 years I have been photographing personalities and events in the emerging discipline of human--computer interaction. Until now, only a few of these photos were published in newsletters or were shown to visitors who sought them out. Now this photo history is going from a personal record to a public archive. This archive should be interesting for professional members of this community who want to reminisce, as well as for historians and journalists who want to understand what happened. Students and Web surfers may also want to look at the people who created better interfaces and more satisfying user experiences.

Probabilistic recognition of human faces from video - Chellapa, Rama; Kruger, V.; Zhou,Shaohua (Image Processing. 2002. Proceedings. 2002 International Conference on, 2002)
Most present face recognition approaches recognize faces based on still images. We present a novel approach to recognize faces in video. In that scenario, the face gallery may consist of still images or may be derived from a videos. For evidence integration we use classical Bayesian propagation over time and compute the posterior distribution using sequential importance sampling. The probabilistic approach allows us to handle uncertainties in a systematic manner. Experimental results using videos collected by NIST/USF and CMU illustrate the effectiveness of this approach in both still-to-video and video-to-video scenarios with appropriate model choices.
Keywords: Bayes; Bayesian; CMU; distribution; Face; faces; gallery; handling; human; image; images; importance; likelihood; methods; NIST/USF; observation; posterior; probabilistic; probability; processing; propagation; recognition; sampling; sequential; signal; still; Still-to-video; Uncertainty; video; Video-to-video

Processing large-scale multi-dimensional data in parallel and distributed environments - Beynon,Michael; Chang,Chialin; Catalyurek,Umit; Kurc,Tahsin; Sussman, Alan; Andrade,Henrique; Ferreira,Renato; Saltz,Joel (Parallel Computing, 2002)
Analysis of data is an important step in understanding and solving a scientific problem. Analysis involves extracting the data of interest from all the available raw data in a dataset and processing it into a data product. However, in many areas of science and engineering, a scientist's ability to analyze information is increasingly becoming hindered by dataset sizes. The vast amount of data in scientific datasets makes it a difficult task to efficiently access the data of interest, and manage potentially heterogeneous system resources to process the data. Subsetting and aggregation are common operations executed in a wide range of data-intensive applications. We argue that common runtime and programming support can be developed for applications that query and manipulate large datasets. This paper presents a compendium of frameworks and methods we have developed to support efficient execution of subsetting and aggregation operations in applications that query and manipulate large, multi-dimensional datasets in parallel and distributed computing environments.
Keywords: Data-intensive applications; Distributed computing; Multi-dimensional datasets; PARALLEL PROCESSING; Runtime systems

Query routing in the TerraDir distributed directory - Silaghi,B.; Bhattacharjee, Bobby; Keleher,P. (Proceedings of the SPIE ITCOM, 2002)
We present the design and evaluation of the query-routing protocol of the TerraDir distributed directory.TerraDir is a wide-area distributed directory designed for hierarchical namespaces, and provides a lookup service for mapping keys to objects. We introduce distributed lookup and caching algorithms that leverage the underlying data hierarchy. Our algorithms provide efficient lookups while avoiding the load imbalances often associated with hierarchical systems. The TerraDir load balancing scheme also incorporates a node replication algorithm that provides configurable failure resilience with provably low overheads.

Rover: scalable location-aware computing - Banerjee,S.; Agarwal,S.; Kamel,K.; Kochut, A.; Kommareddy,C.; Nadeem,T.; Thakkar,P.; Trinh,Bao; Youssef,A.; Youssef, M.; Larsen,R.L.; Udaya Shankar,A.; et al. (Computer, 2002)
All the components necessary for realizing location-aware computing are available in the marketplace today. What has hindered the widespread deployment of location-based systems is the lack of an integration architecture that scales with user populations. The authors have completed the initial implementation of Rover, a system designed to achieve this sort of integration and to automatically tailor information and services to a mobile user's location. Their studies have validated Rover's underlying software architecture, which achieves system scalability through high-resolution, application-specific resource scheduling at the servers and network. The authors believe that this technology will greatly enhance the user experience in many places, including museums, amusement and theme parks, shopping malls, game fields, offices, and business centers. They designed the system specifically to scale to large user populations and expect its benefits to increase with them.
Keywords: amusement; application-specific; architecture; automation; business; business; computing; data; entertainment; handheld; humanities; integration; LAN; location-aware; malls; mobile; museums; office; parks; processing; resource; Rover; scalability; scalable; scheduling; shopping; software; system; theme; units; user; wireless

Scalable application layer multicast - Banerjee,Suman; Bhattacharjee, Bobby; Kommareddy,Christopher (SIGCOMM Comput. Commun. Rev., 2002)
We describe a new scalable application-layer multicast protocol, specifically designed for low-bandwidth, data streaming applications with large receiver sets. Our scheme is based upon a hierarchical clustering of the application-layer multicast peers and can support a number of different data delivery trees with desirable properties.We present extensive simulations of both our protocol and the Narada application-layer multicast protocol over Internet-like topologies. Our results show that for groups of size 32 or more, our protocol has lower link stress (by about 25%), improved or similar end-to-end latencies and similar failure recovery properties. More importantly, it is able to achieve these results by using orders of magnitude lower control traffic.Finally, we present results from our wide-area testbed in which we experimented with 32-100 member groups distributed over 8 different sites. In our experiments, average group members established and maintained low-latency paths and incurred a maximum packet loss rate of less than 1% as members randomly joined and left the multicast group. The average control overhead during our experiments was less than 1 Kbps for groups of size 100.
Keywords: application layer multicast; hierarchy; overlay networks; peer-to-peer systems; scalability

Scalable peer finding on the Internet - Banerjee,S.; Kommareddy,C.; Bhattacharjee, Bobby (Global Telecommunications Conference, 2002. GLOBECOM '02. IEEE, 2002)
We consider the problem of finding nearby application peers over the Internet. We define a new peer-finding scheme (called Tiers) that scales to large application peer groups. Tiers creates a hierarchy of the peers, which allows an efficient and scalable solution to this problem. The scheme can be implemented entirely in the application-layer and does not require the deployment of either any additional measurement services, or well-known reference landmarks in the network. We present detailed evaluation of Tiers and compare it to one previously proposed scheme called Beaconing. Through analysis and detailed simulations on 10,000 node Internet-like topologies we show that Tiers achieves comparable or better performance with a significant reduction in control overheads for groups of size 32 or more.
Keywords: application; application-layer; Beaconing; CONTROL; finding; Internet-like; Internet; measurement; network; overhead; peer; peer-finding; peers; protocol; protocols; reduction; scalable; scheme; services; simulations; solution; Tiers; topologies; topology

Scheduling multiple data visualization query workloads on a shared memory machine - Andrade,H.; Kurc, T.; Sussman, Alan; Saltz, J. (Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM, 2002)
Query scheduling plays an important role when systems are faced with limited resources and high workloads. It becomes even more relevant for servers applying multiple query optimization techniques to batches of queries, in which portions of datasets as well as intermediate results are maintained in memory to speed up query evaluation. We present a dynamic query scheduling model based on a priority queue implementation using a directed graph and a strategy for ranking queries. We examine the relative performance of several ranking strategies on a shared-memory machine using two different versions of an application, called the Virtual Microscope, for browsing digitized microscopy images
Keywords: Atomic force microscopy; Biomedical informatics; Computer science; Data analysis; data visualisation; Data visualization; datasets; deductive databases; digitized microscopy image browsing; directed graph; directed graphs; dynamic query scheduling model; Educational institutions; high workloads; image database; limited resources; multiple data visualization query workloads; multiple query optimization; performance; priority queue; Processor scheduling; Query processing; query ranking; Relational databases; scheduling; shared memory machine; shared memory systems; Virtual Microscope; visual databases

A secure PLAN (extended version) - Hicks, Michael W.; Keromytis,A. D; Smith,J. M (DARPA Active NEtworks Conference and Exposition, 2002. Proceedings, 2002)
Active networks promise greater flexibility than current networks, but threaten safety and security by virtue of their programmability. We describe the design and implementation of a security architecture for the active network PLANet (Hicks et al., 1999). Security is obtained with a two-level architecture that combines a functionally restricted packet language, PLAN (Hicks et al., 1998), with an environment of general-purpose service routines governed by trust management (Blaze et al., 1996). In particular, we employ a technique which expands or contracts a packet's service environment based on its level of privilege, termed namespace-based security. As an application of our security architecture, we present the design and implementation of an active-network firewall. We find that the addition of the firewall imposes an approximately 34% latency overhead and as little as a 6.7% space overhead to incoming packets
Keywords: active internetwork; active networks; active-network firewall; Authentication; authorisation; Authorization; Cities and towns; Computer networks; Computer science; cryptography; functionally restricted packet language; general-purpose service routines; Information security; internetworking; IP networks; latency overhead; namespace-based security; PLAN; PLANet; Planets; programmability; Safety; security architecture; telecommunication security; trust management; two-level architecture; Web and internet services

The START multimedia information system: Current technology and future directions - Katz,B.; Jimmy Lin; Felshin,S. (In Proceedings of the International Workshop on Multimedia Information Systems (MIS 2002), 2002)
To address the problem of information overload intoday’s world, we have developed Start, a natural language question answering system that provides users with high-precision multimedia information ac- cess through the use of natural language annota- tions. To address the difficulty of accessing large amounts of heterogeneous data, we have developed Omnibase, which assists Start by integrating struc- tured and semistructured Web databases into a sin- gle, uniformly structured “virtual database.” Our ultimate goal is to develop a computer system that acts like a “smart reference librarian,” and we be- lieve we have laid a firm foundation for achieving our goal. This paper describes our current implemented system and discusses future research directions.

State of the art in data representation for visualization - Chen,B.; Kaufman,A.; Mueller,K.; Varshney, Amitabh (IEEE Visualization Tutorial, 2002)

A Step Towards Automated Design of Multi-Piece Sacrificial Molds - Dhaliwal,Savinder; Gupta, Satyandra K.; Huang,Jun; Kumar,Malay (ASME, 2002)
This paper describes a feature-based approach for design of multi-piece sacrificial molds. Our mold design algorithm consists of the following three steps. First, the desired gross mold shape is formed based on the feature-based description of the part geometry. Second, if the desired gross mold shape is not machinable as a single piece, the gross mold shape is decomposed into simpler geometric components to make sure that each component is manufacturable using 3-axis CNC machining. The decomposition is performed to ensure that each component is accessible to end-milling tools, and decomposed components can be assembled together to form the gross mold shape. Finally, assembly features are added to mold components to facilitate assembly of mold components and eliminate unnecessary degree of freedoms from the final mold assembly. We expect that our decomposition algorithm will provide a step towards the necessary foundations for automating the design of multi-piece mold and therefore will help in significantly reducing the mold design and manufacturing lead-time.

Strong key-insulated signature schemes - Dodis,Y.; Katz, Jonathan; Xu,S.; Yung,M. (Public Key Cryptography—PKC 2003, 2002)
Signature computation is frequently performed on insecure devices—e.g., mobile phones — operating in an environment where the private (signing)k ey is likely to be exposed. Strong key-insulated signature schemes are one way to mitigate the damage done when this occurs. In the key-insulated model [6], the secret key stored on an insecure device is refreshed at discrete time periods via interaction with a physically-secure device which stores a “master key”. All signing is still done by the insecure device, and the public key remains fixed throughout the lifetime of the protocol. In a strong (t,N)-key-insulated scheme, an adversary who compromises the insecure device and obtains secret keys for up to t periods is unable to forge signatures for any of the remaining N-t periods. Furthermore, the physically-secure device (or an adversary who compromises only this device)is unable to forge signatures for any time period.We present here constructions of strong key-insulated signature schemes based on a variety of assumptions. First, we demonstrate a generic construction of a strong (N— 1,N)-key-insulated signature scheme using any standard signature scheme. We then give a construction of a strong (t,N)-signature scheme whose security may be based on the discrete logarithm assumption in the random oracle model. This construction offers faster signing and verification than the generic construction, at the expense of O(t)k ey update time and key length. Finally, we construct strong (N —1,N)-key-insulated schemes based on any “trapdoor signature scheme” (a notion we introduce here); our resulting construction in fact serves as an identity-based signature scheme as well. This leads to very efficient solutions based on, e.g., the RSA assumption in the random oracle model. Work done in part while at DIMACS.

Three-dimensional visualization of hierarchical task network plans - Kundu,K.; Sessions,C.; desJardins, Marie; Rheingans,P. (In Proceedings of the 3rd International NASA Workshop on Planning and Scheduling for, 2002)
Artificial Intelligence (AI) planning techniques, particularly hierarchical task network (HTN) planners, can produce very complex plans, with many sequential and parallel actions decomposed into multiple levels of abstraction.

Threshold cryptosystems based on factoring - Katz, Jonathan; Yung,M. (Advances in Cryptology—ASIACRYPT 2002, 2002)
We consider threshold cryptosystems over a composite modulus N where the factors of N are shared among the participants as the secret key. This is a new paradigm for threshold cryptosystems based on a composite modulus, differing from the typical treatment of RSA-based systems where a “decryption exponent” is shared among the participants. Our approach yields solutions to some open problems in threshold cryptography; in particular, we obtain the following:1 Threshold Homomorphic Encryption. A number of applications (e.g., electronic voting or efficient multi-party computation) require threshold homomorphic encryption schemes. We present a protocol for threshold decryption of the homomorphic Goldwasser-Micali encryption scheme [34], answering an open question of [21]. 2 Threshold Cryptosystems as Secure as Factoring. We describe a threshold version of a variant of the signature standards ISO 9796-2 and PKCS#1 v1.5 (cf. [39, Section 11.3.4]), thus giving the first threshold signature scheme whose security (in the random oracle model) is equivalent to the hardness of factoring [12]. Our techniques may be adapted to distribute the Rabin encryption scheme [44] whose semantic security may be reduced to the hardness of factoring. 3 Efficient Threshold Schemes without a Trusted Dealer. Because our schemes only require sharing of N - which furthermore need not be a product of strong primes - our schemes are very efficient (compared to previous schemes) when a trusted dealer is not assumed and key generation is done in a distributed manner. Extensions to achieve robustness and proactivation are also possible with our schemes. Work done while at Columbia University and Telcordia Technologies

The use of speech retrieval systems: a study design - Kim,J.; Oard, Douglas (Information retrieval techniques for speech applications, 2002)

Video analysis applications for pervasive environments - Karunanidhi,A.; David Doermann; Parekh,N.; Rautio,V. (1st International Conference on Mobile and Ubiquitous Multimedia, 2002)
Network capabilities are expanding at arate that will soon allow a much wider range of image and video content to be delivered to and transmitted from mobile wireless devices. Current pervasive applications provide image and video content primarily in high performance networks or by streaming video over low-bandwidth networks. For video to be truly integrated into ubiquitous applications, we must carefully consider the role of automated video analysis to move beyond simple content delivery. Compression and content adaptation have been significant areas of research for some time and deal with the problem of moving media to devices with limited network, software and hardware capabilities. In the near future, mobile wireless devices that have been primarily consumers of image and video will be able to produce such content as well. In this paper, we will review some of the significant issues associated with providing video capabilities in pervasive environments. We consider not only streaming video applications, but point-to- point video and video messaging capabilities as well. We will show how our previous work on content adaptation is being applied to these types of environments, show what role more general video analysis can play and describe a general architecture for video capture, storage, analysis and transmission.

Virtual Telescopes in Education - Hoban,S.; desJardins, Marie; Farrell,N.; Rathod,P.; Sachs,J.; Sansare,S.; Yesha,Y.; Keating,J.; Busschots,B.; Means,J.; others (Journal of Digital Information, 2002)
Virtual Telescopes in Education is providing the services required to operate a virtual observatory comprising distributed telescopes, including an interactive, constraint-based scheduling service, data and resource archive, proposal preparation and review environment, and a VTIE Journal. A major goal of VTIE is to elicit from learners questions about the nature of celestial objects and the physical processes that give rise to the spectacular imagery that catches their imaginations. Generation of constrained science questions will assist learners in the science process. To achieve interoperability with other NSDL resources, our approach follows the Open Archives Initiative and the W3C Semantic Web activity.

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

Algorithms for facility location problems with outliers - Charikar,Moses; Khuller, Samir; Mount, Dave; Narasimhan,Giri (Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, 2001)
Facility location problems are traditionally investigated with the assumption that all the clients are to be provided service. A significant shortcoming of this formulation is that a few very distant clients, called outliers, can exert a disproportionately strong influence over the final solution. In this paper we explore a generalization of various facility location problems (K-center, K-median, uncapacitated facility location etc) to the case when only a specified fraction of the customers are to be served. What makes the problems harder is that we have to also select the subset that should get service. We provide generalizations of various approximation algorithms to deal with this added constraint.

Analysis of a donor gene region for a variant surface glycoprotein and its expression site in African trypanosomes - LaCount,D. J; El‐Sayed, Najib M.; Kaul,S.; Wanless,D.; Turner,C. M.R; Donelson,J. E (Nucleic acids research, 2001)

Approximating large convolutions in digital images - Mount, Dave; Kanungo,T.; Netanyahu,N. S; Piatko,C.; Silverman,R.; Wu,A. Y (Image Processing, IEEE Transactions on, 2001)
Computing discrete two-dimensional (2-D) convolutions is an important problem in image processing. In mathematical morphology, an important variant is that of computing binary convolutions, where the kernel of the convolution is a 0-1 valued function. This operation can be quite costly, especially when large kernels are involved. We present an algorithm for computing convolutions of this form, where the kernel of the binary convolution is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some flexibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satisfies certain reasonable requirements. We say that such a convolution is valid. Given this flexibility we show that it is possible to compute binary convolutions more efficiently than would normally be possible for large kernels. Our main result is an algorithm which, given an m times;n image and a k-sided convex polygonal kernel K, computes a valid convolution in O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is independent of the area or perimeter of K, and our techniques do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's (1965) line-drawing algorithm and prefix-sums to update the convolution incrementally as the kernel is moved from one position to another across the image
Keywords: 2D; algorithm; binary; approximation; mathematical; convolution; convolution; binary; convolutions; Bresenham's; convolutions; convex; convolutions; geometric; images; discrete; kernel; convex; kernel; digital; line-drawing; morphology; morphology; approximation; object; image; polygonal; processing; large; processing; mathematical; theory; convolution; image; two-dimensional

Approximation algorithms for partial covering problems - Gandhi,R.; Khuller, Samir; Srinivasan, Aravind (Automata, Languages and Programming, 2001)
We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-vertex cover) in polynomial time. In addition to its simplicity, this algorithm has the advantage of being parallelizable. For instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-vertex cover on planar graphs, and for covering points in R d by disks.

Attentive toys - Haritaoglu,I.; Cozzi,A.; Koons,D.; Flickner,M.; Zotkin,Dmitry N; Yacoob,Yaser (International Conference on Multimedia and Expo, 2001)

Automatically Tracking and Analyzing the Behavior of Live Insect Colonies - Balch, Tucker; Zia Khan; Veloso, Manuela (AGENTS '01 Proceedings of the Fifth International Conference on Autonomous Agents, 2001)
We introduce the study of {\it live} social insect colonies as a relevant and exciting domain for the development and application of multi-agent systems modeling tools. Social insects provide a rich source of {\it traceable} social behavior for testing multi-agent tracking, prediction and modeling algorithms. An additional benefit of this research is the potential for contributions to experimental biology --- the principled techniques developed for analyzing artificial multi-agent systems can be applied to advance the state of knowledge of insect behavior. We contribute a novel machine vision system that addresses the challenge of tracking hundreds of small animals simultaneously. Fast color-based tracking is combined with movement-based tracking to locate ants in a real-time video stream. We also introduce new methods for analyzing the spatial activity of ant colonies. The system was validated in experiments with laboratory colonies of {\it Camponotus festinatus} and several example analyses of the colonies' spatial behavior are provided.

A case for dynamic view management - Kotidis,Yannis; Roussopoulos, Nick (ACM Transactions on Database SystemsACM Trans. Database Syst., 2001)

Cryptographic counters and applications to electronic voting - Katz, Jonathan; Myers,S.; Ostrovsky,R. (Advances in Cryptology—Eurocrypt 2001, 2001)
We formalize the notion of a cryptographic counter, which allows a group of participants to increment and decrement a cryptographic representation of a (hidden) numerical value privately and robustly. The value of the counter can only be determined by a trusted authority (or group of authorities, which may include participants themselves), and participants cannot determine any information about the increment/decrement operations performed by other parties.Previous efficient implementations of such counters have relied on fully-homomorphic encryption schemes; this is a relatively strong requirement which not all encryption schemes satisfy. We provide an alternate approach, starting with any encryption scheme homomorphic over the additive group ℤ2 (i.e., 1-bit XOR). As our main result, we show a general and efficient reduction from any such encryption scheme to a general cryptographic counter. Our main reduction does not use additional assumptions, is efficient, and gives a novel implementation of a general counter. The result can also be viewed as an efficient construction of a general n-bit cryptographic counter from any 1-bit counter which has the additional property that counters can be added securely. As an example of the applicability of our construction, we present a cryptographic counter based on the quadratic residuosity assumption and use it to construct an efficient voting scheme which satisfies universal verifiability, privacy, and robustness. Work done while the author was at Telcordia Technologies.

The Design of TerraDir - Bhattacharjee, Bobby; Keleher,Pete; Silaghi,Bujor (Technical Reports from UMIACS, UMIACS-TR-2001-4299, 2001)
We present the design and initial evaluation of TerraDir: an approach forimplementing customizable, distributed, peer-to-peer directories over which a broad range of wide-area resource discovery applications can be implemented. TerraDir's structure is two-tiered, consisting of a base protocol for providing arbitrary application-layer connectivity, and dynamic view materializations that efficiently realize different user-specified views of application-layer resources. TerraDir is specifically designed for data that can be arranged in a rooted hierarchy, and provides very efficient and robust lookups over such data while still being able to allow efficient searching. (Also referenced as UMIACS-TR-2001-4299)
Keywords: Technical Report

Differential point rendering - Varshney, Amitabh; Kalaiah,A. (Proceedings of 12th Eurographics Workshop on Rendering, 2001)

Distributed processing of very large datasets with DataCutter - Beynon,Michael D.; Kurc,Tahsin; Catalyurek,Umit; Chang,Chialin; Sussman, Alan; Saltz,Joel (Parallel Computing, 2001)
We describe a framework, called DataCutter, that is designed to provide support for subsetting and processing of datasets in a distributed and heterogeneous environment. We illustrate the use of DataCutter with several data-intensive applications from diverse fields, and present experimental results.
Keywords: Component architectures; Data analysis; Distributed computing; Multi-dimensional datasets; Runtime systems

A dynamic replica selection algorithm for tolerating timing faults - Krishnamurthy, S.; Sanders,W. H.; Michel Cukier (2001)
Server replication is commonly used to improve the fault tolerance and response time of distributed services. An important problem when executing time-critical applications in a replicated environment is that of preventing timing failures by dynamically selecting the replicas that can satisfy a client's timing requirement, even when the quality of service is degraded due to replica failures and excess load on the server. We describe the approach we have used to solve this problem in AQuA, a CORBA-based middleware that transparently replicates objects across a local area network. The approach we use estimates a replica's response time distribution based on performance measurements regularly broadcast by the replica. An online model uses these measurements to predict the probability with which a replica can prevent a timing failure for a client. A selection algorithm then uses this prediction to choose a subset of replicas that can together meet the client's timing constraints with at least the probability requested by the client. We conclude with experimental results based on our implementation.
Keywords: AQuA; client; client-server systems; CORBA-based middleware; distributed object management; distributed services; dynamic replica selection algorithm; fault tolerant computing; local area network; Local area networks; quality of service; replica failures; response time; server replication; time-critical applications; timing failures; timing fault tolerance

Dynamic resource allocation via video content and short-term traffic statistics - M. Wu; Joyce,R.A.; Wong,Hau-San; Guan,Long; Kung,Sun-Yuan (Multimedia, IEEE Transactions on, 2001)
The reliable and efficient transmission of high-quality variable bit rate (VBR) video through the Internet generally requires network resources be allocated in a dynamic fashion. This includes the determination of when to renegotiate for network resources, as well as how much to request at a given time. The accuracy of any resource request method depends critically on its prediction of future traffic patterns. Such a prediction can be performed using the content and traffic information of short video segments. This paper presents a systematic approach to select the best features for prediction, indicating that while content is important in predicting the bandwidth of a video hit stream, the use of both content and available short-term bandwidth statistics can yield significant improvements. A new framework for traffic prediction is proposed in this paper; experimental results show a smaller mean-square resource prediction error and higher overall link utilization
Keywords: allocation; link; allocation; multimedia; allocation; variable; bit; codes; content; bandwidth; error; short; Internet; dynamic; patterns; variable; prediction; rate; resource; segments; short-term; statistics; traffic; systems; resource; traffic; utilization; mean-square; video; video; video

Efficient algorithms for location and sizing problems in network design - Kumaran,K.; Srinivasan, Aravind; Qiong Wang; Lanning,S.; Ramakrishnan,K. G (IEEE Global Telecommunications Conference, 2001. GLOBECOM '01, 2001)
Large-scale location, sizing and homing problems of distributed network elements, have received much attention recently due to the massive deployment of broadband communication networks for services like Internet telephony and Web caching. Key considerations in designing these networks include modularity of capacity, economies of scale in cost, and reliability. We formulate a general class of such network design problems as Mixed-Integer Programs. These problems are computationally intractable in general; under various asymptotic conditions, we show how to compute near-optimal solutions. To deal with arbitrary instances, we develop new algorithms based on linear programming, as well as greedy randomized adaptive search. These algorithms achieved near-optimal solutions with reasonable computation time for our experiments
Keywords: Algorithm design and analysis; Broadband communication; broadband communication networks; broadband networks; capacity modularity; Communication networks; computer network reliability; distributed network elements; Economies of scale; greedy randomized adaptive search; homing; integer programming; Intelligent networks; Internet telephony; large-scale location problems; Large-scale systems; Linear programming; mixed-integer programs; near-optimal solutions; network design; Optical switches; randomised algorithms; reliability; search problems; sizing; Technological innovation; telecommunication network planning; Web caching

Efficient and Non-interactive Non-malleable Commitment - Di Crescenzo,Giovanni; Katz, Jonathan; Ostrovsky,Rafail; Smith,Adam (Advances in Cryptology — EUROCRYPT 2001Advances in Cryptology — EUROCRYPT 2001, 2001)
We present new constructions of non-malleable commitment schemes, in the public parameter model (where a trusted party makes parameters available to all parties), based on the discrete logarithm or RSA assumptions. The main features of our schemes are: they achieve near-optimal communication for arbitrarily-large messages and are non-interactive . Previous schemes either required (several rounds of) interaction or focused on achieving non-malleable commitment based on general assumptions and were thus efficient only when committing to a single bit. Although our main constructions are for the case of perfectly-hiding commitment, we also present a communication-efficient, non-interactive commitment scheme (based on general assumptions) that is perfectly binding.
Keywords: Computer science

Efficient network and I/O throttling for fine-grain cycle stealing - Ryu, Kyung D.; Hollingsworth, Jeffrey K; Keleher, Peter J. (Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM) - Supercomputing '01, 2001)

Efficient password-authenticated key exchange using human-memorable passwords - Katz, Jonathan; Ostrovsky,R.; Yung,M. (Advances in Cryptology—EUROCRYPT 2001, 2001)
There has been much interest in password-authenticated keyexchange protocols which remain secure even when users choose passwords from a very small space of possible passwords (say, a dictionary of English words). Under this assumption, one must be careful to design protocols which cannot be broken using off-line dictionary attacks in which an adversary enumerates all possible passwords in an attempt to determine the correct one. Many heuristic protocols have been proposed to solve this important problem. Only recently have formal validations of security (namely, proofs in the idealized random oracle and ideal cipher models) been given for specific constructions [3,10,22].Very recently, a construction based on general assumptions, secure in the standard model with human-memorable passwords, has been proposed by Goldreich and Lindell [17]. Their protocol requires no public parameters; unfortunately, it requires techniques from general multi-party computation which make it impractical. Thus, [17] only proves that solutions are possible “in principal”. The main question left open by their work was finding an efficient solution to this fundamental problem. We showan efficient, 3-round, password-authenticated key exchange protocol with human-memorable passwords which is provably secure under the Decisional Diffie-Hellman assumption, yet requires only (roughly) 8 times more computation than “standard” Diffie-Hellman key exchange [14] (which provides no authentication at all). We assume public parameters available to all parties. We stress that we work in the standard model only, and do not require a “random oracle” assumption.

Efficient perspective-accurate silhouette computation and applications - Pop, Mihai; Duncan,Christian; Barequet,Gill; Goodrich,Michael; Huang,Wenjing; Kumar,Subodh (Proceedings of the seventeenth annual symposium on Computational geometry, 2001)
Silhouettes are perceptually and geometrically salient features of geo metric models. Hence a number of graphics and visualization applications need to find them to aid further processing. The efficient computation of silhouettes, especially in the context of perspective projection, is known to be difficult. This paper presents a novel efficient and practical algorithm to compute silhouettes from a sequence of viewpoints under perspective projection. Parallel projection is a special case of this algorithm. Our approach is based on a point-plane duality in three dimensions, which allows an efficient computation of the changes in the silhouette of a polygonal model between consecutive frames. In addition, we present several applications of our technique to problems from computer graphics and medical visualization. We also provide experimental data that show the efficiency of our approach. million vertices on an SGI Onyx workstation.
Keywords: rendering; silhouette; simplification

An empirical study of regression test selection techniques - Graves,Todd L.; Harrold,Mary Jean; Kim,Jung-Min; Porter, Adam; Rothermel,Gregg (ACM Transactions on Software Engineering and MethodologyACM Trans. Softw. Eng. Methodol., 2001)

Enabling Commuters to Find the Best Route: An Interface for Analyzing Driving History Logs - Konishi,M.; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the IFIP Conference on Human-Computer Interaction (Interact2001), 2001)
This paper describes a prototype interface design for an automobile driving history log. It allows drivers to choose the best route among several alternatives for their common trips. Recorded data includes time to complete the travel, fuel consumption, and number of stops.

A feature-based approach to automated design of multi-piece sacrificial molds - Dhaliwal,S.; Gupta,S.K.; Huang,J.; Kumar,M. (Journal of Computing and Information Science in Engineering, 2001)

Finding close friends on the Internet - Kommareddy,C.; Shankar,N.; Bhattacharjee, Bobby (Network Protocols, 2001. Ninth International Conference on, 2001)
We consider the problem of finding nearby application-peers (close friends) over the Internet. We focus on unicast-only solutions and introduce a new scheme -Beaconing-for finding peers that are near. Our scheme uses distance measurement points (called beacons) and can be implemented entirely in the application-layer without investing in large infrastructure changes. We present an extensive evaluation of Beaconing and compare it to existing schemes including Expanding Ring searches and Triangulation. Our experiments show that 3-8 beacons are sufficient to provide efficient peer-location service on 10 000 node Internet-like topologies. Further, our results are 2-5 times more accurate than existing techniques. We also present results from an implementation of Beaconing over a non-trivial wide-area testbed. In our experiments, Beaconing is able to efficiently (< 3 K Bytes and < 50 packets on average), quickly (< 1 second on average), and accurately (< 20 ms error on average) find nearby peers on the Internet.
Keywords: application-layer; application-peers; Beaconing; beacons; close; distance; Expanding; friends; Internet-like; Internet; IP; measurement; nearby; network; peer-location; points; protocols; Ring; searches; service; solutions; testbed; topologies; topology; transport; Triangulation; unicast-only; wide-area

Gathering knowledge for a question answering system from heterogeneous information sources - Katz,Boris; Jimmy Lin; Felshin,Sue (Proceedings of the workshop on Human Language Technology and Knowledge Management - Volume 2001, 2001)
Although vast amounts of information are available electronically today, no effective information access mechanism exists to provide humans with convenient information access. A general, open-domain question answering system is a solution to this problem. We propose an architecture for a collaborative question answering system that contains four primary components: an annotations system for storing knowledge, a ternary expression representation of language, a transformational rule system for handling some complexities of language, and a collaborative mechanism by which ordinary users can contribute new knowledge by teaching the system new information. We have developed a initial prototype, called Webnotator, with which to test these ideas.

A geometric algorithm for automated design of multi-stage molds for manufacturing multi-material objects - Kumar,Malay; Gupta, Satyandra K. (ACM, 2001)
This paper describes a geometric algorithm for automated design of multi-stage molds for manufacturing multi-material objects. In multi-stage molding process, the desired multi-material object is produced by carrying out multiple molding operations in a sequence, adding one material in the target object in each mold-stage. We model multi-material objects as an assembly of single-material components. Each mold-stage can only add one type of material. Therefore, we need a sequence of mold-stages such that (1) each mold-stage only adds one single-material component either fully or partially, and (2) the molding sequence completely produces the desired object. In other to find a feasible mold-stage sequence, our algorithm decomposes the multi-material object into a number of homogeneous components to find a feasible sequence of homogeneous components that can be added in sequence to produce the desired multi-material object. Our algorithm starts with the final object assembly and considers removing components either completely or partially from the object one-at-a-time such that it results in the previous state of the object assembly. If the component can be removed from the target object leaving the previous state of the object assembly a connected solid then we consider such decomposition a valid step in the stage sequence. This step is recursively repeated on new states of the object assembly, until the object assembly reaches a state where it only consists of one component. When an object-decomposition has been found that leads to a feasible stage sequence, the gross mold for each stage is computed and decomposed into two or more pieces to facilitate the molding operation. We expect that our algorithm will provide a step towards automating the design of multi-stage molds and therefore will help in reducing the mold design lead-time for multi-stage molds.
Keywords: geometric reasoning; mold design; spatial partitioning

Geometry of Eye Design: Biology and Technology - Fermüller, Cornelia; Aloimonos, J. (Multi-Image Analysis, 2001)
Natural or artificial vision systems process the images that they collect with their eyes or cameras in order to derive information for performing tasks related to navigation and recognition. Since the way images are acquired determines how dificult it is to perform a visual task, and since systems have to cope with limited resources, the eyes used by a specific system should be designed to optimize subsequent image processing as it relates to particular tasks. Different ways of sampling light, i.e., different eyes, may be less or more powerful with respect to particular competences. This seems intuitively evident in view of the variety of eye designs in the biological world. It is shown here that a spherical eye (an eye or system of eyes providing panoramic vision) is superior to a camera-type eye (an eye with restricted field of view) as regards the competence of three-dimensional motion estimation. This result is derived from a statistical analysis of all the possible computational models that can be used for estimating 3D motion from an image sequence. The findings explain biological design in a mathematical manner, by showing that systems that fly and thus need good estimates of 3D motion gain advantages from panoramic vision. Also, insights obtained from this study point to new ways of constructing powerful imaging devices that suit particular tasks in robotics, visualization and virtual reality better than conventional cameras, thus leading to a new camera technology.

A hypergraph-based workload partitioning strategy for parallel data aggregation - Chang,C.; Kurc, T.; Sussman, Alan; Catalyurek,U.; Saltz, J. (Proceedings of the Eleventh SIAM Conference on Parallel Processing for Scientific Computing, 2001)

Integrated Microelectromechanical System (MEMS) Inertial Measurement Unit (IMIMU) - Fedder,Gary K.; Blanton,Shawn; Carley,L. R.; Gupta, Satyandra K.; Koester,David (CARNEGIE-MELLON UNIVERSITY, 2001)
Processes, designs and design tools are developed to enable the monolithic integration of arrays of inertial microsensors with electronics. Accelerometers and gyroscopes, fabricated in a single CMOS process, are functional and demonstrate a single chip IMU. Two integrated post CMOS micro-machining processes are demonstrated. Thin-film microstructures are defined from the metal-dielectric stack of a conventional process. In the second process, a back-side silicon etch, followed by front-side DRIE produces bulk silicon microstructures. Accelerometer and gyroscope designs are developed with accompanying low noise electronic circuitry. Noise performance was limited to 1/f circuit noise. The chip output sensibility is set by the interface circuit design. A thermally stabilized accelerometer and circuit design is demonstrated using embedded polysilicon resistors as temperature sensors and heaters in a closed loop. Nested gyroscope topologies are demonstrated with a lateral MEMS accelerometer used as a coriolis acceleration sensor. Modeling and simulation tools that simultaneously consider the electromechanical transducer and the electronic circuit to predict system performance are developed. Electrical, electromechanical and mechanical parasitics required to enable predictive lumped parameter simulation are identified and can be extracted, enabling a designer to confidently estimate design performance prior to fabrication. Generic physics-based fault models for surface-micromachined actuators and sensors are developed that enable effective testing, diagnosis and design for manufacturability.
Keywords: *ELECTROMECHANICAL DEVICES; *GYROSCOPES; *INERTIAL MEASUREMENT UNITS; *INERTIAL NAVIGATION; *MICROELECTROMECHANICAL SYSTEMS; ACCELEROMETERS; BULK MATERIALS; CHIPS(ELECTRONICS); CIRCUITS; CLOSED LOOP SYSTEMS; CORIOLIS EFFECT; Detectors; DIELECTRICS; ELECTRICAL AND ELECTRONIC EQUIPMENT; EMBEDDING; METALS; MICROSENSORS.; MICROSTRUCTURE; MONOLITHIC STRUCTURES(ELECTRONICS); NAVIGATION AND GUIDANCE; PARASITES; PE63739E; PERFORMANCE(ENGINEERING); POLYSILICONS; RESISTORS; SILICON; TEMPERATURE SENSITIVE ELEMENTS; THERMAL STABILITY; THIN FILMS; tools; Topology; WUAFRLE1170030

Integrating distributed scientific data sources with MOCHA and XRoaster - Rodriguez-Martinez,M.; Roussopoulos, Nick; McGann,J. M; Kelley,S.; Mokwa,J.; White,B.; Jala,J. (Thirteenth International Conference on Scientific and Statistical Database Management, 2001. SSDBM 2001. Proceedings, 2001)
MOCHA is a novel middleware system for integrating distributed data sources that we have developed at the University of Maryland. MOCHA is based on the idea that the code that implements user-defined types and functions should be automatically deployed to remote sites by the middleware system itself. To this end, we have developed an XML-based framework to specify metadata about data sites, data sets, and user-defined types and functions. XRoaster is a graphical tool that we have developed to help the user create all the XML metadata elements to be used in MOCHA
Keywords: client-server systems; data sets; data sites; Databases; Distributed computing; distributed databases; distributed scientific data source integration; Educational institutions; graphical tool; hypermedia markup languages; IP networks; java; Large-scale systems; Maintenance engineering; meta data; metadata; Middleware; middleware system; MOCHA; Query processing; remote sites; scientific information systems; user-defined types; visual programming; XML; XML metadata elements; XML-based framework; XRoaster

KidStory: A technology design partnership with children - Taxén,G.; Druin, Allison; Fast,C.; Kjellin,M. (Behaviour & Information Technology, 2001)

Learning probabilistic models of relational structure - Getoor, Lise; Friedman,N.; Koller,D.; Taskar,B. (MACHINE LEARNING-INTERNATIONAL WORKSHOP, 2001)
Most real-world data is stored in relational form. Incontrast, most statistical learning methods work with “flat” data representations, forcing us to convert our data into a form that loses much of the relational struc- ture. The recently introduced framework of proba- bilistic relational models (PRMs) allows us to repre- sent probabilistic models over multiple entities that utilize the relations between them. In this paper, we propose the use of probabilistic models not only for the attributes in a relational model, but for the rela- tional structure itself. We propose two mechanisms for modeling structural uncertainty: reference uncertainty and existence uncertainty. We describe the appropriate conditions for using each model and present learning algorithms for each. We present experimental results showing that the learned models can be used to pre- dict relational structure and, moreover, the observed relational structure can be used to provide better pre- dictions for the attributes in the model.

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

Modeling information content using observable behavior - Oard, Douglas; Kim,J. (PROCEEDINGS OF THE ANNUAL MEETING-AMERICAN SOCIETY FOR INFORMATION SCIENCE, 2001)

Multiprocessor clustering for embedded systems - Kianzad,V.; Bhattacharyya, Shuvra S. (Euro-Par 2001 Parallel Processing, 2001)

Optimal collective dichotomous choice under partial order constraints - Ben-Yashar,Ruth; Khuller, Samir; Kraus,Sarit (Mathematical Social Sciences, 2001)
This paper generalizes optimal collective dichotomous choices by including constraints which limit combinations of acceptance and rejection decisions for m projects under consideration. Two types of constraints are examined. The first type occurs when acceptance of some projects requires acceptance of others. This type reduces the choice problem to the tractable (solvable in polynomial time) problem of finding a maximum weight closed subset of a directed acyclic graph. The second type occurs when some projects must be accepted when certain others are rejected. We show that this type renders the choice problem to be NP-complete by reduction from the problem of Vertex Cover. Applicability of the generalization to information filtering is discussed.
Keywords: constraints; Information filtering; Optimal collective dichotomous choice

Perceptual organization as generic object recognition - Jacobs, David W. (From Fragments to Objects Segmentation and Grouping in VisionFrom Fragments to Objects Segmentation and Grouping in Vision, 2001)
We approach some aspects of perceptual organization as the process of fitting generic models of objects to image data. A generic model of shape encodes prior knowledge of what shapes are likely to come from real objects. For such a model to be useful, it must also lead to efficient computations. We show that models of shape based on local properties of objects can be effectively used by simple, neurally plausible networks, and that they can still encode many perceptually important properties. We also discuss the relationship between perceptual salience and viewpoint invariance. Many gestalt properties are the subset of viewpoint invariant properties that can be encoded using the smallest possible sets of features, making them the ecologically valid properties that can also be used with computational efficiency. These results suggest that implicit models of shape used in perceptual organization arise from a combination of ecological and computational constraints. Finally, we discuss experiments demonstrating the role of convexity in amodal completion. These experiments point out some of the limitations of simple local shape models, and indicate the potential role that the part structure of objects also plays in perceptual organization.

Performance optimization for data intensive grid applications - Beynon,M. D; Sussman, Alan; Catalyurek,U.; Kurc, T.; Saltz, J. (Active Middleware Services, 2001. Third Annual International Workshop on, 2001)

The price of safety in an active network - Alexander,D. S; Menage,P. B; Keromytis,A. D; Arbaugh, William A.; Anagnostakis,K. G; Smith,J. M (Journal of Communications and Networks, 2001)

Probabilistic models of text and link structure for hypertext classification - Getoor, Lise; Segal,E.; Taskar,B.; Koller,D. (IJCAI workshop on text learning: beyond supervision, 2001)
Most text classification methods treat each document as anindependent instance. However, in many text domains, doc- uments are linked and the topics of linked documents are cor- related. For example, web pages of related topics are often connected by hyperlinks and scientific papers from related fields are commonly linked by citations. We propose a unified probabilistic model for both the textual content and the link structure of a document collection. Our model is based on the recently introduced framework of Probabilistic Relational Models (PRMs), which allows us to capture cor- relations between linked documents. We show how to learn these models from data and use them efficiently for classifi- cation. Since exact methods for classification in these large models are intractable, we utilize belief propagation, an ap- proximate inference algorithm. Belief propagation automat- ically induces a very natural behavior, where our knowledge about one document helps us classify related ones, which in turn help us classify others. We present preliminary empiri- cal results on a dataset of university web pages.

A prototype experience management system for a software consulting organization - Mendonça Neto,M. G.; Seaman,C.; Basili, Victor R.; Kim,Y. M (Thirteenth International Conference on Software Engineering and Knowledge Engineering, 2001)
The Experience Management System (EMS) is aimed atsupporting the capture and reuse of software-related experience, based on the Experience Factory concept. It is being developed for use in a multinational software engineering consultancy, Q-Labs. Currently, a prototype EMS exists and has been evaluated. This paper focuses on the EMS architecture, underlying data model, implementation, and user interface.

Provisional authorizations - Jajodia,S.; Kudo,M.; V.S. Subrahmanian (E-commerce Security and Privacy, 2001)
Past generations of access control systems, when faced with an access request, have issued a “yes” (resp. “no”) answer to the access request resulting in access being granted (resp. denied). In this chapter, we argue that for the world’s rapidly proliferating business to business (B2B) applications and auctions, “yes/no” responses are just not enough. We propose the notion of a “provisional authorization” which intuitively says “You may perform the desired access provided you cause condition C to be satisfied.” For instance, a user accessing an online brokerage may receive some information if he fills out his name/address, but not otherwise. While a variety of such provisional authorization mechanisms exist on the web, they are all hardcoded on an application by application basis. We show that given (almost) any logic L, we may define a provisional authorization specification language pASLL. pASLL is based on the declarative, polynomially evaluable authorization specification language ASL proposed by Jajodia et al [JSS97]. We define programs in pASLL, and specify how given any access request, we must find a “weakest” precondition under which the access can be granted (in the worst case, if this weakest precondition is “false” this amounts to a denial). We develop a model theoretic semantics for pASLL and show how it can be applied to online sealed-bid auction servers and online contracting.

The role of a natural language conversational interface in online sales: A case study - Chai,J.; Jimmy Lin; Zadrozny,W.; Ye,Y.; Stys-Budzikowska,M.; Horvath,V.; Kambhatla,N.; Wolf,C. (International Journal of Speech Technology, 2001)
This paper describes the evaluation of a natural language dialog-based navigation system (HappyAssistant) that helps users access e-commerce sites to find relevant information about products and services. The prototype system leverages technologies in natural language processing and human-computer interaction to create a faster and more intuitive way of interacting with websites, especially for less experienced users. The result of a comparative study shows that users prefer the natural language-enabled navigation two to one over the menu driven navigation. In addition, the study confirmed the efficiency of using natural language dialog in terms of the number of clicks and the amount of time required to obtain the relevant information. In the case study, as compared to the menu driven system, the average number of clicks used in the natural language system was reduced by 63.2% and the average time was reduced by 33.3%.

Selectivity estimation using probabilistic models - Getoor, Lise; Taskar,Benjamin; Koller,Daphne (ACM SIGMOD Record, 2001)
Estimating the result size of complex queries that involve selection on multiple attributes and the join of several relations is a difficult but fundamental task in database query processing. It arises in cost-based query optimization, query profiling, and approximate query answering. In this paper, we show how probabilistic graphical models can be effectively used for this task as an accurate and compact approximation of the joint frequency distribution of multiple attributes across multiple relations. Probabilistic Relational Models (PRMs) are a recent development that extends graphical statistical models such as Bayesian Networks to relational domains. They represent the statistical dependencies between attributes within a table, and between attributes across foreign-key joins. We provide an efficient algorithm for constructing a PRM front a database, and show how a PRM can be used to compute selectivity estimates for a broad class of queries. One of the major contributions of this work is a unified framework for the estimation of queries involving both select and foreign-key join operations. Furthermore, our approach is not limited to answering a small set of predetermined queries; a single model can be used to effectively estimate the sizes of a wide collection of potential queries across multiple tables. We present results for our approach on several real-world databases. For both single-table multi-attribute queries and a general class of select-join queries, our approach produces more accurate estimates than standard approaches to selectivity estimation, using comparable space and time.

Shared index scans for data warehouses - Kotidis1⋆,Y.; Sismanis,Y.; Roussopoulos, Nick (Data Warehousing and Knowledge Discovery, 2001)

Temporal agent programs - Dix,Jürgen; Kraus,Sarit; V.S. Subrahmanian (Artificial Intelligence, 2001)
The “agent program” framework introduced by Eiter, Subrahmanian and Pick [Artificial Intelligence 108 (1–2) (1999) 179], supports developing agents on top of arbitrary legacy code. Such agents are continuously engaged in an “event occurs→think→act→event occurs…” cycle. However, this framework has two major limitations: (1)all actions are assumed to have no duration, and (2) all actions are taken now, but cannot be scheduled for the future. In this paper, we present the concept of a “temporal agent program” (tap for short) and show that using taps, it is possible to build agents on top of legacy code that can reason about the past and about the future, and that can make temporal commitments for the future now. We develop a formal semantics for such agents, extending the concept of a status set proposed by Eiter et al., and develop algorithms to compute the status sets associated with temporal agent programs. Last, but not least, we show how taps support the decision making of collaborative agents.
Keywords: agents; Heterogenous systems; Information integration; logic programming; temporal reasoning

Translation lexicon acquisition from bilingual dictionaries - David Doermann; Ma,H.; Karagol-Ayan,B.; Oard, Douglas (Proceedings of SPIE, 2001)

Unforgeable encryption and chosen ciphertext secure modes of operation - Katz, Jonathan; Yung,M. (Fast Software Encryption, 2001)
We find certain neglected issues in the study of private-key encryption schemes. For one, private-key encryption is generally held to the same standard of security as public-key encryption (i.e., indistinguishability) even though usage of the two is very different. Secondly, though the importance of secure encryption of single blocks is well known, the security of modes of encryption (used to encrypt multiple blocks) is often ignored. With this in mind, we present definitions of a new notion of security for private-key encryption called encryption unforgeability which captures an adversary’s inability to generate valid ciphertexts. We show applications of this definition to authentication protocols and adaptive chosen ciphertext security.Additionally, we present and analyze a new mode of encryption, RPC (for Related Plaintext Chaining), which is unforgeable in the strongest sense of the above definition. This gives the first mode provably secure against chosen ciphertext attacks. Although RPC is slightly less efficient than, say, CBC mode (requiring about 33% more block cipher applications and having ciphertext expansion of the same amount when using a block cipher with 128-bit blocksize), it has highly parallelizable encryption and decryption operations.

User modeling for information access based on implicit feedback - Kim,J.; Oard, Douglas; Romanik,K. (3rd Symposium of ISKO-France, Information Filtering and Automatic Summarisation in networds, 2001)

Visualization of large data sets with the Active Data Repository - Kurc, T.; Catalyurek,U.; Chang,Chialin; Sussman, Alan; Saltz, J. (IEEE Computer Graphics and Applications, 2001)
We implement ray-casting-based volume rendering and isosurface rendering methods using the Active Data Repository (ADR) for visualizing out-of-core data sets. We have developed the ADR object-oriented framework to provide support for applications that employ range queries with user-defined mapping and aggregation operations on large-scale multidimensional data. ADR targets distributed-memory parallel machines with one or more disks attached to each node. It is designed as a set of modular services implemented in C++, which can be customized for application-specific processing. The ADR runtime system supports common operations such as memory management, data retrieval, and scheduling of processing across a parallel machine
Keywords: active data repository; ADR runtime system; Algorithm design and analysis; application-specific processing; C++; data mining; data retrieval; data visualisation; Data visualization; distributed-memory parallel machines; Indexing; Information retrieval; isosurface rendering; Isosurfaces; large data sets; large-scale multidimensional data; Memory management; modular services; out-of-core data sets; parallel machine; Parallel machines; Partitioning algorithms; ray-casting-based volume rendering; Rendering (computer graphics); Runtime; software libraries; storage management

z-Approximations - Hassin,Refael; Khuller, Samir (Journal of Algorithms, 2001)
Approximation algorithms for NP-hard optimization problems have been widely studied for over three decades. Most of these measure the quality of the solution produced by taking the ratio of the cost of the solution produced by the algorithm to the cost of an optimal solution. In certain cases, this ratio may not be very meaningful—for example, if the ratio of the worst solution to the best solution is at most some constant α, then an approximation algorithm with factor α may in fact yield the worst solution! To overcome this hurdle (among others), several authors have independently suggested the use of a different measure which we call z-approximation. An algorithm is an α z-approximation if it runs in polynomial time and produces a solution whose distance from the optimal one is at most α times the distance between the optimal solution and the worst possible solution. The results known so far about z-approximations are either of the inapproximability type or rather straightforward observations. We design polynomial time algorithms for several fundamental discrete optimization problems; in particular we obtain a z-approximation factor of 12 for the directed traveling salesman problem (TSP) (with no triangle inequality assumption). For the undirected TSP this improves to 13. We also show that if there is a polynomial time algorithm that for any fixed ϵ > 0 yields an ϵ z-approximation then P = NP. We also present z-approximations for severa1 other problems such as max cut, stacker crane, maximum acyclic subgraph, and minimum disjoint cycle cover.

Agents in Network Management - Ertugay,Osman; Hicks, Michael W.; Smith,Jonathan; Kornblum,Jessica (Technical Reports (CIS), 2000)
The ubiquity and complexity of modern networks require automated management and control. With increases in scale, automated solutions based on simple data access models such as SNMP will give way to more distributed and algorithmic techniques. This article outlines present and near-term solutions based on the ideas of active networks and mobile agents, which permit sophisticated programmable control and management of ultra large scale networks.

Algorithm 805: computation and uses of the semidiscrete matrix decomposition - Kolda,Tamara G.; O'Leary, Dianne P. (ACM Trans. Math. Softw., 2000)
We present algorithms for computing a semidiscrete approximation to a matrix in a weighted norm, with the Frobenius norm as a special case. The approximation is formed as a weighted sum of outer products of vectors whose elements are ±1 or 0, so the storage required by the approximation is quite small. We also present a related algorithm for approximation of a tensor. Applications of the algorithms are presented to data compression, filtering, and information retrieval; software is provided in C and in Matlab.
Keywords: compression; latent semantic indexing; Matrix decomposition; semidiscrete decompositin; singular value decomposition

The analysis of a simple k-means clustering algorithm - Kanungo,Tapas; Mount, Dave; Netanyahu,Nathan S.; Piatko,Christine; Silverman,Ruth; Wu,Angela Y. (Proceedings of the sixteenth annual symposium on Computational geometry, 2000)

Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem - Guttmann-Beck,N.; Hassin,R.; Khuller, Samir; Raghavachari,B. (Algorithmica, 2000)
Let G=(V,E) be a complete undirected graph with vertex set V , edge set E , and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V 1 , . . ., V k . The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them.

Attacking the bottlenecks of backfilling schedulers - Zotkin,Dmitry N; Keleher,P. J; Perkovic,D. (Cluster Computing, 2000)

Automatic Text Detection and Tracking in Digital Video - Li,H.; David Doermann; Kia,O. (IEEE Transactions on Image Processing - Special Issue on Image and Video Processing for Digital Libraries, 2000)
Text that appears in a scene or is graphically added to video can provide an important supplemental source of index information as well as clues for decoding the video's structure and for classification. In this work, we present algorithms for detecting and tracking text in digital video. Our system implements a scale-space feature extractor that feeds an artificial neural processor to detect text blocks. Our text tracking scheme consists of two modules: a sum of squared difference (SSD) based module to find the initial position and a contour-based module to refine the position. Experiments conducted with a variety of video sources show that our scheme can detect and track text robustly.

The capacitated k-center problem - Khuller, Samir; Sussmann,Y. J (SIAM Journal on Discrete Mathematics, 2000)

Centers of sets of pixels - Khuller, Samir; Rosenfeld,Azriel; Wu,Angela (Discrete Applied Mathematics, 2000)
The center of a connected graph G is the set of nodes of G for which the maximum distance to any other node of G is as small as possible. If G is a simply connected set of lattice points (“pixels”) with graph structure defined by 4-neighbor adjacency, we show that the center of G is either a 2×2 square block, a diagonal staircase, or a (dotted) diagonal line with no gaps.
Keywords: Center; Chessboard distance; City block distance; Intrinsic distance; Simply connected set

A chosen ciphertext attack against several e-mail encryption protocols - Katz, Jonathan; Schneier,B. (Ninth USENIX Security Symposium, 2000)

Chromosome Identification Using Hidden Markov Models: Comparison with Neural Networks, Singular Value Decomposition, Principal Components Analysis, and Fisher Discriminant Analysis - Conroy,John M.; Kolda,Tamara G.; O'Leary, Dianne P.; O'Leary,Timothy J (Laboratory Investigation, 2000)
The analysis of G-banded chromosomes remains the most important tool available to the clinical cytogeneticist. The analysis is laborious when performed manually, and the utility of automated chromosome identification algorithms has been limited by the fact that classification accuracy of these methods seldom exceeds about 80% in routine practice. In this study, we use four new approaches to automated chromosome identification — singular value decomposition (SVD), principal components analysis (PCA), Fisher discriminant analysis (FDA), and hidden Markov models (HMM) — to classify three well-known chromosome data sets (Philadelphia, Edinburgh, and Copenhagen), comparing these approaches with the use of neural networks (NN). We show that the HMM is a particularly robust approach to identification that attains classification accuracies of up to 97% for normal chromosomes and retains classification accuracies of up to 95% when chromosome telomeres are truncated or small portions of the chromosome are inverted. This represents a substantial improvement of the classification accuracy for normal chromosomes, and a doubling in classification accuracy for truncated chromosomes and those with inversions, as compared with NN-based methods. HMMs thus appear to be a promising approach for the automated identification of both normal and abnormal G-banded chromosomes.
Keywords: addiction disorders; anxiety; depression; psychopharmacology; schizophrenia

Comparative Evaluation of a Natural Language Dialog Based System and a Menu-Driven System for Information Access: A Case Study - Chai,J.; Jimmy Lin; Zadrozny,W.; Ye,Y.; Budzikowska,M.; Horvath,V.; Kambhatla,N.; Wolf,C. (In Proceedings of the International Conference on Multimedia Information Retrieval (RIAO 2000), 2000)
This paper describes the evaluation of a natural language dialog based navigation system (HappyAssistant) thathelps users access e-commerce sites to find relevant information about products and services. The prototype system leverages technologies in natural language processing and human computer interaction to create a faster and more intuitive way of interacting with websites, especially for the less experienced users. The result of a comparative study shows that users prefer the natural language enabled navigation two to one over the menu driven navigation. In addition, the study confirmed the efficiency of using natural language dialog in terms of the number of clicks and the amount of time required to obtain the relevant information. In the case study, comparing to the menu driven system, the average number of clicks used in the natural language system was reduced by 63.2% and the average time was reduced by 33.3%.

A comparison of voice controlled and mouse controlled web browsing - Christian,Kevin; Kules,Bill; Shneiderman, Ben; Youssef,Adel (Proceedings of the fourth international ACM conference on Assistive technologies, 2000)
Keywords: human-computer; interaction; User interfaces; voice browsers; voice recognition; web browsing

Complete characterization of security notions for probabilistic private-key encryption - Katz, Jonathan; Yung,Moti (Proceedings of the thirty-second annual ACM symposium on Theory of computing, 2000)

DataCutter: Middleware for filtering very large scientific datasets on archival storage systems - Beynon, M.; Ferreira,R.; Kurc, T.; Sussman, Alan; Saltz, J. (NASA conference publication, 2000)

Design of a Framework for Data-Intensive Wide-Area Applications - Beynon,Michael D.; Kurc,Tahsin; Sussman, Alan; Saltz,Joel (Heterogeneous Computing Workshop, 2000)
Applications that use collections of very large, distributed datasets have become an increasingly important part of science and engineering. With high performance wide-area networks become more pervasive, there is interest in making collective use of distributed computational and data resources. Recent work has converged to the notion of the Grid, which attempts to uniformly present a heterogeneous collection of distributed resources. Current Grid research covers many areas from low-level infrastructure issues to high-level application concerns. However, providing support for efficient exploration and processing of very large scientific datasets stored in distributed archival storage systems remains a challenging research issue.We have initiated an effort that focuses on developing efficient data-intensive applications in a Grid environment. In this paper, we present a framework, called filter-stream programming that represents the processing units of a data-intensive application as a set of filters, which are designed to be efficient in their use of memory and scratch space. We describe a prototype infrastructure that supports execution of applications using the proposed framework. We present the implementation of two applications using the filter-stream programming framework, and discuss experimental results demonstrating the effects of heterogeneous resources on application performance.
Keywords: application decomposition; data analysis and exploration; Data-intensive applications

Direct annotation: a drag-and-drop strategy for labeling photos - Shneiderman, Ben; Kang,H. (IEEE International Conference on Information Visualization, 2000. Proceedings, 2000)
Annotating photographs is such a time-consuming, tedious and error-prone data entry task that it discourages most owners of personal photo libraries. By allowing the user to drag labels, such as personal names, from a scrolling list and drop them onto 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: Biomedical imaging; Cities and towns; Computer errors; Computer science; database indexing; database schema; Databases; digital libraries; direct annotation; direct manipulation; drag-and-drop strategy; Educational institutions; graphical user interface; Graphical user interfaces; History; hobby computing; image searching; label placement; Labeling; Laboratories; Libraries; personal information systems; personal names database; PhotoFinder prototype; photograph labelling; photographic libraries; Photography; scrolling list; user interface design; visual databases

Domain name based visualization of Web histories in a zoomable user interface - Gandhi,R.; Kumar,G.; Bederson, Benjamin B.; Shneiderman, Ben (11th International Workshop on Database and Expert Systems Applications, 2000. Proceedings, 2000)
Users of hypertext systems like the World Wide Web (WWW) often find themselves following hypertext links deeper and deeper, only to find themselves “lost” and unable to find their way back to the previously visited pages. We have implemented a Web browser companion called Domain Tree Browser (DTB) that builds a tree structured visual navigation history while browsing the Web. The Domain Tree Browser organizes the URLs visited based on the domain name of each URL and shows thumbnails of each page in a zoomable window
Keywords: Computer science; data visualisation; domain name; domain name based visualization; Domain Tree Browser; Educational institutions; History; hypermedia; hypertext links; hypertext systems; information resources; Navigation; online front-ends; thumbnails; Tree graphs; tree structured visual navigation history; Uniform resource locators; URLs; User interfaces; Visualization; Web browser companion; Web histories; Web pages; World Wide Web; zoomable user interface; zoomable window

On the efficiency of local decoding procedures for error-correcting codes - Katz, Jonathan; Trevisan,Luca (Proceedings of the thirty-second annual ACM symposium on Theory of computing, 2000)

Efficient performance prediction for large-scale, data-intensive applications - Kurc, T.; Uysal, M.; Eom, H.; Hollingsworth, Jeffrey K; Saltz, J.; Sussman, Alan (International Journal of High Performance Computing Applications, 2000)

Efficiently computing and updating triangle strips for real-time rendering - El-Sana,J.; Evans,F.; Kalaiah,A.; Varshney, Amitabh; Skiena,S.; Azanli,E. (Computer Aided Design, 2000)
Triangle strips are a widely used hardware-supported data-structure to compactly represent and efficiently render polygonal meshes. In thispaper we survey the efficient generation of triangle strips as well as their variants. We present efficient algorithms for partitioning polygonal meshes into triangle strips. Triangle strips have traditionally used a buffer size of two vertices. In this paper we also study the impact of larger buffer sizes and various queuing disciplines on the effectiveness of triangle strips. View-dependent simplification has emerged as a powerful tool for graphics acceleration in visualization of complex environments. However, in a view-dependent framework the triangle mesh connectivity changes at every frame making it difficult to use triangle strips. In this paper we present a novel data-structure, Skip Strip, that efficiently maintains triangle strips during such view-dependent changes. A Skip Strip stores the vertex hierarchy nodes in a skip-list-like manner with path compression. We anticipate that Skip Strips will provide a road-map to combine rendering acceleration techniques for static datasets, typical of retained-mode graphics applications, with those for dynamic datasets found in immediate-mode applications.

An empirical study of regression test application frequency - Kim,Jung-Min; Porter, Adam; Rothermel,Gregg (Proceedings of the 22nd international conference on Software engineering - ICSE '00, 2000)

Evaluation challenges for a Federation of heterogeneous information providers: the case of NASA's Earth Science Information Partnerships - Plaisant, Catherine; Komlodi,A.; Lindsay,F. (Enabling Technologies: Infrastructure for Collaborative Enterprises, 2000. (WET ICE 2000). Proeedings. IEEE 9th International Workshops on, 2000)
NASA's Earth Science Information Partnership Federation is an experiment funded to assess the ability of a group of widely heterogeneous earth science data or service providers to self organize and provide improved and affordable access to an expanding earth science user community. As it is self-organizing, the Federation is mandated to set in place an evaluation methodology and collect metrics reflecting the outcomes and benefits of the Federation. This paper describes the challenges of organizing such a federated partnership self-evaluation and discusses the issues encountered during the metrics definition phase of the early data collection. Our experience indicates that a large number of metrics will be needed to fully represent the activities and strengths of all partners, but because of the heterogeneity of the ESIPs the qualitative data (comments accompanying the metric data and success stories) becomes the most useful information. Other lessons learned included the absolute need for online browsing tools to accompany data collection tools. Finally, our experience confirms the effect of evaluation as an agent of change, the best example being the high level of collaboration among the ESIPs which can be in part attributed to the initial identification of collaboration as one of the important evaluation factors of the Federation
Keywords: Browsing; collection; heterogeneous; computing; groupware; data; online; Earth; Federation; data; information; NASA's; Partnership; Science; systems; geophysics; tools; geographic

Fault tolerant K-center problems - Khuller, Samir; Pless,Robert; Sussmann,Yoram J. (Theoretical Computer Science, 2000)
The basic K-center problem is a fundamental facility location problem, where we are asked to locate K facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. This problem is known to be NP-hard, and several optimal approximation algorithms that achieve an approximation factor of 2 have been developed for it. We focus our attention on a generalization of this problem, where each vertex is required to have a set of α (α⩽K) centers close to it. In particular, we study two different versions of this problem. In the first version, each vertex is required to have at least α centers close to it. In the second version, each vertex that does not have a center placed on it is required to have at least α centers close to it. For both these versions we are able to provide polynomial time approximation algorithms that achieve constant approximation factors for any α. For the first version we give an algorithm that achieves an approximation factor of 3 for any α, and achieves an approximation factor of 2 for α<4. For the second version, we provide algorithms with approximation factors of 2 for any α. The best possible approximation factor for even the basic K-center problem is 2, assuming P≠NP. In addition, we give a polynomial time approximation algorithm for a generalization of the K-supplier problem where a subset of at most K supplier nodes must be selected as centers so that every demand node has at least α centers close to it. For this version our approximation factor is 3. The best possible approximation factor for even the basic K-supplier problem is 3, assuming P≠NP.
Keywords: Approximation algorithms; Facility location; Fault-tolerance; K-center

From instances to classes in probabilistic relational models - Getoor, Lise; Koller,D.; Friedman,N. (Proc. ICML 2000 Workshop on Attribute-Value and Relational Learning, 2000)
Probabilistic graphical models, in particular Bayesian net-works, are useful models for representing statistical pat- terns in propositional domains. Recent work develops ef- fective techniques for learning these models directly from data. However these techniques apply only to attribute-value (i.e., flat) representations of the data. Probabilistic relational models (PRMs) allow us to represent much richer depen- dency structures, involving multiple entities and the rela- tions between them; they allow the properties of an entity to depend probabilistically on properties of related entities. PRMs represent a generic dependence, which is then instan- tiated for specific circumstances, i.e., for a particular set of entities and relations between them. Friedman et al. showed how to learn PRMs from relational data, and presented tech- niques for learning both parameters and probabilistic depen- dency structure for the attributes in a relational model. Here we examine the benefit that class hierarchies can provide PRMs. We show how the introduction of subclasses allows us to use inheritance and specialization to refine our models. We show how to learn PRMs with class hierarchies (PRM- CH) in two settings. In the first, the class hierarchy is pro- vided, as part of the input, in the relational schema for the domain. In the second setting, in addition to learning the PRM, we must learn the class hierarchy. Finally we dis- cuss how PRM-CHs allow us to build models that can repre- sent models for both particular instances in our domain, and classes of objects in our domain, bridging the gap between a class-based model and an attribute-value-based model.

High performance computing algorithms for land cover dynamics using remote sensing data - Kalluri, SNV; JaJa, Joseph F.; Bader, D.A.; Zhang,Z.; Townshend,J.R.G.; Fallah-Adl,H. (International Journal of Remote Sensing, 2000)
Global and regional land cover studies need to apply complex models on selected subsets of large volumes of multi-sensor and multi-temporal data sets that have been derived from raw instrument measurements using widely accepted pre-processing algorithms. The computational and storage requirements of most of these studies far exceed what is possible on a single workstation environment. We have been pursuing a new approach that couples scalable and open distributed heterogeneous hardware with the development of high performance software for processing, indexing and organizing remotely sensed data. Hierarchical data management tools are used to ingest raw data, create metadata and organize the archived data so as to automatically achieve computational load balancing among the available nodes and minimize input/output overheads. We illustrate our approach with four specific examples. The first is the development of the first fast operational scheme for the atmospheric correction of Landsat Thematic Mapper scenes, while the second example focuses on image segmentation using a novel hierarchical connected components algorithm. Retrieval of the global Bidirectional Reflectance Distribution Function in the red and near-infrared wavelengths using four years (1983 to 1986) of Pathfinder Advanced Very High Resolution Radiometer (AVHRR) Land data is the focus of our third example. The fourth example is the development of a hierarchical data organization scheme that allows on-demand processing and retrieval of regional and global AVHRR data sets. Our results show that substantial reductions in computational times can be achieved by the high performance computing technology.

Identifying Sports Videos using Replay, Text and Camera Motion Features - Kobla,V.; DeMenthon,D.; David Doermann (SPIE Conference on Storage and Retrieval for Image and Video Databases, 2000)
Automated classification of digital video is emerging as an important piece of the puzzle in the design of contentmanagement systems for digital libraries. The ability to classify videos into various classes such as sports, news, movies, or documentaries, increases the efficiency of indexing, browsing, and retrieval of video in large databases. In this paper, we discuss the extraction of features that enable identification of sports videos directly from the compressed domain of MPEG video. These features include detecting the presence of action replays, determining the amount of scene text in video, and calculating various statistics on camera and/or object motion. The features are derived from the macroblock, motion, and bit-rate information that is readily accessible from MPEG video with very minimal decoding, leading to substantial gains in processing speeds. Full-decoding of selective frames is required only for text analysis. A decision tree classifier built using these features is able to identify sports clips with an accuracy of about 93%.

Iterative regularization and MINRES - Kilmer,M.; Stewart, G.W. (SIAM Journal on Matrix Analysis and Applications, 2000)
In this paper we present three theorems which give insight into the regularizingproperties of MINRES. While our theory does not completely characterize the regularizing behavior of the algorithm, it provides a partial explanation of the observed behavior of the method. Unlike traditional attempts to explain the regularizing properties of Krylov subspace methods, our approach focuses on convergence properties of the residual rather than on convergence analysis of the harmonic Ritz values. The import of our analysis is illustrated by two examples. In particular, our theoret- ical and numerical results support the following important observation: in some circumstances the dimension of the optimal Krylov subspace can be much smaller than the number of the components of the truncated spectral solution that must be computed to attain comparable accuracy.

Kronos: A software system for the processing and retrieval of large-scale AVHRR data sets - Zhang,Z.; JaJa, Joseph F.; Bader, D.A.; Kalluri, SNV; Song,H.; El Saleous,N.; Vermote,E.; Townshend,J.R.G. (PE & RS- Photogrammetric Engineering and Remote Sensing, 2000)
Raw remotely sensed satellite data have to be processed andmapped into a standard projection in order to produce a multi- temporal data set which can then be used for regional or global Earth science studies. However, traditional methods of processing remotely sensed satellite data have inherent limitations because they are based on a fixed processing chain. Different users may need the data in different forms with possibly different processing steps; hence, additional transformations may have to be applied to the processed data, resulting in potentially significant errors. In this paper, we describe a software system, Kronos, for the generation of custom-tailored products from the Advanced Very High Resolution Radiometer (AVHRR) sensor. It allows the generation of a rich set of products that can be easily specified through a simple interface by scientists wishing to carry out Earth system modeling or analysis. Kronos is based on a flexible methodology and consists of four major components: ingest and preprocessing, indexing and storage, a search and processing engine, and a Java interface. After geo-location and calibration, every pixel is indexed and stored using a combination of data structures. Following the users' queries, data are selectively retrieved and secondary processing such as atmospheric correction, compositing, and projection are performed as specified. The processing is divided into two stages, the first of which involves the geo-location and calibration of the remotely sensed data and, hence, results in no loss of information. The second stage involves the retrieval of the appropriate data subsets and the application of the secondary processing specified by the user. This scheme allows the indexing and the storage of data from different sensors without any loss of information and, therefore, allows assimilation of data from multiple sensors. User specified processing can be applied later as needed.

Live multimedia adaptation through wireless hybrid networks - Koivisto,A.; Pietkainen,P.; Sauvola,J.; David Doermann (Multimedia and Expo, 2000. ICME 2000. 2000 IEEE International Conference on, 2000)
We present new techniques to intelligently adapt and combine multimedia presentations in real-time, mobile service environments. We present the techniques necessary to perform mobile multimedia processing for multiple video streams with ldquo;value-adding rdquo; information. The adaptation uses video analysis, content-recognition and automated annotation to provide scalable and interactive presentations over hybrid networks to mobile terminals. As a concrete case, we present a mobile surveillance service called Princess, which has several video sources and supports control information, terminal adaptation and end-to-end service
Keywords: adaptation; mobile; adaptation; value-adding; analysis; wireless; annotation; content-recognition; end-to-end; communication; multimedia; communication; real-time; hybrid; information; video; LAN; multimedia; networks; mobile; Princess; automated; processing; mobile; service; live; service; mobile; streams; real-time; Surveillance; system; terminal; systems; surveillance; wireless; terminals; multiple; video

The Loading Time Scheduling Problem - Bhatia,Randeep; Khuller, Samir; Naor,Joseph (Seffi) (Journal of Algorithms, 2000)
In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the set of machines. Each machine has a loading time that is incurred only for the first task that is scheduled on the machine in a particular run. This basic scheduling problem arises in the context of machining on numerically controlled machines and query optimization in databases and in other artificial intelligence applications. We give the first nontrivial approximation algorithm for this problem. We also prove nontrivial lower bounds on best possible approximation ratios for these problems. These improve on the nonapproximability results that are implied by the nonapproximability results for the shortest common supersequence problem. We use the same algorithm technique to obtain approximation algorithms for a problem arising in the context of code generation for parallel machines and for the weighted shortest common supersequence problem.

On local search and placement of meters in networks - Khuller, Samir; Bhatia,Randeep; Pless,Robert (Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, 2000)

A logic for characterizing multiple bounded agents - Grant,J.; Kraus,S.; Perlis, Don (Autonomous Agents and Multi-Agent Systems, 2000)

Making Computer and Internet Usability a Priority - Kreitzberg,Charles B; Shneiderman, Ben (Technical Reports from UMIACS, 2000)
A management oriented essay on how to promote usability inorganizations. It begins with crafting the message (Good usability is good business). Then it deals with creating a cultural shift in information technology and software engineering departments, so that the impact of poor design and the benefits of improvements are widely understood. It closes with an eight-step call to action. Keywords: usability, technology fluency, user-centered design, software engineering (Also cross-referenced as UMIACS-TR-2000-70)
Keywords: Technical Report

MOCHA: a database middleware system featuring automatic deployment of application-specific functionality - Rodrıguez-Martinez,M.; Roussopoulos, Nick; McGann,J. M; Keyley,S.; Katz,V.; Song,Z.; JaJa, Joseph F. (Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, Texas, 2000)

A model for magnetic aftereffect in the presence of time varying demagnetizing fields - Korman,C.E.; Adly,A.A.; Mayergoyz, Issak D; Rugkwamsook,P. (Magnetics, IEEE Transactions on, 2000)
Preisach models driven by stochastic inputs are employed to model magnetic aftereffect in the presence of demagnetizing fields. As a result of thermal relaxation, the magnetization and, consequently, the demagnetizing field vary in time. The new model generalizes earlier work and self-consistently accounts for the effect of time varying demagnetizing fields on the relaxation process. Three practical numerical techniques are proposed to compute the time variation in the magnetic field and the state of the Preisach plane
Keywords: aftereffect; aftereffect; magnetization; numerical; demagnetizing; field; demagnetisation; magnetic; model; magnetic; Preisach; relaxation; time; simulation; thermal; varying

A Neural Network Approach for Predicting Network Resource Requirements in Video Transmission Systems - Wong,H.S.; Wu,M.; Joyce,R.A.; Guan,L.; Kung, S.Y. (Proc. IEEE Pacific RIM Conference on Multimedia, Sydney, Australia, 2000)
Dynamic resource allocation is important for ensuring ef-ficient network utilization in Internet-based multimedia content delivery system. To allow accurate network traf- fic prediction in the case of video delivery, relevant infor- mation based on video contents and the short term traffic pattern has to be taken into account, while the inclusion of non-relevant features will deterioriate the prediction per- formance due to the "curse of dimensionality" problem. In this work, we propose a neural network-based predic- tion system and specifically address the determination of relevant input features for the system. Experiments have shown that the current system is capable of identifying a highly relevant subset of features for traffic prediction given a large number of video content and short-term net- work traffic descriptors.

Optimal design of signaling networks for Internet telephony - Srinivasan, Aravind; Ramakrishnan,K. G; Kumaran,K.; Aravamudan,M.; Naqvi,S. (IEEE INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, 2000)
We present an approach for efficient design of a signaling network for a network of software switches supporting Internet telephony. While one may take an integer programming approach to solve this problem, it quickly becomes intractable even for modest-sized networks. Instead, our topology design uses random graphs that we show to be nearly optimal in cost, highly connected, and computationally efficient even for large networks. We then formulate a quadratic assignment problem (QAP) to map the abstract topology into the physical network to achieve optimal load balancing for given demand forecasts, which we solve using randomized heuristics. Numerical results on several example networks illustrate the performance and computational efficiency of our method. A graphical design tool has been developed based on our algorithms
Keywords: bandwidth allocation; Computational efficiency; Computer networks; Cost function; Demand forecasting; demand forecasts; graph theory; graphical design tool; Internet telephony; Linear programming; Load forecasting; Load management; Network topology; optimal design; optimal load balancing; optimisation; performance; quadratic assignment problem; random graphs; randomised algorithms; randomized heuristics; Signal design; signaling networks; Switches; telecommunication signalling; topology design

Optimizing retrieval and processing of multi-dimensional scientific datasets - Chang,Chialin; Kurc, T.; Sussman, Alan; Saltz, J. (Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International, 2000)
We have developed the Active Data Repository (ADR), an infrastructure that integrates storage, retrieval, and processing of large multi-dimensional scientific datasets on distributed memory parallel machines with multiple disks attached to each node. In earlier work, we proposed three strategies for processing range queries within the ADR framework. Our experimental results show that the relative performance of the strategies changes under varying application characteristics and machine configurations. In this work we investigate approaches to guide and automate the selection of the best strategy for a given application and machine configuration. We describe analytical models to predict the relative performance of the strategies where input data elements are uniformly distributed in the attribute space of the output dataset, restricting the output dataset to be a regular d-dimensional array
Keywords: active data repository; Area measurement; Computer science; Data analysis; distributed memory parallel machines; Educational institutions; Information retrieval; Information Storage and Retrieval; infrastructure; Microscopy; Microwave integrated circuits; multi-dimensional scientific datasets retrieval; PARALLEL PROCESSING; Pathology; range queries; regular d-dimensional array; Satellites; Tomography

Residual coding in document image compression - Kia,O. E; David Doermann (Image Processing, IEEE Transactions on, 2000)
Symbolic document image compression relies on the detection of similar patterns in a document image and construction of a prototype library. Compression is achieved by referencing multiple pattern instances ( ldquo;components rdquo;) through a single representative prototype. To provide a lossless compression, however, the residual difference between each component and its assigned prototype must be coded. Since the size of the residual can significantly affect the compression ratio, efficient coding is essential. We describe a set of residual coding models for use with symbolic document image compression that exhibit desirable characteristics for compression and rate-distortion and facilitate compressed-domain processing. The first model orders the residual pixels by their distance to the prototype edge. Grouping pixels based on this distance value allows for a more compact coding and lower entropy. This distance model is then extended to a model that defines the structure of the residue and uses it as a basis for continuous and packet reconstruction which provides desired functionality for use in lossy compression and progressive transmission
Keywords: coding; coding; compressed-domain; coding; entropy; lossless; coding; image; communication; compact; compression; data; compression; document; compression; multiple; construction; rate-distortion; representative; detection; symbolic; difference; residual; distortion; document; edge; prototype; image; library; model; efficient; models; residual; pattern; patterns; pixels; similar; processing; compression; processing; entropy; image; prototype; residual; ratio; continuous; reconstruction; distance; reconstruction; progressive; reconstruction; rate; referencing; packet; theory; visual; transmission; prototype

Resource-aware meta-computing - Hollingsworth, Jeffrey K; Keleher, Peter J.; Ryu, Kyung D. (Emphasizing Distributed SystemsEmphasizing Distributed Systems, 2000)
Meta-computing, is an increasingly popular and useful method of obtaining resources to solve large computational problems. However, meta-computer environments pose a number of unique challenges, many of which have yet to be addressed effectively. Among these are dynamicism in both applications and environments, and heterogeneity at several different levels. This chapter discusses current approaches to these problems, and uses them in the Active Harmony system as a running example. Harmony supports an interface that allows applications to export tuning alternatives to the higher-level system. By exposing different parameters that can be changed at runtime, applications can be automatically adapted to changes in their execution environment caused by other programs, the addition or deletion of nodes, or changes in the availability of resources like communication links. Applications expose not only options, but also expected resource utilization with each option and the effect that the option will have on the application's performance. We discuss how this flexibility can be used to tune the overall performance of a collection of applications in a system.

A Review of Current Routing Protocols for Ad Hoc - Royer,E.M.; Toh,C.K.; Hicks, Michael W.; Kakkar,P.; Moore,J. T; Hicks, Michael W.; Moore,J. T; Alexander,D. S; Gunter,C. A; Nettles,S.; others (IEEE Personal Communications, 2000)

REXTOR: a system for generating relations from natural language - Katz,Boris; Jimmy Lin (Proceedings of the ACL-2000 workshop on Recent advances in natural language processing and information retrieval: held in conjunction with the 38th Annual Meeting of the Association for Computational Linguistics - Volume 11, 2000)
This paper argues that a finite-state language model with a ternary expression representation is currently the most practical and suitable bridge between natural language processing and information retrieval. Despite the theoretical computational inadequacies of finite-state grammars, they are very cost effective (in time and space requirements) and adequate for practical purposes. The ternary expressions that we use are not only linguistically-motivated, but also amenable to rapid large-scale indexing. REXTOR (Relations EXtracTOR) is an implementation of this model; in one uniform framework, the system provides two separate grammars for extracting arbitrary patterns of text and building ternary expressions from them. These content representational structures serve as the input to our ternary expressions indexer. This approach to natural language information retrieval promises to significantly raise the performance of current systems.

Scalable Resource Control in Active Networks - Anagnostakis,Kostas; Hicks, Michael W.; Ioannidis,Sotiris; Keromytis,Angelos; Smith,Jonathan (Active NetworksActive Networks, 2000)
The increased complexity of the service model relative to store-and-forward routers has made resource management one of the paramount concerns in active networking research and engineering. In this paper,we address two major challenges in scaling resource management-to-many-node active networks. The first is the use of market mechanisms and trading amongst nodes and programs with varying degrees of competition and cooperation to provide a scalable approach to managing active network resources. The second is the use of a trust-management architecture to ensure that the participants in the resource management marketplace have a policy-driven “rule of law” in which marketplace decisions can be made and relied upon. We have used lottery scheduling and the Keynote trust-management system for our implementation, for which we provide some initial performance indications.

Secure quality of service handling: SQoSH - Alexander,D. S; Arbaugh, William A.; Keromytis,A. D; Muir,S.; Smith,J. M (IEEE Communications Magazine, 2000)
Proposals for programmable network infrastructures, such as active networks and open signaling, provide programmers with access to network resources and data structures. The motivation for providing these interfaces is accelerated introduction of new services, but exposure of the interfaces introduces many new security risks. We describe some of the security issues raised by active networks. We then describe our secure active network environment (SANE) architecture. SANE was designed as a security infrastructure for active networks, and was implemented in the SwitchWare architecture. SANE restricts the actions that loaded modules can perform by restricting the resources that can be named; this is further extended to remote invocation by means of cryptographic credentials. SANE can be extended to support restricted control of quality of service in a programmable network element. The Piglet lightweight device kernel provides a “virtual clock” type of scheduling discipline for network traffic, and exports several tuning knobs with which the clock can be adjusted. The ALIEN active loader provides safe access to these knobs to modules that operate on the network element. Thus, the proposed SQoSH architecture is able to provide safe, secure access to network resources, while allowing these resources to be managed by end users needing customized networking services. A desirable consequence of SQoSH's integration of access control and resource control is that a large class of denial-of-service attacks, unaddressed solely with access control and cryptographic protocols, can now be prevented
Keywords: Acceleration; Access control; active networks; ALIEN active loader; Clocks; Computer network management; cryptographic credentials; cryptography; customized networking services; Data security; Data structures; denial-of-service attacks; interfaces; Kernel; loaded modules; network resources; network traffic; open signaling; packet switching; Piglet lightweight device kernel; programmable network element; programmable network infrastructures; Programming profession; Proposals; quality of service; remote invocation; resource control; restricted control of quality of service; SANE; scheduling; scheduling discipline; secure active network environment architecture; secure quality of service handling; security infrastructure; security risks; SQoSH; SwitchWare architecture; telecommunication security; tuning knobs; virtual clock

Simulation based learning environments and the use of learning histories - Rose,A.; Salter,R.; Keswani,S.; Kositsyna,N.; Plaisant, Catherine; Rubloff,G.; Shneiderman, Ben (CHI '00 extended abstracts on Human factors in computing systems, 2000)
We have developed an application framework for constructing simulation-based learning environments using dynamic simulations and visualizations to represent realistic time-dependent behavior. The development environment is described and many examples are given. In particular we will focus on the learning historian which provides users and learners with a manipulatable recording of their actions which facilitates the exchange of annotated history records among peers and mentors.
Keywords: education; engineering; History; learning; simulation

Textual data mining to support science and technology management - Losiewicz,P.; Oard, Douglas; Kostoff,R.N. (Journal of Intelligent Information Systems, 2000)

Using Feature Hierarchies in Bayesian Network Learning - desJardins, Marie; Getoor,Lise; Koller,Daphne (Abstraction, Reformulation, and Approximation, 2000)
In recent years, researchers in statistics and the UAI community have developed an impressive body of theory and algorithmic machinery for learning Bayesian networks from data. Learned Bayesian networks can be used for pattern discovery, prediction, diagnosis, and density estimation tasks. Early pioneering work in this area includes [ 5 , 9 , 10 , 13 ]. The algorithm that has emerged as the current most popular approach is a simple greedy hill-climbing algorithm that searches the space of candidate structures, guided by a network scoring function (either Bayesian or Minimum Description Length (MDL)-based). The search begins with an initial candidate network (typically the empty network, which has no edges), and then considers making small local changes such as adding, deleting, or reversing an edge in the network.

Visibility stabs and depth-first spiralling on line segments in output sensitive time - Keil,M.; Mount, Dave; Wismath,S.K. (International Journal of Computational Geometry and Applications, 2000)
Given a set S of n non-intersecting line segments in the plane, we present a newtechnique for e ciently traversing the endpoint visibility graph of S to solve a variety of visibility problems in output sensitive time. In particular, we develop two techniques to compute the 2n visibility polygons of the endpoints of S, in output sensitive time. Depth- rst spiralling is a technique that relies on the ordered endpoint visibility graph information to traverse the endpoints of S in a spiral-like manner using a combination of Jarvis' March and depth- rst search. It is a practical method and has been implemented in C++ using LEDA.

Visualization methods for personal photo collections: browsing and searching in the PhotoFinder - Kang,Hyunmo; Shneiderman, Ben (2000 IEEE International Conference on Multimedia and Expo, 2000. ICME 2000, 2000)
Software tools for personal photo collection management are proliferating, but they usually have limited searching and browsing functions. We implemented the PhotoFinder prototype to enable non-technical users of personal photo collections to search and browse easily. PhotoFinder provides a set of visual Boolean query interfaces, coupled with dynamic query and query preview features. It gives users powerful search capabilities. Using a scatter plot thumbnail display and drag-and-drop interface, PhotoFinder is designed to be easy to use for searching and browsing photos
Keywords: Browsing; Computer science; digital photo library; Displays; drag-and-drop interface; dynamic query; Educational institutions; Filters; Histograms; Image retrieval; personal computing; personal photo collections; photo collection management; PhotoFinder; Prototypes; query preview; scatter plot thumbnail display; Scattering; searching; software libraries; software tools; User interfaces; visual Boolean query interfaces; visual databases; Visualization; visualization methods

Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem - Caprara,Alberto; Italiano,Giuseppe; Mohan,G.; Panconesi,Alessandro; Srinivasan, Aravind (Approximation Algorithms for Combinatorial Optimization, 2000)
Wavelength rerouting has been suggested as a viable and cost-effective method to improve the blocking performance of wavelength-routed Wavelength-Division Multiplexing (WDM) networks. This method leads to the following combinatorial optimization problem, dubbed Venetian Routing. Given a directed multigraph G along with two vertices s and t and a collection of pairwise arc-disjoint paths, we wish to find an st -path which arc-intersects the smallest possible number of such paths. In this paper we prove the computational hardness oft his problem even in various special cases, and present several approximation algorithms for its solution. In particular we show a non-trivial connection between Venetian Routing and Label Cover.

The active MultiSync controller of the cubetree storage organization - Roussopoulos, Nick; Kotidis,Y.; Sismanis,Y. (ACM SIGMOD Record, 1999)

Agents vs. direct manipulation: what's best to disentangle the Web? - Sánchez,J.A.; Etzioni,O.; Kautz,H.; Lieberman,H.; Shneiderman, Ben (Proceedings of the eighth international conference on World Wide Web, 1999)