bluuebunny/crossref_metadata_2025 huggingface dataset:
Design of a body-driven multiplayer game system
Authors: Laakso Sami , Laakso Mikko
Published: January 2007

We have designed and evaluated a novel multiplayer game system using just one top-view camera. With the proposed system, player avatar movement can be directly mapped to the physical movement of the player, accompanied by additional hand gestures triggering more complex actions. This article presents a study of the concepts of body-driven multiplayer games using the proposed system. We have created four different test games using human-centered design (HCD). We describe both the computer vision- based implementation and the lessons we learned about designing effective content for interactive body-driven multiplayer games.
FILA in gameland, a holistic approach to a problem of many dimensions
Authors: Ferretti Stefano , Palazzi Claudio E. , Roccetti Marco , Pau Giovanni , Gerla Mario
Published: January 2007

Multiplayer online games have now become popular with millions across the globe, capturing the attention of both researchers and practitioners. Unfortunately, online games still have to deal with the limitations imposed by some unresolved issues. Interactivity, consistency, fairness, and scalability are the major requirements that need to be addressed efficiently in order to provide an appealing product to a huge number of potential customers worldwide. To answer this demand, we describe a holistic approach that can exploit the semantics of the game to satisfy the aforementioned requirements. We provide extensive and comparative results that demonstrate how our scheme copes efficiently with an elevated level of game traffic.
Lucid platform
Authors: Liu Elvis S. , Yip Milo K. , Yu Gino
Published: January 2007

Multiplayer online game (MOG) middleware is a set of software toolkits that assists and simplifies the MOG development process. Using the middleware enables developers to focus more resources on improving game design while spending less time and money on 3D rendering and server infrastructure issues. As the scale of MOGs grows rapidly, providing scalable data-sharing service, or interest management, becomes one of the major requirements for MOG middleware. In this article we present the details of the interest management system of our MOG middleware, Lucid Platform. We employ the data distribution management (DDM) service of the high-level architecture (HLA) as the main concept of our design. Since the message-filtering mechanisms of DDM are very complex and may impose significant computational overheads, we use an efficient interest-matching algorithm for the implementation. Experimental results, based on the demo games and the emulator programs, show that our approach works well in practice.
Towards integrated imitation of strategic planning and motion modeling in interactive computer games
Authors: Gorman Bernard , Humphrys Mark
Published: January 2007

Modern, commercial computer games rely primarily on AI techniques that were developed several decades ago, and until recently there has been little impetus to change this. Despite the fact that the computer-controlled agents in such games often possess abilities far in advance of the limits imposed on human participants, competent players are capable of easily beating their artificial opponents, suggesting that approaches based on the analysis and imitation of human play may produce superior agents, in terms of both performance and believability.In this article, we describe our work in imitating the observed goal-oriented behaviors of a human player, based on concepts from data analysis and reinforcement learning. Since even the most intelligent artificial agent will be quickly identified as such if it is observed to move in a robotic manner, we also seek to incorporate mechanisms that will result in believably human-like motion. We then present some illustrative examples, demonstrating the effectiveness of our model. Finally, we discuss future work in this field.
EurolTV 2007 CFP
Authors: Lee Newton
Published: January 2007

EuroITV brings together researchers from diverse disciplines that include telecommunications, media studies, multimedia, audiovisual design, human-computer interaction, and management. The organizing committee invites you to submit original high quality papers addressing the special theme and the topics, for presentation at the conference and inclusion in the proceedings.
GDTW 2006
Authors: Lee Newton
Published: January 2007

A two-day event of lectures, research, tutorials and exhibitions on Computer Games Research and Development
CGIE2006: Joint International Conference on CyberGames and Interactive Entertainment & IE 2006: The Third Australasian Conference on Interactive Entertainment
Authors: Lee Newton
Published: January 2007

Exploring and familiarizing with the latest developments in the game and interactive entertainment industry.
On countering online dictionary attacks with login histories and humans-in-the-loop
Authors: Van Oorschot Paul C. , Stubblebine Stuart
Published: January 2007

Automated Turing Tests (ATTs), also known as human-in-the-loop techniques, were recently employed in a login protocol by Pinkas and Sander (2002) to protect against online password-guessing attacks. We present modifications providing a new history-based login protocol with ATTs, which uses failed-login counts. Analysis indicates that the new protocol offers opportunities for improved security and user friendliness (fewer ATTs to legitimate users) and greater flexibility (e.g., allowing protocol parameter customization for particular situations and users). We also note that the Pinkas--Sander and other protocols involving ATTs are susceptible to minor variations of well-known middle-person attacks. We discuss complementary techniques to address such attacks, and to augment the security of the original protocol.
XML access control using static analysis
Authors: Murata Makoto , Tozawa Akihiko , Kudo Michiharu , Hada Satoshi
Published: January 2007

