bluuebunny/crossref_metadata_2025 huggingface dataset:
Alcohol Attenuates Load‐related Activation During a Working Memory Task: Relation to Level of Response to Alcohol
Authors: Paulus Martin P. , Tapert Susan F. , Pulido Carmen , Schuckit Marc A.
Published: July 2006

Background: A low level of response to alcohol is a major risk factor for the development of alcohol dependence, but neural correlates of this marker are unclear.

Method: Ten healthy volunteers were classified by median split on level of response to alcohol and underwent 2 sessions of functional magnetic resonance imaging following ingestion of a moderate dose of alcohol and a placebo. The blood oxygen level–dependent activation to an event‐related visual working memory test was examined.

Results: The subjects exhibited longer response latencies and more errors as a function of increasing working memory load and showed a load‐dependent increase in activation in dorsolateral prefrontal cortex, posterior parietal cortex, and visual cortex. Alcohol did not affect performance (errors or response latency), but attenuated the working memory load–dependent activation in the dorsolateral prefrontal cortex. During the placebo condition, individuals with a low level of response to alcohol showed greater activation in dorsolateral prefrontal cortex and posterior parietal cortex than those with a high level of response to alcohol. During the alcohol condition, groups showed similar attenuation of load‐dependent brain activation in these regions.

Conclusion:
Low‐level responders relative to high‐level responders exhibited an increased working memory load–dependent activation in dorsolateral prefrontal cortex and posterior parietal cortex when not exposed to alcohol. This increase in brain response was attenuated in low‐level responders after ingesting a moderate dose of alcohol.
Reducing Adverse Outcomes from Prenatal Alcohol Exposure: A Clinical Plan of Action
Authors: Louise Floyd R. , O'Connor Mary J. , Bertrand Jacquelyn , Sokol Robert
Published: July 2006

Fetal alcohol spectrum disorders (FASDs) are among the leading preventable causes of developmental disorders in the United States; however, recognition and prevention of these conditions cannot be achieved without informed and educated health providers. This commentary addresses the importance of recognition and prevention of FASDs through the use of well‐established standardized practices of diagnosis, screening, and brief alcohol reduction counseling. It is hoped that more knowledge on currently available procedures will encourage their use in the provision of routine health care to all women of childbearing age.
Simultaneous implant placement and bone regeneration around dental implants using tissue‐engineered bone with fibrin glue, mesenchymal stem cells and platelet‐rich plasma
Authors: Ito Kenji , Yamada Yoichi , Naiki Takahito , Ueda Minoru
Published: July 2006

Abstract: This study was undertaken to evaluate the use of tissue‐engineered bone as grafting material for alveolar augmentation with simultaneous implant placement. Twelve adult hybrid dogs were used in this study. One month after the extraction of teeth in the mandible region, bone defects on both sides of the mandible were induced using a trephine bar with a diameter of 10 mm. Dog mesenchymal stem cells (dMSCs) were obtained via iliac bone biopsy and cultured for 4 weeks before implantation. After installing the dental implants, the defects were simultaneously implanted with the following graft materials: (i) fibrin, (ii) dMSCs and fibrin (dMSCs/fibrin), (iii) dMSCs, platelet‐rich plasma (PRP) and fibrin (dMSCs/PRP/fibrin) and (iv) control (defect only). The implants were assessed by histological and histomorphometric analysis, 2, 4 and 8 weeks after implantation. The implants exhibited varying degrees of bone–implant contact (BIC). The BIC was 17%, 19% and 29% (control), 20%, 22% and 25% (fibrin), 22%, 32% and 42% (dMSCs/fibrin) and 25%, 49% and 53% (dMSCs/PRP/fibrin) after 2, 4 and 8 weeks, respectively. This study suggests that tissue‐engineered bone may be of sufficient quality for predictable enhancement of bone regeneration around dental implants when used simultaneous by with implant placement.
Diet of introduced largemouth bass in Korean rivers and potential interactions with native fishes
Authors: Jang M.‐H. , Joo G.‐J. , Lucas M. C.
Published: July 2006

Abstract – A dietary analysis of largemouth bass (Micropterus salmoides), an exotic, piscivorous species, was conducted in large South Korean river systems (>third order streams, 31 sites).Micropterus salmoideslarger than 100 mm exhibited intense piscivory on native Korean juvenile fishes, with levels of piscivory amongst the highest recorded globally, for native and introduced populations. Largemouth bass exhibited an ontogenetic shift in diet, showing a progressive increase in piscivory with size, typical of this species within its native range but unlike several studies on introduced largemouth bass in Europe and Africa. Sampling of fish communities at the same sites used for diet studies showed that native piscivores and the main food fish species of largemouth bass were significantly less abundant (P = 0.049 and 0.045, respectively) at sites where bass were present than at sites where no bass were recorded. Largemouth bass may pose a threat to the structure of fish assemblages in Korean river systems and further study of their population interactions and how to minimise their spread is needed.
Melatonin prevents H2O2‐induced activation of rat hepatic stellate cells
Authors: Gu Jing , Zhuang Li , Huang Guang‐Cun
Published: July 2006

