bluuebunny/crossref_metadata_2025 huggingface dataset:
A search engine for 3D models
Authors: Funkhouser Thomas , Min Patrick , Kazhdan Michael , Chen Joyce , Halderman Alex , Dobkin David , Jacobs David
Published: January 2003

As the number of 3D models available on the Web grows, there is an increasing need for a search engine to help people find them. Unfortunately, traditional text-based search techniques are not always effective for 3D data. In this article, we investigate new shape-based search methods. The key challenges are to develop query methods simple enough for novice users and matching algorithms robust enough to work for arbitrary polygonal models. We present a Web-based search engine system that supports queries based on 3D sketches, 2D sketches, 3D models, and/or text keywords. For the shape-based queries, we have developed a new matching algorithm that uses spherical harmonics to compute discriminating similarity measures without requiring repair of model degeneracies or alignment of orientations. It provides 46 to 245% better performance than related shape-matching methods during precision--recall experiments, and it is fast enough to return query results from a repository of 20,000 models in under a second. The net result is a growing interactive index of 3D models available on the Web (i.e., a Google for 3D models).
Continuous contact simulation for smooth surfaces
Authors: Kry Paul G. , Pai Dinesh K.
Published: January 2003

Dynamics simulation of smooth surfaced rigid bodies in contact is a critical problem in physically based animation and interactive virtual environments. We describe a technique that uses reduced coordinates to evolve a single continuous contact between smooth piecewise parametric surfaces. The incorporation of friction into our algorithm is straightforward. The dynamics equations, although slightly more complex due to the reduced coordinate formulation, can be integrated easily using explicit integrators without the need for constraint stabilization. Reduced coordinates confine integration errors to the constraint manifold, thereby permitting a wide choice of step sizes with visually acceptable results. We demonstrate these results using Loop Subdivision surfaces with parametric evaluation.
Run-time support for distributed sharing in safe languages
Authors: Hu Y. Charlie , Yu Weimin , Cox Alan , Wallach Dan , Zwaenepoel Willy
Published: January 2003

We present a new run-time system that supports object sharing in a distributed system. The key insight in this system is that a handle-based implementation of such a system enables efficient and transparent sharing of data with both fine- and coarse-grained access patterns. In addition, it supports efficient execution of garbage-collected programs. In contrast, conventional distributed shared memory (DSM) systems are limited to providing only one granularity with good performance, and have experienced difficulty in efficiently supporting garbage collection. A safe language, in which no pointer arithmetic is allowed, can transparently be compiled into a handle-based system and constitutes its preferred mode of use. A programmer can also directly use a handle-based programming model that avoids pointer arithmetic on the handles, and achieve the same performance but without the programming benefits of a safe programming language. This new run-time system, DOSA (Distributed Object Sharing Architecture), provides a shared object space abstraction rather than a shared address space abstraction. The key to its efficiency is the observation that a handle-based distributed implementation permits VM-based access and modification detection without suffering false sharing for fine-grained access patterns. We compare DOSA to TreadMarks, a conventional DSM system that is efficient at handling coarse-grained sharing. The performance of fine-grained applications and garbage-collected applications is considerably better than in TreadMarks, and the performance of coarse-grained applications is nearly as good as in TreadMarks. Inasmuch as the performance of such applications is already good in TreadMarks, we consider this an acceptable performance penalty.
Run-time adaptation in river
Authors: Arpaci-Dusseau Remzi H.
Published: January 2003

We present the design, implementation, and evaluation of run-time adaptation within the River dataflow programming environment. The goal of the River system is to provide adaptive mechanisms that allow database query-processing applications to cope with performance variations that are common in cluster platforms. We describe the system and its basic mechanisms, and carefully evaluate those mechanisms and their effectiveness. In our analysis, we answer four previously unanswered and important questions. Are the core run-time adaptive mechanisms effective, especially as compared to the ideal? What are the keys to making them work well? Can applications easily use these primitives? And finally, are there situations in which run-time adaptation is not sufficient? In performing our study, we utilize a three-pronged approach, comparing results from idealized models of system behavior, targeted simulations, and a prototype implementation. As well as providing insight on the positives and negatives of run-time adaptation both specifically in River and in a broader context, we also comment on the interplay of modeling, simulation, and implementation in system design.
Measuring thin-client performance using slow-motion benchmarking
Authors: Nieh Jason , Yang S. Jae , Novik Naomi
Published: January 2003

