bluuebunny/crossref_metadata_2025 huggingface dataset:
THE SHELL MODEL AND THE IMPULSE APPROXIMATIONS APPROACH TO THE RESPONSE FUNCTION OF 4He, 16O AND 40Ca NUCLEI
Authors: MODARRES M. , YOUNESIZADEH Y.
Published: July 2011

The ambiguities proposed by Benhar et al., about the the different implementation of the impulse approximation for calculating the response function of many-fermion systems, are investigated theoretically in the frame work of simple harmonic oscillator shell model for the double closed shell nuclei, e.g. 4 He , 16 O and 40 Ca nuclei. For each nucleus as a finite system, we evaluate the response function by using its definition in terms of the one-body spectral function and the one-body momentum distribution. It is demonstrated analytically, that there exists a sizable shift between the two schemes for each nucleus, which increases as we switch to the heavier nuclei. So one can conclude that for the nuclei with atomic number less than 4, such as 2 H , 3 H or 3 He , it is good approximation to ignore this discrepancy. This conclusion is important for theoretical explanation of the ongoing deep inelastic scattering (DIS) experiments of 3 H or 3 H in the Jefferson Laboratory. However present calculation confirms the work of Modarres and Younesizadeh (2010), in which they have shown that, the above shift can be removed by imposing the impulse approximation in the same footing in the many-fermion wave-function.
ROBUST 3-D OBJECT DETECTION AND FEATURE EXTRACTION FOR MULTI-ROBOT COOPERATION
Authors: LIYANAGE ARUNASIRI K. , DE SILVA CLARENCE W.
Published: July 2011

This paper develops a computer vision system for multi-robot cooperation in rescue operations. The work is focused on providing robust and fast vision capabilities to the robots to meet the expected level of performance. Enhanced versions of existing techniques and new techniques are utilized to develop an adaptive vision system architecture for use in an unstructured environment of multi-robot activity in an emergency scenario. Different types of object detection methods are selected in real time in the developed system according to the requirements of a robot. To validate the developed system for use in a multi-robot application, rigorous experiments are conducted in a typical unstructured environment. Features such as invariance of scale, rotation, illumination, and occlusion are tested with different types of objects, for various methods. Generally, good results are obtained.
BINARY TREE BASED CLASSIFICATION METHOD FOR THE MATERIAL LAYER AND MULTILINK CONVERSION MODEL OF SIGNAL PROPAGATION PROCESS OF INFORMATION ACQUISITION
Authors: SONG JIFENG , GE YUNJIAN
Published: July 2011

This research proposed a binary tree based classification method, which classifies sensory mechanisms according to material movements. This classification is a beneficial attempt that tries to explain the working mechanisms of sensors from a global view for the material layer of the discipline of information acquisition science and technology. Almost all types of mechanisms have been expressed with the Boolean symbol. The binary expression method presented in the paper also describes the deference of sensors' performances, including accuracy and dynamic performance. One actual application was analyzed to verify the reliability of the relation concluded from the binary classification presented in this paper. The results showed that this method could be used to forecast the performances of new sensor to a certain extent, especially in the inertial sensor field. A multilink conversion conception of sensing mechanisms is put forward to characterize the error propagation phenomenon. Corresponding mathematical expressions have been set up, which indicates a way to decrease total error by reducing signal conversion links. This deduction is supported by the binary tree based classification method.
POWER DISTURBANCES PATTERN RECOGNITION USING SUPPORT VECTOR MACHINE
Authors: MANIMALA K. , SELVI K. , AHILA R.
Published: July 2011

Recently, many signal processing techniques, such as fast Fourier transform, short-time Fourier transform, wavelet transform (WT), and wavelet packet transform (WPT), have been applied to detect, identify, and classify power quality (PQ) disturbances. For research on PQ analysis, it is critical to apply the appropriate signal processing techniques and classifier to solve PQ problems. The aim of this paper is to develop a classification method based on the combination of Hilbert transform (HT) and support vector machine (SVM) for the assessment of power quality events. Recent data mining literature has shown that support vector machine methods generally outperform traditional statistical and neural methods in classification problems involving power disturbance signals. The features obtained from the Hilbert transform are distinct, understandable and immune to noise. Analysis is presented to verify that the merits of HT and SVM combination make it adequate for PQ analysis when compared with the existing techniques in the literature.
REGION BASED PATCH PROPAGATION AND PATCH INPAINTING FOR IMAGE COMPLETION
Authors: JEMI FLORINABEL D. , EBENEZER JULIET S. , SADASIVAM V.
Published: July 2011