Abstract:  Considerable evidence shows therapeutic effects of melatonin on liver injury and the involvement of hepatic stellate cells (HSCs) in vivo. In the present studies, we investigate the protective effect of melatonin on H2O2‐induced activation of HSCs in vitro. Compared with that in control HSCs, synthesis of collagen type I was increased in H2O2‐treated cells. Melatonin pretreatment significantly inhibited the above effects of H2O2 in HSCs. CCAAT/enhancer‐binding protein alpha (C/EBP‐α), which could partially reverse the phenotype of activated HSCs, augmented in HSCs pretreated with melatonin. Moreover, secretion of the most important fibrotic cytokine transforming growth factor beta 1 (TGF‐β1) diminished in melatonin‐pretreated HSCs. These results suggest that melatonin prevents H2O2‐induced activation of HSCs and that the mechanism involves, at least in part, differential regulation of TGF‐β1 and C/EBP‐α gene expression.
Microvessel density and vascular endothelial growth factor expression in sinus augmentation using Bio‐Oss®
Authors: Degidi M , Artese L , Rubini C , Perrotti V , Iezzi G , Piattelli A
Published: July 2006

Aim:  The aim of this study was to evaluate microvessel density (MVD) and vascular endothelial growth factor (VEGF) expression in sinus augmentation with Bio‐Oss®.

Methods:  Twenty patients participated in this study. The sinuses were filled with 100% Bio‐Oss®. Implants were inserted after 3 months in group A, and 6 months in group B. A trephine was used to harvest bone cores. As control, the pre‐existing subantral bone was used.

Results:  The mean MVD in control bone was 23.6 ± 1.8. In the sites augmented with Bio‐Oss®, at 3 months, the MVD was 23.3 ± 2.1, while in the sites retrieved at 6 months the MVD was 29.5 ± 2.4. The difference in MVD between the control bone and group A was not statistically significant. The difference between the control bone and group B was statistically significant (P < 0.05). The statistical analysis showed that the difference in MVD between group A and group B was statistically significant (P < 0.05).

Conclusions:  Bio‐Oss® seemed to induce an increase in MVD that reached a higher value after 6 months. The percentage of vessels positive to VEGF was higher in group A than in group B. Our data also showed a higher percentage of vessel and stromal cells positive to VEGF and higher MVD values in areas where there was newly formed bone compared with areas where maturation processes were occuring, and this fact could point to a close spatial relationship between angiogenesis and osteogenesis.
A “Messy” History and its Many “Messy” Texts: An Essay on Partition (India, 1947) and its Narratives
Authors: Kamra Sukeshi
Published: July 2006

The division of British India into India and Pakistan in August 1947 was accompanied by the dislocation of between twelve and sixteen million people and the violent deaths of around a million. Punjab and Bengal, the two provinces that were divided, were the most affected but so were other parts of the country. After all, mixed populations (Muslim, Hindu, Sikh, Christian, and so on) were more the norm than not in rural and urban India, making the very notion of two homelands, one with a Muslim majority and another with a Hindu majority, somewhat difficult to realize. Apparently the leadership expected what was euphemistically referred to as “an orderly exchange of population” in spite of the fact that the boundaries were officially announced on August 17, 1947, that is, after the actual transfer of power to the two successor states on August 14–15, 1947. Individuals, families, and communities that found themselves on the “wrong” side of the border were dispossessed of land and home, faced with the threat of bodily harm, spent months on the road and in refugee camps, and began the long process of resettlement. The place where the shock and disbelief first register, as do attempts to negotiate an impossible history of violence, is the literary text. This article attempts to introduce a literature that self‐identifies with this traumatic historical experience. Partition literature is best contextualized by developments in two academic, disciplinary fields: history and literary criticism. Disciplinary history has only recently acknowledged the need for a social history of Partition and literary criticism has only recently expanded to allow for ways of discussing a traumatic literature other than the limiting one of “literariness.” Thus the article attempts to interweave a discussion of Partition literature with a discussion of shifting critical approaches to it. By beginning with a look at Partition's erasure in disciplinary history, the article aims to encourage the readership to consider ways in which the historiographical has informed or shaped Partition literature and the history of its reception.
Why are there so many loop formulas?
Authors: Lifschitz Vladimir , Razborov Alexander
Published: July 2006

