bluuebunny/crossref_metadata_2025 huggingface dataset:
Modeling by example
Authors: Funkhouser Thomas , Kazhdan Michael , Shilane Philip , Min Patrick , Kiefer William , Tal Ayellet , Rusinkiewicz Szymon , Dobkin David
Published: October 2004

In this paper, we investigate a data-driven synthesis approach to constructing 3D geometric surface models. We provide methods with which a user can search a large database of 3D meshes to find parts of interest, cut the desired parts out of the meshes with intelligent scissoring, and composite them together in different ways to form new objects. The main benefit of this approach is that it is both easy to learn and able to produce highly detailed geometric models -- the conceptual design for new models comes from the user, while the geometric details come from examples in the database. The focus of the paper is on the main research issues motivated by the proposed approach: (1) interactive segmentation of 3D surfaces, (2) shape-based search to find 3D models with parts matching a query, and (3) composition of parts to form new models. We provide new research contributions on all three topics and incorporate them into a prototype modeling system. Experience with our prototype system indicates that it allows untrained users to create interesting and detailed 3D models.
Digital photography with flash and no-flash image pairs
Authors: Petschnigg Georg , Szeliski Richard , Agrawala Maneesh , Cohen Michael , Hoppe Hugues , Toyama Kentaro
Published: October 2004

Digital photography has made it possible to quickly and easily take a pair of images of low-light environments: one with flash to capture detail and one without flash to capture ambient illumination. We present a variety of applications that analyze and combine the strengths of such flash/no-flash image pairs. Our applications include denoising and detail transfer (to merge the ambient qualities of the no-flash image with the high-frequency flash detail), white-balancing (to change the color tone of the ambient image), continuous flash (to interactively adjust flash intensity), and red-eye removal (to repair artifacts in the flash image). We demonstrate how these applications can synthesize new images that are of higher quality than either of the originals.
Flash photography enhancement via intrinsic relighting
Authors: Eisemann Elmar , Durand Frédo
Published: October 2004

We enhance photographs shot in dark environments by combining a picture taken with the available light and one taken with the flash. We preserve the ambiance of the original lighting and insert the sharpness from the flash image. We use the bilateral filter to decompose the images into detail and large scale. We reconstruct the image using the large scale of the available lighting and the detail of the flash. We detect and correct flash shadows. This combines the advantages of available illumination and flash photography.
Non-photorealistic camera
Authors: Raskar Ramesh , Tan Kar-Han , Feris Rogerio , Yu Jingyi , Turk Matthew
Published: October 2004

We present a non-photorealistic rendering approach to capture and convey shape features of real-world scenes. We use a camera with multiple flashes that are strategically positioned to cast shadows along depth discontinuities in the scene. The projective-geometric relationship of the camera-flash setup is then exploited to detect depth discontinuities and distinguish them from intensity edges due to material discontinuities.We introduce depiction methods that utilize the detected edge features to generate stylized static and animated images. We can highlight the detected features, suppress unnecessary details or combine features from multiple images. The resulting images more clearly convey the 3D structure of the imaged scenes.We take a very different approach to capturing geometric features of a scene than traditional approaches that require reconstructing a 3D model. This results in a method that is both surprisingly simple and computationally efficient. The entire hardware/software setup can conceivably be packaged into a self-contained device no larger than existing digital cameras.
Protected interactive 3D graphics via remote rendering
Authors: Koller David , Turitzin Michael , Levoy Marc , Tarini Marco , Croccia Giuseppe , Cignoni Paolo , Scopigno Roberto
Published: October 2004

Valuable 3D graphical models, such as high-resolution digital scans of cultural heritage objects, may require protection to prevent piracy or misuse, while still allowing for interactive display and manipulation by a widespread audience. We have investigated techniques for protecting 3D graphics content, and we have developed a remote rendering system suitable for sharing archives of 3D models while protecting the 3D geometry from unauthorized extraction. The system consists of a 3D viewer client that includes low-resolution versions of the 3D models, and a rendering server that renders and returns images of high-resolution models according to client requests. The server implements a number of defenses to guard against 3D reconstruction attacks, such as monitoring and limiting request streams, and slightly perturbing and distorting the rendered images. We consider several possible types of reconstruction attacks on such a rendering server, and we examine how these attacks can be defended against without excessively compromising the interactive experience for non-malicious users.
Eyes for relighting
Authors: Nishino Ko , Nayar Shree K.
Published: October 2004