Film and photography archives nowadays go through an accelerated process of degradation. Since the preservation of cultural heritage plays an important role in our society, photograph/film restoration has drawn a lot of attention recently. In this paper, an extent of exemplar based inpainting at determining patch priority and patch matching is proposed. Patch priority is defined by two terms: the number of homogeneous regions within the patch (heterogeneous term) obtained by image segmentation and the variance of the pixels within each homogeneous region. The first term prioritizes the heterogeneous patches and the second term defines the inconsistency within each homogeneous region of the heterogeneous patch to discriminate patches having similar heterogeneous term. Patch inpainting is done in two stages. First, the missing pixels of the patch under consideration are interpolated and then a weighted patch matching criterion is applied for finding the candidate patch. Experimental results on damaged digitized photographs and natural images are presented, which demonstrate the effectiveness of the image-completion framework for tasks such as scratch/text, object removal and image inpainting.
DYNAMIC MODELING AND EVALUATION OF A ROBOTIC EXOSKELETON FOR UPPER-LIMB REHABILITATION
Authors: RAHMAN MOHAMMAD HABIBUR , KITTEL-OUIMET THIERRY , SAAD MAAROUF , KENNÉ JEAN-PIERRE , ARCHAMBAULT PHILIPPE S.
Published: July 2011

Proper functioning of the shoulder, elbow, and wrist movements play a vital role in the performance of essential daily activities. To assist physically disabled people with impaired upper-limb function, we have been developing an exoskeleton robot (ExoRob) to rehabilitate and to ease upper limb motion. The proposed ExoRob will be comprised of seven degrees of freedom (DOFs) to enable natural movements of the human upper-limb. This paper focuses on the kinematic and dynamic modeling of the proposed ExoRob that corresponds to human upper-limbs. For this purpose, a nonlinear computed torque control technique was employed. In simulations, trajectory tracking corresponding to typical rehabilitation exercises were carried out to evaluate the performances of the developed model and controller. For the experimental part, only 3DOFs (elbow, wrist flexion/extension, wrist abduction/adduction) were considered. Simulated and experimental results show that the controller was able to maneuver the proposed ExoRob efficiently in order to track the desired trajectories, which in this case consisted in passive arm movements. Such movements are widely used in therapy and were performed efficiently with the developed ExoRob and the controller.
Click chemistry: the emerging role of the azide-alkyne Huisgen dipolar addition in the preparation of substituted tetrapyrrolic derivatives
Authors: Dumoulin Fabienne , Ahsen Vefa
Published: July 2011

The review aims at being an exhaustive summary of the use of Huisgen azide-alkyne dipolar addition in the synthesis of tetrapyrrolic compounds, mainly porphyrins, phthalocyanines, chlorins and bacteriochlorins.
INVESTIGATION OF HIGH-COERCIVITY FePt-C NANOGRANULAR FILMS FOR PERPENDICULAR MAGNETIC RECORDING (PMR) MEDIA
Authors: PENG JIEGANG , XUE S. , YAN Z. , WU X. , ZHAN L.
Published: July 2011

In this work, we studied FePt-C nanogranular films for ultrahigh-density perpendicular recording media towards 1 Tbits/in2 because they have high magnetocrystalline anisotropy at its L10-phase. We deposit Fe 52 Pt 48- C 50% (7.2 nm) films on oxidized silicon substrates at 400°C and various Ar pressures. Results show that at the Ar pressure of 0.50 Pa, the FePt-C granular film has the best granular structure and MH loop shape with a perpendicular coercivity of 20 kOe. The average grain size of the optimized film is 6.4 ± 1.5 nm. We studied the thermal stability of the optimized film and obtained the energy barrier Eb of 340kBT at room temperature, meaning excellent thermal stability as magnetic recording media.
Request Bridging and Interleaving
Authors: Shin Dong In , Yu Young Jin , Kim Hyeong S. , Eom Hyeonsang , Yeom Heon Young
Published: July 2011

Write-through caching in modern disk drives enables the protection of data in the event of power failures as well as from certain disk errors when the write-back cache does not. Host system can achieve these benefits at the price of significant performance degradation, especially for small disk writes. We present new block-level techniques to address the performance problem of write-through caching disks. Our techniques are strongly motivated by some interesting results when the disk-level caching is turned off. By extending the conventional request merging, request bridging increases the request size and amortizes the inherent delays in the disk drive across more bytes of data. Like sector interleaving, request interleaving rearranges requests to prevent the disk head from missing the target sector position in close proximity, and thus reduces disk latency. We have evaluated our block-level approach using a variety of I/O workloads and shown that it increases disk I/O throughput by up to about 50%. For some real-world workloads, the disk performance is comparable or even superior to that of using the write-back disk cache. In practice, our simple yet effective solutions achieve better tradeoffs between data reliability and disk performance when applied to write-through caching disks.
PRESIDIO
Authors: You Lawrence L. , Pollack Kristal T. , Long Darrell D. E. , Gopinath K.
Published: July 2011

The ever-increasing volume of archival data that needs to be reliably retained for long periods of time and the decreasing costs of disk storage, memory, and processing have motivated the design of low-cost, high-efficiency disk-based storage systems. However,
managed
disk storage is still expensive. To further lower the cost, redundancy can be eliminated with the use of interfile and intrafile data compression. However, it is not clear what the optimal strategy for compressing data is, given the diverse collections of data.

