bluuebunny/crossref_metadata_2025 huggingface dataset:
Intelligent storage
Authors: Won Youjip , Chang Hyungkyu , Ryu Jaemin , Kim Yongdai , Shim Junseok
Published: January 2007

In this work, we develop an intelligent storage system framework for soft real-time applications. Modern software systems consist of a collection of layers and information exchange across the layers is performed via well-defined interfaces. Due to the strictness and inflexibility of interface definition, it is not possible to pass the information specific to one layer to other layers. In practice, the exploitation of this information across the layers can greatly enhance the performance, reliability, and manageability of the system. We address the limitation of legacy interface definition via enabling intelligence in the storage system. The objective is to enable the lower-layer entity, for example, a physical or block device, to conjecture the semantic and contextual information of that application behavior which cannot be passed via the legacy interface. Based upon the knowledge obtained by the intelligence module, the system can perform a number of actions to improve the performance, reliability, security, and manageability of the system. Our intelligence storage system focuses on optimizing the I/O subsystem performance for a soft real-time application. Our intelligence framework consists of three components: the
workload monitor
,
workload analyzer
, and
system optimizer
. The workload monitor maintains a window of recent I/O requests and extracts
feature vectors
in regular intervals. The workload analyzer is trained to determine the class of the incoming workload by using the feature vector. The system optimizer performs various actions to tune the storage system for a given workload. We use
confidence rate boosting
to train the workload analyzer. This sophisticated learner achieves a higher than 97% accuracy of workload class prediction. We develop a prototype intelligence storage system on the legacy operating system platform. The system optimizer performs; (1) dynamic adjustment of the file-system-level read-ahead size; (2) dynamic adjustment of I/O request size; and (3) filtering of I/O requests. We examine the effect of this autonomic optimization via experimentation. We find that the storage level pro-active optimization greatly enhances the efficiency of the underlying storage system. The sophisticated intelligence module developed in this work does not restrict its usage for performance optimization. It can be effectively used as classification engine for generic autonomic computing environment, i.e. management, diagnosis, security and etc.
The
Conquest
file system
Authors: Wang An-I Andy , Kuenning Geoff , Reiher Peter , Popek Gerald
Published: January 2007

Modern file systems assume the use of disk, a system-wide performance bottleneck for over a decade. Current disk caching and RAM file systems either impose high overhead to access memory content or fail to provide mechanisms to achieve data persistence across reboots.The
Conquest
file system is based on the observation that memory is becoming inexpensive, which enables all file system services to be delivered from memory, except for providing large storage capacity. Unlike caching,
Conquest
uses memory with battery backup as persistent storage, and provides specialized and separate data paths to memory and disk. Therefore, the memory data path contains no disk-related complexity. The disk data path consists of optimizations only for the specialized disk usage pattern.Compared to a memory-based file system,
Conquest
incurs little performance overhead. Compared to several disk-based file systems,
Conquest
achieves 1.3x to 19x faster memory performance, and 1.4x to 2.0x faster performance when exercising both memory and disk.
Conquest
realizes most of the benefits of persistent RAM at a fraction of the cost of a RAM-only solution. It also demonstrates that disk-related optimizations impose high overheads for accessing memory content in a memory-rich environment.
Improving scalability of wireless network simulation with bounded inaccuracies
Authors: Ji Zhengrong , Zhou Junlan , Takai Mineo , Bagrodia Rajive
Published: January 2007

Discrete event network simulators have emerged as popular tools for verification and performance evaluation of wireless networks. Nevertheless, the desire to model such networks at high fidelity implies high computational costs, limiting most researchers the ability to simulate networks with thousands of nodes. Previous attempts to optimize simulation of large-scale wireless networks have not appropriately modeled accumulation of weak interference, thereby suffering inaccuracies that may be further magnified in the evaluation of upper-layer protocols. This article presents a comprehensive analysis on the effects of common optimization techniques for large-scale wireless network simulation on the overall network performance. Based on the analysis, it formulates distance limit derivation and mobility update reduction that introduce bounded inaccuracy to the radio propagation simulation. It further proposes a novel technique, Lazy Event Scheduling with Corrective Retrospection, that reduces simulation events twenty-five fold without introducing any inaccuracy at all. The experimental results show that these optimizations can substantially improve the runtime performance of an already efficient wireless network simulator, by a factor of up to 55 for wireless networks with 3200 nodes without compromising the simulation's accuracy.
Simulation optimization with countably infinite feasible regions
Authors: Andradóttir Sigrún
Published: January 2007