Modern thin-client systems are designed to provide the same graphical interfaces and applications available on traditional desktop computers while centralizing administration and allowing more efficient use of computing resources. Despite the rapidly increasing popularity of these client-server systems, there are few reliable analyses of their performance. Industry standard benchmark techniques commonly used for measuring desktop system performance are ill-suited for measuring the performance of thin-client systems because these benchmarks only measure application performance on the server, not the actual user-perceived performance on the client. To address this problem, we have developed slow-motion benchmarking, a new measurement technique for evaluating thin-client systems. In slow-motion benchmarking, performance is measured by capturing network packet traces between a thin client and its respective server during the execution of a slow-motion version of a conventional benchmark application. These results can then be used either independently or in conjunction with conventional benchmark results to yield an accurate and objective measure of the performance of thin-client systems. We have demonstrated the effectiveness of slow-motion benchmarking by using this technique to measure the performance of several popular thin-client systems in various network environments on Web and multimedia workloads. Our results show that slow-motion benchmarking solves the problems with using conventional benchmarks on thin-client systems and is an accurate tool for analyzing the performance of these systems.
On type systems for object-oriented database programming languages
Authors: Leontiev Yuri , Özsu M. Tamer , Szafron Duane
Published: January 2003

The concept of an object-oriented database programming language (OODBPL) is appealing because it has the potential of combining the advantages of object orientation and database programming to yield a powerful and universal programming language design. A uniform and consistent combination of object orientation and database programming, however, is not straightforward. Since one of the main components of an object-oriented programming language is its type system, one of the first problems that arises during an OODBPL design is related to the development of a uniform, consistent, and theoretically sound type system that is sufficiently expressive to satisfy the combined needs of object orientation and database programming.The purpose of this article is to answer two questions: "What are the requirements that a modern type system for an object-oriented database programming language should satisfy?" and "Are there any type systems developed to-date that satisfy these requirements?". In order to answer the first question, we compile the set of requirements that an OODBPL type system should satisfy. We then use this set of requirements to evaluate more than 30 existing type systems. The result of this extensive analysis shows that while each of the requirements is satisfied by at least one type system, no type system satisfies all of them. It also enables identification of the mechanisms that lie behind the strengths and weaknesses of the current type systems.
A survey of customizability in operating systems research
Authors: Denys G. , Piessens F. , Matthijs F.
Published: January 2003

An important goal of an operating system is to make computing and communication resources available in a fair and efficient way to the applications that will run on top of it. To achieve this result, the operating system implements a number of policies for allocating resources to, and sharing resources among applications, and it implements safety mechanisms to guard against misbehaving applications. However, for most of these allocation and sharing tasks, no single optimal policy exists. Different applications may prefer different operating system policies to achieve their goals in the best possible way. A
customizable
or
adaptable
operating system is an operating system that allows for flexible modification of important system policies. Over the past decade, a wide range of approaches for achieving customizability has been explored in the operating systems research community. In this survey, an overview of these approaches, structured around a taxonomy, is presented.
A survey of Web metrics
Authors: Dhyani Devanshu , Ng Wee Keong , Bhowmick Sourav S.
Published: January 2003

The unabated growth and increasing significance of the World Wide Web has resulted in a flurry of research activity to improve its capacity for serving information more effectively. But at the heart of these efforts lie implicit assumptions about "quality" and "usefulness" of Web resources and services. This observation points towards measurements and models that quantify various attributes of web sites. The science of measuring all aspects of information, especially its storage and retrieval or
informetrics
has interested information scientists for decades before the existence of the Web. Is Web informetrics any different, or is it just an application of classical informetrics to a new medium? In this article, we examine this issue by classifying and discussing a wide ranging set of Web metrics. We present the origins, measurement functions, formulations and comparisons of well-known Web metrics for quantifying
Web graph properties
,
Web page significance
,
Web page similarity
,
search and retrieval
,
usage characterization
and
information theoretic properties
. We also discuss how these metrics can be applied for improving Web information access and use.
Some facets of complexity theory and cryptography
Authors: Rothe Jörg
Published: January 2003

In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical cryptography, and then move on to modern public-key cryptography. Particular attention is paid to cryptographic protocols and the problem of constructing key components of protocols such as one-way functions. A function is one-way if it is easy to compute, but hard to invert. We discuss the notion of one-way functions both in a cryptographic and in a complexity-theoretic setting. We also consider interactive proof systems and present some interesting zero-knowledge protocols. In a zero-knowledge protocol, one party can convince the other party of knowing some secret information without disclosing any bit of this information. Motivated by these protocols, we survey some complexity-theoretic results on interactive proof systems and related complexity classes.
Algorithmic issues in modeling motion
Authors: Agarwal Pankaj K. , Guibas Leonidas J. , Edelsbrunner Herbert , Erickson Jeff , Isard Michael , Har-Peled Sariel , Hershberger John , Jensen Christian , Kavraki Lydia , Koehl Patrice , Lin Ming , Manocha Dinesh , Metaxas Dimitris , Mirtich Brian , Mount David , Muthukrishnan S. , Pai Dinesh , Sacks Elisha , Snoeyink Jack , Suri Subhash , Wolefson Ouri
Published: January 2003