To create a scalable archival storage system that efficiently stores diverse data, we present PRESIDIO, a framework that selects from different space-reduction efficent storage methods (ESMs) to detect similarity and reduce or eliminate redundancy when storing objects. In addition, the framework uses a virtualized content addressable store (VCAS) that hides from the user the complexity of knowing which space-efficient techniques are used, including chunk-based deduplication or delta compression. Storing and retrieving objects are polymorphic operations independent of their content-based address. A new technique, harmonic super-fingerprinting, is also used for obtaining successively more accurate (but also more costly) measures of similarity to identify the existing objects in a very large data set that are most similar to an incoming new object.

The PRESIDIO design, when reported earlier, had comprehensively introduced for the first time the notion of deduplication, which is now being offered as a service in storage systems by major vendors. As an aid to the design of such systems, we evaluate and present various parameters that affect the efficiency of a storage system using empirical data.
Qualitative concurrent parity games
Authors: Chatterjee Krishnendu , Alfaro Luca De , Henzinger Thomas A.
Published: July 2011

We consider two-player games played on a finite state space for an infinite number of rounds. The games are
concurrent
: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine the successor state. We consider ω-regular winning conditions specified as
parity
objectives. Both players are allowed to use randomization when choosing their moves. We study the computation of the
limit-winning
set of states, consisting of the states where the sup-inf value of the game for player 1 is 1: in other words, a state is
limit-winning
if player 1 can ensure a probability of winning arbitrarily close to 1. We show that the limit-winning set can be computed in
O
(
n

2
d

+2) time, where
n
is the size of the game structure and 2
d
is the number of priorities (or colors). The membership problem of whether a state belongs to the limit-winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of
turn-based
parity games, where in each state only one of the two players has a choice of moves, our algorithms are considerably more involved than those for turn-based games. This is because concurrent games do not satisfy two of the most fundamental properties of turn-based parity games. First, in concurrent games limit-winning strategies require randomization; and second, they require infinite memory.
From interests to values
Authors: DiSalvo Betsy , Bruckman Amy
Published: July 2011

Computer science is not that difficult but wanting to learn it is.
The pain of implementing LINQ providers
Authors: Eini Oren
Published: July 2011

It's no easy task for NoSQL.
The robustness principle reconsidered
Authors: Allman Eric
Published: July 2011

Seeking a middle ground.
Cognitive computing
Authors: Modha Dharmendra S. , Ananthanarayanan Rajagopal , Esser Steven K. , Ndirango Anthony , Sherbondy Anthony J. , Singh Raghavendra
Published: July 2011

Unite neuroscience, supercomputing, and nanotechnology to discover, demonstrate, and deliver the brain's core algorithms.
Reputation systems for open collaboration
Authors: De Alfaro Luca , Kulshreshtha Ashutosh , Pye Ian , Adler B. Thomas
Published: July 2011

Algorithmic-based user incentives ensure the trustworthiness of evaluations of Wikipedia entries and Google Maps business information.
Gender and computing conference papers
Authors: Cohoon J. McGrath , Nigai Sergey , Kaye Joseph "Jofish"
Published: July 2011

Women increasingly publish in ACM conference proceedings and are notably productive authors.
Skinput
Authors: Harrison Chris , Tan Desney , Morris Dan
Published: July 2011

Skinput
is a technology that appropriates the skin as an input surface by analyzing mechanical vibrations that propagate through the body. Specifically, we resolve the location of finger taps on the arm and hand using a novel sensor array, worn as an armband. This approach provides an on-body finger input system that is always available, naturally portable, and minimally invasive. When coupled with a pico-projector, a fully interactive graphical interface can be rendered directly on the body. To view video of Skinput, visit http://cacm.acm.org.
Puzzled: Uncommon divisors
Authors: Winkler Peter
Published: July 2011

Welcome to three new puzzles. Solutions to the first two will be published next month; the third is (as yet) unsolved. In fact, this time it's a famously unsolved problem.
How well can primal-dual and local-ratio algorithms perform?
Authors: Borodin Allan , Cashman David , Magen Avner
Published: July 2011

We define an algorithmic paradigm, the stack model, that captures many primal-dual and local-ratio algorithms for approximating covering and packing problems. The stack model is defined syntactically and without any complexity limitations and hence our approximation bounds are independent of the
P
versus
NP
question. Using the stack model, we bound the performance of a broad class of primal-dual and local-ratio algorithms and supply a (log
n
+1)/2 inapproximability result for set cover, a 4/3 inapproximability for min Steiner tree, and a 0.913 inapproximability for interval scheduling on two machines.
S-T connectivity on digraphs with a known stationary distribution
Authors: Chung Kai-Min , Reingold Omer , Vadhan Salil
Published: July 2011