This article is concerned with proving the almost sure and global convergence of a broad class of algorithms for solving simulation optimization problems with countably infinite number of feasible points. We first describe the class of simulation optimization algorithms under consideration and discuss how the estimate of the optimal solution should be chosen when the feasible region of the underlying optimization problem is countably infinite. Then, we present a general result that guarantees the global convergence with probability one of the simulation optimization algorithms in this class. The assumptions of this result are sufficiently weak to allow the algorithms under consideration to be efficient, in that they are not required to either allocate the same amount of computer effort to all the feasible points these algorithms visit, or to spend an increasing amount of computer effort per iteration as the number of iterations grows. This article concludes with a discussion of how our assumptions can be satisfied and also generalized.
A fuzzy set theoretic approach to validate simulation models
Authors: Martens Jurgen , Put Ferdi , Kerre Etienne
Published: January 2007

We develop a new approach to the validation of simulation models by exploiting elements from fuzzy set theory and machine learning. A fuzzy resemblance relation concept is used to set up a mathematical framework for measuring the degree of similarity between the input-output behavior of a simulation model and the corresponding behavior of the real system. A neuro-fuzzy inference algorithm is employed to automatically learn the required resemblance relation from real and simulated data. Ultimately, defuzzification strategies are applied to obtain a coefficient on the unit interval that characterizes the degree of model validity. An example in the airline industry illustrates the practical application of this methodology.
Interview with Masa Inakage
Authors: Lee Newton , Inakage Masa
Published: January 2007

Masa Inakage is a professor of the Faculty of Environmental Information at Keio University, president of the Media Studio, a member of ACM SIGGRAPH Executive Committee, and a member of Visual Effects Society. Masa produced the digital visual effects for the Hollywood feature film Spawn for the first time in Japan. In addition, he has published a large number of artworks at SIGGRAPH and other exhibitions worldwide as a media artist. In research, he has established both the Digital Cinema Laboratory and Digital Cinema Consortium at Keio Research Institute. Masa served a co-director with Mark Dippe for the digital short film Magick Lesson, which has been shown at various international film festivals. In the video interview, you will hear Masa's answers to the following questions:1. You have published a large number of artworks at ACM SIGGRAPH and other exhibitions worldwide, what is your art style and what is your favorite piece of creation?2. What is the future of artistic expression? More 3D arts or something entirely new?3. How do you compare and contrast Japanese animation vs American animation?4. What is the future of Digital Cinema? What do you do to advance its technology and business models?5. What are some of the interesting research that you are currently working on?
A fast and handy method for skeleton-driven body deformation
Authors: Zhaoqi Wang , Tianlu Mao , Shihong Xia
Published: January 2007

This article presents a deformation method for a skeleton-driven body with real-time efficiency. The idea is developed from the cross-sectional method, and inherits its basic deformation strategy. The main contribution of our method is a generalized cross-sections method, with which the complex processes for construction of cross-sectional contours, skin representation, and welding are elided, while the details of an existent body model are retained. The conception and subdivision method for generalized cross-sections are introduced, and the interpolation method is employed to improve the results of shoulder deformation. Finally, the results of our method are given, which are realistic and satisfy real-time applications.
Methods and limitations of security policy reconciliation
Authors: McDaniel Patrick , Prakash Atul
Published: January 2007

A security policy specifies session participant requirements. However, existing frameworks provide limited facilities for the automated reconciliation of participant policies. This paper considers the limits and methods of reconciliation in a general-purpose policy model. We identify an algorithm for efficient two-policy reconciliation and show that, in the worst-case, reconciliation of three or more policies is intractable. Further, we suggest efficient heuristics for the detection and resolution of intractable reconciliation. Based upon the policy model, we describe the design and implementation of the Ismene policy language. The expressiveness of Ismene, and indirectly of our model, is demonstrated through the representation and exposition of policies supported by existing policy languages. We conclude with brief notes on the integration and enforcement of Ismene policy within the Antigone communication system.
Wrapper-based evolution of legacy information systems
Authors: Thiran Philippe , Hainaut Jean-Luc , Houben Geert-Jan , Benslimane Djamal
Published: January 2007