This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines.
Implementing Hager's exchange methods for matrix profile reduction
Authors: Reid John K. , Scott Jennifer A.
Published: January 2003

Hager recently introduced down and up exchange methods for reducing the profile of a sparse matrix with a symmetric sparsity pattern. The methods are particularly useful for refining orderings that have been obtained using a standard profile reduction algorithm, such as the Sloan method. The running times for the exchange algorithms reported by Hager suggested their cost could be prohibitive for practical applications. We examine how to implement the exchange algorithms efficiently. For a range of real test problems, it is shown that the cost of running our new implementation does not add a prohibitive overhead to the cost of the original reordering.
Recursive blocked algorithms for solving triangular systems—Part I
Authors: Jonsson Isak , Kågström Bo
Published: January 2003

Triangular matrix equations appear naturally in estimating the condition numbers of matrix equations and different eigenspace computations, including block-diagonalization of matrices and matrix pairs and computation of functions of matrices. To solve a triangular matrix equation is also a major step in the classical Bartels--Stewart method for solving the standard continuous-time Sylvester equation (
AX
−
XB
=
C
). We present novel recursive blocked algorithms for solving one-sided triangular matrix equations, including the continuous-time Sylvester and Lyapunov equations, and a generalized coupled Sylvester equation. The main parts of the computations are performed as level-3 general matrix multiply and add (GEMM) operations. In contrast to explicit standard blocking techniques, our recursive approach leads to an automatic variable blocking that has the potential of matching the memory hierarchies of today's HPC systems. Different implementation issues are discussed, including when to terminate the recursion, the design of new optimized superscalar kernels for solving leaf-node triangular matrix equations efficiently, and how parallelism is utilized in our implementations. Uniprocessor and SMP parallel performance results of our recursive blocked algorithms and corresponding routines in the state-of-the-art libraries LAPACK and SLICOT are presented. The performance improvements of our recursive algorithms are remarkable, including 10-fold speedups compared to standard algorithms.
Recursive blocked algorithms for solving triangular systems—Part II
Authors: Jonsson Isak , Kågström Bo
Published: January 2003

We continue our study of high-performance algorithms for solving triangular matrix equations. They appear naturally in different condition estimation problems for matrix equations and various eigenspace computations, and as reduced systems in standard algorithms. Building on our successful recursive approach applied to one-sided matrix equations (Part I), we now present novel recursive blocked algorithms for two-sided matrix equations, which include matrix product terms such as

AXB
T

. Examples are the discrete-time standard and generalized Sylvester and Lyapunov equations. The means for achieving high performance is the recursive variable blocking, which has the potential of matching the memory hierarchies of today's high-performance computing systems, and level-3 computations which mainly are performed as GEMM operations. Different implementation issues are discussed, including the design of efficient new algorithms for two-sided matrix products. We present uniprocessor and SMP parallel performance results of recursive blocked algorithms and routines in the state-of-the-art SLICOT library. Although our recursive algorithms with optimized kernels for the two-sided matrix equations perform more operations, the performance improvements are remarkable, including 10-fold speedups or more, compared to standard algorithms.
Algorithm 822: GIZ, HIZ
Authors: Gil Amparo , Segura Javier , Temme Nico M.
Published: January 2003

Two Fortran 77 routines for the evaluation of Scorer functions of complex arguments Gi(
z
), Hi(
z
), and their derivatives are presented. The routines are based on the use of quadrature, Maclaurin series, and asymptotic expansions. For real
z
, comparison with a previous code by A. J. MacLeod [1994] is provided.
A software package for sparse orthogonal factorization and updating
Authors: Edlund Ove
Published: January 2003

Although there is good software for sparse QR factorization, there is little support for updating and downdating, something that is absolutely essential in some linear programming algorithms, for example. This article describes an implementation of sparse LQ factorization, including block triangularization, approximate minimum degree ordering, symbolic factorization, multifrontal factorization,
and
updating and downdating. The factor Q is not retained. The updating algorithm expands the nonzero pattern of the factor L, which is reflected in dynamic representation of L. The block triangularization is used as an "ordering for sparsity" rather than as a prerequisite for block backward substitution. In symbolic factorization, something called "element counters" is introduced to reduce the overestimation of the number of nonzeros that the commonly used methods do. Both the approximate minimum degree ordering and the symbolic factorization are done without explicitly forming the nonzero pattern of the symmetric matrix in the corresponding normal equations. Tests show that the average time used for a single update or downdate is essentially the same as the time used for a single forward or backward substitution. Other parts of the implementation show the same range of performance as existing code, but cannot be replaced because of the special character of the systems that are solved.
Toward a unified approach to statistical language modeling for Chinese
Authors: Gao Jianfeng , Goodman Joshua , Li Mingjing , Lee Kai-Fu
Published: January 2003