Access control policies for XML typically use regular path expressions such as XPath for specifying the objects for access-control policies. However such access-control policies are burdens to the query engines for XML documents. To relieve this burden, we introduce static analysis for XML access-control. Given an access-control policy, query expression, and an optional schema, static analysis determines if this query expression is guaranteed not to access elements or attributes that are hidden by the access-control policy but permitted by the schema. Static analysis can be performed without evaluating any query expression against actual XML documents. Run-time checking is required only when static analysis is unable to determine whether to grant or deny access requests. A side effect of static analysis is query optimization: access-denied expressions in queries can be evaluated to empty lists at compile time. We further extend static analysis for handling value-based access-control policies and introduce view schemas.
Safety in automated trust negotiation
Authors: Winsborough William H. , Li Ninghui
Published: January 2007

Exchange of attribute credentials is a means to establish mutual trust between strangers wishing to share resources or conduct business transactions. Automated Trust Negotiation (ATN) is an approach to regulate the exchange of sensitive information during this process. It treats credentials as potentially sensitive resources, access to which is under policy control. Negotiations that correctly enforce policies have been called “safe” in the literature. Prior work on ATN lacks an adequate definition of this safety notion. In large part, this is because fundamental questions such as “what needs to be protected in ATN?” and “what are the security requirements?” are not adequately answered. As a result, many prior methods of ATN have serious security holes. We introduce a formal framework for ATN in which we give precise, usable, and intuitive definitions of correct enforcement of policies in ATN. We argue that our chief safety notion captures intuitive security goals. We give precise comparisons of this notion with two alternative safety notions that may seem intuitive, but that are seen to be inadequate under closer inspection. We prove that an approach to ATN from the literature meets the requirements set forth in the preferred safety definition, thus validating the safety of that approach, as well as the usability of the definition.
Process modeling in Web applications
Authors: Brambilla Marco , Ceri Stefano , Fraternali Piero , Manolescu Ioana
Published: January 2007

While Web applications evolve towards ubiquitous, enterprise-wide or multienterprise information systems, they face new requirements, such as the capability of managing complex processes spanning multiple users and organizations, by interconnecting software provided by different organizations. Significant efforts are currently being invested in application integration, to support the composition of business processes of different companies, so as to create complex, multiparty business scenarios. In this setting, Web applications, which were originally conceived to allow the user-to-system dialogue, are extended with Web services, which enable system-to-system interaction, and with process control primitives, which permit the implementation of the required business constraints. This article presents new Web engineering methods for the high-level specification of applications featuring business processes and remote services invocation. Process- and service-enabled Web applications benefit from the high-level modeling and automatic code generation techniques that have been fruitfully applied to conventional Web applications, broadening the class of Web applications that take advantage of these powerful software engineering techniques. All the concepts presented in this article are fully implemented within a CASE tool.
Postlayout optimization for synthesis of Domino circuits
Authors: Cao Aiqun , Lu Ruibing , Li Chen , Koh Cheng-Kok
Published: January 2007

Logic duplication, a commonly used synthesis technique to remove trapped inverters in reconvergent paths of Domino circuits, incurs high area and power penalties. In this article, we propose a synthesis scheme to reduce the duplication cost by allowing inverters in Domino logic under certain timing constraints for both simple and complex gates. Moreover, we can include the logic duplication minimization during technology mapping for synthesis of Domino circuits with complex gates. In order to guarantee the robustness of such Domino circuits, we perform the logic optimization as a postlayout step. Experimental results show significant reduction in duplication cost, which translates into significant improvements in area and power. As a byproduct, the timing performance is also improved owing to smaller layout area and/or logic depth.
Statistical timing analysis using levelized covariance propagation considering systematic and random variations of process parameters
Authors: Kang Kunhyuk , Paul Bipul C. , Roy Kaushik
Published: January 2007

Variability in process parameters is making accurate timing analysis of nano-scale integrated circuits an extremely challenging task. In this article, we propose a new algorithm for statistical static timing analysis (SSTA) using levelized covariance propagation (LCP). The algorithm simultaneously considers the effect of die-to-die variations in process parameters as well as within-die variation, including systematic and random variations. In order to efficiently handle complicated process variation models while contending with the arbitrary correlation among timing signals, we employ a compact form of the levelized statistical data structure. Furthermore, we propose two enhancements to the LCP algorithms to the make it practical for the analysis of large sized circuits. Results on several ISCAS'85 benchmark circuits in predictive 70nm technology show an average of 0.19% and 0.57% errors in the mean and standard deviation, respectively, of timing analysis using the proposed technique, as compared to the Monte Carlo-based approach.
Crosstalk minimization in logic synthesis for PLAs
Authors: Liu Yi-Yu , Wang Kuo-Hua , Hwang Tingting
Published: January 2007