System evolution most often implies the integration of legacy components, such as databases, with newly developed ones, leading to mixed architectures that suffer from severe heterogeneity problems. For instance, incorporating a new program in a legacy database application can create an integrity mismatch, since the database model and the program data view can be quite different (e.g. standard file model versus OO model). In addition, neither the legacy DBMS (too weak to address integrity issues correctly) nor the new program (that relies on data server responsibility) correctly cope with data integrity management. The component that can reconciliate these mismatched subsystems is the
R/W wrapper
, which allows any client program to read, but also to update the legacy data, while controlling the integrity constraints that are ignored by the legacy DBMS.This article describes a generic, technology-independent, R/W wrapper architecture, a methodology for specifying them in a disciplined way, and a CASE tool for generating most of the corresponding code.The key concept is that of
implicit construct
, which is a structure or a constraint that has not been declared in the database, but which is controlled by the legacy application code. The implicit constructs are elicited through reverse engineering techniques, and then translated into validation code in the wrapper. For instance, a wrapper can be generated for a collection of COBOL files in order to allow external programs to access them through a relational, object-oriented or XML interface, while offering referential integrity control. The methodology is based on a transformational approach that provides a formal way to build the wrapper schema and to specify inter-schema mappings.
Efficient path conditions in dependence graphs for software safety analysis
Authors: Snelting Gregor , Robschink Torsten , Krinke Jens
Published: January 2007

A new method for software safety analysis is presented which uses program slicing and constraint solving to construct and analyze
path conditions
, conditions defined on a program's input variables which must hold for information flow between two points in a program. Path conditions are constructed from subgraphs of a program's dependence graph, specifically, slices and chops. The article describes how constraint solvers can be used to determine if a path condition is satisfiable and, if so, to construct a witness for a safety violation, such as an information flow from a program point at one security level to another program point at a different security level. Such a witness can prove useful in legal matters.The article reviews previous research on path conditions in program dependence graphs; presents new extensions of path conditions for arrays, pointers, abstract data types, and multithreaded programs; presents new decomposition formulae for path conditions; demonstrates how interval analysis and BDDs (binary decision diagrams) can be used to reduce the scalability problem for path conditions; and presents case studies illustrating the use of path conditions in safety analysis. Applying interval analysis and BDDs is shown to overcome the combinatorial explosion that can occur in constructing path conditions. Case studies and empirical data demonstrate the usefulness of path conditions for analyzing practical programs, in particular, how illegal influences on safety-critical programs can be discovered and analyzed.
Synthesis of time-constrained multitasking embedded software
Authors: Nácul André C. , Givargis Tony
Published: January 2007

In modern embedded systems, software development plays a vital role. Many key functions are being migrated to software, aiming at a shorter time to market and easier upgrades. Multitasking is increasingly common in embedded software, and many of these tasks incorporate real-time constraints. Although multitasking simplifies coding, it demands an operating system and imposes significant overhead on the system. The use of serializing compilers, such as the Phantom compiler, allows the synthesis of a monolithic code from a multitasking C application, eliminating the need for an operating system. In this article, we introduce the synthesis of multitasking applications that execute in a timely manner. We incorporate the notion of timing constraints into the Phantom compiler, and show that our approach is effective in meeting such constraints, allowing fine-grained concurrency among the tasks. As an additional case study, we present the implementation of a software-based modem and show that real-time applications such as the modem have guaranteed performance in the serialized code generated by the Phantom compiler.
Decomposition of instruction decoders for low-power designs
Authors: Kuo Wu-An , Hwang Tingting , Wu Allen C.-H.
Published: January 2007

During the execution of processor instruction, decoding the instructions is a major task in identifying instructions and generating control signals for data paths. In this article, we propose two instruction decoder decomposition techniques for low-power designs. First, by tracing program execution sequences, we propose an algorithm that explores the relations between frequently executed instructions. Second, we propose a two-stage low-power decomposition structure for decoding instructions. Experimental results demonstrate that our proposed techniques achieve an average of 34.18% in power reduction and 12.93% in critical-path delay reduction for the instruction decoder.
Test sequence generation for controller verification and test with high coverage
Authors: Gören Sezer , Ferguson F. Joel
Published: January 2007

Verification and test are critical phases in the development of any hardware or software system. This article focuses on black box testing of the control part of hardware and software systems. Black box testing involves specification, test generation, and fault coverage. Finite state machines (FSMs) are commonly used for specifying controllers. FSMs may have shortcomings in modeling complex systems. With the introduction of X-machines, complex systems can be modeled at higher levels of abstraction. An X-machine can be converted into an FSM while preserving the level of abstraction. The fault coverage of a test sequence for an FSM specification provides a confidence level. We propose a fault coverage metric for an FSM specification based on the transition fault model, and using this metric, we derive the coverage of a test sequence. The article also presents a method which generates short test sequences that meet a specific coverage level and then extends this metric to determine the coverage of a test sequence for an FSM driven by an FSM network. We applied our FSM verification technique to a real-life FSM, namely, the fibre channel arbitrated loop port state machine, used in the field of storage area networks.
Multiple wire reconnections based on implication flow graph
Authors: Wu Zhong-Zhen , Chang Shih-Chieh
Published: January 2007

