bluuebunny/crossref_metadata_2025 huggingface dataset:
Data base directions
Authors: Berg John L.
Published: January 2005

What information about data base technology does a manager need to make prudent decisions about using this new technology? To provide this information the National Bureau of Standards and the Association for Computing Machinery established a workshop of approximately 80 experts in five major subject areas. The five subject areas were auditing, evolving technology, government regulations, standards, and user experience. Each area prepared a report contained in these proceedings. The proceedings provide guidance of steps managers should follow to prepare themselves and their organization for the installation of data base management concepts. The auditing working panel noted the increased vulnerability of organizations who integrate their formerly dispersed and redundant files into a data base and suggest actions to address this risk. The technology report noted several promising parallel developments but concluded that the future would see evolving, rather than revolutionary data base progress. Government regulations, particularly the drive for individual privacy rights, were seen to play an important role in determining data base directions and the panel's guidance on cost impact suggest that organizations would experience reduced costs with data base technology. Standards pervaded all issues and were found necessary in several sub-areas of data base technology but the panel saw no immediate likelihood of national data base standards. The user experience working panel noted that data base systems had impacted their organizations to the extent of reconsidering existing data flows, areas of responsibilities, and procedures.
A survey of peer-to-peer content distribution technologies
Authors: Androutsellis-Theotokis Stephanos , Spinellis Diomidis
Published: January 2005

Distributed computer architectures labeled "peer-to-peer" are designed for the sharing of computer resources (content, storage, CPU cycles) by direct exchange, rather than requiring the intermediation or support of a centralized server or authority. Peer-to-peer architectures are characterized by their ability to adapt to failures and accommodate transient populations of nodes while maintaining acceptable connectivity and performance.Content distribution is an important peer-to-peer application on the Internet that has received considerable research attention. Content distribution applications typically allow personal computers to function in a coordinated manner as a distributed storage medium by contributing, searching, and obtaining digital content.In this survey, we propose a framework for analyzing peer-to-peer content distribution technologies. Our approach focuses on nonfunctional characteristics such as security, scalability, performance, fairness, and resource management potential, and examines the way in which these characteristics are reflected in---and affected by---the architectural design decisions adopted by current peer-to-peer systems.We study current peer-to-peer systems and infrastructure technologies in terms of their distributed object location and routing mechanisms, their approach to content replication, caching and migration, their support for encryption, access control, authentication and identity, anonymity, deniability, accountability and reputation, and their use of resource trading and management schemes.
Local ratio
Authors: Bar-Yehuda Reuven , Bendel Keren , Freund Ari , Rawitz Dror
Published: January 2005

The
local ratio
technique is a methodology for the design and analysis of algorithms for a broad range of optimization problems. The technique is remarkably simple and elegant, and yet can be applied to several classical and fundamental problems (including covering problems, packing problems, and scheduling problems). The local ratio technique uses elementary math and requires combinatorial insight into the structure and properties of the problem at hand. Typically, when using the technique, one has to invent a weight function for a problem instance under which every "reasonable" solution is "good." The local ratio technique is closely related to the
primal-dual
schema, though it is not based on weak LP duality (which is the basis of the primal-dual approach) since it is not based on linear programming.In this survey we, introduce the local ratio technique and demonstrate its use in the design and analysis of algorithms for various problems. We trace the evolution path of the technique since its inception in the 1980's, culminating with the most recent development, namely,
fractional local ratio
, which can be viewed as a new LP rounding technique.
The usability problem for home appliances
Authors: Marks Joe
Published: January 2005

Ordinary people already have great difficulty using the advanced features of digitally enabled household appliances, and the problem grows worse with time as more customization and programming features are added. This usability problem cannot be solved using the tiny displays and limited control buttons typically found on such devices. In this talk I will describe a new type of collaborative interface in which the appliance actively helps the user, especially with complex features that are only used occasionally. This interface provides a consistent and pervasive mechanism for answering the who-what-where-when-why-how questions that often cause users to consult a manual, call a help line, or simply give up. A crucial aspect of the interface architecture is the use of home networking to share a physically large and computationally powerful display among multiple appliances.

Why is this a relevant talk for a software-engineering conference? A contributing factor to the usability crisis is the dominance of engineers in product design at many companies. The development of more-usable devices requires a broader conception of engineering that includes interaction design, artificial intelligence, and human factors - at a minimum. I will describe how these disciplines can complement traditional electrical and software engineering in the context of attempting to solve a commercially significant real-world problem.
Resolving uncertainties during trace analysis
Authors: Egyed Alexander
Published: January 2005

Software models provide independent perspectives onto software systems. Ideally, all models should use the same model element to describe the same part of a system. Practically, models elements are not shared because of syntactic and semantic differences among modeling notations. Trace dependencies explicitly maintain the commonalities among the distinct model elements.