The combination of the cornea of an eye and a camera viewing the eye form a catadioptric (mirror + lens) imaging system with a very wide field of view. We present a detailed analysis of the characteristics of this corneal imaging system. Anatomical studies have shown that the shape of a normal cornea (without major defects) can be approximated with an ellipsoid of fixed eccentricity and size. Using this shape model, we can determine the geometric parameters of the corneal imaging system from the image. Then, an environment map of the scene with a large field of view can be computed from the image. The environment map represents the illumination of the scene with respect to the eye. This use of an eye as a natural light probe is advantageous in many relighting scenarios. For instance, it enables us to insert virtual objects into an image such that they appear consistent with the illumination of the scene. The eye is a particularly useful probe when relighting faces. It allows us to reconstruct the geometry of a face by simply waving a light source in front of the face. Finally, in the case of an already captured image, eyes could be the only direct means for obtaining illumination information. We show how illumination computed from eyes can be used to replace a face in an image with another one. We believe that the eye not only serves as a useful tool for relighting but also makes relighting possible in situations where current approaches are hard to use.
Capture of hair geometry from multiple images
Authors: Paris Sylvain , Briceño Hector M. , Sillion François X.
Published: October 2004

Hair is a major feature of digital characters. Unfortunately, it has a complex geometry which challenges standard modeling tools. Some dedicated techniques exist, but creating a realistic hairstyle still takes hours. Complementary to user-driven methods, we here propose an image-based approach to capture the geometry of hair.The novelty of this work is that we draw information from the scattering properties of the hair that are normally considered a hindrance. To do so, we analyze image sequences from a fixed camera with a moving light source. We first introduce a novel method to compute the image orientation of the hairs from their anisotropic behavior. This method is proven to subsume and extend existing work while improving accuracy. This image orientation is then raised into a 3D orientation by analyzing the light reflected by the hair fibers. This part relies on minimal assumptions that have been proven correct in previous work.Finally, we show how to use several such image sequences to reconstruct the complete hair geometry of a real person. Results are shown to illustrate the fidelity of the captured geometry to the original hair. This technique paves the way for a new approach to digital hair generation.
Volumetric reconstruction and interactive rendering of trees from photographs
Authors: Reche-Martinez Alex , Martin Ignacio , Drettakis George
Published: October 2004

Reconstructing and rendering trees is a challenging problem due to the geometric complexity involved, and the inherent difficulties of capture. In this paper we propose a volumetric approach to capture and render trees with relatively sparse foliage. Photographs of such trees typically have single pixels containing the blended projection of numerous leaves/branches and background. We show how we estimate opacity values on a recursive grid, based on alphamattes extracted from a small number of calibrated photographs of a tree. This data structure is then used to render billboards attached to the centers of the grid cells. Each billboard is assigned a set of view-dependent textures corresponding to each input view. These textures are generated by approximating coverage masks based on opacity and depth from the camera. Rendering is performed using a view-dependent texturing algorithm. The resulting volumetric tree structure has low polygon count, permitting interactive rendering of realistic 3D trees. We illustrate the implementation of our system on several different real trees, and show that we can insert the resulting model in virtual scenes.
Perceptually-supported image editing of text and graphics
Authors: Saund Eric , Fleet David , Larner Daniel , Mahoney James
Published: October 2004

This extended abstract reprises our UIST '03 paper on "Perceptually-Supported Image Editing of Text and Graphics." We introduce a novel image editing program, called
ScanScribe
, that emphasizes easy selection and manipulation of material found in informal, casual documents such as sketches, handwritten notes, whiteboard images, screen snapshots, and scanned documents.
VisionWand
Authors: Cao Xiang , Balakrishnan Ravin
Published: October 2004

A passive wand tracked in 3D using computer vision techniques is explored as a new input mechanism for interacting with large displays. We demonstrate a variety of interaction techniques and visual widgets that exploit the affordances of the wand, resulting in an effective interface for large scale display interaction. The lack of any buttons or other electronics on the wand presents a challenge that we address by developing a set of gestures and postures to track and enable command input.
The CAT for efficient 2D and 3D interaction as an alternative to mouse adaptations
Authors: Hachet Martin , Guitton Pascal , Reuter Patrick , Tyndiuk Florence
Published: October 2004

We present the CAT (Control Action Table), a 6 degrees of freedom freestanding input device designed for interaction with Virtual Environments displayed on huge screens. Both isotonic and isometric sensing modes allow the user to easily and efficiently perform 3D interaction techniques. A 2D tablet fixed on the tabletop allows them to perform accurate 2D interaction techniques.
Super wide viewer using catadioptrical optics
Authors: Nagahara Hajime , Yagi Yasushi , Yachida Masahiko
Published: October 2004