Global flow optimization (GFO) can perform multiple fanout/fanin wire reconnections at a time by modeling the problem of multiple wire reconnections with a flow graph, and then solving the problem using the maxflow-mincut algorithm on the flow graph. In this article, we propose an efficient multiple wire reconnection technique that modifies the framework of GFO, and as a result, can obtain better optimization quality. First, we observe that the flow graph in GFO cannot fully characterize wire reconnections, which causes the GFO to lose optimality in several obvious cases. In addition, we find that fanin reconnection can have more optimization power than fanout reconnection, but requires more sophisticated modeling. We reformulate the problem of fanout/fanin reconnections by a new graph, called the implication flow graph (IFG). We show that the problem of wire reconnections on the implication flow graph is NP-complete and also propose an efficient heuristic on the new graph. To demonstrate the effectiveness of our proposed method, we conduct an application which utilizes the flexibility of the wire reconnections explored in the logic domain to further minimize interconnects in the physical layout. Our experimental results are very exciting.
Performance-driven technology mapping with MSG partition and selective gate duplication
Authors: Wang Chi-Shong , Yeh Chingwei
Published: January 2007

Traditionally, technology mapping is done by first partitioning a circuit into a forest of trees. Each individual tree is then mapped using dynamic programming. The links among the mappings of different trees are provided via propagating the essential mapping information along multiple fanout branches. While this approach may achieve optimality within each tree, the overall result is compromised from the very first treatment of fanouts. In this article, we propose a new scheme that greatly improves technology mapping. Instead of a forest of trees, we partition the circuit into a set of maximal super-gates (MSGs). These are used to transform the original circuit into trees. We then apply the dynamic programming technique to the trees and allow duplication of gates in the mapping of each individual MSG. Experimental results on ISCAS'85 benchmarks show that our approach delivers an average of 20.6% reduction in delay with only a 9.5% increase on area.
Understanding the Problem
Authors: Neville-Neil George
Published: January 2007

I’ve done a one-day intro class and read a book on Java but never had to write any serious code in it. As an admin, however, I’ve been up close and personal with a number of Java server projects, which seem to share a number of problems.
Better Health Care Through Technology
Authors: Creeger Mache
Published: January 2007

Leveraging technology to support aging relatives in their homes is a cost-efficient way to maintain health and happiness and extend life. As the technology expert for my extended family, it has fallen to me to architect the infrastructure that will support my family’s aging loved ones in their homes as long as possible. Over the years, I have assisted four different senior households in achieving this goal, and although things have been bumpy at times, I have refined technical solutions and methodologies that seem to work well.
Cybercrime: An Epidemic
Authors: Team Cymru
Published: January 2007

Painted in the broadest of strokes, cybercrime essentially is the leveraging of information systems and technology to commit larceny, extortion, identity theft, fraud, and, in some cases, corporate espionage. Who are the miscreants who commit these crimes, and what are their motivations? One might imagine they are not the same individuals committing crimes in the physical world. Bank robbers and scam artists garner a certain public notoriety after only a few occurrences of their crimes, yet cybercriminals largely remain invisible and unheralded. Based on sketchy news accounts and a few public arrests, such as Mafiaboy, accused of paralyzing Amazon, CNN, and other Web sites, the public may infer these miscreants are merely a subculture of teenagers. In this article we provide insight into the root causes of cybercrime, its participants and their motivations, and we identify some of the issues inherent in dealing with this crime wave.
E-mail Authentication: What, Why, How?
Authors: Allman Eric
Published: January 2007

Internet e-mail was conceived in a different world than we live in today. It was a small, tightly knit community, and we didn’t really have to worry too much about miscreants. Generally, if someone did something wrong, the problem could be dealt with through social means; “shunning” is very effective in small communities. Perhaps we should have figured out what was going to happen when Usenet started to go bad. Usenet was based on an inexpensive network called UUCP, which was fairly easy to join, so it gave us a taste of what happens when the community becomes larger and more distributed—and harder to manage. Even the worst flame wars seemed fairly innocuous in the grand scheme of things, and kill files were really enough, but there was a seed of something ominous that was going to germinate all too soon.
Playing for Keeps
Authors: Geer Daniel E.
Published: January 2007

Inflection points come at you without warning and quickly recede out of reach. We may be nearing one now. If so, we are now about to play for keeps, and “we” doesn’t mean just us security geeks. If anything, it’s because we security geeks have not worked the necessary miracles already that an inflection point seems to be approaching at high velocity.
Calendar
Authors: O'Hanlon Charlene
Published: January 2007