Generating and maintaining trace dependencies is difficult, costly, and highly error-prone. Automated trace analysis techniques are scarce. This paper extends an existing, testing-based technique for generating and maintaining trace dependencies. It is based on the commonality principle: if two model elements of different perspectives are the same then they must have the same source code. The existing approach associates test scenarios with model elements, tests them, and observes what lines of code are being executed. Model elements are considered the same/similar if their testing uses the same/overlapping lines of code.

This paper extends the existing approach (and tool) by giving the user a richer, more powerful, yet precise language on how to relate model elements, test scenarios, and source code (the input). This allows some forms of uncertainties to exist in input data without sacrificing reliability. The extended approach also identifies "shared code." Shared code works against the commonality principle in that model elements do not relate if they overlap solely on their use of generic source code (e.g., queue). As a pre-requisite, our approach requires an executable and observable software system and test scenarios.
Automating comprehensive safety analysis of concurrent programs using verisoft and TXL
Authors: Dingel Juergen , Liang Hongzhi
Published: January 2005

In run-time safety analysis the executions of a concurrent program are monitored and analyzed with respect to safety properties. Similar to testing, run-time analysis is quite efficient, but it also tends to be incomplete. The results pertain only to the observed executions which may constitute just a small subset of all possible executions.

In this paper, we describe a tool called ViP which uses the software model checker VeriSoft to perform comprehensive run-time safety analyses of concurrent C/C++ programs. A ViP analysis proceeds in three fully automated steps: First, the input program is prepared for a VeriSoft analysis through instrumentation. Next, VeriSoft is invoked to generate the traces corresponding to all possible executions of the program. Then, the traces are checked efficiently for specification violations. The instrumentation is based on the source code transformation language TXL. TXL allows for the instrumentation to be described in terms of rewrite rules and gives ViP a remarkable amount of flexibility.

The paper describes ViP together with its use of VeriSoft and TXL. Several sample analyses are discussed to illustrate the use of ViP.
Merging partial behavioural models
Authors: Uchitel Sebastian , Chechik Marsha
Published: January 2005

Constructing comprehensive operational models of intended system behaviour is a complex and costly task. Consequently, practitioners have adopted techniques that support incremental elaboration of partial behaviour descriptions. A noteworthy example is the wide adoption of scenario-based notations such as message sequence charts. Scenario-based specifications are partial descriptions that can be incrementally elaborated to cover the system behaviour that is of interest. However, how should partial behavioural models described by different stakeholders with different viewpoints covering different aspects of behaviour be composed? How should partial models of component instances of the same type be put together.

In this paper, we propose model merging as a general solution to these questions. We formally define model merging based on observational refinement and show that merging consistent models is a process that should result in a minimal common refinement. Because minimal common refinements are not guaranteed to be unique, we argue that the modeller should participate in the process of elaborating such a model. We also discuss the role of the least common refinement and the greatest lower bound of all minimal common refinements in this elaboration process. In addition, we provide algorithms for i) checking consistency between two models; ii) constructing their least common refinement if one exists; iii) supporting the construction of a minimal common refinement if there is no least common refinement.
Reasoning about partial goal satisfaction for requirements and design engineering
Authors: Letier Emmanuel , van Lamsweerde Axel
Published: January 2005

Exploring alternative options is at the heart of the requirements and design processes. Different alternatives contribute to different degrees of achievement of non-functional goals about system safety, security, performance, usability, and so forth. Such goals in general cannot be satisfied in an absolute, clear-cut sense. Various qualitative and quantitative frameworks have been proposed to support the assessment of alternatives for design decision making. In general they lead to limited conclusions due to the lack of accuracy and measurability of goal formulations and the lack of impact propagation rules along goal contribution links.

The paper presents techniques for specifying partial degrees of goal satisfaction and for quantifying the impact of alternative system designs on the degree of goal satisfaction. The approach consists in enriching goal refinement models with a probabilistic layer for reasoning about partial satisfaction. Within such models, non-functional goals are specified in a precise, probabilistic way; their specification is interpreted in terms of application-specific measures; impact of alternative goal refinements is evaluated in terms of refinement equations over random variables involved in the system's functional goals. A systematic method is presented for guiding the elaboration of such models. The latter can then be used to assess the impact of alternative decisions on the degree of goal satisfaction or to derive quantitative, fine-grained requirements on the software to achieve the higher-level goals.
Testing static analysis tools using exploitable buffer overflows from open source code
Authors: Zitser Misha , Lippmann Richard , Leek Tim
Published: January 2005