Many applications have used a head-mounted display (HMD), such as in virtual and mixed realities and telepresence. However, the field of view (FOV) of commercial HMD systems is too narrow for feeling immersion. In this paper, we propose a super-wide field of view head-mounted display consisting of an ellipsoidal mirror and a hyperboloidal curved mirror. The horizontal FOV of the proposed HMD is 180 degrees and includes the peripheral vision of humans. It increases the reality and immersion for users.
Perception-motivated high dynamic range video encoding
Authors: Mantiuk Rafal , Krawczyk Grzegorz , Myszkowski Karol , Seidel Hans-Peter
Published: October 2004

Due to rapid technological progress in high dynamic range (HDR) video capture and display, the efficient storage and transmission of such data is crucial for the completeness of any HDR imaging pipeline. We propose a new approach for inter-frame encoding of HDR video, which is embedded in the well-established MPEG-4 video compression standard. The key component of our technique is luminance quantization that is optimized for the contrast threshold perception in the human visual system. The quantization scheme requires only 10--11 bits to encode 12 orders of magnitude of visible luminance range and does not lead to perceivable contouring artifacts. Besides video encoding, the proposed quantization provides perceptually-optimized luminance sampling for fast implementation of any global tone mapping operator using a lookup table. To improve the quality of synthetic video sequences, we introduce a coding scheme for discrete cosine transform (DCT) blocks with high contrast. We demonstrate the capabilities of HDR video in a player, which enables decoding, tone mapping, and applying post-processing effects in real-time. The tone mapping algorithm as well as its parameters can be changed interactively while the video is playing. We can simulate post-processing effects such as glare, night vision, and motion blur, which appear very realistic due to the usage of HDR data.
Perceptual illumination components
Authors: Stokes William A. , Ferwerda James A. , Walter Bruce , Greenberg Donald P.
Published: October 2004

In this paper we introduce a new perceptual metric for efficient, high quality, global illumination rendering. The metric is based on a rendering-by-components framework in which the direct, and indirect diffuse, glossy, and specular light transport paths are separately computed and then composited to produce an image. The metric predicts the perceptual importances of the computationally expensive indirect illumination components with respect to image quality. To develop the metric we conducted a series of psychophysical experiments in which we measured and modeled the perceptual importances of the components. An important property of this new metric is that it predicts component importances from inexpensive estimates of the reflectance properties of a scene, and therefore adds negligible overhead to the rendering process. This perceptual metric should enable the development of an important new class of efficient global-illumination rendering systems that can intelligently allocate limited computational resources, to provide high quality images at interactive rates.
Supra-threshold control of peripheral LOD
Authors: Watson Benjamin , Walker Neff , Hodges Larry F.
Published: October 2004

Level of detail (LOD) is widely used to control visual feedback in interactive applications. LOD control is typically based on perception at threshold -- the conditions in which a stimulus first becomes perceivable. Yet most LOD manipulations are quite perceivable and occur well above threshold. Moreover, research shows that supra-threshold perception differs drastically from perception at threshold. In that case, should supra-threshold LOD control also differ from LOD control at threshold?In two experiments, we examine supra-threshold LOD control in the visual periphery and find that indeed, it should differ drastically from LOD control at threshold. Specifically, we find that LOD must support a task-dependent level of reliable perceptibility. Above that level, perceptibility of LOD control manipulations should be minimized, and detail contrast is a better predictor of perceptibility than detail size. Below that level, perceptibility must be maximized, and LOD should be
improved
as eccentricity rises or contrast drops. This directly contradicts prevailing threshold-based LOD control schemes, and strongly suggests a reexamination of LOD control for foveal display.
Brook for GPUs
Authors: Buck Ian , Foley Theresa , Horn Daniel , Sugerman Jeremy , Fatahalian Kayvon , Houston Mike , Hanrahan Pat
Published: October 2004

In this paper, we present Brook for GPUs, a system for general-purpose computation on programmable graphics hardware. Brook extends C to include simple data-parallel constructs, enabling the use of the GPU as a streaming co-processor. We present a compiler and runtime system that abstracts and virtualizes many aspects of graphics hardware. In addition, we present an analysis of the effectiveness of the GPU as a compute engine compared to the CPU, to determine when the GPU can outperform the CPU for a particular algorithm. We evaluate our system with five applications, the SAXPY and SGEMV BLAS operators, image segmentation, FFT, and ray tracing. For these applications, we demonstrate that our Brook implementations perform comparably to hand-written GPU code and up to seven times faster than their CPU counterparts.
Adaptive tetrapuzzles
Authors: Cignoni Paolo , Ganovelli Fabio , Gobbetti Enrico , Marton Fabio , Ponchio Federico , Scopigno Roberto
Published: October 2004