This article presents a unified approach to Chinese statistical language modeling (SLM). Applying SLM techniques like trigram language models to Chinese is challenging because (1) there is no standard definition of words in Chinese; (2) word boundaries are not marked by spaces; and (3) there is a dearth of training data. Our unified approach automatically and consistently gathers a high-quality training data set from the Web, creates a high-quality lexicon, segments the training data using this lexicon, and compresses the language model, all by using the maximum likelihood principle, which is consistent with trigram model training. We show that each of the methods leads to improvements over standard SLM, and that the combined method yields the best pinyin conversion result reported.
Meaningful term extraction and discriminative term selection in text categorization via unknown-word methodology
Authors: Lai Yu-Sheng , Wu Chung-Hsien
Published: January 2003

In this article, an approach based on unknown words is proposed for meaningful term extraction and discriminative term selection in text categorization. For meaningful term extraction, a phrase-like unit (PLU)-based likelihood ratio is proposed to estimate the likelihood that a word sequence is an unknown word. On the other hand, a discriminative measure is proposed for term selection and is combined with the PLU-based likelihood ratio to determine the text category. We conducted several experiments on a news corpus, called MSDN. The MSDN corpus is collected from an online news Website maintained by the Min-Sheng Daily News, Taiwan. The corpus contains 44,675 articles with over 35 million words. The experimental results show that the system using a simple classifier achieved 95.31% accuracy. When using a state-of-the-art classifier, kNN, the average accuracy is 96.40%, outperforming all the other systems evaluated on the same collection, including the traditional term-word by kNN (88.52%); sleeping-experts (82.22%); sparse phrase by four-word sleeping-experts (86.34%); and Boolean combinations of words by RIPPER (87.54%). A proposed purification process can effectively reduce the dimensionality of the feature space from 50,576 terms in the word-based approach to 19,865 terms in the unknown word-based approach. In addition, more than 80% of automatically extracted terms are meaningful. Experiments also show that the proportion of meaningful terms extracted from training data is relative to the classification accuracy in outside testing.
Morpheme-based grapheme to phoneme conversion using phonetic patterns and morphophonemic connectivity information
Authors: Kim Byeongchang , Lee Gary Geunbae , Lee Jong-Hyeok
Published: January 2003

Both dictionary-based and rule-based methods on grapheme-to-phoneme conversion have their own advantages and limitations. For example, a large sized phonetic dictionary and complex morphophonemic rules are required for the dictionary-based method and the LTS (letter to sound) rule-based method itself cannot model the complete morphophonemic constraints.This paper describes a grapheme-to-phoneme conversion method for Korean using a dictionary-based and rule-based hybrid method with a phonetic pattern dictionary and CCV (consonant consonant vowel) LTS (letter to sound) rules. The phonetic pattern dictionary, standing for the dictionary-based method, contains entries in the form of a morpheme pattern and its phonetic pattern. The patterns represent candidate phonological changes in left and right boundaries of morphemes. Obviously, the CCV LTS rules stand for the rule-based method. The rules are in charge of grapheme-to-phoneme conversion within morphemes.The conversion method consists of mainly two steps including morpheme to phoneme conversion and morphophonemic connectivity check, and two preprocessing steps including phrase break prediction and morpheme normalization. Phrase break prediction presumes phrase breaks using the stochastic method on part-of-speech (POS) information. Morpheme normalization is to replace non-Korean symbols with their corresponding standard Korean graphemes. In the morpheme-phoneticizing module, each morpheme in the phrase is converted into phonetic patterns by looking it up in the phonetic pattern dictionary. Graphemes within a morpheme are grouped into CCV units and converted into phonemes by the CCV LTS rules. The morphophonemic connectivity table supports grammaticality checking of the two adjacent phonetic morphemes.In experiments with a non-Korean symbol free corpus of 4,973 sentences, we achieved a 99.98% grapheme-to-phoneme conversion performance rate and a 99.0% sentence conversion performance rate. With a broadcast news corpus of 621 sentences, 99.7% of the graphemes and 86.6% of the sentences are correctly converted. The full Korean TTS (Text-to-Speech) system is now being implemented using this conversion method.
Using tone information in Cantonese continuous speech recognition
Authors: Lee Tan , Lau Wai , Wong Y. W. , Ching P. C.
Published: January 2003