We propose a maximum crosstalk effect minimization algorithm that takes logic synthesis into consideration for PLA structures. To minimize the crosstalk effect, a technique for permuting wire is used which contains the following steps. First, product terms are partitioned into long and short sets, and then the product terms in the long and short sets are interleaved. After that, we take advantage of the crosstalk immunity of product terms in the long set to further reduce the maximum coupling capacitance of the PLA. Finally, synthesis techniques such as local and global transformations are taken into consideration to search for a better result. The experiments demonstrate that our algorithm can effectively minimize the maximum coupling capacitance of a circuit by 51% as compared with the original area-minimized PLA without crosstalk effect minimization.
The Criminal Mind
Authors: O'Hanlon Charlene
Published: January 2007

Technology is a catch-22. It makes our lives easier and more productive, but in doing so it also makes us more vulnerable to the elements that can make our lives very difficult.
News 2.0
Authors: Stanik John
Published: January 2007

Medical Profession Slow to Embrace ’Net… or Is It?
What’s on Your Hard Drive?
Authors: O'Hanlon Charlene
Published: January 2007

Working with the same specific programs on a daily basis, developers often form intimate relationships with them.
Criminal Code: The Making of a Cybercriminal
Authors: Wadlow Thomas , Gorelik Vlad
Published: January 2007

This is a fictional account of malware creators and their experiences. Although the characters are made up, the techniques and events are patterned on real activities of many different groups developing malicious software. “Make some money!” Misha’s father shouted. “You spent all that time for a stupid contest and where did it get you? Nowhere! You have no job and you didn’t even win! You need to stop playing silly computer games and earn some money!”
Review of "Phishing Exposed by Lance James and Joe Stewart," Syngress Publishing, 2005, $49.95, ISBN: 159749030X.
Authors: State Radu
Published: January 2007

Review of "Phishing Exposed by Lance James and Joe Stewart," Syngress Publishing, 2005, $49.95, ISBN: 159749030X.
RFID and the end of cash?
Authors: Angell Ian , Kietzmann Jan
Published: January 2007

RFID-embedded money is likely to mean the end of anonymous transactions and with it one of the last bastions of personal anonymity.
How they manage IT
Authors: Montazemi Ali Reza
Published: January 2007

Small and medium-sized companies in the U.S. make better use of IT than their Canadian counterparts.
Fungible credentials and next-generation fraud
Authors: Berghel Hal
Published: January 2007

Digital technology is easing access and lowering barriers for a new generation of criminal.
Robots make computer science personal
Authors: Blank Douglas
Published: January 2007

They also make it more hands-on, real, practical, and immediate, inspiring a new generation of scientists' deep interest in the field.
Software product line modeling made practical
Authors: Eriksson Magnus , Börstler Jürgen , Borg Kjell
Published: January 2007

An example from the Swedish Defense Industry.
Multi-level customization in application engineering
Authors: Czarnecki Krzysztof , Antkiewicz Michal , Kim Chang Hwan Peter
Published: January 2007

Developing mechanisms for mapping features to analysis models.
Change management patterns in software product lines
Authors: Mohan Kannan , Ramesh Balasubramaniam
Published: January 2007

Establishing effective change management practices to prevent uncontrolled evolution of the product platform.
Software product line testing
Authors: Pohl Klaus , Metzger Andreas
Published: January 2007

Exploring principles and potential solutions.
Domain-dependent knowledge in answer set planning
Authors: Son Tran Cao , Baral Chitta , Tran Nam , Mcilraith Sheila
Published: January 2007

In this article we consider three different kinds of domain-dependent control knowledge (temporal, procedural and HTN-based) that are useful in planning. Our approach is declarative and relies on the language of logic programming with answer set semantics (AnsProlog*). AnsProlog* is designed to plan without control knowledge. We show how temporal, procedural and HTN-based control knowledge can be incorporated into AnsProlog* by the modular addition of a small number of domain-dependent rules, without the need to modify the planner. We formally prove the correctness of our planner, both in the absence and presence of the control knowledge. Finally, we perform some initial experimentation that demonstrates the potential reduction in planning time that can be achieved when procedural domain knowledge is used to solve planning problems with large plan length.
Video-guided motion synthesis using example motions
Authors: Park Min Je , Choi Min Gyu , Shinagawa Yoshihisa , Shin Sung Yong
Published: January 2007