We present a deterministic logspace algorithm for solving S-T Connectivity on directed graphs if: (i) we are given a stationary distribution of the random walk on the graph in which both of the input vertices
s
and
t
have nonnegligible probability mass and (ii) the random walk which starts at the source vertex
s
has polynomial mixing time. This result generalizes the recent deterministic logspace algorithm for S-T Connectivity on undirected graphs [Reingold, 2008]. It identifies knowledge of the stationary distribution as the gap between the S-T Connectivity problems we know how to solve in logspace (
L
) and those that capture all of randomized logspace (
RL
).
Routing (un-) splittable flow in games with player-specific affine latency functions
Authors: Gairing Martin , Monien Burkhard , Tiemann Karsten
Published: July 2011

In this work we study weighted network congestion games with player-specific latency functions where selfish players wish to route their traffic through a shared network. We consider both the case of splittable and unsplittable traffic. Our main findings are as follows. For routing games on parallel links with linear latency functions, we introduce two new potential functions for unsplittable and for splittable traffic, respectively. We use these functions to derive results on the convergence to pure Nash equilibria and the computation of equilibria. For several generalizations of these routing games, we show that such potential functions do not exist. We prove tight upper and lower bounds on the price of anarchy for games with polynomial latency functions. All our results on the price of anarchy translate to general congestion games.
Minimizing flow time in the wireless gathering problem
Authors: Bonifaci Vincenzo , Korteweg Peter , Marchetti-Spaccamela Alberto , Stougie Leen
Published: July 2011

We address the problem of efficient data gathering in a wireless network through multihop communication. We focus on two objectives related to flow times, that is, the times spent by data packets in the system: minimization of the maximum flow time and minimization of the average flow time of the packets. For both problems we prove that, unless
P
=
NP
, no polynomial-time algorithm can approximate the optimal solution within a factor less than Ω(
m
1
−ε) for any 0<ε<1, where
m
is the number of packets. We then assess the performance of two natural algorithms by proving that their cost remains within the optimal cost of the respective problem if we allow the algorithms to transmit data at a speed 5 times higher than that of the optimal solutions to which we compare them.
Randomized rendezvous with limited memory
Authors: Kranakis Evangelos , Krizanc Danny , Morin Pat
Published: July 2011

We present a trade-off between the expected time for two identical agents to rendezvous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show there exists a 2
t
state agent which can achieve rendezvous on an
n
-node ring in expected time
O
(
n
2
/2

t

+ 2

t

) and that any
t
/2 state agent requires expected time Ω(
n
2
/2

t

). As a corollary we observe that Θ(log log
n
) bits of memory are necessary and sufficient to achieve rendezvous in linear time.
Max-coloring and online coloring with bandwidths on interval graphs
Authors: Pemmaraju Sriram V. , Raman Rajiv , Varadarajan Kasturi
Published: July 2011

Given a graph
G
= (
V, E
) and positive integral vertex weights
w
:
V
→
N
, the
max-coloring problem
seeks to find a proper vertex coloring of
G
whose color classes
C
1
, C
2
, …, C

k

, minimize ∑

i

=1

k

max

v

∈
C

i

w
(
v
). This problem, restricted to interval graphs, arises whenever there is a need to design dedicated memory managers that provide better performance than the general-purpose memory management of the operating system.

Though this problem seems similar to the dynamic storage allocation problem, there are fundamental differences. We make a connection between max-coloring and online graph coloring and use this to devise a simple 2-approximation algorithm for max-coloring on interval graphs. We also show that a simple first-fit strategy, that is a natural choice for this problem, yields an 8-approximation algorithm. We show this result by proving that the first-fit algorithm for online coloring an interval graph
G
uses no more than 8 ċ χ(
G
) colors, significantly improving the bound of 26 ċ χ(
G
) by Kierstead and Qin [1995]. We also show that the max-coloring problem is NP-hard.

The problem of online coloring of intervals with bandwidths is a simultaneous generalization of online interval coloring and online bin packing. The input is a set
I
of intervals, each interval
i
∈
I
having an associated
bandwidth
b
(
i
) ∈ (0, 1]. We seek an online algorithm that produces a coloring of the intervals such that for any color
c
and any real
r
, the sum of the bandwidths of intervals containing
r
and colored
c
is at most 1. Motivated by resource allocation problems, Adamy and Erlebach [2003] consider this problem and present an algorithm that uses at most 195 times the number of colors used by an optimal offline algorithm. Using the new analysis of first-fit coloring of interval graphs, we show that the Adamy-Erlebach algorithm is 35-competitive. Finally, we generalize the Adamy-Erlebach algorithm to a class of algorithms and show that a different instance from this class is 30-competitive.
To fill or not to fill
Authors: Khuller Samir , Malekian Azarakhsh , Mestre Julián
Published: July 2011