In Chinese languages, tones carry important information at various linguistic levels. This research is based on the belief that tone information, if acquired accurately and utilized effectively, contributes to the automatic speech recognition of Chinese. In particular, we focus on the Cantonese dialect, which is spoken by tens of millions of people in Southern China and Hong Kong. Cantonese is well known for its complicated tone system, which makes automatic tone recognition very difficult. This article describes an effective approach to explicit tone recognition of Cantonese in continuously spoken utterances. Tone feature vectors are derived, on a short-time basis, to characterize the syllable-wide patterns of F0 (fundamental frequency) and energy movements. A moving-window normalization technique is proposed to reduce the tone-irrelevant fluctuation of F0 and energy features. Hidden Markov models are employed for context-dependent acoustic modeling of different tones. A tone recognition accuracy of 66.4% has been achieved in the speaker-independent case. The recognized tone patterns are then utilized to assist Cantonese large-vocabulary continuous speech recognition (LVCSR) via a lattice expansion approach. Experimental results show that reliable tone information helps to improve the overall performance of LVCSR.
Mobile safe ambients
Authors: Levi Francesca , Sangiorgi Davide
Published: January 2003

Two forms of interferences are individuated in Cardelli and Gordon's
Mobile Ambients
(MA):
plain interferences
, which are similar to the interferences one finds in CCS and π-calculus; and
grave interferences
, which are more dangerous and may be regarded as programming errors. To control interferences, the MA movement primitives are modified; the resulting calculus is called
Mobile Safe Ambients
(SA).The modification also has computational significance. In the MA interaction rules, an ambient may enter, exit, or open another ambient. The second ambient undergoes the action; it has no control on
when
the action takes place. In SA this is rectified: any movement takes place only if both participants agree.Existing type systems for MA can be easily adapted to SA. The type systems for controlling mobility, however, appear to be more powerful in SA, in that (i) type systems for MA may give more precise information when transplanted onto SA , and (ii) new type systems may be defined. Two type systems are presented that remove all grave interferences.Other advantages of SA are: a useful algebraic theory; programs sometimes more robust (they require milder conditions for correctness) and/or simpler. All these points are illustrated in several examples.
Pointer analysis for structured parallel programs
Authors: Rugina Radu , Rinard Martin C.
Published: January 2003

This paper presents a novel interprocedural, flow-sensitive, and context-sensitive pointer analysis algorithm for multithreaded programs that may concurrently update shared pointers. The algorithm is designed to handle programs with structured parallel constructs, including fork-join constructs, parallel loops, and conditionally spawned threads. For each pointer and each program point, the algorithm computes a conservative approximation of the memory locations to which that pointer may point. The algorithm correctly handles a wide range of programming language constructs, including recursive functions, recursively generated parallelism, function pointers, structures, arrays, nested structures and arrays, pointer arithmetic, casts between different pointer types, heap and stack allocated memory, shared global variables, and thread-private global variables. We have implemented the algorithm in the SUIF compiler system and used the implementation to analyze a set of multithreaded programs written in the Cilk programming language. Our experimental results show that the analysis has good precision and converges quickly for our set of Cilk programs.
Information flow inference for ML
Authors: Pottier François , Simonet Vincent
Published: January 2003

This paper presents a type-based information flow analysis for a call-by-value λ-calculus equipped with references, exceptions and let-polymorphism, which we refer to as ML. The type system is constraint-based and has decidable type inference. Its noninterference proof is reasonably light-weight, thanks to the use of a number of orthogonal techniques. First, a syntactic segregation between
values
and
expressions
allows a lighter formulation of the type system. Second, noninterference is reduced to
subject reduction
for a nonstandard language extension. Lastly, a
semi-syntactic
approach to type soundness allows dealing with constraint-based polymorphism separately.
The marriage of effects and monads
Authors: Wadler Philip , Thiemann Peter
Published: January 2003

Gifford and others proposed an
effect
typing discipline to delimit the scope of computational effects within a program, while Moggi and others proposed
monads
for much the same purpose. Here we marry effects to monads, uniting two previously separate lines of research. In particular, we show that the type, region, and effect system of Talpin and Jouvelot carries over directly to an analogous system for monads, including a type and effect reconstruction algorithm. The same technique should allow one to transpose any effect system into a corresponding monad system.
Deciding the confluence of ordered term rewrite systems
Authors: Comon Hubert , Narendran Paliath , Nieuwenhuis Robert , Rusinowitch Michael
Published: January 2003

replace me
Resource-distribution via Boolean constraints
Authors: Harland James , Pym David
Published: January 2003

We consider the problem of searching for proofs in sequential presentations of logics with multiplicative (or intensional) connectives. Specifically, we start with the multiplicative fragment of linear logic and extend, on the one hand, to linear logic with its additives and, on the other, to the additives of the logic of bunched implications (
BI
). We give an algebraic method for calculating the distribution of the side-formulæ in multiplicative rules which allows the occurrence or non-occurrence of a formula on a branch of a proof to be determined once sufficient information is available. Each formula in the conclusion of such a rule is assigned a Boolean expression. As a search proceeds, a set of Boolean constraint equations is generated. We show that a solution to such a set of equations determines a proof corresponding to the given search. We explain a range of strategies, from the lazy to the eager, for solving sets of constraint equations. We indicate how to apply our methods systematically to large family of relevant systems.
Fixed-parameter complexity of semantics for logic programs
Authors: Lonc Zbigniew , Truszczyński Miroslaw
Published: January 2003