Five modern static analysis tools (ARCHER, BOON, Poly-Space C Verifier, Splint, and UNO) were evaluated using source code examples containing 14 exploitable buffer overflow vulnerabilities found in various versions of Sendmail, BIND, and WU-FTPD. Each code example included a "BAD" case with and a "OK" case without buffer overflows. Buffer overflows varied and included stack, heap, bss and data buffers; access above and below buffer bounds; access using pointers, indices, and functions; and scope differences between buffer creation and use. Detection rates for the "BAD" examples were low except for Poly-Space and Splint which had average detection rates of 87% and 57%, respectively. However, average false alarm rates were high and roughly 50% for these two tools. On patched programs these two tools produce one warning for every 12 to 46 lines of source code and neither tool appears able to accurately distinguished between vulnerable and patched code.
An efficient and backwards-compatible transformation to ensure memory safety of C programs
Authors: Xu Wei , DuVarney Daniel C. , Sekar R.
Published: January 2005

Memory-related errors, such as buffer overflows and dangling pointers, remain one of the principal reasons for failures of C programs. As a result, a number of recent research efforts have focused on the problem of dynamic detection of memory errors in C programs. However, existing approaches suffer from one or more of the following problems: inability to detect all memory errors (e.g., Purify), requiring non-trivial modifications to existing C programs (e.g., Cyclone), changing the memory management model of C to use garbage collection (e.g., CCured), and excessive performance overheads. In this paper, we present a new approach that addresses these problems. Our approach operates via source code transformation and combines efficient data-structures with simple, localized optimizations to obtain good performance.
Variability management with feature-oriented programming and aspects
Authors: Mezini Mira , Ostermann Klaus
Published: January 2005

This paper presents an analysis of feature-oriented and aspect-oriented modularization approaches with respect to variability management as needed in the context of system families. This analysis serves two purposes. On the one hand, our analysis of the weaknesses of feature-oriented approaches (FOAs for short) emphasizes the importance of crosscutting modularity as supported by the aspect-oriented concepts of pointcut and advice. On the other hand, by pointing out some of AspectJ's weaknesses and by demonstrating how Caesar, a language which combines concepts from both AspectJ and FOAs, is more effective in this context, we also demonstrate the power of appropriate support for layer modules.
Verifying aspect advice modularly
Authors: Krishnamurthi Shriram , Fisler Kathi , Greenberg Michael
Published: January 2005

Aspect-oriented programming has become an increasingly important means of expressing cross-cutting program abstractions. Despite this, aspects lack support for computer-aided verification. We present a technique for verifying aspect-oriented programs (expressed as state machines). Our technique assumes that the set of pointcut designators is known statically, but that the actual advice can vary. This calls for a modular technique that does not require repeated analysis of the entire system every time a developer changes advice. We present such an analysis, addressing several subtleties that arise. We also present an important optimization for handling multiple pointcut designators. We have implemented a prototype verifier and applied it to some simple but interesting cases.
Modular design and verification of component-based mechatronic systems with online-reconfiguration
Authors: Giese Holger , Burmester Sven , Schäfer Wilhelm , Oberschelp Oliver
Published: January 2005

The development of complex mechatronic systems requires a careful and ideally verifiable design. In addition, engineers from different disciplines, namely mechanical, electrical and software engineering, have to cooperate. The current technology is to use block diagrams including discrete blocks with statecharts for the design and verification of such systems. This does not adequately support the verification of large systems which improve the system behavior at run-time by means of online reconfiguration of its controllers because the system as whole has to be verified. It also does not support cooperative interdisciplinary work because a white-box view on all blocks involved in the online reconfiguration is required. This paper proposes a rigorous component concept based on the notion of UML component diagrams which enables modular composition and decomposition of complex systems with online reconfiguration given by hierarchical hybrid component specifications. The approach enables compatibility checks between components that are often independently developed (across the different disciplines) and supports compositional model checking based on a rigorously defined semantics.
Refining code-design mapping with flow analysis
Authors: Zhang Xiaofang , Young Michal , Lasseter John H. E. F.
Published: January 2005

We address the problem of refining and completing a partially specified high-level design model and a partially-defined mapping from source code to design model. This is related but not identical to tasks that have been automated with a variety of reverse engineering tools to support software modification tasks. We posited that set-based flow analysis algorithms would provide a convenient and powerful basis for refining an initial rough model and partial mapping, and in particular that the ability to compute fixed points of set equations would be useful in propagating constraints on the relations among the model, the mapping, and facts extracted from the implementation. Here we report our experience applying this approach to a modest but realistic example problem. We were successful in expressing a variety of useful transformations very succinctly as flow equations, and the propagation of recursively-defined constraints was indeed useful in refining the mapping from implementation to model. On the other hand, our experience highlights remaining challenges to make this an attractive approach for general use. Special measures are required to identify and remove inconsistent constraints before they propagate through a system. Also, while the required flow equations are succinct, they are also rather opaque; it is not obvious how their expressive power might be preserved in a more accessible notation.
Scaling regression testing to large software systems
Authors: Orso Alessandro , Shi Nanjuan , Harrold Mary Jean
Published: January 2005