In this article we study several routing problems that generalize shortest paths and the traveling salesman problem. We consider a more general model that incorporates the actual cost in terms of gas prices. We have a vehicle with a given tank capacity. We assume that at each vertex gas may be purchased at a certain price. The objective is to find the cheapest route to go from
s
to
t
, or the cheapest tour visiting a given set of locations. We show that the problem of finding a cheapest plan to go from
s
to
t
can be solved in polynomial time. For most other versions, however, the problem is NP-complete and we develop polynomial-time approximation algorithms for these versions.
The tree inclusion problem
Authors: Bille Philip , Gortz Inge Li
Published: July 2011

Given two rooted, ordered, and labeled trees
P
and
T
the tree inclusion problem is to determine if
P
can be obtained from
T
by deleting nodes in
T
. This problem has recently been recognized as an important query primitive in XML databases. Kilpeläinen and Mannila [1995] presented the first polynomial-time algorithm using quadratic time and space. Since then several improved results have been obtained for special cases when
P
and
T
have a small number of leaves or small depth. However, in the worst case these algorithms still use quadratic time and space. Let
n

S

,
l

S

, and
d

S

denote the number of nodes, the number of leaves, and the depth of a tree
S
∈
P
,
T
. In this article we show that the tree inclusion problem can be solved in space
O
(
n

T

) and time: O⎛⎝min⎧⎨⎩lPnTlPlT log log nT + nTnPnTlog nT+ nT log nT⎫⎬⎭⎞⎠.

This improves or matches the best known time complexities while using only linear space instead of quadratic. This is particularly important in practical applications, such as XML databases, where the space is likely to be a bottleneck.
The multidimensional role of social media in healthcare
Authors: Lewis Dana
Published: July 2011

Dana Lewis is a leading voice and an active participant in the use of social media in healthcare. As the founder and moderator of #hcsm, the fast-growing and fast-paced Sunday-night healthcare chat on Twitter, she has regular interactions with a diverse network of stakeholders in the healthcare social media ecosystem---from patients to providers, from instigators to administrators. Dana kindly accepted my invitation to serve as guest editor for a Social Mediator forum about the use of social media in healthcare and promptly solicited the engagement of other participant-leaders representing several key dimensions of this growing movement.

Joe McCarthy, Editor
Mobilizing for community building and everyday innovation
Authors: Olander Sissel , Lenskjold Tau Ulv , Yndigegn Signe Louise , Foverskov Maria
Published: July 2011

Community + Culture features practitioner perspectives on designing technologies for and with communities. We highlight compelling projects and provocative points of view that speak to both community technology practice and the interaction design field as a whole.Tad Hirsch, Editor
African ICTD research (or the lack thereof)
Authors: Gitau Shikoh , Plantinga Paul , Diga Kathleen , Hutchful David
Published: July 2011

This forum looks at how the fields of interaction design and HCI can extend to cover "developing" communities around the world, ones that are gaining access to digital technology for the first time.

Gary Marsden, Editor
An Abstract Model of Certificate Translation
Authors: Barthe Gilles , Kunz César
Published: July 2011

A certificate is a mathematical object that can be used to establish that a piece of mobile code satisfies some security policy. In general, certificates cannot be generated automatically. There is thus an interest in developing methods to reuse certificates generated for source code to provide strong guarantees of the compiled code correctness. Certificate translation is a method to transform certificates of program correctness along semantically justified program transformations. These methods have been developed in previous work, but they were strongly dependent on particular programming and verification settings. This article provides a more general development in the setting of abstract interpretation, showing the scalability of certificate translation.
Online geometric reconstruction
Authors: Chazelle Bernard , Seshadhri C.
Published: July 2011

We investigate a new class of geometric problems based on the idea of online error correction. Suppose one is given access to a large geometric dataset though a query mechanism; for example, the dataset could be a terrain and a query might ask for the coordinates of a particular vertex or for the edges incident to it. Suppose, in addition, that the dataset satisfies some known structural property
P
(for example, monotonicity or convexity) but that, because of errors and noise, the queries occasionally provide answers that violate
P
. Can one design a filter that modifies the query's answers so that (i) the output satisfies
P
; (ii) the amount of data modification is minimized? We provide upper and lower bounds on the complexity of online reconstruction for convexity in 2D and 3D.
Content redundancy in YouTube and its application to video tagging
Authors: Pedro Jose San , Siersdorfer Stefan , Sanderson Mark
Published: July 2011

The emergence of large-scale social Web communities has enabled users to share online vast amounts of multimedia content. An analysis of YouTube reveals a high amount of redundancy, in the form of videos with overlapping or duplicated content. We use robust content-based video analysis techniques to detect overlapping sequences between videos. Based on the output of these techniques, we present an in-depth study of duplication and content overlap in YouTube, and analyze various dependencies between content overlap and meta data such as video titles, views, video ratings, and tags. As an application, we show that content-based links provide useful information for generating new tag assignments. We propose different tag propagation methods for automatically obtaining richer video annotations. Experiments on video clustering and classification as well as a user evaluation demonstrate the viability of our approach.
Exploring the music similarity space on the web
Authors: Schedl Markus , Pohle Tim , Knees Peter , Widmer Gerhard
Published: July 2011