A decision problem is called
parameterized
if its input is a pair of strings. One of these strings is referred to as a
parameter
. The following problem is an example of a parameterized decision problem with
k
serving as a parameter: given a propositional logic program
P
and a nonnegative integer
k
, decide whether
P
has a stable model of size no more than
k
. Parameterized problems that are NP-complete often become solvable in polynomial time if the parameter is fixed. The problem to decide whether a program
P
has a stable model of size no more than
k
, where
k
is fixed and not a part of input, can be solved in time
O
(

mn
k

), where
m
is the size of
P
and
n
is the number of atoms in
P
. Thus, this problem is in the class P. However, algorithms with the running time given by a polynomial of order
k
are not satisfactory even for relatively small values of
k
.The key question then is whether significantly better algorithms (with the degree of the polynomial not dependent on
k
) exist. To tackle it, we use the framework of fixed-parameter complexity. We establish the fixed-parameter complexity for several parameterized decision problems involving models, supported models, and stable models of logic programs. We also establish the fixed-parameter complexity for variants of these problems resulting from restricting attention to definite Horn programs and to purely negative programs. Most of the problems considered in the paper have high fixed-parameter complexity. Thus, it is unlikely that fixing bounds on models (supported models, stable models) will lead to fast algorithms to decide the existence of such models.
A complete characterization of complete intersection-type preorders
Authors: Dezani-Ciancaglini M. , Honsell F. , Alessi F.
Published: January 2003

We characterize those
type preorders
which yield complete
intersection-type assignment systems
for λ-calculi, with respect to the three canonical set-theoretical semantics for intersection-types: the inference semantics, the simple semantics, and the F-semantics. These semantics arise by taking as interpretation of types subsets of applicative structures, as interpretation of the
preorder relation
, ≤, set-theoretic inclusion, as interpretation of the
intersection constructor
, ∩, set-theoretic intersection, and by taking the interpretation of the
arrow constructor
, → à
la
Scott, with respect to either
any possible functionality set
, or the
largest
one, or the
least
one.These results strengthen and generalize significantly all earlier results in the literature, to our knowledge, in at least three respects. First of all the inference semantics had not been considered before. Second, the characterizations are all given just in terms of simple closure conditions on the
preorder relation
, ≤, on the types, rather than on the typing judgments themselves. The task of checking the condition is made therefore considerably more tractable. Last, we do not restrict attention just to λ-models, but to arbitrary applicative structures which admit an interpretation function. Thus we allow also for the treatment of models of restricted λ-calculi. Nevertheless the characterizations we give can be tailored just to the case of λ-models.
Query evaluation via tree-decompositions
Authors: Flum Jörg , Frick Markus , Grohe Martin
Published: January 2003

A number of efficient methods for evaluating first-order and monadic-second order queries on finite relational structures are based on tree-decompositions of structures or queries. We systematically study these methods.In the first part of the article, we consider arbitrary formulas on tree-like structures. We generalize a theorem of Courcelle [1990] by showing that on structures of bounded tree-width a monadic second-order formula (with free first- and second-order variables) can be evaluated in time linear in the structure size plus the size of the output.In the second part, we study tree-like formulas on arbitrary structures. We generalize the notions of acyclicity and bounded tree-width from conjunctive queries to arbitrary first-order formulas in a straightforward way and analyze the complexity of evaluating formulas of these fragments. Moreover, we show that the acyclic and bounded tree-width fragments have the same expressive power as the well-known guarded fragment and the finite-variable fragments of first-order logic, respectively.
Cosmological lower bound on the circuit complexity of a small problem in logic
Authors: Stockmeyer Larry , Meyer Albert R.
Published: January 2003

An exponential lower bound on the circuit complexity of deciding the weak monadic second-order theory of one successor (WS1S) is proved. Circuits are built from binary operations, or 2-input gates, which compute arbitrary Boolean functions. In particular, to decide the truth of logical formulas of length at most 610 in this second-order language requires a circuit containing at least 10
125
gates. So even if each gate were the size of a proton, the circuit would not fit in the known universe. This result and its proof, due to both authors, originally appeared in 1974 in the Ph.D. thesis of the first author. In this article, the proof is given, the result is put in historical perspective, and the result is extended to probabilistic circuits.*
Correctness properties in a shared-memory parallel language
Authors: Caplain Gilbert
Published: January 2003