CIKM (Conference on Information and Knowledge Management)
The Joy of Spam
Authors: Laplante Phillip A.
Published: January 2007

Not a day goes by that a large amount of spam doesn’t get past the two filters that I have in place. Most of this e-mail is annoying and some of it dangerous. But I have finally come to peace with spam and it no longer bothers me. How did I do that, you ask? I have learned to respect, even love, spam’s malicious beauty. I want to share my journey to inner peace, hopeful that you will find happiness, too.
Software frameworks for advanced procurement auction markets
Authors: Bichler Martin , Kalagnanam Jayant R.
Published: January 2007

A range of versatile auction formats are coming that allow more flexibility in specifying demand and supply.
ACM honors distinguished members for contributions to computing
Authors: CACM Staff
Published: January 2007

Inaugural class represents leading industries, research labs, and universities.
Getting there from here
Authors: Clements Paul C. , Jones Lawrence G. , McGregor John D. , Northrop Linda M.
Published: January 2007

Mapping the technical and business activities and steps required for successful organizational adoption.
New methods in software product line practice
Authors: Krueger Charles W.
Published: January 2007

Examining the benefits of next-generation SPL methods.
Feature-oriented variability management in product line engineering
Authors: Lee Jaejoon , Muthig Dirk
Published: January 2007

Implementing feature-oriented variability modeling throughout the life cycle.
Formal verification and software product lines
Authors: Kishi Tomoji , Noda Natsuko
Published: January 2007

Using formal verification techniques to verify designs within a product line.
Defining functions on equivalence classes
Authors: Paulson Lawrence C.
Published: January 2007

A
quotient construction
defines an abstract type from a concrete type, using an equivalence relation to identify elements of the concrete type that are to be regarded as indistinguishable. The elements of a quotient type are
equivalence classes
: sets of equivalent concrete values. Simple techniques are presented for defining and reasoning about quotient constructions, based on a general lemma library concerning functions that operate on equivalence classes. The techniques are applied to a definition of the integers from the natural numbers, and then to the definition of a recursive datatype satisfying equational constraints.
Efficient solving of quantified inequality constraints over the real numbers
Authors: Ratschan Stefan
Published: January 2007

Let a quantified inequality constraint over the reals be a formula in the first-order predicate language over the structure of the real numbers, where the allowed predicate symbols are ≤ and <. Solving such constraints is an undecidable problem when allowing function symbols such sin or cos. In this article, we give an algorithm that terminates with a solution for all, except for very special, pathological inputs. We ensure the practical efficiency of this algorithm by employing constraint programming techniques.
Kleene algebra with domain
Authors: Desharnais Jules , Möller Bernhard , Struth Georg
Published: January 2007

We propose Kleene algebra with domain (KAD), an extension of Kleene algebra by simple equational axioms for a domain and a codomain operation. KAD considerably augments the expressiveness of Kleene algebra, in particular for the specification and analysis of programs and state transition systems. We develop the basic calculus, present the most interesting models and discuss some related theories. We demonstrate applicability by two examples: algebraic reconstructions of Noethericity and propositional Hoare logic based on equational reasoning.
Vector field design on surfaces
Authors: Zhang Eugene , Mischaikow Konstantin , Turk Greg
Published: January 2007

Vector field design on surfaces is necessary for many graphics applications: example-based texture synthesis, nonphotorealistic rendering, and fluid simulation. For these applications, singularities contained in the input vector field often cause visual artifacts. In this article, we present a vector field design system that allows the user to create a wide variety of vector fields with control over vector field topology, such as the number and location of singularities. Our system combines basis vector fields to make an initial vector field that meets user specifications.The initial vector field often contains unwanted singularities. Such singularities cannot always be eliminated due to the Poincaré-Hopf index theorem. To reduce the visual artifacts caused by these singularities, our system allows the user to move a singularity to a more favorable location or to cancel a pair of singularities. These operations offer topological guarantees for the vector field in that they only affect user-specified singularities. We develop efficient implementations of these operations based on
Conley index theory
. Our system also provides other editing operations so that the user may change the topological and geometric characteristics of the vector field.To create continuous vector fields on curved surfaces represented as meshes, we make use of the ideas of
geodesic polar maps
and
parallel transport
to interpolate vector values defined at the vertices of the mesh. We also use geodesic polar maps and parallel transport to create basis vector fields on surfaces that meet the user specifications. These techniques enable our vector field design system to work for both planar domains and curved surfaces.We demonstrate our vector field design system for several applications: example-based texture synthesis, painterly rendering of images, and pencil sketch illustrations of smooth surfaces.
Deringing cartoons by image analogies
Authors: Wang Guangyu , Wong Tien-Tsin , Heng Pheng-Ann
Published: January 2007