This article comprehensively addresses the problem of similarity measurement between music artists via text-based features extracted from Web pages. To this end, we present a thorough evaluation of different term-weighting strategies, normalization methods, aggregation functions, and similarity measurement techniques. In large-scale genre classification experiments carried out on real-world artist collections, we analyze several thousand combinations of settings/parameters that influence the similarity calculation process, and investigate in which way they impact the quality of the similarity estimates. Accurate similarity measures for music are vital for many applications, such as automated playlist generation, music recommender systems, music information systems, or intelligent user interfaces to access music collections by means beyond text-based browsing. Therefore, by exhaustively analyzing the potential of text-based features derived from artist-related Web pages, this article constitutes an important contribution to context-based music information research.
A Clustering-Driven LDAP Framework
Authors: Koutsonikola Vassiliki , Vakali Athena
Published: July 2011

LDAP directories have proliferated as the appropriate storage framework for various and heterogeneous data sources, operating under a wide range of applications and services. Due to the increased amount and heterogeneity of the LDAP data, there is a requirement for appropriate data organization schemes. The LPAIR & LMERGE (LP-LM) algorithm, presented in this article, is a hierarchical agglomerative structure-based clustering algorithm which can be used for the LDAP directory information tree definition. A thorough study of the algorithm’s performance is provided, which designates its efficiency. Moreover, the
Relative Link
as an alternative merging criterion is proposed, since as indicated by the experimentation, it can result in more balanced clusters. Finally, the
LP and LM Query Engine
is presented, which considering the clustering-based LDAP data organization, results in the enhancement of the LDAP server’s performance.
ACConv -- An Access Control Model for Conversational Web Services
Authors: Paci Federica , Mecella Massimo , Ouzzani Mourad , Bertino Elisa
Published: July 2011

With organizations increasingly depending on Web services to build complex applications, security and privacy concerns including the protection of access control policies are becoming a serious issue. Ideally, service providers would like to make sure that clients have knowledge of only portions of the access control policy relevant to their interactions to the extent to which they are entrusted by the Web service and without restricting the client’s choices in terms of which operations to execute. We propose
ACConv
, a novel model for access control in Web services that is suitable when interactions between the client and the Web service are conversational and long-running. The conversation-based access control model proposed in this article allows service providers to limit how much knowledge clients have about the credentials specified in their access policies. This is achieved while reducing the number of times credentials are asked from clients and minimizing the risk that clients drop out of a conversation with the Web service before reaching a final state due to the lack of necessary credentials. Clients are requested to provide credentials, and hence are entrusted with part of the Web service access control policies, only for some specific
granted conversations
which are decided based on: (1) a level of trust that the Web service provider has vis-à-vis the client, (2) the operation that the client is about to invoke, and (3)
meaningful conversations
which represent conversations that lead to a final state from the current one. We have implemented the proposed approach in a software prototype and conducted extensive experiments to show its effectiveness.
On Computing Deltas of RDF/S Knowledge Bases
Authors: Zeginis Dimitris , Tzitzikas Yannis , Christophides Vassilis
Published: July 2011

The ability to compute the differences that exist between two RDF/S Knowledge Bases (KB) is an important step to cope with the evolving nature of the Semantic Web (SW). In particular, RDF/S deltas can be employed to reduce the amount of data that need to be exchanged and managed over the network in order to build SW synchronization and versioning services. By considering deltas as sets of change operations, in this article we introduce various RDF/S differential functions which take into account inferred knowledge from an RDF/S knowledge base. We first study their correctness in transforming a source to a target RDF/S knowledge base in conjunction with the semantics of the employed change operations (i.e., with or without side-effects on inferred knowledge). Then we formally analyze desired properties of RDF/S deltas such as size minimality, semantic identity, redundancy elimination, reversibility, and composability, as well as identify those RDF/S differential functions that satisfy them. Subsequently, we experimentally evaluate the computing time and size of the produced deltas over real and synthetic RDF/S knowledge bases.
Building Mashups by Demonstration
Authors: Tuchinda Rattapoom , Knoblock Craig A. , Szekely Pedro
Published: July 2011

The latest generation of WWW tools and services enables Web users to generate applications that combine content from multiple sources. This type of Web application is referred to as a mashup. Many of the tools for constructing mashups rely on a widget paradigm, where users must select, customize, and connect widgets to build the desired application. While this approach does not require programming, the users must still understand programming concepts to successfully create a mashup. As a result, they are put off by the time, effort, and expertise needed to build a mashup. In this article, we describe our programming-by-demonstration approach to building mashup by example. Instead of requiring a user to select and customize a set of widgets, the user simply demonstrates the integration task by example. Our approach addresses the problems of extracting data from Web sources, cleaning and modeling the extracted data, and integrating the data across sources. We implemented these ideas in a system called Karma, and evaluated Karma on a set of 23 users. The results show that, compared to other mashup construction tools, Karma allows more of the users to successfully build mashups and makes it possible to build these mashups significantly faster compared to using a widget-based approach.
HipG
Authors: Krepska Elzbieta , Kielmann Thilo , Fokkink Wan , Bal Henri
Published: July 2011