A theorem by Lin and Zhao shows how to turn any nondisjunctive logic program, understood in accordance with the answer set semantics, into an equivalent set of propositional formulas. The set of formulas generated by this process can be significantly larger than the original program. In this article we show (assuming
P
⊈
NC
1
/
poly
, a conjecture from the theory of computational complexity that is widely believed to be true) that this is inevitable: any equivalent translation from logic programs to propositional formulas involves a significant increase in size.
A characterization of first-order topological properties of planar spatial data
Authors: Benedikt Michael , Kuijpers Bart , Löding Christof , Bussche Jan Van den , Wilke Thomas
Published: July 2006

Planar spatial datasets can be modeled by closed semi-algebraic sets in the plane. We establish a characterization of the topological properties of such datasets expressible in the relational calculus with real polynomial constraints. The characterization is in the form of a query language that can only point that can only talk about points in the set and the “cones” around these points.
Inferring Internet denial-of-service activity
Authors: Moore David , Shannon Colleen , Brown Douglas J. , Voelker Geoffrey M. , Savage Stefan
Published: July 2006

In this article, we seek to address a simple question: “How prevalent are denial-of-service attacks in the Internet?” Our motivation is to quantitatively understand the nature of the current threat as well as to enable longer-term analyses of trends and recurring patterns of attacks. We present a new technique, called “backscatter analysis,” that provides a conservative estimate of
worldwide
denial-of-service activity. We use this approach on 22 traces (each covering a week or more) gathered over three years from 2001 through 2004. Across this corpus we quantitatively assess the number, duration, and focus of attacks, and qualitatively characterize their behavior. In total, we observed over 68,000 attacks directed at over 34,000 distinct victim IP addresses---ranging from well-known e-commerce companies such as Amazon and Hotmail to small foreign ISPs and dial-up connections. We believe our technique is the first to provide quantitative estimates of Internet-wide denial-of-service activity and that this article describes the most comprehensive public measurements of such activity to date.
On the performance of wide-area thin-client computing
Authors: Lai Albert M. , Nieh Jason
Published: July 2006

While many application service providers have proposed using thin-client computing to deliver computational services over the Internet, little work has been done to evaluate the effectiveness of thin-client computing in a wide-area network. To assess the potential of thin-client computing in the context of future commodity high-bandwidth Internet access, we have used a novel, noninvasive slow-motion benchmarking technique to evaluate the performance of several popular thin-client computing platforms in delivering computational services cross-country over Internet2. Our results show that using thin-client computing in a wide-area network environment can deliver acceptable performance over Internet2, even when client and server are located thousands of miles apart on opposite ends of the country. However, performance varies widely among thin-client platforms and not all platforms are suitable for this environment. While many thin-client systems are touted as being bandwidth efficient, we show that network latency is often the key factor in limiting wide-area thin-client performance. Furthermore, we show that the same techniques used to improve bandwidth efficiency often result in worse overall performance in wide-area networks. We characterize and analyze the different design choices in the various thin-client platforms and explain which of these choices should be selected for supporting wide-area computing services.
Reducing dynamic and leakage energy in VLIW architectures
Authors: Zhang W. , Tsai Y.-F. , Duarte D. , Vijaykrishnan N. , Kandemir M. , Irwin M. J.
Published: July 2006

The mobile computing device market has been growing rapidly. This brings the technologies that optimize system energy to the forefront. As circuits continue to scale in the future, it would be important to optimize both leakage and dynamic energy. Effective optimization of leakage and dynamic energy consumption requires a vertical integration of techniques spanning from circuit to software levels. Schedule slacks in codes executing in VLIW architectures present an opportunity for such an integration. In this paper, we present three compiler-directed techniques that take advantage of schedule slacks to optimize leakage and dynamic energy consumption. Integer ALU (IALU) components operating with multiple supply voltages are designed to provide different low-energy versions that possess different operational latencies. The goal of the first technique explored is to maximize the number of operations mapped to IALU components with the lowest energy consumption without extending the schedule length. We also consider a variant of this technique that saves more energy at the cost of some performance loss. The second technique uses two leakage-control mechanisms to reduce leakage energy consumption when no operations are scheduled in the component. Our evaluation of these two approaches, using fifteen benchmarks, shows that based on the number and duration of slacks, the availability of low-energy functional units and the relative magnitude of leakage and dynamic energy, either leakage or dynamic energy consumption, will provide more energy gains. Finally, we provide a unified energy-optimization strategy that integrates both dynamic and leakage energy-reduction schemes. The proposed techniques have been incorporated into a cycle accurate simulator using parameters extracted from circuit-level simulation. Our results show that the unified scheme generates better results than using either of dynamic and leakage energy-reduction techniques independently.
Software security is software reliability
Authors: Lindner Felix "FX"
Published: July 2006

Enlist hacker expertise, but stay with academic fault naming conventions, when defending against the risk of exploitation of vulnerabilities and intrusions.
Topological relationships between complex spatial objects
Authors: Schneider Markus , Behr Thomas
Published: July 2006