In this article, we propose a novel method to reduce ringing artifacts in BDCT-encoded cartoon images using image analogies. The quantization procedure of BDCT compression (such as JPEG and MPEG) introduces annoying visual artifacts. Our main focus is on the removal of ringing artifacts that is seldom addressed by existing methods. In the proposed method, the contaminated image is modeled as a Markov random field (MRF). We “learn” the behavior of contamination by extracting massive numbers of artifact patterns from a training set, and organizing them using tree-structured vector quantization (TSVQ). Instead of
postfiltering
the input contaminated image, we
synthesize
an artifact-reduced image. Our method is noniterative and hence, can remove artifacts within a very short period of time. We show that substantial improvement is achieved using the proposed method in terms of visual quality and statistics.
Animation space
Authors: Merry Bruce , Marais Patrick , Gain James
Published: January 2007

Skeletal subspace deformation (SSD), a simple method of character animation used in many applications, has several shortcomings; the best-known being that joints tend to collapse when bent. We present
animation space
, a generalization of SSD that greatly reduces these effects and effectively eliminates them for joints that do not have an unusually large range of motion.While other, more expensive generalizations exist, ours is unique in expressing the animation process as a simple linear transformation of the input coordinates. We show that linearity can be used to derive a measure of average distance (across the space of poses), and apply this to improving parametrizations.Linearity also makes it possible to fit a model to a set of examples using least-squares methods. The extra generality in animation space allows for a good fit to realistic data, and overfitting can be controlled to allow fitted models to generalize to new poses. Despite the extra vertex attributes, it is possible to render these animation-space models in hardware with no loss of performance relative to SSD.
Mean value coordinates for arbitrary planar polygons
Authors: Hormann Kai , Floater Michael S.
Published: January 2007

Barycentric coordinates for triangles are commonly used in computer graphics, geometric modeling, and other computational sciences because they provide a convenient way to linearly interpolate the data that is given at the corners of a triangle. The concept of barycentric coordinates can also be extended in several ways to convex polygons with more than three vertices, but most of these constructions break down when used in the nonconvex setting.Mean value coordinatesoffer a choice that is not limited to convex configurations, and we show that they are in fact well-defined for arbitrary planar polygons without self-intersections. Besides their many other important properties, these coordinate functions are smooth and allow an efficient and robust implementation. They are particularly useful for interpolating data that is given at the vertices of the polygons and we present several examples of their application to common problems in computer graphics and geometric modeling.
An alternative for Wang tiles
Authors: Lagae Ares , Dutré Philip
Published: January 2007

In this article we revisit the concept of Wang tiles and introduce corner tiles, square tiles with colored corners. During past years, Wang tiles have become a valuable tool in computer graphics. Important applications of Wang tiles include texture synthesis, tile-based texture mapping, and generating Poisson disk distributions. Through their colored edges, Wang tiles enforce continuity with their direct neighbors. However, Wang tiles do not directly constrain their diagonal neighbors. This leads to continuity problems near tile corners, a problem commonly known as the corner problem. Corner tiles, on the other hand, do impose restrictions on their diagonal neighbors, and thus are not subject to the corner problem. In this article we show that previous applications of Wang tiles can also be done using corner tiles, but that corner tiles have distinct advantages for each of these applications. Compared to Wang tiles, corner tiles are easier to tile, textures synthesized with corner tiles contain more samples from the original texture, corner tiles reduce the required texture memory by a factor of two for tile-based texture mapping, and Poisson disk distributions generated with corner tiles have better spectral properties. Corner tiles result in cleaner, simpler, and more efficient applications.
Periodic global parameterization
Authors: Ray Nicolas , Li Wan Chiu , Lévy Bruno , Sheffer Alla , Alliez Pierre
Published: January 2007