Video taken from a single monocular camera is the most common means of recording human motion. In this article, we present a practical, semiautomatic method for synthesizing a human motion that is guided by such video. After preprocessing an input video, we select a precaptured motion clip called a
reference motion
from a motion library. We then compute the sequence of body configurations of a virtual character by deforming this motion, according to spacetime constraints derived from a sequence of 2D features in the input video. Experimental results show that our method can synthesize highly dynamic motions, such as kicking and header motions of soccer players. We also showed the potential of our scheme as a new paradigm for motion capture, that is, capturing motions from videos taken with a monocular camera, even outside a motion capture studio.
Encoding of high dynamic range video with a model of human cones
Authors: Van Hateren J. H.
Published: January 2007

A recently developed quantitative model describing the dynamical response characteristics of primate cones is used for rendering high dynamic range (HDR) video. The model provides range compression, as well as luminance-dependent noise suppression. The steady-state (static) version of the model provides a global tone mapping algorithm for rendering HDR images. Both the static and dynamic cone models can be inverted, enabling expansion of the HDR images and video that were compressed with the cone model.
Shared family calendars
Authors: Plaisant Catherine , Clamage Aaron , Hutchinson Hilary Browne , Bederson Benjamin B. , Druin Allison
Published: January 2007

We describe the design and use of a system facilitating the sharing of calendar information between remotely located, multi-generational family members. Most previous work in this area involves software enabling younger family members to monitor their parents. We have found, however, that older adults are equally if not more interested in the activities of younger family members. The major obstacle preventing them from participating in information sharing is the technology itself. Therefore, we developed a multi-layered interface approach that offers simple interaction to older users. In our system, users can choose to enter information into a computerized calendar or write it by hand on digital paper calendars. All of the information is automatically shared among everyone in the distributed family. By making the interface more accessible to older users, we promote symmetrical sharing of information among both older and younger family members. We present our participatory design process, describe the user interface, and report on an exploratory field study in three households of an extended family.
Designing a portal for older users
Authors: Newell Alan F. , Dickinson Anna , Smith Mick J. , Gregor Peter
Published: January 2007

A multidisciplinary team from industry, government, and academia developed prototype email, Web search, and navigation systems for users over 60 years old who were inexperienced in using computers and had never used the Internet. The academics encountered problems in persuading other team members of the specific challenges of designing for and working with older people. A number of ways of overcoming such challenges were implemented, and the final “radically simple” systems evaluated by a team of older people. The collaboration highlighted the conflicting pressures of the commercial world and the time and patience needed to design for older users.
Leveraging data complexity
Authors: Moloney Kevin P. , Jacko Julie A. , Vidakovic Brani , Sainfort François , Leonard V. Kathlene , Shi Bin
Published: January 2007

The current ubiquity of information technology has increased variability among users, creating a corresponding need to properly capture and understand these individual differences. This study introduces a novel application of multifractal statistical methods to distinguish users via patterns of variability within high frequency pupillary response behavior (PRB) data collected during computer-based interaction. PRB was measured from older adults, including two groups diagnosed with age-related macular degeneration (AMD) maintaining a range of visual acuities (n = 14), and one visually healthy control group (i.e., disease-free, 20/20--20/32 acuity) (n = 14). Three measures of the multifractal spectrum, the distribution of regularity indices extracted from time series data, distinguished the user groups, including: 1) Spectral Mode; 2) Broadness; and 3) Left Slope. The results demonstrate a clear relationship between the values of these measures and the level of visual capabilities. These analytical techniques leverage the inherent complexity and richness of this high frequency physiological response data, which can be used to meaningfully differentiate individuals whose sensory and cognitive capabilities may be affected by aging and visual impairment. Multifractality analysis provides an objective, quantifiable means of uncovering and examining the underlying signatures in physiological behavior that may account for individual differences in interaction needs and behaviors.
Online information disclosure
Authors: Hui Kai-Lung , Tan Bernard C. Y. , Goh Chyan-Yee
Published: January 2007

To increase their revenue from electronic commerce, more and more Internet businesses are soliciting personal information from consumers in order to target products and services at the right consumers. But when deciding whether to disclose their personal information to Internet businesses, consumers may weigh the concerns of giving up information privacy against the benefits of information disclosure. This article examines how Internet businesses can motivate consumers to disclose their personal information. Based on a synthesis of the literature, the article identifies seven types of extrinsic or intrinsic benefits that Internet businesses can provide when soliciting personal information from consumers. Through comprehensive conceptual and empirical validation processes, the article develops an instrument that allows Internet businesses to gauge the preference of consumers for the various types of benefits. By testing a set of nomological networks, some ideas are presented to Internet businesses about what types of benefits may be more effective given the personality traits of particular consumer populations. Besides providing a foundation for efforts aimed at developing theories on information, privacy and information disclosure, the results of this research provide useful suggestions to Internet businesses on how best to solicit personal information from consumers. Implications for research and practical application are discussed.
A heuristic bidding strategy for buying multiple goods in multiple english auctions
Authors: He Minghua , Jennings Nicholas R. , Prügel-Bennett Adam
Published: January 2007