When software is modified, during development and maintenance, it is regression tested to provide confidence that the changes did not introduce unexpected errors and that new features behave as expected. One important problem in regression testing is how to select a subset of test cases, from the test suite used for the original version of the software, when testing a modified version of the software. Regression-test-selection techniques address this problem. Safe regression-test-selection techniques select every test case in the test suite that may behave differently in the original and modified versions of the software. Among existing safe regression testing techniques, efficient techniques are often too imprecise and achieve little savings in testing effort, whereas precise techniques are too expensive when used on large systems. This paper presents a new regression-test-selection technique for Java programs that is safe, precise, and yet scales to large systems. It also presents a tool that implements the technique and studies performed on a set of subjects ranging from 70 to over 500 KLOC. The studies show that our technique can efficiently reduce the regression testing effort and, thus, achieve considerable savings.
A key-chain-based keying scheme for many-to-many secure group communication
Authors: Huang Dijiang , Medhi Deep
Published: January 2005

We propose a novel secure group keying scheme using
hash chain
for
many-to-many
secure group communication. This scheme requires a
key predistribution center
to generate multiple hash chains and allocates exactly one hash value from each chain to a group member. A group member can use its allocated hash values (secrets) to generate group and subgroup keys. Key distribution can be offline or online via the key distribution protocol. Once keys are distributed, this scheme enables a group member to communicate with any possible subgroups
without
the help of the key distribution center, and without having to leave the overall group, thus avoiding any setup delay. Our scheme is suitable for applications where the population of a system is stable, group size is moderate, subgroup formation is frequent, and the application is delay sensitive. Through analysis, we present effectiveness of our approach.
Client-side caching for TLS
Authors: Shacham Hovav , Boneh Dan , Rescorla Eric
Published: January 2005

We propose two new mechanisms for caching handshake information on TLS clients. The "fast-track" mechanism provides a client-side cache of a server's public parameters and negotiated parameters in the course of an initial, enabling handshake. These parameters need not be resent on subsequent handshakes. Fast-track reduces both network traffic and the number of round trips, and requires no additional server state. These savings are most useful in high-latency environments such as wireless networks. The second mechanism, "client-side session caching," allows the server to store an encrypted version of the session information on a client, allowing a server to maintain a much larger number of active sessions in a given memory footprint. Our design is fully backward-compatible with TLS: extended clients can interoperate with servers unaware of our extensions and vice versa. We have implemented our fast-track proposal to demonstrate the resulting efficiency improvements.
Hypothesizing and reasoning about attacks missed by intrusion detection systems
Authors: Ning Peng , Xu Dingbang
Published: January 2005

Several alert correlation methods have been proposed over the past several years to construct high-level attack scenarios from low-level intrusion alerts reported by intrusion detection systems (IDSs). However, all of these methods depend heavily on the underlying IDSs, and cannot deal with attacks missed by IDSs. In order to improve the performance of intrusion alert correlation and reduce the impact of missed attacks, this paper presents a series of techniques to hypothesize and reason about attacks possibly missed by the IDSs. In addition, this paper also discusses techniques to infer attribute values for hypothesized attacks, to validate hypothesized attacks through raw audit data, and to consolidate hypothesized attacks to generate concise attack scenarios. The experimental results in this paper demonstrate the potential of these techniques in building high-level attack scenarios.
On equivalence and canonical forms in the LF type theory
Authors: Harper Robert , Pfenning Frank
Published: January 2005

Decidability of definitional equality and conversion of terms into canonical form play a central role in the meta-theory of a type-theoretic logical framework. Most studies of definitional equality are based on a confluent, strongly normalizing notion of reduction. Coquand has considered a different approach, directly proving the correctness of a practical equivalance algorithm based on the shape of terms. Neither approach appears to scale well to richer languages with, for example, unit types or subtyping, and neither provides a notion of canonical form suitable for proving adequacy of encodings.In this article, we present a new, type-directed equivalence algorithm for the LF type theory that overcomes the weaknesses of previous approaches. The algorithm is practical, scales to richer languages, and yields a new notion of canonical form sufficient for adequate encodings of logical systems. The algorithm is proved complete by a Kripke-style logical relations argument similar to that suggested by Coquand. Crucially, both the algorithm itself and the logical relations rely only on the shapes of types, ignoring dependencies on terms.
A new decidability technique for ground term rewriting systems with applications
Authors: Verma Rakesh , Hayrapetyan Ara
Published: January 2005