Distributed processing of real-world graphs is challenging due to their size and the inherent irregular structure of graph computations. We present HipG, a distributed framework that facilitates programming parallel graph algorithms by composing the parallel application automatically from the user-defined pieces of sequential work on graph nodes. To make the user code high-level, the framework provides a unified interface to executing methods on local and non-local graph nodes and an abstraction of exclusive execution. The graph computations are managed by logical objects called synchronizers, which we used, for example, to implement distributed divide-and-conquer decomposition into strongly connected components. The code written in HipG is independent of a particular graph representation, to the point that the graph can be created on-the-fly, i.e. by the algorithm that computes on this graph, which we used to implement a distributed model checker. HipG programs are in general short and elegant; they achieve good portability, memory utilization, and performance.
Performance driven multi-objective distributed scheduling for parallel computations
Authors: Narang Ankur , Srivastava Abhinav , Katta Naga Praveen Kumar , Shyamasundar Rudrapatna K.
Published: July 2011

With the advent of many-core architectures and strong need for Petascale (and Exascale) performance in scientific domains and industry analytics, efficient scheduling of parallel computations for higher productivity and performance has become very important. Further, movement of massive amounts (Terabytes to Petabytes) of data is very expensive, which necessitates affinity driven computations. Therefore, distributed scheduling of parallel computations on multiple places 1 needs to optimize multiple performance objectives: follow affinity maximally and ensure efficient space, time and message complexity. Simultaneous consideration of these objectives makes distributed scheduling a particularly challenging problem. In addition, parallel computations have data dependent execution patterns which requires online scheduling to effectively optimize the computation orchestration as it unfolds.

This paper presents an online algorithm for affinity driven distributed scheduling of multi-place 2 parallel computations. To optimize multiple performance objectives simultaneously, our algorithm uses a low time and message complexity mechanism for ensuring affinity and a randomized work-stealing mechanism within places for load balancing. Theoretical analysis of the expected and probabilistic lower and upper bounds on time and message complexity of this algorithm has been provided. On multi-core clusters such as Blue Gene/P (MPP architecture) and Intel multicore cluster, we demonstrate performance close to the custom MPI+Pthreads code. Further, strong, weak and data (increasing input data size) scalability have been demonstrated on multi-core clusters. Using well known benchmarks, we demonstrate 16% to 30% performance gain as compared to Cilk [6] on multi-core Intel Xeon 5570 (NUMA) architecture. Detailed experimental analysis illustrates efficient space (main memory) utilization as well. To the best of our knowledge, this is the first time multi-objective affinity driven distributed scheduling algorithm has been designed, theoretically analyzed and experimentally evaluated in a multi-place setup for multi-core cluster architectures.
On the performance of distributed lock-based synchronization?
Authors: Lubowich Yuval , Taubenfeld Gadi
Published: July 2011

Distributed mutual exclusion locks are the de facto mechanism for concurrency control on distributed data structures. A process accesses the data structure only while holding the lock, and hence the process is guaranteed exclusive access. The popularity of this approach is largely due to the apparently simple programming model of such locks and the availability of efficient implementations. We study the relation between classical types of distributed locking mechanisms and several distributed data structures which use locking for synchronization. Our objectives are:

To determine which one of the two classical locking techniques -- token-based locking or permission-based locking -- is more efficient. Our strategy to achieve this objective is to implement several locks and to compare their performance.

To propose, implement and test several distributed data structures, namely, two different types of counters, a queue, a stack and a linked list; and for each one of the data structures to determine what is the preferred mutual exclusion lock to be used as the underling locking mechanism.

To determine which one of the two proposed counters is better to be used either as a stand-alone data structure or when used as a building block for implementing other high level data structures.

Our testing environment is consisting of 20 Intel XEON 2.4 GHz machines running theWindows XP OS with 2GB of RAM and using a JRE version 1.4.2_08. All the machines were located inside the same LAN and were connected using a 20 port Cisco switch.
Improving the performance of identifying contributors for XML keyword search
Authors: Lin Rung-Ren , Chang Ya-Hui , Chao Kun-Mao
Published: July 2011

Keyword search is a friendly mechanism for users to identify desired information in XML databases, and
LCA
is a popular concept for locating the meaningful subtrees corresponding to query keywords. Among all the LCA-based approaches, MaxMatch [9] is the only one which could achieve the property of
monotonicity
and
consistency
, by outputting only
contributors
instead of the whole subtree. Although the MaxMatch algorithm performs efficiently in some cases, there is still room for improvement. In this paper, we first propose to improve its performance by avoiding unnecessary index accesses. We then speed up the process of
subset detection
, which is a core procedure for determining contributors. The resultant algorithm is called
MinMap
and
MinMap
+, respectively. At last, we analytically and empirically demonstrate the efficiency of our methods. According to our experiments, our two algorithms work better than the existing one, and
MinMap
+ is particularly helpful when the breadth of the tree is large and the number of keywords grows.
Gem #65
Authors: Briot Emmanuel
Published: July 2011