We describe an efficient technique for out-of-core construction and accurate view-dependent visualization of very large surface models. The method uses a regular conformal hierarchy of tetrahedra to spatially partition the model. Each tetrahedral cell contains a precomputed simplified version of the original model, represented using cache coherent indexed strips for fast rendering. The representation is constructed during a fine-to-coarse simplification of the surface contained in diamonds (sets of tetrahedral cells sharing their longest edge). The construction preprocess operates out-of-core and parallelizes nicely. Appropriate boundary constraints are introduced in the simplification to ensure that all conforming selective subdivisions of the tetrahedron hierarchy lead to correctly matching surface patches. For each frame at runtime, the hierarchy is traversed coarse-to-fine to select diamonds of the appropriate resolution given the view parameters. The resulting system can interatively render high quality views of out-of-core models of hundreds of millions of triangles at over 40Hz (or 70M triangles/s) on current commodity graphics platforms.
A stereo display prototype with multiple focal distances
Authors: Akeley Kurt , Watt Simon J. , Girshick Ahna Reza , Banks Martin S.
Published: October 2004

Typical stereo displays provide incorrect focus cues because the light comes from a single surface. We describe a prototype stereo display comprising two independent fixed-viewpoint volumetric displays. Like autostereoscopic volumetric displays, fixed-viewpoint volumetric displays generate near-correct focus cues without tracking eye position, because light comes from sources at the correct focal distances. (In our prototype, from three image planes at different physical distances.) Unlike autostereoscopic volumetric displays, however, fixed-viewpoint volumetric displays retain the qualities of modern projective graphics: view-dependent lighting effects such as occlusion, specularity, and reflection are correctly depicted; modern graphics processor and 2-D display technology can be utilized; and realistic fields of view and depths of field can be implemented. While not a practical solution for general-purpose viewing, our prototype display is a proof of concept and a platform for ongoing vision research. The design, implementation, and verification of this stereo display are described, including a novel technique of filtering along visual lines using 1-D texture mapping.
3D TV
Authors: Matusik Wojciech , Pfister Hanspeter
Published: October 2004

Three-dimensional TV is expected to be the next revolution in the history of television. We implemented a 3D TV prototype system with real-time acquisition, transmission, and 3D display of dynamic scenes. We developed a distributed, scalable architecture to manage the high computation and bandwidth demands. Our system consists of an array of cameras, clusters of network-connected PCs, and a multi-projector 3D display. Multiple video streams are individually encoded and sent over a broadband network to the display. The 3D display shows high-resolution (1024 × 768) stereoscopic color images for multiple viewpoints without special glasses. We implemented systems with rear-projection and front-projection lenticular screens. In this paper, we provide a detailed overview of our 3D TV system, including an examination of design choices and tradeoffs. We present the calibration and image alignment procedures that are necessary to achieve good image quality. We present qualitative results and some early user feedback. We believe this is the first real-time end-to-end 3D TV system with enough views and resolution to provide a truly immersive 3D experience.
Synthetic aperture confocal imaging
Authors: Levoy Marc , Chen Billy , Vaish Vaibhav , Horowitz Mark , McDowall Ian , Bolas Mark
Published: October 2004

Confocal microscopy is a family of imaging techniques that employ focused patterned illumination and synchronized imaging to create cross-sectional views of 3D biological specimens. In this paper, we adapt confocal imaging to large-scale scenes by replacing the optical apertures used in microscopy with arrays of real or virtual video projectors and cameras. Our prototype implementation uses a video projector, a camera, and an array of mirrors. Using this implementation, we explore confocal imaging of partially occluded environments, such as foliage, and weakly scattering environments, such as murky water. We demonstrate the ability to selectively image any plane in a partially occluded environment, and to see further through murky water than is otherwise possible. By thresholding the confocal images, we extract mattes that can be used to selectively illuminate any plane in the scene.
Painting detail
Authors: Carr Nathan A. , Hart John C.
Published: October 2004

Surface painting is a technique that allows a user to paint a texture directly onto a surface, usually with a texture atlas: a 1:1 mapping between the surface and its texture image. Many good automatic texture atlas generation methods exist that evenly distribute texture samples across a surface based on its area and/or curvature, and some are even sensitive to the frequency spectrum of the input texture. However, during the surface painting process, the texture can change non-uniformly and unpredictably and even the atlases are static and can thus fail to reproduce sections of finely painted detail such as surface illustration.We present a new texture atlas algorithm that distributes initial texture samples evenly according to surface area and texture frequency, and, more importantly, maintains this distribution as the texture signal changes during the surface painting process. The running time is further accelerated with a novel GPU implementation of the surface painting process. The redistribution of samples is transparent to the user, resulting in a surface painting system of seemingly unlimited resolution. The atlas construction is local, making it fast enough to run interactively on models containing over 100K faces.
Cross-parameterization and compatible remeshing of 3D models
Authors: Kraevoy Vladislav , Sheffer Alla
Published: October 2004