Programming language interpreters, proving equations (e.g.
x
3
=
x
implies the ring is Abelian), abstract data types, program transformation and optimization, and even computation itself (e.g., turing machine) can all be specified by a set of rules, called a rewrite system. Two fundamental properties of a rewrite system are the confluence or Church--Rosser property and the unique normalization property. In this article, we develop a standard form for ground rewrite systems and the concept of standard rewriting. These concepts are then used to: prove a pumping lemma for them, and to derive a new and direct decidability technique for decision problems of ground rewrite systems. To illustrate the usefulness of these concepts, we apply them to prove: (i) polynomial size bounds for witnesses to violations of unique normalization and confluence for ground rewrite systems containing unary symbols and constants, and (ii) polynomial height bounds for witnesses to violations of unique normalization and confluence for arbitrary ground systems. Apart from the fact that our technique is direct in contrast to previous decidability results for both problems, which were indirectly obtained using tree automata techniques, this approach also yields tighter bounds for rewrite systems with unary symbols than the ones that can be derived with the indirect approach. Finally, as part of our results, we give a polynomial-time algorithm for checking whether a rewrite system has the unique normalization property for all subterms in the rules of the system.
A modal logic framework for multi-agent belief fusion
Authors: Liau Churn-Jung
Published: January 2005

This article provides a modal logic framework for reasoning about multi-agent belief and its fusion. We propose logics for reasoning about cautiously merged agent beliefs that have different degrees of reliability. These logics are obtained by combining the multi-agent epistemic logic and multi-source reasoning systems. The fusion is cautious in the sense that if an agent's belief is in conflict with those of higher priorities, then his belief is completely discarded from the merged result. We consider two strategies for the cautious merging of beliefs. In the first, calledlevel cutting fusion, if inconsistency occurs at some level, then all beliefs at the lower levels are discarded simultaneously. In the second, calledlevel skipping fusion, only the level at which the inconsistency occurs is skipped. We present the formal semantics and axiomatic systems for these two strategies and discuss some applications of the proposed logical systems. We also develop a tableau proof system for the logics and prove the complexity result for the satisfiability and validity problems of these logics.
Eternity variables to prove simulation of specifications
Authors: Hesselink Wim H.
Published: January 2005

Simulations of specifications are introduced as a unification and generalization of refinement mappings, history variables, forward simulations, prophecy variables, and backward simulations. A specification implements another specification if and only if there is a simulation from the first one to the second one that satisfies a certain condition. By adding stutterings, the formalism allows that the concrete behaviors take more (or possibly less) steps than the abstract ones.Eternity variables are introduced as a more powerful alternative for prophecy variables and backward simulations. This formalism is semantically complete: every simulation that preserves quiescence is a composition of a forward simulation, an extension with eternity variables, and a refinement mapping. This result does not need finite invisible nondeterminism and machine closure as in the Abadi--Lamport Theorem. The requirement of internal continuity is weakened to preservation of quiescence.Almost all concepts are illustrated by tiny examples or counter-examples.
Querying web metadata
Authors: Özsoyoǧlu Gültekin , Altingövde Ismail Sengör , Al-Hamdani Abdullah , Özel Selma Ayşe , Ulusoy Özgür , Özsoyoǧlu Zehra Meral
Published: January 2005

In this article, we discuss the issues involved in adding a native score management system to object-relational databases, to be used in querying Web metadata (that describes the semantic content of Web resources). The Web metadata model is based on topics (representing entities), relationships among topics (called
metalinks
), and importance scores (sideway values) of topics and metalinks. We extend database relations with scoring functions and importance scores. We add to SQL score-management clauses with well-defined semantics, and propose the sideway-value algebra (SVA), to evaluate the extended SQL queries. SQL extensions and the SVA algebra are illustrated through two Web resources, namely, the DBLP Bibliography and the SIGMOD Anthology.SQL extensions include clauses for propagating input tuple importance scores to output tuples during query processing, clauses that specify query stopping conditions, threshold predicates (a type of approximate similarity predicates for text comparisons), and user-defined-function-based predicates. The propagated importance scores are then used to rank and return a small number of output tuples. The query stopping conditions are propagated to SVA operators during query processing. We show that our SQL extensions are well-defined, meaning that, given a database and a query Q, under any query processing scheme, the output tuples of Q and their importance scores stay the same.To process the SQL extensions, we discuss two sideway value algebra operators, namely, sideway value algebra join and topic closure, give their implementation algorithms, and report their experimental evaluations.
Multiversion-based view maintenance over distributed data sources
Authors: Chen Songting , Liu Bin , Rundensteiner Elke A.
Published: January 2005