This paper presents the design, implementation, and evaluation of a novel bidding algorithm that a software agent can use to obtain multiple goods from multiple overlapping English auctions. Specifically, an
Earliest Closest First
heuristic algorithm is proposed that uses neurofuzzy techniques to predict the expected closing prices of the auctions and to adapt the agent's bidding strategy to reflect the type of environment in which it is situated. This algorithm first identifies the set of auctions that are most likely to give the agent the best return and then, according to its attitude to risk, it bids in some other auctions that have approximately similar expected returns, but which finish earlier than those in the best return set. We show through empirical evaluation against a number of methods proposed in the multiple auction literature that our bidding strategy performs effectively and robustly in a wide range of scenarios.
New hardness results for congestion minimization and machine scheduling
Authors: Chuzhoy Julia , Naor Joseph (Seffi)
Published: January 2007

We study the approximability of two natural NP-hard problems. The first problem is
congestion minimization
in directed networks. In this problem, we are given a directed graph and a set of source-sink pairs. The goal is to route all the pairs with minimum congestion on the network edges. The second problem is
machine scheduling
, where we are given a set of jobs, and for each job, there is a list of intervals on which it can be scheduled. The goal is to find the smallest number of machines on which all jobs can be scheduled such that no two jobs overlap in their execution on any machine. Both problems are known to be
O
(log
n
/log log
n
)-approximable via the randomized rounding technique of Raghavan and Thompson [1987]. However, until recently, only Max SNP hardness was known for each problem. We make progress in closing this gap by showing that both problems are Ω(log log
n
)-hard to approximate unless NP ⊆ DTIME(
n

O
(log log log
n
)

).
Logarithmic hardness of the undirected edge-disjoint paths problem
Authors: Andrews Matthew , Zhang Lisa
Published: January 2007

We show that there is no log
⅓ − ε
M
approximation for the undirected Edge-Disjoint Paths problem unless
NP
⊆
ZPTIME
(
n

polylog(
n
)

), where
M
is the size of the graph and ε is any positive constant. This hardness result also applies to the undirected All-or-Nothing Multicommodity Flow problem and the undirected Node-Disjoint Paths problem.
Combining expert advice in reactive environments
Authors: Farias Daniela Pucci De , Megiddo Nimrod
Published: January 2007

“Experts algorithms” constitute a methodology for choosing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the environment. An experts algorithm has access to a set of strategies (“experts”), each of which may recommend which action to choose. The algorithm learns how to combine the recommendations of individual experts so that, in the long run, for any fixed sequence of states of the environment, it does as well as the best expert would have done relative to the same sequence. This methodology may not be suitable for situations where the evolution of states of the environment depends on past chosen actions, as is usually the case, for example, in a repeated non-zero-sum game.A general exploration-exploitation experts method is presented along with a proper definition of value. The definition is shown to be adequate in that it both captures the impact of an expert's actions on the environment and is learnable. The new experts method is quite different from previously proposed experts algorithms. It represents a shift from the paradigms of regret minimization and myopic optimization to consideration of the long-term effect of a player's actions on the environment. The importance of this shift is demonstrated by the fact that this algorithm is capable of inducing cooperation in the repeated Prisoner's Dilemma game, whereas previous experts algorithms converge to the suboptimal non-cooperative play. The method is shown to asymptotically perform as well as the best available expert. Several variants are analyzed from the viewpoint of the exploration-exploitation tradeoff, including explore-then-exploit, polynomially vanishing exploration, constant-frequency exploration, and constant-size exploration phases. Complexity and performance bounds are proven.
Articulating information needs in XML query languages
Authors: Kamps Jaap , Marx Maarten , Rijke Maarten de , Sigurbjörnsson Börkur
Published: January 2007

Document-centric XML is a mixture of text and structure. With the increased availability of document-centric XML documents comes a need for query facilities in which both structural constraints and constraints on the content of the documents can be expressed. How does the expressiveness of languages for querying XML documents help users to express their information needs? We address this question from both an experimental and a theoretical point of view. Our experimental analysis compares a structure-ignorant with a structure-aware retrieval approach using the test suite of the INEX XML Retrieval Evaluation Initiative. Theoretically, we create two mathematical models of users' knowledge of a set of documents and define query languages which exactly fit these models. One of these languages corresponds to an XML version of fielded search, the other to the INEX query language.Our main experimental findings are: First, while structure is used in varying degrees of complexity, two-thirds of the queries can be expressed in a fielded-search-like format which does not use the hierarchical structure of the documents. Second, three-quarters of the queries use constraints on the context of the elements to be returned; these contextual constraints cannot be captured by ordinary keyword queries. Third, structure is used as a search hint, and not as a strict requirement, when judged against the underlying information need. Fourth, the use of structure in queries functions as a precision enhancing device.
Dynamic element retrieval in a structured environment
Authors: Crouch Carolyn J.
Published: January 2007