Many geometry processing applications, such as morphing, shape blending, transfer of texture or material properties, and fitting template meshes to scan data, require a bijective mapping between two or more models. This mapping, or
cross-parameterization
, typically needs to preserve the shape and features of the parameterized models, mapping legs to legs, ears to ears, and so on. Most of the applications also require the models to be represented by
compatible
meshes, i.e. meshes with identical connectivity, based on the cross-parameterization. In this paper we introduce novel methods for shape preserving cross-parameterization and compatible remeshing. Our cross-parameterization method computes a low-distortion bijective mapping between models that satisfies user prescribed constraints. Using this mapping, the remeshing algorithm preserves the user-defined feature vertex correspondence and the shape correlation between the models. The remeshing algorithm generates output meshes with significantly fewer elements compared to previous techniques, while accurately approximating the input geometry. As demonstrated by the examples, the compatible meshes we construct are ideally suitable for morphing and other geometry processing applications.
Inter-surface mapping
Authors: Schreiner John , Asirvatham Arul , Praun Emil , Hoppe Hugues
Published: October 2004

We consider the problem of creating a map between two arbitrary triangle meshes. Whereas previous approaches compose parametrizations over a simpler intermediate domain, we directly create and optimize a continuous map between the meshes. Map distortion is measured with a new symmetric metric, and is minimized during interleaved coarse-to-fine refinement of both meshes. By explicitly favoring low inter-surface distortion, we obtain maps that naturally align corresponding shape elements. Typically, the user need only specify a handful of feature correspondences for initial registration, and even these constraints can be removed during optimization. Our method robustly satisfies hard constraints if desired. Inter-surface mapping is shown using geometric and attribute morphs. Our general framework can also be applied to parametrize surfaces onto simplicial domains, such as coarse meshes (for semi-regular remeshing), and octahedron and toroidal domains (for geometry image remeshing). In these settings, we obtain better parametrizations than with previous specialized techniques, thanks to our fine-grain optimization.
Robust repair of polygonal models
Authors: Ju Tao
Published: October 2004

We present a robust method for repairing arbitrary polygon models. The method is guaranteed to produce a closed surface that partitions the space into disjoint internal and external volumes. Given any model represented as a polygon soup, we construct an inside/outside volume using an octree grid, and reconstruct the surface by contouring. Our novel algorithm can efficiently process large models containing millions of polygons and is capable of reproducing sharp features in the original geometry.
Interpolating and approximating implicit surfaces from polygon soup
Authors: Shen Chen , O'Brien James F. , Shewchuk Jonathan R.
Published: October 2004

This paper describes a method for building interpolating or approximating implicit surfaces from polygonal data. The user can choose to generate a surface that exactly interpolates the polygons, or a surface that approximates the input by smoothing away features smaller than some user-specified size. The implicit functions are represented using a moving least-squares formulation with constraints integrated over the polygons. The paper also presents an improved method for enforcing normal constraints and an iterative procedure for ensuring that the implicit surface tightly encloses the input vertices.
Calculating error rates for filtering software
Authors: Resnick Paul J. , Hansen Derek L. , Richardson Caroline R.
Published: October 2004

Surveys in the U.S. have found that 95% of schools [4], 43% of public libraries [5], and 33% of teenagers' parents [8] employ filtering software to block access to pornography and other inappropriate content. Many products are also now available to filter out spam email.Filtering software, however, cannot perfectly discriminate between allowed and forbidden content, resulting in two types of errors. First, under-blocking occurs when content is not blocked that should be restricted. Second, over-blocking occurs when content is blocked that should not have been restricted. Steps can be taken to reduce the frequency of errors, and to reduce their costs (for example, by providing easy appeals processes, quick overrides, and corrections) but some errors are inevitable.
Supporting systems analysis and design through fisheye views
Authors: Turetken Ozgur , Schuff David , Sharda Ramesh , Ow Terence T.
Published: October 2004

Demonstrating the usefulness of integrating context-based views into the systems analysis and design process.
Toward the eco-grid
Authors: Zhuge Hai , Shi Xiaoqing
Published: October 2004

The Internet, along with its myriad resources and users, constitutes a vast artificial virtual environment that benefits all of human society. But both the general public and the research community may be unaware of its developmental trend toward disorder due to the exponential growth of the numbers and types of its resources and users. By way of analogy, this trend can be explained with the help of the second law of thermodynamics, which states that if we regard the environment as a closed system with constant volume and energy, then every change to the system increases its tendency toward entropy.
Academic vs. practitioner systems planning and analysis
Authors: Lippert Susan K. , Anandarajan Murugan
Published: October 2004