Materialized views can be maintained by submitting maintenance queries to the data sources. However, the query results may be erroneous due to concurrent source updates. State-of-the-art maintenance strategies typically apply compensations to resolve such conflicts and assume all source schemata remain stable over time. In a loosely coupled dynamic environment, the sources may autonomously change not only their data but also their schema or semantics. Consequently, either the maintenance or the compensation queries may be broken. Unlike compensation-based approaches found in the literature, we instead model the complete materialized view maintenance process as a view maintenance transaction (VM_Transaction). This way, the anomaly problem can be rephrased as the serializability of VM_Transactions. To achieve VM_Transaction serializability, we propose a multiversion concurrency control algorithm, called
TxnWrap
, which is shown to be the appropriate design for loosely coupled environments with autonomous data sources. TxnWrap is complementary to the maintenance algorithms proposed in the literature, since it removes concurrency issues from consideration allowing the designer to focus on the maintenance logic. We show several optimizations of TxnWrap, in particular, (1) space optimizations on versioned data materialization and (2) parallel maintenance scheduling. With these optimizations, TxnWrap even outperforms state-of-the-art view maintenance solutions in terms of refresh time. Further, several design choices of TxnWrap are studied each having its respective advantages for certain environmental settings. A correctness proof based on transaction theory for TxnWrap is also provided. Last, we have implemented TxnWrap. The experimental results confirm that TxnWrap achieves predictable performance under a varying rate of concurrency.
Processing XML streams with deterministic automata and stream indexes
Authors: Green Todd J. , Gupta Ashish , Miklau Gerome , Onizuka Makoto , Suciu Dan
Published: January 2005

We consider the problem of evaluating a large number of XPath expressions on a stream of XML packets. We contribute two novel techniques. The first is to use a single Deterministic Finite Automaton (DFA). The contribution here is to show that the DFA can be used effectively for this problem: in our experiments we achieve a constant throughput, independently of the number of XPath expressions. The major issue is the size of the DFA, which, in theory, can be exponential in the number of XPath expressions. We provide a series of theoretical results and experimental evaluations that show that the
lazy
DFA has a small number of states, for all practical purposes. These results are of general interest in XPath processing, beyond stream processing. The second technique is the Streaming IndeX (SIX), which consists of adding a small amount of binary data to each XML packet that allows the query processor to achieve significant speedups. As an application of these techniques we describe the XML Toolkit (XMLTK), a collection of command-line tools providing highly scalable XML data processing.
Decoupling partitioning and grouping
Authors: Samet Hanan
Published: January 2005

The principle of decoupling the partitioning and grouping processes that form the basis of most spatial indexing methods that use tree directories of buckets is explored. The decoupling is designed to overcome the following drawbacks of traditional solutions:(1) multiple postings in disjoint space decomposition methods that lead to balanced trees such as the hB-tree where a node split in the event of node overflow may be such that one of the children of the node that was split becomes a child of both of the nodes resulting from the split;(2) multiple coverage and nondisjointness of methods based on object hierarchies such as the R-tree which lead to nonunique search paths;(3) directory nodes with similarly-shaped hyper-rectangle bounding boxes with minimum occupancy in disjoint space decomposition methods such as those based on quadtrees and k-d trees that make use of regular decomposition.The first two drawbacks are shown to be overcome by the BV-tree where as a result of decoupling the partitioning and grouping processes, the union of the regions associated with the nodes at a given level of the directory does not necessarily contain all of the data points although all searches take the same amount of time. The BV-tree is not plagued by the third drawback. The third drawback is shown to be overcome by the PK-tree where the grouping process is based on ensuring that every node has at least k objects or blocks. The PK-tree is not plagued by the first two drawbacks as they are inapplicable to it. In both cases, the downside of decoupling the partitioning and grouping processes is that the resulting structure is not necessarily balanced, although, since the nodes have a relatively large fanout, the deviation from a balanced structure is relatively small.
Evaluating information security investments using the analytic hierarchy process
Authors: Bodin Lawrence D. , Gordon Lawrence A. , Loeb Martin P.
Published: January 2005

In today's information-based economy, organizations must avoid costly information security breaches. Unfortunately, organizations cannot make all of their information 100% secure all of the time. There are economic, as well as technical, impediments that prevent perfect information security. Accordingly, organizations usually prepare an annual fixed (limited) budget for the maintenance and improvement of their information security systems. Two key issues confront the chief information security officer (CISO) of an organization: how to spend this limited information security budget most effectively, and how to make the case to the organization's chief financial officer (CFO) for an increase in funds to further enhance the organization's information security. The primary objective of this article is to show how to use the analytic hierarchy process (AHP) to address these two information security issues.
The value of mobile applications
Authors: Nah Fiona Fui-Hoon , Siau Keng , Sheng Hong
Published: January 2005