This research examines the feasibility of dynamic element retrieval in a structured environment. Structured documents and queries are represented in extended vector form, based on a modification of the basic vector space model suggested by Fox [1983]. A method for the dynamic retrieval of XML elements, which requires only a single indexing of the documents at the level of the basic indexing node, is presented. This method, which we refer to as
flexible retrieval
, produces a rank ordered list of retrieved elements that is equivalent to the result produced by the same retrieval against an all-element index of the collection. Flexible retrieval obviates the need for storing either an all-element index or multiple indices of the collection.
A system for the static analysis of XPath
Authors: Genevès Pierre , Layaïda Nabil
Published: January 2007

XPath is the standard language for navigating XML documents and returning a set of matching nodes. We present a sound and complete decision procedure for containment of XPath queries, as well as other related XPath decision problems such as satisfiability, equivalence, overlap, and coverage. The considered XPath fragment covers most of the language features used in practice. Specifically, we propose a unifying logic for XML, namely, the alternation-free modal μ-calculus with converse. We show how to translate major XML concepts such as XPath and regular XML types (including DTDs) into this logic. Based on these embeddings, we show how XPath decision problems, in the presence or absence of XML types, can be solved using a decision procedure for μ-calculus satisfiability. We provide a complexity analysis of our system together with practical experiments to illustrate the efficiency of the approach for realistic scenarios.
eXtended cumulated gain measures for the evaluation of content-oriented XML retrieval
Authors: Kazai Gabriella , Lalmas Mounia
Published: January 2007

We propose and evaluate a family of measures, the eXtended Cumulated Gain (XCG) measures, for the evaluation of content-oriented XML retrieval approaches. Our aim is to provide an evaluation framework that allows the consideration of dependency among XML document components. In particular, two aspects of dependency are considered: (1) near-misses, which are document components that are structurally related to relevant components, such as a neighboring paragraph or container section, and (2) overlap, which regards the situation wherein the same text fragment is referenced multiple times, for example, when a paragraph and its container section are both retrieved. A further consideration is that the measures should be flexible enough so that different models of user behavior may be instantiated within. Both system- and user-oriented aspects are investigated and both recall and precision-like qualities are measured. We evaluate the reliability of the proposed measures based on the INEX 2004 test collection. For example, the effects of assessment variation and topic set size on evaluation stability are investigated, and the upper and lower bounds of expected error rates are established. The evaluation demonstrates that the XCG measures are stable and reliable, and in particular, that the novel measures of effort-precision and gain-recall (
ep
/
gr
) show comparable behavior to established IR measures like precision and recall.
The ballad of DVD Jon
Authors: Rowel Laurie Freeman
Published: January 2007

Can one legendary hacker's assault on DRM change the rules for protecting digital content?
The new face of malware
Authors: Greiner Lynn
Published: January 2007

It's not often one hears a vendor say that the problem its flagship product was created to address has been solved. That statement would seem, at first blush, a wee bit self-destructive.
Building a new cluster machine
Authors: Treese Win
Published: January 2007

Over the past several years of writing this column, I've had the opportunity to explore many different aspects of emerging technology for networking and communications. This column is a little different; I'd like to share something about my day job with you.
Playing politics with our digital lives
Authors: Korman Ken
Published: January 2007

It was almost exactly a year ago---long before the Democratic Party won the fight to control both houses of the US Congress---that House Democrats released a document calling for renewed legislative efforts to support math, science, and IT in our universities and beyond. Among the primary components of the "Innovation Agenda: A Commitment to Competitiveness to Keep America #1" is affordable broadband access for every American within five years. It's time to hold our representatives to their self-imposed timetable. There are only four years left to go.
Denali
Authors: Joshi Rajeev , Nelson Greg , Zhou Yunhong
Published: January 2007

This article presents a design for the Denali-2 superoptimizer, which will generate minimum-instruction-length machine code for realistic machine architectures using automatic theorem-proving technology: specifically, using E-graph matching (a technique for pattern matching in the presence of equality information) and Boolean satisfiability solving.This article presents a precise definition of the underlying automatic programming problem solved by the Denali-2 superoptimizer. It sketches the E-graph matching phase and presents a detailed exposition and proof of soundness of the reduction of the automatic programming problem to the Boolean satisfiability problem.
Adaptive functional programming
Authors: Acar Umut A. , Blelloch Guy E. , Harper Robert
Published: January 2007