We study a property of
correctness
of programs written in a shared-memory parallel language. This property is a semantic equivalence between the parallel program and its
sequential version
, that we define. We consider some standard parallel imperative language. Within this language, this correctness property follows from the preservation of data dependences by the control flow and the synchronizations. Our result makes use of the semantics of the sequential version only. Hence, through our result, checking the correctness of some
parallel
program boils down to verifying properties of some
sequential
program.
Towards a theory of cache-efficient algorithms
Authors: Sen Sandeep , Chatterjee Siddhartha , Dumir Neeraj
Published: January 2003

We present a model that enables us to analyze the running time of an algorithm on a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our cache model, an extension of Aggarwal and Vitter's I/O model, enables us to establish useful relationships between the cache complexity and the I/O complexity of computations. As a corollary, we obtain cache-efficient algorithms in the single-level cache model for fundamental problems like sorting, FFT, and an important subclass of permutations. We also analyze the average-case cache behavior of mergesort, show that ignoring associativity concerns could lead to inferior performance, and present supporting experimental evidence.We further extend our model to multiple levels of cache with limited associativity and present optimal algorithms for matrix transpose and sorting. Our techniques may be used for systematic exploitation of the memory hierarchy starting from the algorithm design stage, and for dealing with the hitherto unresolved problem of limited associativity.
The verifying compiler
Authors: Hoare Tony
Published: January 2003

This contribution proposes a set of criteria that distinguish a grand challenge in science or engineering from the many other kinds of short-term or long-term research problems that engage the interest of scientists and engineers. As an example drawn from Computer Science, it revives an old challenge: the construction and application of a verifying compiler that guarantees correctness of a program before running it.
Why haven't more quantum algorithms been found?
Authors: Shor Peter W.
Published: January 2003

I examine the question of why so few classes of quantum algorithms have been discovered. I give two possible explanations for this, and some thoughts about what lines of research might lead to the discovery of more quantum algorithms.
Deterministic versus nondeterministic time and lower bound problems
Authors: Stearns Richard E.
Published: January 2003

Because many problems of general interest have natural nondeterministic algorithms and because computers act deterministically, it is important to understand the relationship between deterministic and nondeterministic time. Specifically, it is important to understand how quickly a deterministic computing device can determine the outcome of a nondeterministic calculation. So far, we have no general techniques that work any better than trying all step-by-step simulations, an exponential method.The most famous question concerning determinism versus nondeterminism is the P = NP question. However, this is a different question than "what is the relationship?" and it is possible that significant progress about the relationship can be achieved without answering the Pv = NP question. Thanks to efficient reductions from Turing machine simulation to SAT, the relationship question can be posed as a question about SAT. The problem of proving a nontrivial lower bound on the time required to solve SAT is just an instance of the larger problem of proving lower bounds for any natural problem. It is suggested that a study of generic problems might be a fruitful approach toward insights on such problems.
The decay and failures of web references
Authors: Spinellis Diomidis
Published: January 2003

Attempting to determine how quickly archival information becomes outdated.
Where now for development methodologies?
Authors: Avison David E. , Fitzgerald Guy
Published: January 2003

The current swirl of diversity could signal a return to the days of ad hoc systems development, lack of formalmethodology, and consequent increase in failure.
How to identify new high-payoff information systems for the organization
Authors: Peffers Ken , Gengler Charles E.
Published: January 2003

Viewing users as partners and their personal knowledge of the organization as a strategic asset helps CIOs justify project proposals with the greatest promise for achieving organizational goals.
The knowledge grid
Authors: Cannataro Mario , Talia Domenico
Published: January 2003

Designing, building, and implementing an architecture for distributed knowledge discovery.
Organic data memory using the DNA approach
Authors: Wong Pak Chung , Wong Kwong-kwok , Foote Harlan
Published: January 2003

For very long-term storage and retrieval, encode information as artificial DNA strands and insert into living hosts. As vectors, bacteria, even some bugs and weeds, might be good for hundreds of millions of years.
Hibernating during telecom winter
Authors: McGinity Meg
Published: January 2003

Somewhere along the way, hyperbole took over and exaggerations about telecom changing the world didn't live up to expectations.
On auditing audit trails
Authors: Mercuri Rebecca T.
Published: January 2003

It is incumbent upon us to examine our own auditing practices for their intrinsic vulnerabilities.
Making money selling content that others are giving away
Authors: Karp Alan H.
Published: January 2003

Attempts to protect existing business models will only serve to delay, or even prevent, the arrival of new content-delivery approaches.
COPLINK
Authors: Chen Hsinchun , Zeng Daniel , Atabakhsh Homa , Wyzga Wojciech , Schroeder Jenny
Published: January 2003