Mobile and wireless devices are enabling organizations to conduct business more effectively. Mobile applications can be used to support e-commerce with customers and suppliers, and to conduct e-business within and across organizational boundaries. Despite these benefits, organizations and their customers still lack an understanding of the value of mobile applications. Value is defined here as the principles for evaluating the consequences of action, inaction, or decision [4]. The value proposition of mobile applications can be defined as the net value of the benefits and costs associated with the adoption and adaptation of mobile applications [2].
On the nature of computing
Authors: Crowcroft Jon
Published: January 2005

Computing is its own virtual world, bound only by its practitioners' imaginations and creativity.
Virtual colonoscopy
Authors: Kaufman Arie E. , Lakare Sarang , Kreeger Kevin , Bitter Ingmar
Published: January 2005

A computer-graphics-based alternative to conventional optical colonoscopy, known as virtual colonoscopy (VC) or computed tomography colonography (CTC), is rapidly gaining popularity. During this procedure, which was concurrently developed by our group at Stony Brook University [5] and by other researchers [10], the distended colon is imaged by a helical or multislice CT scanner. The acquired abdominal CT scan commonly consists of 350--750 axial images of 512x512 sub-millimeter resolution, providing excellent contrast between the colon wall and the lumen. A 3D model of the colon is then reconstructed from the CT scan by automatically segmenting the colon out of the rest of the abdomen and employing an electronic cleansing algorithm for computer-based removal of the residual material. The PC-based visualization software employs volume rendering and allows the user, typically a physician, to interactively navigate through the virtual 3D model of the colon. An intuitive user interface with customized tools supports measurements and virtual biopsy to inspect suspicious regions. Unlike optical colonoscopy (see the sidebar "Conventional Colorectal Cancer Screening"), VC is patient friendly since the patient undergoes less rigorous preparation prior to the procedure. VC is also a fast, noninvasive, highly accurate, cost-effective method for mass screening of colon polyps.
Volumetric heart modeling and analysis
Authors: Park Kyoungju , Montillo Albert , Metaxas Dimitris , Axel Leon
Published: January 2005

Heart disease is the leading cause of death in the Western world and consequently the study of normal and pathological heart behavior is an active research area. In particular, the study of the shape and motion of the heart is important because many heart diseases are strongly correlated to these two factors. The human heart is composed of two separate pumps: a right heart that pumps the blood through the lungs and a left heart that pumps the blood through the peripheral organs. In turn, each of these "hearts" is a two-chamber pump composed of an atrium and a ventricle. Special mechanisms in the heart provide cardiac rhythm and transmit action potentials throughout the heart muscle to cause the heart's rhythmic relaxation (diastole) and contraction (systole).
Open source software for medical image processing and visualization
Authors: Yoo Terry S. , Ackerman Michael J.
Published: January 2005

Societies often create smaller subsets or communities that connect with one another for commerce and intellectual exchange over mutual interests. In science and engineering, the need for communication among researchers is often hampered by artificial barriers of university politics, economic market forces, and the sheer momentum of an academic reward structure that values individual discovery over joint development. Recent initiatives have attempted to reduce some of these barriers, encouraging collaborative multidisciplinary research programs. Through this effort, we have studied the processes that lead to the successful foundation of new communities.
Dataless objects considered harmful
Authors: Hu Chenglie
Published: January 2005

Novice programmers should be taught not only the value of faithfully representing objects but, even more important, multiple programming paradigms as well.
Technology mapping and architecture evalution for
k/m
-macrocell-based FPGAs
Authors: Cong Jason , Huang Hui , Yuan Xin
Published: January 2005

In this article, we study the technology mapping problem for a novel field-programmable gate array (FPGA) architecture that is based on
k
-input single-output programmable logic array- (PLA-) like cells, or,
k/m
-macrocells. Each cell in this architecture can implement a single output function of up to
k
inputs and up to
m
product terms. We develop a very efficient technology mapping algorithm, k_m_flow, for this new type of architecture. The experimental results show that our algorithm can achieve depth-optimality on almost all the testcases in a set of 16 Microelectronics Center of North Carolina (MCNC) benchmarks. Furthermore it is shown that on this set of benchmarks, with only a relatively small number of product terms (
m
≤
k
+ 3), the
k/m
-macrocell-based FPGAs can achieve the same or similar mapping depth compared with the traditional
k
-input single-output lookup table- (
k
-LUT-) based FPGAs. We also investigate the total area and delay of
k/m
-macrocell-based FPGAs and compare them with those of the commonly used 4-LUT-based FPGAs. The experimental results show that
k/m
-macrocell-based FPGAs can outperform 4-LUT-based FPGAs in terms of both delay and area after placement and routing by VPR on this set of benchmarks.
Bipartitioning and encoding in low-power pipelined circuits
Authors: Ruan Shanq-Jang , Tsai Kun-Lin , Naroska Edwin , Lai Feipei
Published: January 2005