For a long time topological relationships between spatial objects have been a focus of research in a number of disciplines like artificial intelligence, cognitive science, linguistics, robotics, and spatial reasoning. Especially as predicates they support the design of suitable query languages for spatial data retrieval and analysis in spatial databases and geographical information systems (GIS). Unfortunately, they have so far only been defined for and applicable to simplified abstractions of spatial objects like single points, continuous lines, and simple regions. With the introduction of
complex spatial data types
an issue arises regarding the design, definition, and number of topological relationships operating on these complex types. This article closes this gap and first introduces definitions of general and versatile spatial data types for
complex points
,
complex lines
, and
complex regions
. Based on the well known 9-intersection model, it then determines the complete sets of mutually exclusive topological relationships for all type combinations. Completeness and mutual exclusion are shown by a proof technique called
proof-by-constraint-and-drawing
. Due to the resulting large numbers of predicates and the difficulty of handling them, the user is provided with the concepts of
topological cluster predicates
and
topological predicate groups
, which permit one to reduce the number of predicates to be dealt with in a user-defined and/or application-specific manner.
B-tree concurrency control and recovery in page-server database systems
Authors: Jaluta Ibrahim , Sippu Seppo , Soisalon-Soininen Eljas
Published: July 2006

We develop new algorithms for the management of transactions in a page-shipping client-server database system in which the physical database is organized as a sparse B-tree index. Our starvation-free fine-grained locking protocol combines adaptive callbacks with key-range locking and guarantees repeatable-read-level isolation (i.e., serializability) for transactions containing any number of record insertions, record deletions, and key-range scans. Partial and total rollbacks of client transactions are performed by the client. Each structure modification such as a page split or merge is defined as an atomic action that affects only two levels of the B-tree and is logged using a single redo-only log record, so that the modification never needs to be undone during transaction rollback or restart recovery. The steal-and-no-force buffering policy is applied by the server when flushing updated pages onto disk and by the clients when shipping updated data pages to the server, while pages involved in a structure modification are forced to the server when the modification is finished. The server performs the restart recovery from client and system failures using an ARIES/CSA-based recovery protocol. Our algorithms avoid accessing stale data but allow a data page to be updated by one client transaction and read by many other client transactions simultaneously, and updates may migrate from a data page to another in structure modifications caused by other transactions while the updating transaction is still active.
Consensus on transaction commit
Authors: Gray Jim , Lamport Leslie
Published: July 2006

The distributed transaction commit problem requires reaching agreement on whether a transaction is committed or aborted. The classic Two-Phase Commit protocol blocks if the coordinator fails. Fault-tolerant consensus algorithms also reach agreement, but do not block whenever any majority of the processes are working. The Paxos Commit algorithm runs a Paxos consensus algorithm on the commit/abort decision of each participant to obtain a transaction commit protocol that uses 2
F
+ 1 coordinators and makes progress if at least
F
+ 1 of them are working properly. Paxos Commit has the same stable-storage write delay, and can be implemented to have the same message delay in the fault-free case as Two-Phase Commit, but it uses more messages. The classic Two-Phase Commit algorithm is obtained as the special
F
= 0 case of the Paxos Commit algorithm.
Algorithm 853
Authors: Foster Leslie , Kommu Rajesh
Published: July 2006

Existing routines, such as xGELSY or xGELSD in LAPACK, for solving rank-deficient least squares problems require O(
mn
2
) operations to solve min ‖
b
−
Ax
‖ where
A
is an
m
by
n
matrix. We present a modification of the LAPACK routine xGELSY that requires O(
mnk
) operations where
k
is the effective numerical rank of the matrix
A
. For low rank matrices the modification is an order of magnitude faster than the LAPACK code.
Type inference for unique pattern matching
Authors: Vansummeren Stijn
Published: July 2006

Regular expression patterns provide a natural, declarative way to express constraints on semistructured data and to extract relevant information from it. Indeed, it is a core feature of the programming language Perl, surfaces in various UNIX tools such as sed and awk, and has recently been proposed in the context of the XML programming language XDuce. Since regular expressions can be ambiguous in general, different disambiguation policies have been proposed to get a unique matching strategy. We formally define the matching semantics under both (1) the POSIX, and (2) the first and longest match disambiguation strategies. We show that the generally accepted method of defining the longest match in terms of the first match and recursion does not conform to the natural notion of longest match. We continue by solving the type inference problem for both disambiguation strategies, which consists of calculating the set of all subparts of input values a subexpression can match under the given policy.
MultiJava
Authors: Clifton Curtis , Millstein Todd , Leavens Gary T. , Chambers Craig
Published: July 2006