In response to the September 11 terrorist attacks, major government efforts to modernize federal law enforcement authorities' intelligence collection and processing capabilities have been initiated. At the state and local levels, crime and police report data is rapidly migrating from paper records to automated records management systems in recent years, making them increasingly accessible.
Geospatial decision support for drought risk management
Authors: Goddard Steve , Harms Sherri K. , Reichenbach Stephen E. , Tadesse Tsegaye , Waltman William J.
Published: January 2003

Drought affects virtually all regions of the world and results in significant economic, social, and environmental impacts. The Federal Emergency Management Agency estimates annual drought-related losses in the U.S. at $6--$8 billion, which is more than any other natural hazard. Congress enacted the Agricultural Risk Protection Act of 2000 to encourage the U.S. Department of Agriculture (USDA) Risk Management Agency (RMA) and farmers to be more proactive in managing drought risk.
Harvesting information to sustain forests
Authors: Delcambre Lois , Tolle Timothy , The Forest Project Team
Published: January 2003

We are building a Web-based system to provide easy access to documents for use by natural resource managers, scientists, and other interested parties in the Pacific Northwest. Initially, we are focusing on the Adaptive Management Area Program (www.fs.fed.us/r6/plan/adapt.htm) with the USDA Forest Service as the lead government partner in collaboration with natural resource management specialists from the USDI Bureau of Land Management, USDI Fish and Wildlife Service, as well as other agencies and groups.
Prospects for improving the regulatory process using e-rulemaking
Authors: Fountain Jane E.
Published: January 2003

U.S. citizens participate directly in rulemaking---a deliberate agenda-setting process designed to elicit, sort, and clarify fact and opinion from a wide variety of interested parties. The rulemaking process offers a directness and scope for public participation unavailable in other policy-making processes [1].
Geospatial IT for mobile field data collection
Authors: Nusser Sarah , Miller Leslie , Clarke Keith , Goodchild Michael
Published: January 2003

Federal statistical agencies generate critical data about the nation's population, economy, and natural resources. This data is gathered largely by mobile field data collection. Although geospatial information is an essential reference material in the field and serves as a base for recording spatially linked data, it is nearly always used in printed form due to limitations in mobile computing systems and tools for handling geospatial data. The ability to interact with digital geospatial data in the field offers significant enhancements for data quality and operational efficiencies. However, basic research is needed on extensible infrastructure designs for limited field computing environments and appropriate field tools for mobile data gatherers.
Supporting statistical electronic table usage by citizens
Authors: Hert Carol A. , Liddy Elizabeth D. , Shneiderman Ben , Marchionini Gary
Published: January 2003

Over 70 agencies at the federal level are charged with collecting data and producing and disseminating statistics. These statistics are used to inform government policy, shape health care initiatives, provide information on the state of the economy, and others. They also have significant impact on the lives of citizens who use the statistics, for example, to determine job opportunities, changes in social security benefits, and quality of life in particular areas. Our digital government project developed several specific technologies to support the location, manipulation, and understanding of a quintessential format for statistical information---the table.
FedStats
Authors: Dippo Cathryn
Published: January 2003

FedStats.gov is an award-winning portal to a distributed digital library of statistical information compiled by more than 70 federal agencies. The challenges in simply providing access are many---organizational, bureaucratic, technical, and usability to name just a few.
Table servers protect confidentiality in tabular data releases
Authors: Karr Alan F. , Dobra Adrian , Sanil Ashish P.
Published: January 2003

Federal statistical agencies must balance concern over confidentiality of data with their obligation to report information to the public. Advances in IT threaten privacy, but new technologies can also protect confidentiality while meeting user needs in innovative ways.
Supporting visual analysis of federal geospatial statistics
Authors: MacEachren Alan M. , Hardisty Frank , Dai Xiping , Pickle Linda
Published: January 2003

Federal government agencies generate, summarize, and disseminate a large and growing volume of statistical data that can be linked through common geospatial referencing. The potential of this data is often unrealized because agencies and their data users lack usable and useful data analysis tools that support multivariate geospatial data exploration and processing.
Use of the SAND spatial browser for digital government applications
Authors: Samet Hanan , Alborzi Houman , Brabec František , Esperança Claudio , Hjaltason Gísli R. , Morgan Frank , Tanin Egemen
Published: January 2003

Numerous federal agencies produce official statistics made accessible to ordinary citizens for searching and data retrieval. This is frequently done via the Internet through a Web browser interface. If this data is presented in textual format, it can often be searched and retrieved by such attributes as topic, responsible agency, keywords, or press release. However, if the data is of spatial nature, for example, in the form of a map, then using text-based queries is often too cumbersome for the intended audience. We describe the use of the SAND Spatial Browser to provide more power to users of these databases by enabling them to define and explore the specific spatial region of interest graphically. The SAND Spatial Browser allows users to form either purely spatial or mixed spatial/nonspatial queries intuitively, which can present information to users that might have been missed if only a textual interface was available.