We present techniques for incremental computing by introducing adaptive functional programming. As an
adaptive
program executes, the underlying system represents the data and control dependences in the execution in the form of a
dynamic dependence graph
. When the input to the program changes, a change propagation algorithm updates the output and the dynamic dependence graph by propagating changes through the graph and re-executing code where necessary. Adaptive programs adapt their output to any change in the input, small or large.We show that adaptivity techniques are practical by giving an efficient implementation as a small ML library. The library consists of three operations for making a program adaptive, plus two operations for making changes to the input and adapting the output to these changes. We give a general bound on the time it takes to adapt the output, and based on this, show that an adaptive Quicksort adapts its output in logarithmic time when its input is extended by one key.To show the safety and correctness of the mechanism we give a formal definition of AFL, a call-by-value functional language extended with adaptivity primitives. The modal type system of AFL enforces correct usage of the adaptivity mechanism, which can only be checked at run time in the ML library. Based on the AFL dynamic semantics, we formalize thechange-propagation algorithm and prove its correctness.
Inverting the symmetrical beta distribution
Authors: L'Ecuyer Pierre , Simard Richard
Published: January 2007

We propose a fast algorithm for computing the inverse symmetrical beta distribution. Four series (two around
x
= 0 and two around
x
= 1/2) are used to approximate the distribution function, and its inverse is found via Newton's method. This algorithm can be used to generate beta random variates by inversion and is much faster than currently available general inversion methods for the beta distribution. It turns out to be very useful for generating gamma processes efficiently via bridge sampling.
Algorithm 858
Authors: Deun Joris Van , Cools Ronald
Published: January 2007

We present an algorithm to compute integrals of the form ∫
∞
0
x

m

∏

k

i

= 1
J

ν

i

(
a

i

x
)
dx
with
J

ν

i

(
x
) the Bessel function of the first kind and (real) order ν

i

. The parameter
m
is a real number such that ∑

i

ν

i

+
m
> −1 and the coefficients
a

i

are strictly positive real numbers. The main ingredients in this algorithm are the well-known asymptotic expansion for
J

ν

i

(
x
) and the observation that the infinite part of the integral can be approximated using the incomplete Gamma function Γ(
a
,
z
). Accurate error estimates are included in the algorithm, which is implemented as a MATLAB program.
Algorithm 859
Authors: Amodio Pierluigi , Romanazzi Giuseppe
Published: January 2007

BABDCR is a package of Fortran 90 subroutines for the solution of linear systems with bordered almost block diagonal coefficient matrices. It is designed to handle matrices with blocks of the same size, that is, having a block upper bidiagonal structure with an additional block in the right upper corner. The algorithm implemented in the package performs cyclic reduction of the coefficient matrix in order to reduce the fill-in due to the corner block.
Algorithm 860
Authors: Gonçalves Eduardo N. , Palhares Reinaldo M. , Takahashi Ricardo H. C. , Mesquita Renato C.
Published: January 2007

This article presents a simple efficient algorithm for the subdivision of a
d
-dimensional simplex in
k

d

simplices, where
k
is any positive integer number. The algorithm is an extension of Freudenthal's subdivision method. The proposed algorithm deals with the more general case of
k

d

subdivision, and is considerably simpler than the
RedRefinementND
algorithm for implementation of Freudenthal's strategy. The proposed simplex subdivision algorithm is motivated by a problem in the field of robust control theory: the computation of a tight upper bound of a dynamical system performance index by means of a branch-and-bound algorithm.
Algorithm 861
Authors: Erricolo Danilo
Published: January 2007

A translation to Fortran 90 of Gertrude Blanch's algorithm for computing the expansion coefficients of the series that represent Mathieu functions is presented. Its advantages are portability, higher precision, practicality of use, and extended documentation. In addition, numerical validations and comparisons with other existing methods are presented.
Algorithm 862
Authors: Bader Brett W. , Kolda Tamara G.
Published: January 2007

Tensors (also known as multidimensional arrays or
N
-way arrays) are used in a variety of applications ranging from chemometrics to psychometrics. We describe four MATLAB classes for tensor manipulations that can be used for fast algorithm prototyping. The tensor class extends the functionality of MATLAB's multidimensional arrays by supporting additional operations such as tensor multiplication. The tensor_as_matrix class supports the “matricization” of a tensor, that is, the conversion of a tensor to a matrix (and vice versa), a commonly used operation in many algorithms. Two additional classes represent tensors stored in decomposed formats: cp_tensor and tucker_tensor. We describe all of these classes and then demonstrate their use by showing how to implement several tensor algorithms that have appeared in the literature.
Cache-efficient string sorting using copying
Authors: Sinha Ranjan , Zobel Justin , Ring David
Published: January 2007