The gap between academic and practitioner research focus and time perspectives inhibits the education and training of systems analysts and undermines systems planning and performance.
Weaving a wireless safety net
Authors: McGinity Meg
Published: October 2004

Relying on the pervasive technology network for security is potentially perilous when the technology fails.
Wireless infidelity I
Authors: Berghel Hal
Published: October 2004

Although WiFi technology security vulnerabilities are well known, the extent of these vulnerabilities may be surprising: War driving experiences identify many potential points of entry.
Meta-design
Authors: Fischer G. , Giaccardi E. , Ye Y. , Sutcliffe A. G. , Mehandjiev N.
Published: October 2004

End-user development (EUD) activities range from customization to component configuration and programming. Office software, such as the ubiquitous spreadsheet, provides customization facilities, while the growth of the Web has added impetus to end-user scripting for interactive functions in Web sites. In scientific and engineering domains, end users frequently develop complex systems with standard programming languages such as C++ and Java. However, only a minority of users adapt commercial off-the-shelf (COTS) software products. Indeed, composing systems from reusable components, such as enterprise resource planing (ERP) systems, defeats most end users who resort to expensive and scarce expert developers for implementation.
Reducing expertise tension
Authors: Beringer Joerg
Published: October 2004

As an explicit design topic, end-user development (EUD) is rather new to human-computer interaction (HCI), although it is implicitly embedded in many design projects. What makes EUD different from other HCI topics is that in traditional HCI terms, users are experts in their tasks, and good tools should match these tasks. Conversely, end-user developers are trying to complete development tasks in which, by definition, they are not experts. Therefore, the dominating design goal of EUD tools is to compensate for a discrepancy between the user's expertise and the development task to be performed.
The economics of end-user development
Authors: Wulf Volker , Jarke Matthias
Published: October 2004

The productivity paradox raised concerns that IT investment rarely leads to productivity gains [1]. End-user development (EUD), however, may provide the answer to this concern if increased productivity can be demonstrated. Recent research has questioned the productivity paradox and substantially improved our understanding about how IT productivity may be influenced by the manner of change.
Agent-based end-user development
Authors: Repenning Alexander , Ioannidou Andri
Published: October 2004

The goal of agent-based end-user development (EUD) is to empower end users with agents they can instruct directly. This process of instruction is completely transparent to the user; that is, it is not based on opaque adaptation mechanisms. Conceptually, the idea of instructing agents includes what is often called end-user programming [3] that addresses some of the major objections users have toward agents, such as the lack of trust and the need to train them. However, it poses the huge challenge of creating development tools suitable for end users who possess no programming background or interest in learning how to program.
Natural programming languages and environments
Authors: Myers Brad A. , Pane John F. , Ko Amy J.
Published: October 2004

Over the last six years, we have been working to create programming languages and environments that are more natural, or closer to the way people think about their tasks. Our goal is to make it possible for people to express their ideas in the same way they think about them. To achieve this, we have performed various studies about how people think about programming tasks, both when trying to create a new program and when trying to find and fix bugs in existing programs. We then use this knowledge to develop new tools for programming and debugging. Our user studies have shown the resulting systems provide significant benefits to users.
Managing P2P security
Authors: Bailes Jason E. , Templeton Gary F.
Published: October 2004

Considering the potential benefits and trade-offs of file-sharing systems.
Extracting predicates from mining models for efficient query evaluation
Authors: Chaudhuri Surajit , Narasayya Vivek , Sarawagi Sunita
Published: October 2004

Modern relational database systems are beginning to support ad hoc queries on mining models. In this article, we explore novel techniques for optimizing queries that contain predicates on the results of application of mining models to relational data. For such queries, we use the internal structure of the mining model to automatically derive traditional database predicates. We present algorithms for deriving such predicates for a large class of popular discrete mining models: decision trees, naive Bayes, clustering and linear support vector machines. Our experiments on Microsoft SQL Server demonstrate that these derived predicates can significantly reduce the cost of evaluating such queries.
Exploiting
k
-constraints to reduce memory overhead in continuous queries over data streams
Authors: Babu Shivnath , Srivastava Utkarsh , Widom Jennifer
Published: October 2004