In this article, we present a bipartition dual-encoding architecture for low-power pipelined circuits. We exploit the bipartition approach as well as encoding techniques to reduce power dissipation not only of combinational logic blocks but also of the pipeline registers. Based on Shannon expansion, we partition a given circuit into two subcircuits such that the number of different outputs of both subcircuits are reduced, and then encode the output of both subcircuits to minimize the Hamming distance for transitions with a high switching probability. We measure the benefits of four different combinational bipartitioning and encoding architectures for comparison. The transistor-level simulation results show that bipartition dual-encoding can effectively reduce power by 72.7% for the pipeline registers and 27.1% for the total power consumption on average. To the best of our knowledge, it is the first work that presents an in-depth study on bipartition and encoding techniques to optimize power for pipelined circuits.
Algorithmic aspects of hardware/software partitioning
Authors: Arató Péter , Mann Zoltán Ádám , Orbán András
Published: January 2005

One of the most crucial steps in the design of embedded systems is hardware/software partitioning, that is, deciding which components of the system should be implemented in hardware and which ones in software. Most formulations of the hardware/software partitioning problem are NP-hard, so the majority of research efforts on hardware/software partitioning has focused on developing efficient heuristics.This article considers the combinatorial structure behind hardware/software partitioning. Two similar versions of the partitioning problem are defined, one of which turns out to be NP-hard, whereas the other one can be solved in polynomial time. This helps in understanding the real cause of complexity in hardware/software partitioning. Moreover, the polynomial-time algorithm serves as the basis for a highly efficient novel heuristic for the NP-hard version of the problem. Unlike general-purpose heuristics such as genetic algorithms or simulated annealing, this heuristic makes use of problem-specific knowledge, and can thus find high-quality solutions rapidly. Moreover, it has the unique characteristic that it also calculateslower bounds on the optimum solution. It is demonstrated on several benchmarks and also large random examples that the new algorithm clearly outperforms other heuristics that are generally applied to hardware/software partitioning.
Efficient and portable multiple recursive generators of large order
Authors: Deng Lih-Yuan
Published: January 2005

Deng and Xu [2003] proposed a system of multiple recursive generators of prime moduluspand orderk, where all nonzero coefficients of the recurrence are equal. This type of generator is efficient because only a single multiplication is required. It is common to choosep= 231−1 and some multipliers to further improve the speed of the generator. In this case, some fast implementations are available without using explicit division or multiplication. For such ap, Deng and Xu [2003] provided specific parameters, yielding the maximum period for recurrence of orderk, up to 120. One problem of extending it to a largerkis the difficulty of finding a complete factorization ofpk−1. In this article, we apply an efficient technique to findksuch that it is easy to factorpk−1, withp= 231−1. The largest one found isk= 1597. To find multiple recursive generators of large orderk, we introduce an efficient search algorithm with an early exit strategy in case of a failed search. Fork= 1597, we constructed several efficient and portable generators with the period length approximately 1014903.1.
ASAP3: a batch means procedure for steady-state simulation analysis
Authors: Steiger Natalie M. , Lada Emily K. , Wilson James R. , Joines Jeffrey A. , Alexopoulos Christos , Goldsman David
Published: January 2005

We introduce ASAP3, a refinement of the batch means algorithms ASAP and ASAP2, that delivers point and confidence-interval estimators for the expected response of a steady-state simulation. ASAP3 is a sequential procedure designed to produce a confidence-interval estimator that satisfies user-specified requirements on absolute or relative precision as well as coverage probability. ASAP3 operates as follows: the batch size is progressively increased until the batch means pass the Shapiro-Wilk test for multivariate normality; and then ASAP3 fits a first-order autoregressive (AR(1)) time series model to the batch means. If necessary, the batch size is further increased until the autoregressive parameter in the AR(1) model does not significantly exceed 0.8. Next, ASAP3 computes the terms of an inverse Cornish-Fisher expansion for the classical batch means
t
-ratio based on the AR(1) parameter estimates; and finally ASAP3 delivers a correlation-adjusted confidence interval based on this expansion. Regarding not only conformance to the precision and coverage-probability requirements but also the mean and variance of the half-length of the delivered confidence interval, ASAP3 compared favorably to other batch means procedures (namely, ABATCH, ASAP, ASAP2, and LBATCH) in an extensive experimental performance evaluation.