gprbuild is a new program builder, superseding gnatmake. It supports multiple languages, automatically manages source dependencies, and reduces the need for recompilation. This Gem describes a high-level view of how gprbuild works.
Gem #73
Authors: Kuo Dean , Wallenburg Angela
Published: July 2011

In the previous Gem in this series, we saw how to deal with overflow errors, based on source code from Tokeneer. In this Gem, we show how to ensure secure information flow.

This Gem brings us to the end of this series on Tokeneer, and we would like to say a big thank you to the SPARK team at Praxis HIS for providing these resources.
Developing a profile for using object-oriented Ada in high-integrity systems
Authors: Rosen Jean-Pierre
Published: July 2011

This paper reports on the workshop that was held on Oct 27th, 2010 during the SIGAda conference in Fairfax, VA. The goal of the workshop was to start an effort for defining a restricted profile for Object Oriented programming with Ada for high integrity systems, following the example of the Ravenscar profile for the concurrency aspects.
Reusable software components
Authors: Levine Trudy
Published: July 2011

This column consists of our June 2011 listing of sources for reusable software components. All information is obtained directly from web sites or from the parties involved. As always, no recommendation or guarantee by this column is implied.

We would appreciate comments, corrections, and suggestions from our readers.
Performance profiling of virtual machines
Authors: Du Jiaqing , Sehrawat Nipun , Zwaenepoel Willy
Published: July 2011

Profilers based on hardware performance counters are indispensable for performance debugging of complex software systems. All modern processors feature hardware performance counters, but current virtual machine monitors (VMMs) do not properly expose them to the guest operating systems. Existing profiling tools require privileged access to the VMM to profile the guest and are only available for VMMs based on paravirtualization. Diagnosing performance problems of software running in a virtualized environment is therefore quite difficult.

This paper describes how to extend VMMs to support performance profiling. We present two types of profiling in a virtualized environment: guest-wide profiling and system-wide profiling. Guest-wide profiling shows the runtime behavior of a guest. The profiler runs in the guest and does not require privileged access to the VMM. System-wide profiling exposes the runtime behavior of both the VMM and any number of guests. It requires profilers both in the VMM and in those guests.

Not every VMM has the right architecture to support both types of profiling. We determine the requirements for each of them, and explore the possibilities for their implementation in virtual machines using hardware assistance, paravirtualization, and binary translation.

We implement both guest-wide and system-wide profiling for a VMM based on the x86 hardware virtualization extensions and system-wide profiling for a VMM based on binary translation. We demonstrate that these profilers provide good accuracy with only limited overhead.
Perfctr-Xen
Authors: Nikolaev Ruslan , Back Godmar
Published: July 2011

Virtualization is a powerful technique used for variety of application domains, including emerging cloud environments that provide access to virtual machines as a service. Because of the interaction of virtual machines with multiple underlying software and hardware layers, the analysis of the performance of applications running in virtualized environments has been difficult. Moreover, performance analysis tools commonly used in native environments were not available in virtualized environments, a gap which our work closes.

This paper discusses the challenges of performance monitoring inherent to virtualized environments and introduces a technique to virtualize access to low-level performance counters on a per-thread basis. The technique was implemented in perfctr-xen, a framework for the Xen hypervisor that provides an infrastructure for higher-level profilers. This framework supports both accumulative event counts and interrupt-driven event sampling. It is light-weight, providing direct user mode access to logical counter values. perfctr-xen supports multiple modes of virtualization, including paravirtualization and hardware-assisted virtualization. perfctr-xen applies guest kernel-hypervisor coordination techniques to reduce virtualization overhead. We present experimental results based on microbenchmarks and SPEC CPU2006 macrobenchmarks that show the accuracy and usability of the obtained measurements when compared to native execution.
Fast and correct performance recovery of operating systems using a virtual machine monitor
Authors: Kourai Kenichi
Published: July 2011

Rebooting an operating system is a final but effective recovery technique. However, the system performance largely degrades just after the reboot due to the page cache being lost in the main memory. For fast performance recovery, we propose a new reboot mechanism called the warm-cache reboot. The warm-cache reboot preserves the page cache during the reboot and enables an operating system to restore it after the reboot, with the help of a virtual machine monitor (VMM). To perform correct recovery, the VMM guarantees that the reused page cache is consistent with the corresponding files on disks. We have implemented the warm-cache reboot mechanism in the Xen VMM and the Linux operating system. Our experimental results showed that the warm-cache reboot decreased performance degradation just after the reboot. In addition, we confirmed that the file cache corrupted by faults was not reused. The overheads for maintaining cache consistency were not usually large.