MultiJava is a conservative extension of the Java programming language that adds symmetric multiple dispatch and open classes. Among other benefits, multiple dispatch provides a solution to the binary method problem. Open classes provide a solution to the extensibility problem of object-oriented programming languages, allowing the modular addition of both new types and new operations to an existing type hierarchy. This article illustrates and motivates the design of MultiJava and describes its modular static typechecking and modular compilation strategies. Although MultiJava extends Java, the key ideas of the language design are applicable to other object-oriented languages, such as C# and C++, and even, with some modifications, to functional languages such as ML.This article also discusses the variety of application domains in which MultiJava has been successfully used by others, including pervasive computing, graphical user interfaces, and compilers. MultiJava allows users to express desired programming idioms in a way that is declarative and supports static typechecking, in contrast to the tedious and type-unsafe workarounds required in Java. MultiJava also provides opportunities for new kinds of extensibility that are not easily available in Java.
Survey and benchmark of block ciphers for wireless sensor networks
Authors: Law Yee Wei , Doumen Jeroen , Hartel Pieter
Published: July 2006

Cryptographic algorithms play an important role in the security architecture of wireless sensor networks (WSNs). Choosing the most storage- and energy-efficient block cipher is essential, due to the facts that these networks are meant to operate without human intervention for a long period of time with little energy supply, and that available storage is scarce on these sensor nodes. However, to our knowledge, no systematic work has been done in this area so far. We construct an evaluation framework in which we first identify the candidates of block ciphers suitable for WSNs, based on existing literature and authoritative recommendations. For evaluating and assessing these candidates, we not only consider the security properties but also the storage- and energy-efficiency of the candidates. Finally, based on the evaluation results, we select the most suitable ciphers for WSNs, namely Skipjack, MISTY1, and Rijndael, depending on the combination of available memory and required security (energy efficiency being implicit). In terms of operation mode, we recommend Output Feedback Mode for pairwise links but Cipher Block Chaining for group communications.
Redundancy and coverage detection in sensor networks
Authors: Cărbunar Bogdan , Grama Ananth , Vitek Jan , Cărbunar Octavian
Published: July 2006

We study the problem of detecting and eliminating redundancy in a sensor network with a view to improving energy efficiency, while preserving the network's coverage. We also examine the impact of redundancy elimination on the related problem of coverage-boundary detection. We reduce both problems to the computation of Voronoi diagrams, prove and achieve lower bounds on the solution of these problems, and present efficient distributed algorithms for computing and maintaining solutions in cases of sensor failures or insertion of new sensors. We prove the correctness and termination properties of our distributed algorithms, and analytically characterize the time complexity and traffic generated by our algorithms. Using detailed simulations, we also quantify the impact of system parameters such as sensor density, transmission range, and failure rates on network traffic.
Dynamic indexing for multidimensional non-ordered discrete data spaces using a data-partitioning approach
Authors: Qian Gang , Zhu Qiang , Xue Qiang , Pramanik Sakti
Published: July 2006

Similarity searches in multidimensional Non-ordered Discrete Data Spaces (NDDS) are becoming increasingly important for application areas such as bioinformatics, biometrics, data mining and E-commerce. Efficient similarity searches require robust indexing techniques. Unfortunately, existing indexing methods developed for multidimensional (ordered) Continuous Data Spaces (CDS) such as the R-tree cannot be directly applied to an NDDS. This is because some essential geometric concepts/properties such as the minimum bounding region and the area of a region in a CDS are no longer valid in an NDDS. Other indexing methods based on metric spaces such as the M-tree and the Slim-trees are too general to effectively utilize the special characteristics of NDDSs, resulting in nonoptimized performance. In this article, we propose a new dynamic data-partitioning-based indexing technique, called the ND-tree, to support efficient similarity searches in an NDDS. The key idea is to extend the relevant geometric concepts as well as some indexing strategies used in CDSs to NDDSs. Efficient algorithms for ND-tree construction and techniques to solve relevant issues such as handling dimensions with different alphabets in an NDDS are presented. Our experimental results on synthetic data and real genome sequence data demonstrate that the ND-tree outperforms the linear scan, the M-tree and the Slim-trees for similarity searches in multidimensional NDDSs. A theoretical model is also developed to predict the performance of the ND-tree for random data.
Maintenance of
K
-nn and spatial join queries on continuously moving points
Authors: Iwerks Glenn S. , Samet Hanan , Smith Kenneth P.
Published: July 2006

Cars, aircraft, mobile cell phones, ships, tanks, and mobile robots all have the common property that they are moving objects. A kinematic representation can be used to describe the location of these objects as a function of time. For example, a moving point can be represented by the function
p
(
t
) =

x
→

0
+ (
t
-
t
0
)

v
→

, where

x
→

0
is the start location,
t
0
is the start time, and

v
→