We present a new globally smooth parameterization method for the triangulated surfaces of arbitrary topology. Given two orthogonal piecewise linear vector fields defined over the input mesh (typically the estimated principal curvature directions), our method computes two piecewise linear periodic functions, aligned with the input vector fields, by minimizing an objective function. The bivariate function they define is a smooth parameterization almost everywhere on the surface, except in the vicinity of singular vertices, edges, and triangles, where the derivatives of the parameterization vanish. We extract a quadrilateral chart layout from the parameterization function and propose an automatic procedure to detect the singularities, and fix them by splitting and reparameterizing the containing charts. Our method can construct both quasiconformal (angle preserving) and quasi-isometric (angle and area preserving) parameterizations. The more restrictive class of quasi-isometric parameterizations is constructed at the expense of introducing more singularities. The constructed parameterizations can be used for a variety of geometry processing applications. Since we can align the parameterization with the principal curvature directions, our result is particularly suitable for surface fitting and remeshing.
Trends, similarities, and differences in the usage of teen and senior public online newsgroups
Authors: Zaphiris Panayiotis , Sarwar Rifaht
Published: January 2007

This article presents an analysis of the human to human interactions in two public online newsgroups, one targeting the young generation and the other the elderly. The main goal of this study was to establish a better understanding of similarities and differences in the ways of interacting among the participants of these two newsgroups. A series of analytical/statistical techniques, like Social Network Analysis (SNA), were used in order to get a better understanding of the online communities that have emerged around the participants of these two newsgroups. The SNA analysis showed that the teens newsgroup is more highly connected, has more messages sent and received and has a higher reciprocity. On the other hand, the senior newsgroup has more central dominant people who tend to make the rest of the network dependent on them for communication.
A mobile computing middleware for location- and context-aware internet data services
Authors: Bellavista Paolo , Corradi Antonio , Montanari Rebecca , Stefanelli Cesare
Published: January 2007

The widespread diffusion of mobile computing calls for novel services capable of providing results that depend on both the current physical position of users (location) and the logical set of accessible resources, subscribed services, preferences, and requirements (context). Leaving the burden of location/context management to applications complicates service design and development. In addition, traditional middleware solutions tend to hide location/context visibility to the application level and are not suitable for supporting novel adaptive services for mobile computing scenarios. The article proposes a flexible middleware for the development and deployment of location/context-aware services for heterogeneous data access in the Internet. A primary design choice is to exploit a high-level policy framework to simplify the specification of services that the middleware dynamically adapts to the client location/context. In addition, the middleware adopts the mobile agent technology to effectively support autonomous, asynchronous, and local access to data resources, and is particularly suitable for temporarily disconnected clients. The article also presents the case study of a museum guide assistant service that provides visitors with location/context-dependent artistic data. The case study points out the flexibility and usability of the proposed middleware that permits automatic service reconfiguration with no impact on the implementation of the application logic.
Computing customized page ranks
Authors: Tsoi Ah Chung , Hagenbuchner Markus , Scarselli Franco
Published: January 2007

In this article, we present a new approach to page ranking. The page rank of a collection of Web pages can be represented in a parameterized model, and the user requirements can be represented by a set of constraints. For a particular parameterization, namely, a linear combination of the page ranks produced by different forcing functions, and user requirements represented by a set of linear constraints, the problem can be solved using a quadratic programming method. The solution to this problem produces a set of parameters which can be used for ranking all pages in the Web. We show that the method is suitable for building customized versions of PageRank which can be readily adapted to the needs of a vertical search engine or that of a single user.
Automated gathering of Web information
Authors: Jansen Bernard J. , Mullen Tracy , Spink Amanda , Pedersen Jan
Published: January 2007

The Web has become a worldwide repository of information which individuals, companies, and organizations utilize to solve or address various information problems. Many of these Web users utilize automated agents to gather this information for them. Some assume that this approach represents a more sophisticated method of searching. However, there is little research investigating how Web agents search for online information. In this research, we first provide a classification for information agent using stages of information gathering, gathering approaches, and agent architecture. We then examine an implementation of one of the resulting classifications in detail, investigating how agents search for information on Web search engines, including the session, query, term, duration and frequency of interactions. For this temporal study, we analyzed three data sets of queries and page views from agents interacting with the Excite and AltaVista search engines from 1997 to 2002, examining approximately 900,000 queries submitted by over 3,000 agents. Findings include: (1) agent sessions are extremely interactive, with sometimes hundreds of interactions per second (2) agent queries are comparable to human searchers, with little use of query operators, (3) Web agents are searching for a relatively limited variety of information, wherein only 18% of the terms used are unique, and (4) the duration of agent-Web search engine interaction typically spans several hours. We discuss the implications for Web information agents and search engines.
Inferring binary trust relationships in Web-based social networks
Authors: Golbeck Jennifer , Hendler James
Published: January 2007