Continuous queries often require significant run-time state over arbitrary data streams. However, streams may exhibit certain data or arrival patterns, or
constraints
, that can be detected and exploited to reduce state considerably without compromising correctness. Rather than requiring constraints to be satisfied precisely, which can be unrealistic in a data streams environment, we introduce
k-constraints
, where
k
is an
adherence parameter
specifying how closely a stream adheres to the constraint. (Smaller
k
's are closer to strict adherence and offer better memory reduction.) We present a query processing architecture, called
k-Mon
, that detects useful
k
-constraints automatically and exploits the constraints to reduce run-time state for a wide range of continuous queries. Experimental results showed dramatic state reduction, while only modest computational overhead was incurred for our constraint monitoring and query execution algorithms.
Patent frenzy!
Authors: Weiss Aaron
Published: October 2004

The Ouroboros is a universal symbol. This iconic depiction of a serpent eating its own tail has been interpreted and re-interpreted by a diverse array of cultures, from Egypt, India, and Japan to the Aztecs and Native Americans. Had the ancient Egyptians filed for a patent with the U.S. Patent Office for the method of drawing said symbol, they'd probably have spent the next several centuries in court pursuing intellectual property infringement claims. Then again, many would argue that the U.S. Patent Office itself has become an Ouroboros.
One device to find them all
Authors: Schindler Esther
Published: October 2004

GPS and location-based computing is far more than the navigation system built into your car. Increasingly, these technologies are changing the way businesses operate.
The state of security on the internet
Authors: Treese Win
Published: October 2004

How bad is security on the Internet? It seems that almost every day we see reports about new malicious software, and that's just in the popular media. In the specialized news of the computer security world, it's nearly impossible to keep up with the flood of detail about new viruses, worms, spam, spyware, or other attacks against computers on the network.
Suffocating software patents and the flying bear
Authors: Weiss Aaron
Published: October 2004

The 2,167-mile Appalachian Trail stretches continuously from Georgia to Maine, thanks in part to rights-of-way that grant the hiking trail access through property that might otherwise remain under the control of thousands of individual landowners. Imagine a trail where each landowner had the right to enforce his or her interests on passing hikers---from tolls to usage requirements. Such a trail would not be very popular. The trail itself would cease to exist. The common interest would not be served.
A framework for resolution of time in natural language
Authors: Han Benjamin , Lavie Alon
Published: October 2004

Automatic extraction and reasoning over temporal properties in natural language discourse has not had wide use in practical systems due to its demand for a rich and compositional, yet inference-friendly, representation of time. Motivated by our study of temporal expressions from the Penn Treebank corpora, we address the problem by proposing a two-level constraint-based framework for processing and reasoning over temporal information in natural language. Within this framework, temporal expressions are viewed as partial assignments to the variables of an underlying calendar constraint system, and multiple expressions together describe a temporal constraint-satisfaction problem (TCSP). To support this framework, we designed a typed formal language for encoding natural language expressions. The language can cope with phenomena such as under-specification and granularity change. The constraint problems can be solved using various constraint propagation and search methods, and the solutions can then be used to answer a wide range of time-related queries.
Extracting meaning from temporal nouns and temporal prepositions
Authors: Schilder Frank
Published: October 2004

This article provides a compositional semantics for temporal nouns and temporal prepositions that are annotated as temporal prepositional phrases or noun phrases by an automatic tagging system (e.g.,

last Monday, on Dec. 1
st
, for three weeks or before Christmas

). Current temporal tagging systems rely on an ad-hoc-representation for temporal date and time expressions, but the more demanding tasks of temporal question-answering and automatic text summarization require a sound logical derivation and representation of temporal expressions. Our proposal draws from two formal accounts of temporal prepositional phrases by Pratt and Francez [2001] and von Stechow [2002b], and is realized within an automatic temporal tagging system for German newspaper articles.
Automatic TIMEX2 tagging of Korean news
Authors: Jang Seok Bae , Baldwin Jennifer , Mani Inderjeet
Published: October 2004

This article reports on a temporal tagger for Korean based on a Korean extension of the TIDES TIMEX2 guidelines. The extension, which primarily addresses the idiosyncrasies of Korean morphology, shows high inter-annotator reliability (0.893 F-measure for tag extent) when applied to a corpus of Korean newspaper articles. A machine-learning approach based on rote learning from a human-edited, automatically-derived dictionary of temporal expressions is compared with a second approach that adds manual patterns, and a third onethat tries to learn the patterns. Results for the first two are promising (0.87 F-measure for tag extent). Overall, the article shows that rote learning approaches can be very useful when language-specific features such as morphology are taken into account.
An ontology of time for the semantic web
Authors: Hobbs Jerry R. , Pan Feng
Published: October 2004

In connection with the DAML project for bringing about the Semantic Web, an ontology of time is being developed for describing the temporal content of Web pages and the temporal properties of Web services. This ontology covers topological properties of instants and intervals, measures of duration, and the meanings of clock and calendar terms.
Automatic information extraction from large websites
Authors: Crescenzi Valter , Mecca Giansalvatore
Published: October 2004

Information extraction from websites is nowadays a relevant problem, usually performed by software modules called wrappers. A key requirement is that the wrapper generation process should be automated to the largest extent, in order to allow for large-scale extraction tasks even in presence of changes in the underlying sites. So far, however, only semi-automatic proposals have appeared in the literature.We present a novel approach to information extraction from websites, which reconciles recent proposals for supervised wrapper induction with the more traditional field of grammar inference. Grammar inference provides a promising theoretical framework for the study of unsupervised---that is, fully automatic---wrapper generation algorithms. However, due to some unrealistic assumptions on the input, these algorithms are not practically applicable to Web information extraction tasks.The main contributions of the article stand in the definition of a class of regular languages, called the prefix mark-up languages, that abstract the structures usually found in HTML pages, and in the definition of a polynomial-time unsupervised learning algorithm for this class. The article shows that, differently from other known classes, prefix mark-up languages and the associated algorithm can be practically used for information extraction purposes.A system based on the techniques described in the article has been implemented in a working prototype. We present some experimental results on known Websites, and discuss opportunities and limitations of the proposed approach.
Self-stabilizing clock synchronization in the presence of Byzantine faults
Authors: Dolev Shlomi , Welch Jennifer L.
Published: October 2004

We initiate a study of bounded clock synchronization under a more severe fault model than that proposed by Lamport and Melliar-Smith [1985]. Realistic aspects of the problem of synchronizing clocks in the presence of faults are considered. One aspect is that clock synchronization is an on-going task, thus the assumption that some of the processors
never
fail is too optimistic. To cope with this reality, we suggest
self-stabilizing
protocols that stabilize in any (long enough) period in which less than a third of the processors are faulty. Another aspect is that the clock value of each processor is bounded. A single transient fault may cause the clock to reach the upper bound. Therefore, we suggest a bounded clock that wraps around when appropriate.We present two randomized self-stabilizing protocols for synchronizing bounded clocks in the presence of Byzantine processor failures. The first protocol assumes that processors have a common pulse, while the second protocol does not. A new type of distributed counter based on the Chinese remainder theorem is used as part of the first protocol.
A unified theory of shared memory consistency
Authors: Steinke Robert C. , Nutt Gary J.
Published: October 2004

The traditional assumption about memory is that a read returns the value written by the most recent write. However, in a shared memory multiprocessor several processes independently and simultaneously submit reads and writes resulting in a partial order of memory operations. In this partial order, the definition of most recent write may be ambiguous. Memory consistency models have been developed to specify what values may be returned by a read given that memory operations may only be partially ordered. Before this work, consistency models were defined independently. Each model followed a set of rules which was separate from the rules of every other model. In our work, we have defined a set of four consistency properties. Any subset of the four properties yields a set of rules which constitute a consistency model. Every consistency model previously described in the literature can be defined based on our four properties. Therefore, we present these properties as a unfied theory of shared memory consistency.Our unified theory provides several benefits. First, we claim that these four properties capture the underlying structure of memory consistency. That is, the goal of memory consistency is to ensure certain declarative properties which can be intuitively understood by a programmer, and hence allow him or her to write a correct program. Our unified theory provides a uniform, formal definition of all previously described consistency models, and in addition some combinations of properties produce new models that have not yet been described. We believe these new models will prove to be useful because they are based on declarative properties which programmers desire to be enforced. Finally, we introduce the idea of selecting a consistency model as an on-line activity. Before our work, a shared memory program would run start to finish under a single consistency model. Our unified theory allows the consistency model to change as the program runs while maintaining a consistent definition of what values may be returned by each read.
multithreaded context for robust conversational interfaces
Authors: Lemon Oliver , Gruenstein Alexander
Published: October 2004

We focus on the issue of robustness of conversational interfaces that are flexible enough to allow natural "multithreaded" conversational flow. Our main advance is to use context-sensitive speech recognition in a general way, with a representation of dialogue context that is rich and flexible enough to support conversation about multiple interleaved topics, as well as the interpretation of corrective fragments. We explain, by use of worked examples, the use of our "Conversational Intelligence Architecture" (CIA) to represent conversational threads, and how each thread can be associated with a language model (LM) for more robust speech recognition. The CIA uses fine-grained dynamic representations of dialogue context, which supersede those used in finite-state or form-based dialogue managers. In an evaluation of a dialogue system built using this architecture we found that 87.9% of recognized utterances were recognized using a context-specific language model, resulting in an 11.5% reduction in the overall utterance recognition error rate, and a 13.4% reduction in concept error rate. Thus we show that by using context-sensitive recognition based on the predicted type of the user's next dialogue move, a more flexible dialogue system can also exhibit an improvement in speech recognition performance.