is its velocity vector. Instead of storing the location of the object at a given time in a database, the coefficients of the function are stored. When an object's behavior changes enough so that the function describing its location is no longer accurate, the function coefficients for the object are updated. Because the location of each object is represented as a function of time, spatial query results can change even when no transactions update the database. We present efficient algorithms to maintain
k
-nearest neighbor, and spatial join queries in this domain as time advances and updates occur. We assume no previous knowledge of what the updates will be before they occur. We experimentally compare these new algorithms with more straight forward adaptations of previous work to support updates. Experiments are conducted using synthetic uniformly distributed data, and real aircraft flight data. The primary metric of comparison is the number of I/O disk accesses needed to maintain the query results and the supporting data structures.
Query optimization in distributed networks of autonomous database systems
Authors: Pentaris Fragkiskos , Ioannidis Yannis
Published: July 2006

Large-scale distributed environments, where each node is completely autonomous and offers services to its peers through external communication, pose significant challenges to query processing and optimization. Autonomy is the main source of the problem, as it results in lack of knowledge about any particular node with respect to the information it can produce and its characteristics, for example, cost of production or quality of produced results. In this article, inspired by e-commerce technology, we recognize queries as commodities and model query optimization as a trading negotiation process. Subquery answers and subquery operator execution jobs are traded between nodes until deals are struck with some nodes for all of them. Such trading may also occur recursively, in the sense that some nodes may play the role of intermediaries between other nodes (subcontracting). We identify the key parameters of the overall framework and suggest several potential alternatives for each one. In comparison to trading negotiations for e-commerce, query optimization faces unique new challenges that stem primarily from the fact that queries have a complex structure and can be broken into smaller parts. We address these challenges through a particular instantiation of our framework focusing primarily on the optimization algorithms run on “buying” and “selling” nodes, the evaluation metrics of the queries, and the negotiation strategy. Finally, we present the results of several experiments that demonstrate the performance characteristics of our approach compared to those of traditional query optimization.
Rewriting queries with arbitrary aggregation functions using views
Authors: Cohen Sara , Nutt Werner , Sagiv Yehoshua
Published: July 2006

The problem of rewriting aggregate queries using views is studied for conjunctive queries with arbitrary aggregation functions and built-in predicates. Two types of queries over views are introduced for rewriting aggregate queries:
pure candidates
and
aggregate candidates
. Pure candidates can be used to rewrite arbitrary aggregate queries. Aggregate candidates can be used to rewrite queries containing aggregate functions definable in terms of a commutative-semigroup operation. For both types of candidates (as well as for several relaxations of these candidates), the
unfolding property
holds. This allows characterizations for query equivalence to be used to determine whether a candidate is a rewriting of a query. The complexity of the rewriting-existence problem is also studied and upper and lower complexity bounds are given.
Domain-independent data cleaning via analysis of entity-relationship graph
Authors: Kalashnikov Dmitri V. , Mehrotra Sharad
Published: July 2006

In this article, we address the problem of
reference disambiguation
. Specifically, we consider a situation where entities in the database are referred to using descriptions (e.g., a set of instantiated attributes). The objective of reference disambiguation is to identify the unique entity to which each description corresponds. The key difference between the approach we propose (called RelDC) and the traditional techniques is that RelDC analyzes not only object features but also inter-object relationships to improve the disambiguation quality. Our extensive experiments over two real data sets and over synthetic datasets show that analysis of relationships significantly improves quality of the result.
Fitting B-spline curves to point clouds by curvature-based squared distance minimization
Authors: Wang Wenping , Pottmann Helmut , Liu Yang
Published: July 2006

Computing a curve to approximate data points is a problem encountered frequently in many applications in computer graphics, computer vision, CAD/CAM, and image processing. We present a novel and efficient method, calledsquared distance minimization(SDM), for computing a planar B-spline curve, closed or open, to approximate a target shape defined by apoint cloud, that is, a set of unorganized, possibly noisy data points. We show that SDM significantly outperforms other optimization methods used currently in common practice of curve fitting. In SDM, a B-spline curve starts from some properly specified initial shape and converges towards the target shape through iterative quadratic minimization of the fitting error. Our contribution is the introduction of a new fitting error term, called thesquared distance (SD) error term, defined by a curvature-based quadratic approximant of squared distances from data points to a fitting curve. The SD error term faithfully measures the geometric distance between a fitting curve and a target shape, thus leading to faster and more stable convergence than the point distance (PD) error term, which is commonly used in computer graphics and CAGD, and the tangent distance (TD) error term, which is often adopted in the computer vision community. To provide a theoretical explanation of the superior performance of SDM, we formulate the B-spline curve fitting problem as a nonlinear least squares problem and conclude that SDM is a quasi-Newton method which employs a curvature-based positive definite approximant to the true Hessian of the objective function. Furthermore, we show that the method based on the TD error term is a Gauss-Newton iteration, which is unstable for target shapes with high curvature variations, whereas optimization based on the PD error term is the alternating method that is known to have linear convergence.
Animating Chinese paintings through stroke-based decomposition
Authors: Xu Songhua , Xu Yingqing , Kang Sing Bing , Salesin David H. , Pan Yunhe , Shum Heung-Yeung
Published: July 2006