The growth of Web-based social networking and the properties of those networks have created great potential for producing intelligent software that integrates a user's social network and preferences. Our research looks particularly at assigning trust in Web-based social networks and investigates how trust information can be mined and integrated into applications. This article introduces a definition of trust suitable for use in Web-based social networks with a discussion of the properties that will influence its use in computation. We then present two algorithms for inferring trust relationships between individuals that are not directly connected in the network. Both algorithms are shown theoretically and through simulation to produce calculated trust values that are highly accurate.. We then present TrustMail, a prototype email client that uses variations on these algorithms to score email messages in the user's inbox based on the user's participation and ratings in a trust network.
Using expander graphs to find vertex connectivity
Authors: Gabow Harold N.
Published: January 2007

The (vertex) connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known algorithm for finding κ. For a digraph with
n
vertices,
m
edges and connectivity κ the time bound is
O
((
n
+ min{κ
5/2;
, κ
n
3/4;
})
m
). This improves the previous best bound of
O
((
n
+ min{κ
3
, κ
n
})
m
). For an undirected graph both of these bounds hold with
m
replaced by κ
n
. Expander graphs are useful for solving the following subproblem that arises in connectivity computation: A known set
R
of vertices contains two large but unknown subsets that are separated by some unknown set
S
of κ vertices; we must find two vertices of
R
that are separated by
S
.
Online algorithms for market clearing
Authors: Blum Avrim , Sandholm Tuomas , Zinkevich Martin
Published: January 2007

In this article, we study the problem of online market clearing where there is one commodity in the market being bought and sold by multiple buyers and sellers whose bids arrive and expire at different times. The auctioneer is faced with an online clearing problem of deciding which buy and sell bids to match without knowing what bids will arrive in the future. For maximizing
profit
, we present a (randomized) online algorithm with a competitive ratio of ln(
p
max
−
p
min
) + 1, when bids are in a range [
p
min
,
p
max
], which we show is the best possible. A simpler algorithm has a ratio twice this, and can be used even if expiration times are not known. For maximizing the
number
of trades, we present a simple greedy algorithm that achieves a factor of 2 competitive ratio if no money-losing trades are allowed. We also show that if the online algorithm is allowed to
subsidize
matches---match money-losing pairs if it has already collected enough money from previous pairs to pay for them---then it can actually be 1-competitive with respect to the optimal offline algorithm that is not allowed subsidy. That is, for maximizing the number of trades, the ability to subsidize is at least as valuable as knowing the future. We also consider objectives of maximizing buy or sell volume and social welfare. We present all of these results as corollaries of theorems on online matching in an incomplete interval graph.We also consider the issue of incentive compatibility, and develop a nearly optimal incentive-compatible algorithm for maximizing social welfare. For maximizing
profit
, we show that no incentive-compatible algorithm can achieve a sublinear competitive ratio, even if only one buy bid and one sell bid are alive at a time. However, we provide an algorithm that, under certain mild assumptions on the bids, performs nearly as well as the best fixed pair of buy and sell prices, a weaker but still natural performance measure. This latter result uses online learning methods, and we also show how such methods can be used to improve our “optimal” algorithms to a broader notion of optimality. Finally, we show how some of our results can be generalized to settings in which the buyers and sellers themselves have online bidding strategies, rather than just each having individual bids.
Who needs Windows Vista?
Authors: Weiss Aaron
Published: January 2007

Eleven years ago, Microsoft heralded the launch of Windows 95 with great media fanfare, famously backed by the Rolling Stones' "Start Me Up." Five years ago, Microsoft unleashed Windows XP, feted with a $250 million marketing campaign. Eighteen months ago, Microsoft unveiled an estimated $200 million campaign to promote…Windows XP, again. Because by 2005, its planned successor, now known as Windows Vista, was nowhere to be found---and already six months late.
Flow-insensitive type qualifiers
Authors: Foster Jeffrey S. , Johnson Robert , Kodumal John , Aiken Alex
Published: January 2007

We describe flow-insensitive type qualifiers, a lightweight, practical mechanism for specifying and checking properties not captured by traditional type systems. We present a framework for adding new, user-specified type qualifiers to programming languages with static type systems, such as C and Java. In our system, programmers add a few type qualifier annotations to their program, and automatic type qualifier inference determines the remaining qualifiers and checks the annotations for consistency. We describe a tool CQual for adding type qualifiers to the C programming language. Our tool CQual includes a visualization component for displaying browsable inference results to the programmer. Finally, we present several experiments using our tool, including inferring
const
qualifiers, finding security vulnerabilities in several popular C programs, and checking initialization data usage in the Linux kernel. Our results suggest that inference and visualization make type qualifiers lightweight, that type qualifier inference scales to large programs, and that type qualifiers are applicable to a wide variety of problems.