Burstsort is a cache-oriented sorting technique that uses a dynamic trie to efficiently divide large sets of string keys into related subsets small enough to sort in cache. In our original burstsort, string keys sharing a common prefix were managed via a bucket of pointers represented as a list or array; this approach was found to be up to twice as fast as the previous best string sorts, mostly because of a sharp reduction in out-of-cache references. In this paper, we introduce C-burstsort, which copies the unexamined tail of each key to the bucket and discards the original key to improve data locality. On both Intel and PowerPC architectures, and on a wide range of string types, we show that sorting is typically twice as fast as our original burstsort and four to five times faster than multikey quicksort and previous radixsorts. A variant that copies both suffixes and record pointers to buckets, CP-burstsort, uses more memory, but provides stable sorting. In current computers, where performance is limited by memory access latencies, these new algorithms can dramatically reduce the time needed for internal sorting of large numbers of strings.
Security analysis in role-based access control
Authors: Li Ninghui , Tripunitara Mahesh V.
Published: January 2007

The administration of large role-based access control (RBAC) systems is a challenging problem. In order to administer such systems, decentralization of administration tasks by the use of delegation is an effective approach. While the use of delegation greatly enhances flexibility and scalability, it may reduce the control that an organization has over its resources, thereby diminishing a major advantage RBAC has over discretionary access control (DAC). We propose to use security analysis techniques to maintain desirable security properties while delegating administrative privileges. We give a precise definition of a family of security analysis problems in RBAC, which is more general than safety analysis that is studied in the literature. We show that two classes of problems in the family can be reduced to similar analysis in the RT[↞∩] role-based trust-management language, thereby establishing an interesting relationship between RBAC and the
RT
framework. The reduction gives efficient algorithms for answering most kinds of queries in these two classes and establishes the complexity bounds for the intractable cases.
Controlled and cooperative updates of XML documents in byzantine and failure-prone distributed systems
Authors: Mella Giovanni , Ferrari Elena , Bertino Elisa , Koglin Yunhua
Published: January 2007

This paper proposes an infrastructure and related algorithms for the controlled and cooperative updates of XML documents. Key components of the proposed system are a set of XML-based languages for specifying access-control policies and the path that the document must follow during its update. Such path can be fully specified before the update process begins or can be
dynamically
modified by properly authorized subjects while being transmitted. Our approach is fully distributed in that each party involved in the process can verify the correctness of the operations performed until that point on the document without relying on a central authority. More importantly, the recovery procedure also does not need the participation of a central authority. Our approach is based on the use of some special control information that is transmitted together with the document and a suite of protocols. We formally specify the structure of such control information and the protocols. We also analyze security and complexity of the proposed protocols.
Analysis of cache-coherence bottlenecks with hybrid hardware/software techniques
Authors: Marathe Jaydeep , Mueller Frank , de Supinski Bronis R.
Published: January 2007

Application performance on high-performance shared-memory systems is often limited by sharing patterns resulting in cache-coherence bottlenecks. Current approaches to identify coherence bottlenecks incur considerable run-time overhead and do not scale. We present two novel hardware-assisted coherence-analysis techniques that reduce trace sizes by two orders of magnitude over full traces. First, hardware performance monitoring is combined with capturing stores in software to provide a lossy-trace mechanism, which is an order of magnitude faster than software-instrumentation-based full-tracing and retains accuracy. Second, selected long-latency loads are instrumented via binary rewriting, which provides even higher accuracy and control over tracing, but requires additional overhead.
Future execution
Authors: Ganusov Ilya , Burtscher Martin
Published: January 2007

This paper describes future execution (FE), a simple hardware-only technique to accelerate individual program threads running on multicore microprocessors. Our approach uses available idle cores to prefetch important data for the threads executing on the active cores. FE is based on the observation that many cache misses are caused by loads that execute repeatedly and whose address-generating program slices do not change (much) between consecutive executions. To exploit this property, FE dynamically creates a prefetching thread for each active core by simply sending a copy of all committed, register-writing instructions to an otherwise idle core. The key innovation is that on the way to the second core, a value predictor replaces each predictable instruction in the prefetching thread with a
load immediate
instruction, where the immediate is the predicted result that the instruction is likely to produce during its
n
th next dynamic execution. Executing this modified instruction stream (i.e., the prefetching thread) on another core allows to compute the future results of the instructions that are not directly predictable, issue prefetches into the shared memory hierarchy, and thus reduce the primary threads' memory access time. We demonstrate the viability and effectiveness of future execution by performing cycle-accurate simulations of a two-way CMP running the single-threaded SPECcpu2000 benchmark suite. Our mechanism improves program performance by 12%, on average, over a baseline that already includes an optimized hardware stream prefetcher. We further show that FE is complementary to runahead execution and that the combination of these two techniques raises the average speedup to 20% above the performance of the baseline processor with the aggressive stream prefetcher.