This article proposes a technique to animate a Chinese style painting given its image. We first extract descriptions of the brush strokes that hypothetically produced it. The key to the extraction process is the use of a brush stroke library, which is obtained by digitizing single brush strokes drawn by an experienced artist. The steps in our extraction technique are first to segment the input image, then to find the best set of brush strokes that fit the regions, and, finally, to refine these strokes to account for local appearance. We model a single brush stroke using its skeleton and contour, and we characterize texture variation within each stroke by sampling perpendicularly along its skeleton. Once these brush descriptions have been obtained, the painting can be animated at the brush stroke level. In this article, we focus on Chinese paintings with relatively sparse strokes. The animation is produced using a graphical application we developed. We present several animations of real paintings using our technique.
Trust beyond security
Authors: Hoffman Lance J. , Lawson-Jenkins Kim , Blum Jeremy
Published: July 2006

Developing an improved trust model and related metrics for distributed computer-based systems that will be useful immediately and resilient to changing technology.
Introduction
Authors: Spohrer Jim , Riecken Doug
Published: July 2006

This special section on services science is intended to broaden and challenge traditional thinking about services and service innovation. To the majority of computer scientists, whether in academia or industry, the term "services" is associated with Web services and service-oriented architectures. However, there is a broader story to be told of the remarkable growth of the service sector, which has come to dominate economic activity in most advanced economies over the last 50 years.Globalization, increasing automation, the growth of the Internet, and the dynamic componentization of business are driving the reconfiguration of service value networks at a scale and pace never before seen in history. The opportunity to innovate in services, to realize business and societal value from knowledge about service, to research, develop, and deliver new information services and business services, has never been greater. The challenges are both the multidisciplinary nature of service innovation, which combines business, technology, social-organizational, and demand innovation as well as the lack of formal representations of service systems.
A research manifesto for services science
Authors: Chesbrough Henry , Spohrer Jim
Published: July 2006

The services sector has grown over the last 50 years to dominate economic activity in most advanced industrial economies, yet scientific understanding of modern services is rudimentary. Here, we argue for a services science discipline to integrate across academic silos and advance service innovation more rapidly.
Service systems, service scientists, SSME, and innovation
Authors: Maglio Paul P. , Srinivasan Savitha , Kreulen Jeffrey T. , Spohrer Jim
Published: July 2006

Computer scientists work with formal models of algorithms and computation, and someday service scientists may work with formal models of service systems. The four examples here document some of the early efforts to establish a new academic discipline and new profession.
Accumulating Householder transformations, revisited
Authors: Joffrain Thierry , Low Tze Meng , Quintana-Ortí Enrique S. , Geijn Robert van de , Zee Field G. Van
Published: July 2006

A theorem related to the accumulation of Householder transformations into a single orthogonal transformation known as the compact WY transform is presented. It provides a simple characterization of the computation of this transformation and suggests an alternative algorithm for computing it. It also suggests an alternative transformation, the UT transform, with the same utility as the compact WY Transform which requires less computation and has similar stability properties. That alternative transformation was first published over a decade ago but has gone unnoticed by the community.
Optimizing FIAT with level 3 BLAS
Authors: Kirby Robert C.
Published: July 2006

Our previous work on FIAT (Finite Element Automatic Tabulator) developed a “computational representation theory ” that allowed us to construct arbitrary order instances of a wide range of finite elements, many of which are infrequently used owing to their associated code complexity. In our present work, we further hone this theory by rephrasing most of the internal operations as linear transformations over finite-dimensional Banach spaces. This additional insight has led to increased code granularity and allowed the use of level 3 BLAS operations. This is both a conceptual and a practical development; as the run-time performance of FIAT has been improved multiple orders of magnitude.
Sequential reservoir sampling with a nonuniform distribution
Authors: Kolonko M. , Wäsch D.
Published: July 2006

We present a simple algorithm that allows sampling from a stream of data items without knowing the number of items in advance and without having to store all items in main memory. The sampling distribution may be general, that is, the probability of selecting a data item
i
may depend on the individual item. The main advantage of the algorithms is that they have to pass through the data items only once to produce a sample of arbitrary size
n
.We give different variants of the algorithm for sampling with and without replacement and analyze their complexity. We generalize earlier results of Knuth on reservoir sampling with a uniform sampling distribution. The general distribution considered here allows us to sample an item with a probability equal to the relative weight (or fitness) of the data item within the whole set of items. Applications include heuristic optimization procedures such as genetic algorithms where solutions are sampled from a population with probability proportional to their fitness.
Perceived quality of compressed stereoscopic images
Authors: Seuntiens Pieter , Meesters Lydia , Ijsselsteijn Wijnand
Published: July 2006

JPEG compression of the left and right components of a stereo image pair is a way to save valuable bandwidth when transmitting stereoscopic images. This paper presents results on the effects of camera-base distance (B) and JPEG coding on overall image quality, perceived depth, perceived sharpness, and perceived eye strain. In the experiment, two stereoscopic still scenes were used, varying in depth (three different camera-base distances: 0, 8, and 12 cm) and compression ratio (4 levels: original, 1:30, 1:40, and 1:60). All levels of compression were applied to both the left and right stereo image, resulting in a 4 × 4 matrix of all possible symmetric and asymmetric coding combinations. The observers were asked to assess image quality, sharpness, depth, and eye strain. Results showed that an increase in JPEG coding had a negative effect on image quality, sharpness, and eye strain, but had no effect on perceived depth. An increase in camera-base distance increased perceived depth and reported eye strain, but had no effect on perceived sharpness. Results on asymmetric and symmetric coding showed that the relationship between perceived image quality and average bit rate is not straightforward. In some cases, image quality ratings of a symmetric coded pair can be higher than for an asymmetric coded pair, even if the averaged bit rate for the symmetric pair is lower, than for the asymmetric pair. Furthermore, sharpness and eye strain correlated highly and medium, respectively, with perceived image quality.
CDM
Authors: Sutner Klaus
Published: July 2006

CDM, for computational discrete mathematics, is a course that attempts to teach a number of topics in discrete mathematics to computer science majors. The course abandons the classical definition-theorem-proof model, and instead relies heavily on computation as a source of motivation and also for experimentation and illustration. The emphasis on computational issues is particularly attractive to computer science majors and increases their involvement and participation.
Hybrid images
Authors: Oliva Aude , Torralba Antonio , Schyns Philippe G.
Published: July 2006

We present
hybrid images
, a technique that produces static images with two interpretations, which change as a function of viewing distance. Hybrid images are based on the multiscale processing of images by the human visual system and are motivated by masking studies in visual perception. These images can be used to create compelling displays in which the image appears to change as the viewing distance changes. We show that by taking into account perceptual grouping mechanisms it is possible to build compelling hybrid images with stable percepts at each distance. We show examples in which hybrid images are used to create textures that become visible only when seen up-close, to generate facial expressions whose interpretation changes with viewing distance, and to visualize changes over time within a single picture.
Partial and approximate symmetry detection for 3D geometry
Authors: Mitra Niloy J. , Guibas Leonidas J. , Pauly Mark
Published: July 2006

"Symmetry is a complexity-reducing concept [...]; seek it every-where." - Alan J. PerlisMany natural and man-made objects exhibit significant symmetries or contain repeated substructures. This paper presents a new algorithm that processes geometric models and efficiently discovers and extracts a compact representation of their Euclidean symmetries. These symmetries can be partial, approximate, or both. The method is based on matching simple local shape signatures in pairs and using these matches to accumulate evidence for symmetries in an appropriate transformation space. A clustering stage extracts potential significant symmetries of the object, followed by a verification step. Based on a statistical sampling analysis, we provide theoretical guarantees on the success rate of our algorithm. The extracted symmetry graph representation captures important high-level information about the structure of a geometric model which in turn enables a large set of further processing operations, including shape compression, segmentation, consistent editing, symmetrization, indexing for retrieval, etc.
Reassembling fractured objects by geometric matching
Authors: Huang Qi-Xing , Flöry Simon , Gelfand Natasha , Hofer Michael , Pottmann Helmut
Published: July 2006

We present a system for automatic reassembly of broken 3D solids. Given as input 3D digital models of the broken fragments, we analyze the geometry of the fracture surfaces to find a globally consistent reconstruction of the original object. Our reconstruction pipeline consists of a graph-cuts based segmentation algorithm for identifying potential fracture surfaces, feature-based robust global registration for pairwise matching of fragments, and simultaneous constrained local registration of multiple fragments. We develop several new techniques in the area of geometry processing, including the novel integral invariants for computing multi-scale surface characteristics, registration based on forward search techniques and surface consistency, and a non-penetrating iterated closest point algorithm. We illustrate the performance of our algorithms on a number of real-world examples.
Perfect spatial hashing
Authors: Lefebvre Sylvain , Hoppe Hugues
Published: July 2006

We explore using hashing to pack sparse data into a compact table while retaining efficient random access. Specifically, we design a perfect multidimensional hash function -- one that is precomputed on static data to have no hash collisions. Because our hash function makes a single reference to a small offset table, queries always involve exactly two memory accesses and are thus ideally suited for parallel SIMD evaluation on graphics hardware. Whereas prior hashing work strives for pseudorandom mappings, we instead design the hash function to preserve spatial coherence and thereby improve runtime locality of reference. We demonstrate numerous graphics applications including vector images, texture sprites, alpha channel compression, 3D-parameterized textures, 3D painting, simulation, and collision detection.