bluuebunny/crossref_metadata_2025 huggingface dataset:
Remote data checking using provable data possession
Authors: Ateniese Giuseppe , Burns Randal , Curtmola Reza , Herring Joseph , Khan Osama , Kissner Lea , Peterson Zachary , Song Dawn
Published: June 2011

We introduce a model for
provable data possession
(PDP) that can be used for remote data checking: A client that has stored data at an untrusted server can verify that the server possesses the original data without retrieving it. The model generates probabilistic proofs of possession by sampling random sets of blocks from the server, which drastically reduces I/O costs. The client maintains a constant amount of metadata to verify the proof. The challenge/response protocol transmits a small, constant amount of data, which minimizes network communication. Thus, the PDP model for remote data checking is lightweight and supports large data sets in distributed storage systems. The model is also robust in that it incorporates mechanisms for mitigating arbitrary amounts of data corruption.

We present two provably-secure PDP schemes that are more efficient than previous solutions. In particular, the overhead at the server is low (or even constant), as opposed to linear in the size of the data. We then propose a generic transformation that adds robustness to any remote data checking scheme based on spot checking. Experiments using our implementation verify the practicality of PDP and reveal that the performance of PDP is bounded by disk I/O and not by cryptographic computation. Finally, we conduct an in-depth experimental evaluation to study the tradeoffs in performance, security, and space overheads when adding robustness to a remote data checking scheme.
False data injection attacks against state estimation in electric power grids
Authors: Liu Yao , Ning Peng , Reiter Michael K.
Published: June 2011

A power grid is a complex system connecting electric power generators to consumers through power transmission and distribution networks across a large geographical area. System monitoring is necessary to ensure the reliable operation of power grids, and
state estimation
is used in system monitoring to best estimate the power grid state through analysis of meter measurements and power system models. Various techniques have been developed to detect and identify bad measurements, including
interacting bad measurements
introduced by
arbitrary, nonrandom
causes. At first glance, it seems that these techniques can also defeat malicious measurements injected by attackers.

In this article, we expose an unknown vulnerability of existing bad measurement detection algorithms by presenting and analyzing a new class of attacks, called
false data injection attacks
, against state estimation in electric power grids. Under the assumption that the attacker can access the current power system configuration information and manipulate the measurements of meters at physically protected locations such as substations, such attacks can introduce
arbitrary
errors into certain state variables without being detected by existing algorithms. Moreover, we look at two scenarios, where the attacker is either constrained to specific meters or limited in the resources required to compromise meters. We show that the attacker can systematically and efficiently construct attack vectors in both scenarios to change the results of state estimation in
arbitrary
ways. We also extend these attacks to
generalized false data injection attacks
, which can further increase the impact by exploiting measurement errors typically tolerated in state estimation. We demonstrate the success of these attacks through simulation using IEEE test systems, and also discuss the practicality of these attacks and the real-world constraints that limit their effectiveness.
Practical and efficient cryptographic enforcement of interval-based access control policies
Authors: Crampton Jason
Published: June 2011

The enforcement of access control policies using cryptography has received considerable attention in recent years and the security of such enforcement schemes is increasingly well understood. Recent work in the area has considered the efficient enforcement of temporal and geo-spatial access control policies, and asymptotic results for the time and space complexity of efficient enforcement schemes have been obtained. However, for practical purposes, it is useful to have explicit bounds for the complexity of enforcement schemes.

In this article we consider interval-based access control policies, of which temporal and geo-spatial access control policies are special cases. We define enforcement schemes for interval-based access control policies for which it is possible, in almost all cases, to obtain exact values for the schemes' complexity, thereby subsuming a substantial body of work in the literature. Moreover, our enforcement schemes are more practical than existing schemes, in the sense that they operate in the same way as standard cryptographic enforcement schemes, unlike other efficient schemes in the literature. The main difference between our approach and earlier work is that we develop techniques that are specific to the cryptographic enforcement of interval-based access control policies, rather than applying generic techniques that give rise to complex constructions and asymptotic bounds.
Simple design; research vs. teaching; and quest to learn
Authors: Reed Daniel , Guzdial Mark , Robertson Judy
Published: June 2011

The
Communications
Web site, http://cacm.acm.org, features more than a dozen bloggers in the BLOG@CACM community. In each issue of
Communications
, we'll publish selected posts or excerpts.

twitter

Follow us on Twitter at http://twitter.com/blogCACM

http://cacm.acm.org/blogs/blog-cacm

Daniel Reed writes about design and disruptive technologies. Mark Guzdial discusses the tension between teaching and research at U.S. universities. Judy Robertson argues in favor of educational video games in the classroom.
Biology-inspired networking
Authors: Kroeker Kirk L.
Published: June 2011

Researchers have developed a new networking algorithm, modeled after the neurological development of the fruit fly, to help distributed networks self-organize more efficiently.
All the news that's fit for you
Authors: Krakovsky Marina
Published: June 2011

Personalized news promises to make daily journalism profitable again, but technical and cultural obstacles have slowed the industry's adoption of automated personalization.
The promise of flexible displays
Authors: Geller Tom
Published: June 2011

New screen materials could lead to portable devices that are anything but rectangular, flat, and unbendable.
Beauty and elegance
Authors: Anthes Gary
Published: June 2011

Leslie Valiant talks about machine learning; parallel computing, and his quest for simplicity.
Unlimited possibilities
Authors: Goth Gregory
Published: June 2011

M. Frans Kaashoek discusses systems work, "undo computing," and what he learned from Andrew S. Tanenbaum.
Who are we---now?
Authors: Denning Peter J. , Frailey Dennis J.
Published: June 2011

Considerable progress has been made toward the formation of a computing profession since we started tracking it in this column a decade ago.
Identity management and privacy
Authors: Schwartz Ari
Published: June 2011

The National Strategy for Trusted Identities in Cyberspace represents a shift in the way the U.S. government is approaching identity management, privacy, and the Internet.
Practical application of theoretical estimation
Authors: Armour Phillip G.
Published: June 2011

Estimation models at the extreme.
The risks of stopping too soon
Authors: Parnas David Lorge
Published: June 2011

Good software design is never easy, but stopping too soon makes the job more difficult.
Think before you fork
Authors: Neville-Neil George V.
Published: June 2011

KV's thoughts on forking, config files, and using internal wikis.
Computer science can use more science
Authors: Morrison Clayton T. , Snodgrass Richard T.
Published: June 2011

Software developers should use empirical methods to analyze their designs to predict how working systems will behave.
If you have too much data, then 'good enough' is good enough
Authors: Helland Pat
Published: June 2011

In today's humongous database systems, clarity may be relaxed, but business needs can still be met.
Does deterrence work in reducing information security policy abuse by employees?
Authors: Hu Qing , Xu Zhengchuan , Dinev Tamara , Ling Hong
Published: June 2011

Methods for evaluating and effectively managing the security behavior of employees.
Advancing the state of home networking
Authors: Edwards W. Keith , Grinter Rebecca E. , Mahajan Ratul , Wetherall David
Published: June 2011

Before building the network or its components, first understand the home and the behavior of its human inhabitants.
From polynomial time queries to graph structure theory
Authors: Grohe Martin
Published: June 2011

We give a logical characterization of the polynomial-time properties of graphs with excluded minors: For every class
C
of graphs such that some graph
H
is not a minor of any graph in
C
, a property
P
of graphs in
C
is decidable in polynomial time if and only if it is definable in fixed-point logic with counting. Furthermore, we prove that for every class
C
of graphs with excluded minors there is a
k
such that a simple combinatorial algorithm, namely "the
k
-dimensional Weisfeiler--Lehman algorithm," decides isomorphism of graphs in
C
in polynomial time.
Viscous democracy for social networks
Authors: Boldi Paolo , Bonchi Francesco , Castillo Carlos , Vigna Sebastiano
Published: June 2011

Decision-making procedures in online social networks should reflect participants' political influence within the network.
Wireless on the precipice
Authors: Mcmanus Denise , Carr Houston , Adams Benjamin
Published: June 2011

Business continuity plans for the wireless world must address solar activity.
Indexing methods for approximate dictionary searching
Authors: Boytsov Leonid
Published: June 2011

The primary goal of this article is to survey state-of-the-art indexing methods for approximate dictionary searching. To improve understanding of the field, we introduce a taxonomy that classifies all methods into direct methods and sequence-based filtering methods. We focus on infrequently updated dictionaries, which are used primarily for retrieval. Therefore, we consider indices that are optimized for retrieval rather than for update. The indices are assumed to be associative, that is, capable of storing and retrieving auxiliary information, such as string identifiers. All solutions are lossless and guarantee retrieval of strings within a specified edit distance
k
. Benchmark results are presented for the practically important cases of
k
=1, 2, and 3. We concentrate on natural language datasets, which include synthetic English and Russian dictionaries, as well as dictionaries of frequent words extracted from the ClueWeb09 collection. In addition, we carry out experiments with dictionaries containing DNA sequences. The article is concluded with a discussion of benchmark results and directions for future research.
Relational languages and data models for continuous queries on sequences and data streams
Authors: Law Yan-Nei , Wang Haixun , Zaniolo Carlo
Published: June 2011

Most data stream management systems are based on extensions of the relational data model and query languages, but rigorous analyses of the problems and limitations of this approach, and how to overcome them, are still wanting. In this article, we elucidate the interaction between stream-oriented extensions of the relational model and continuous query language constructs, and show that the resulting expressive power problems are even more serious for data streams than for databases. In particular, we study the loss of expressive power caused by the loss of blocking query operators, and characterize nonblocking queries as monotonic functions on the database. Thus we introduce the notion of
NB
-completeness to assure that a query language is as suitable for continuous queries as it is for traditional database queries. We show that neither RA nor SQL are
NB
-complete on unordered sets of tuples, and the problem is even more serious when the data model is extended to support order—a sine-qua-non in data stream applications. The new limitations of SQL, compounded with well-known problems in applications such as sequence queries and data mining, motivate our proposal of extending the language with user-defined aggregates (UDAs). These can be natively coded in SQL, according to simple syntactic rules that set nonblocking aggregates apart from blocking ones. We first prove that SQL with UDAs is Turing complete. We then prove that SQL with monotonic UDAs and union operators can express all monotonic set functions computable by a Turing machine (
NB
-completeness) and finally extend this result to queries on sequences ordered by their timestamps. The proposed approach supports data stream models that are more sophisticated than append-only relations, along with data mining queries, and other complex applications.
Continuous nearest-neighbor search in the presence of obstacles
Authors: Gao Yunjun , Zheng Baihua , Chen Gang , Chen Chun , Li Qing
Published: June 2011

Despite the ubiquity of physical obstacles (e.g., buildings, hills, and blindages, etc.) in the real world, most of spatial queries ignore the obstacles. In this article, we study a novel form of continuous nearest-neighbor queries in the presence of obstacles, namely continuous obstructed nearest-neighbor (CONN) search, which considers the impact of obstacles on the distance between objects. Given a data set
P
, an obstacle set
O
, and a query line segment
q
, in a two-dimensional space, a CONN query retrieves the nearest neighbor
p
∈
P
of each point
p′
on
q
according to the obstructed distance, the shortest path between
p
and
p
′
without crossing any obstacle in
O
. We formalize CONN search, analyze its unique properties, and develop algorithms for exact CONN query-processing assuming that both
P
and
O
are indexed by conventional data-partitioning indices (e.g., R-trees). Our methods tackle CONN retrieval by performing a single query for the entire query line segment, and only process the data points and obstacles relevant to the final query result via a novel concept of control points and an efficient quadratic-based split point computation approach. Then, we extend our techniques to handle variations of CONN queries, including (1) continuous obstructed
k
nearest neighbor (CO
k
NN) search which, based on obstructed distances, finds the
k
(≥ 1) nearest neighbors (NNs) to every point along
q
; and (2) trajectory obstructed
k
nearest-neighbor (TO
k
NN) search, which, according to obstructed distances, returns the
k
NNs for each point on an arbitrary trajectory (consisting of several consecutive line segments). Finally, we explore approximate CO
k
NN (ACO
k
NN) retrieval. Extensive experiments with both real and synthetic datasets demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.
Design and analysis of a ranking approach to private location-based services
Authors: Yiu Man Lung , Jensen Christian S. , Møller Jesper , Lu Hua
Published: June 2011

Users of mobile services wish to retrieve nearby points of interest without disclosing their locations to the services. This article addresses the challenge of optimizing the query performance while satisfying given location privacy and query accuracy requirements. The article's proposal, SpaceTwist, aims to offer location privacy for
k
nearest neighbor (
k
NN) queries at low communication cost without requiring a trusted anonymizer. The solution can be used with a conventional DBMS as well as with a server optimized for location-based services. In particular, we believe that this is the first solution that expresses the server-side functionality in a single SQL statement. In its basic form, SpaceTwist utilizes well-known incremental NN query processing on the server. When augmented with a server-side granular search technique, SpaceTwist is capable of exploiting relaxed query accuracy guarantees for obtaining better performance. We extend SpaceTwist with so-called ring ranking, which improves the communication cost, delayed termination, which improves the privacy afforded the user, and the ability to function in spatial networks in addition to Euclidean space. We report on analytical and empirical studies that offer insight into the properties of SpaceTwist and suggest that our proposal is indeed capable of offering privacy with very good performance in realistic settings.
Reverse data exchange
Authors: Fagin Ronald , Kolaitis Phokion G. , Popa Lucian , Tan Wang-Chiew
Published: June 2011

An inverse of a schema mapping
M
is intended to undo what
M
does, thus providing a way to perform reverse data exchange. In recent years, three different formalizations of this concept have been introduced and studied, namely the notions of an inverse of a schema mapping, a quasi-inverse of a schema mapping, and a maximum recovery of a schema mapping. The study of these notions has been carried out in the context in which source instances are restricted to consist entirely of constants, while target instances may contain both constants and labeled nulls. This restriction on source instances is crucial for obtaining some of the main technical results about these three notions, but, at the same time, limits their usefulness, since reverse data exchange naturally leads to source instances that may contain both constants and labeled nulls.

We develop a new framework for reverse data exchange that supports source instances that may contain nulls, and we thereby overcome the semantic mismatch between source and target instances of the previous formalizations. The development of this new framework requires a careful reformulation of all the important notions, including the notions of the identity schema mapping, inverse, and maximum recovery. To this effect, we introduce the notions of extended identity schema mapping, extended inverse, and maximum extended recovery, by making systematic use of the homomorphism relation on instances. We give results concerning the existence of extended inverses and of maximum extended recoveries, and results concerning their applications to reverse data exchange and query answering. Moreover, we show that maximum extended recoveries can be used to capture in a quantitative way, the amount of information loss embodied in a schema mapping specified by source-to-target tuple-generating dependencies.
Asymptotically efficient algorithms for skyline probabilities of uncertain data
Authors: Atallah Mikhail J. , Qi Yinian , Yuan Hao
Published: June 2011

Skyline computation is widely used in multicriteria decision making. As research in uncertain databases draws increasing attention, skyline queries with uncertain data have also been studied. Some earlier work focused on probabilistic skylines with a given threshold; Atallah and Qi [2009] studied the problem to compute skyline probabilities for all instances of uncertain objects without the use of thresholds, and proposed an algorithm with subquadratic time complexity. In this work, we propose a new algorithm for computing all skyline probabilities that is asymptotically faster: worst-case
O(n
√
n
log
n
) time and
O(n)
space for 2D data;
O
(
n
2−1/d
log

d
−1

n
) time and
O(n
log

d
−2

n
) space for
d
-dimensional data. Furthermore, we study the online version of the problem: Given any query point
p
(unknown until the query time), return the probability that no instance in the given data set dominates
p
. We propose an algorithm for answering such an online query for
d
-dimensional data in
O(n

1−1/
d

log

d
−1

n
) time after preprocessing the data in
O(n
2−1/d
log

d
−1

) time and space.
A relational approach to functional decomposition of logic circuits
Authors: Lee Tony T. , Ye Tong
Published: June 2011

Functional decomposition of Boolean functions has a profound influence on all quality aspects of cost-effectively implementing modern digital systems and data-mining. The relational databases are multivalued tables, which include any truth tables of logic functions as special cases. In this article, we propose a relational database approach to the decomposition of logic circuits. The relational algebra consists of a set of well-defined algebraic operations that can be performed on multivalued tables. Our approach shows that the functional decomposition of logic circuits is similar to the normalization of relational databases; they are governed by the same concepts of functional dependency (FD) and multivalued dependency (MVD). The completeness of relational algebra demonstrated by our approach to functional decomposition reveals that the relational database is a fundamental computation model, the same as the Boolean logic circuit.
Closed world data exchange
Authors: Hernich André , Libkin Leonid , Schweikardt Nicole
Published: June 2011

Data exchange deals with translating data structured in some source format into data structured in some target format, given a specification of the relationship between the source and the target and possibly constraints on the target; and answering queries over the target in a way that is semantically consistent with the information in the source. Theoretical foundations of data exchange have been actively explored recently. It was also noticed that the standard semantics for query answering in data exchange may lead to counterintuitive or anomalous answers.

In the present article, we explain that this behavior is due to the fact that solutions can contain invented information (information that is not related to the source instance), and that the presence of incomplete information in target instances has been ignored. In particular, proper query evaluation techniques for databases with nulls have not been used, and the distinction between closed and open world semantics has not been made.

We present a concept of solutions, called CWA-solutions, that is based on the closed world assumption. For data exchange settings without constraints on the target, the space of CWA-solutions has two extreme points: the canonical universal solution (the maximal CWA-solution) and the core of the universal solutions (the minimal CWA-solution), both of them well studied in data exchange. In the presence of constraints on the target, the core of the universal solutions is still the minimal CWA-solution, but there may be no unique maximal CWA-solution. We show how to define the semantics of query-answering taking into account incomplete information, and show that some of the well-known anomalies go away with the new semantics. The article also contains results on the complexity of query-answering, upper approximations to queries (maybe-answers), and various extensions.
Effective handling of dialogue state in the hidden information state POMDP-based dialogue manager
Authors: Gašić Milica , Young Steve
Published: June 2011

Effective dialogue management is critically dependent on the information that is encoded in the dialogue state. In order to deploy reinforcement learning for policy optimization, dialogue must be modeled as a Markov Decision Process. This requires that the dialogue state must encode all relevent information obtained during the dialogue prior to that state. This can be achieved by combining the user goal, the dialogue history, and the last user action to form the dialogue state. In addition, to gain robustness to input errors, dialogue must be modeled as a Partially Observable Markov Decision Process (POMDP) and hence, a distribution over all possible states must be maintained at every dialogue turn. This poses a potential computational limitation since there can be a very large number of dialogue states. The Hidden Information State model provides a principled way of ensuring tractability in a POMDP-based dialogue model. The key feature of this model is the grouping of user goals into partitions that are dynamically built during the dialogue. In this article, we extend this model further to incorporate the notion of complements. This allows for a more complex user goal to be represented, and it enables an effective pruning technique to be implemented that preserves the overall system performance within a limited computational resource more effectively than existing approaches.
Spatially-aware dialogue control using hierarchical reinforcement learning
Authors: Cuayáhuitl Heriberto , Dethlefs Nina
Published: June 2011

This article addresses the problem of scalable optimization for spatially-aware dialogue systems. These kinds of systems must perceive, reason, and act about the spatial environment where they are embedded. We formulate the problem in terms of Semi-Markov Decision Processes and propose a hierarchical reinforcement learning approach to optimize subbehaviors rather than full behaviors. Because of the vast number of policies that are required to control the interaction in a dynamic environment (e.g., a dialogue system assisting a user to navigate in a building from one location to another), our learning approach is based on two stages: (a) the first stage learns low-level behavior, in advance; and (b) the second stage learns high-level behavior, in real time. For such a purpose we extend an existing algorithm in the literature of reinforcement learning in order to support reusable policies and therefore to perform fast learning. We argue that our learning approach makes the problem feasible, and we report on a novel reinforcement learning dialogue system that performs a joint optimization between dialogue and spatial behaviors. Our experiments, using simulated and real environments, are based on a text-based dialogue system for indoor navigation. Experimental results in a realistic environment reported an overall user satisfaction result of 89%, which suggests that our proposed approach is attractive for its application in real interactions as it combines fast learning with adaptive and reasonable behavior.
Natural actor and belief critic
Authors: Jurčíček Filip , Thomson Blaise , Young Steve
Published: June 2011

This article presents a novel algorithm for learning parameters in statistical dialogue systems which are modeled as Partially Observable Markov Decision Processes (POMDPs). The three main components of a POMDP dialogue manager are a dialogue model representing dialogue state information; a policy that selects the system's responses based on the inferred state; and a reward function that specifies the desired behavior of the system. Ideally both the model parameters and the policy would be designed to maximize the cumulative reward. However, while there are many techniques available for learning the optimal policy, no good ways of learning the optimal model parameters that scale to real-world dialogue systems have been found yet.

The presented algorithm, called the Natural Actor and Belief Critic (NABC), is a policy gradient method that offers a solution to this problem. Based on observed rewards, the algorithm estimates the natural gradient of the expected cumulative reward. The resulting gradient is then used to adapt both the prior distribution of the dialogue model parameters and the policy parameters. In addition, the article presents a variant of the NABC algorithm, called the Natural Belief Critic (NBC), which assumes that the policy is fixed and only the model parameters need to be estimated. The algorithms are evaluated on a spoken dialogue system in the tourist information domain. The experiments show that model parameters estimated to maximize the expected cumulative reward result in significantly improved performance compared to the baseline hand-crafted model parameters. The algorithms are also compared to optimization techniques using plain gradients and state-of-the-art random search algorithms. In all cases, the algorithms based on the natural gradient work significantly better.
Classifying dialogue in high-dimensional space
Authors: González-Brenes José P. , Mostow Jack
Published: June 2011

The richness of multimodal dialogue makes the space of possible features required to describe it very large relative to the amount of training data. However, conventional classifier learners require large amounts of data to avoid overfitting, or do not generalize well to unseen examples. To learn dialogue classifiers using a rich feature set and fewer data points than features, we apply a recent technique, ℓ1-regularized logistic regression. We demonstrate this approach empirically on real data from Project LISTEN's Reading Tutor, which displays a story on a computer screen and listens to a child read aloud. We train a classifier to predict task completion (i.e., whether the student will finish reading the story) with 71% accuracy on a balanced, unseen test set. To characterize differences in the behavior of children when they choose the story they read, we likewise train and test a classifier that with 73.6% accuracy infers who chose the story based on the ensuing dialogue. Both classifiers significantly outperform baselines and reveal relevant features of the dialogue.
Modeling spoken decision support dialogue and optimization of its dialogue strategy
Authors: Misu Teruhisa , Sugiura Komei , Kawahara Tatsuya , Ohtake Kiyonori , Hori Chiori , Kashioka Hideki , Kawai Hisashi , Nakamura Satoshi
Published: June 2011

This article presents a user model for user simulation and a system state representation in spoken decision support dialogue systems. When selecting from a group of alternatives, users apply different decision-making criteria with different priorities. At the beginning of the dialogue, however, users often do not have a definite goal or criteria in which they place value, thus they can learn about new features while interacting with the system and accordingly create new criteria. In this article, we present a user model and dialogue state representation that accommodate these patterns by considering the user's knowledge and preferences. To estimate the parameters used in the user model, we implemented a trial sightseeing guidance system, collected dialogue data, and trained a user simulator. Since the user parameters are not observable from the system, the dialogue is modeled as a partially observable Markov decision process (POMDP), and a dialogue state representation was introduced based on the model. We then optimized its dialogue strategy so that users can make better choices. The dialogue strategy is evaluated using a user simulator trained from a large number of dialogues collected using a trial dialogue system.
Logarithmic-Time FPGA Bitstream Analysis
Authors: Bergeron Etienne , Perron Louis-David , Feeley Marc , David Jean Pierre
Published: June 2011

Just-In-Time (JIT) compilation is frequently used in software engineering to accelerate program execution. Parts of the code are translated to machine code at runtime to speedup their execution by exploiting local and dynamic information of the computation. Modern FPGAs manufactured by Xilinx allow partial and dynamic configuration. Such features make them eligible platforms for JIT hardware compilation. Nevertheless, this has not been achieved until now because the mapping between a bitstream and the programmable points inside these FPGAs is not documented. In this article, we propose a methodology to retrieve the relevant information in logarithmic time per bit by methodically using the tools distributed by Xilinx. We give a practical case study which details the analysis of a Virtex-II Pro FPGA bitstream. The mapping of CLBs, BRAMs, and multipliers has been fully determined. Thanks to this information, we have been able to prototype tools in the fields of reverse mapping FPGA bitstreams, low-level simulation, and custom place-and-route. Finally preliminary results demonstrate that a processor embedded in an FPGA can compile, place, and route arithmetic and logic expressions inside the FPGA within a few milliseconds.
A Novel Multicontext Coarse-Grained Reconfigurable Architecture (CGRA) For Accelerating Column-Oriented Databases
Authors: Vaidya Pranav , Lee Jaehwan John
Published: June 2011

The storage model of column-oriented databases is similar in structure to densely packed matrices/vectors found in many high-performance computing applications. Hence, hardware-accelerated vectorized matrix operations using Reconfigurable Logic (RL) coprocessors may find parallels in hardware acceleration of databases. In this article, we explore this hypothesis by proposing a multicontext, coarse-grained Reconfigurable coprocessor Unit (RU) model that is used to accelerate some of the database operations in hardware for column-oriented databases. We then describe the implementation of hardware algorithms for the equi-join, nonequi-join, and inverse-lookup database operations. Finally, we evaluate these algorithms using a microbenchmark query. Our results indicate that the query execution on the proposed RU model is one to two orders of magnitude faster than the software-only query execution.
Fast Optical Reconfiguration of a Nine-Context DORGA Using a Speed Adjustment Control
Authors: Nakajima Mao , Watanabe Minoru
Published: June 2011

Demand for fast dynamic reconfiguration has increased since dynamic reconfiguration can accelerate the performance of implementation circuits. Such dynamic reconfiguration requires two important features: fast reconfiguration and numerous reconfiguration contexts. However, fast reconfiguration and numerous reconfiguration contexts share a trade-off relation on current VLSIs. Therefore, Optically Reconfigurable Gate Arrays (ORGAs) have been developed to resolve this dilemma. An ORGA architecture allows many configuration contexts by exploiting the large storage capacity of a holographic memory and fast reconfiguration using wide-bandwidth optical connections between a holographic memory and a programmable gate array VLSI. In addition, Dynamic Optically Reconfigurable Gate Arrays (DORGAs) using a photodiode memory architecture have already been developed to realize a high-gate-density VLSI. Therefore, this article presents the first demonstration of a nanosecond-order configuration of a nine-context DORGA architecture. Moreover, this article presents a proposal of a reconfiguration period adjustment technique to control each reconfiguration period to its best setting.
A Performance-Oriented Algorithm with Consideration on Communication Cost for Dynamically Reconfigurable FPGA Partitioning
Authors: Tai Tzu-Chiang , Lai Yen-Tai
Published: June 2011

Dynamically reconfigurable FPGAs (DRFPGAs) have high logic utilization because of time-multiplexed interconnects and logic. In this article, we propose a performance-oriented algorithm for the DRFPGA partitioning problem. This algorithm partitions a given circuit system into stages such that the upper bound of the execution times of subcircuits is minimized. The communication cost is taken into consideration in the process of searching for the optimal solution. A graph is first constructed to represent the precedence constraints and calculate the number of buffers needed in a partitioning. This algorithm includes three phases. The first phase reduces the problem size by clustering the gates into subsystems that have only one output. Such a subsystem has a large number of intraconnections because the fan-outs of all vertices except for the one output are fed to the vertices inside the subsystem. This phase significantly reduces the computational complexity of partitioning. The second phase finds a partition with optimal performance. Finally, the third phase minimizes the communication cost by using an iterative improvement approach. Experimental results based on the Xilinx architecture show that our algorithm yields better partitioning solutions than traditional approaches.
Domain-Specific Optimization of Signal Recognition Targeting FPGAs
Authors: Demertzi Melina , Diniz Pedro C. , Hall Mary W. , Gilbert Anna C. , Wang Yi
Published: June 2011

Domain-specific optimizations on matrix computations exploiting specific arithmetic and matrix representation formats have achieved significant performance/area gains in Field-Programmable Gate Array (FPGA) hardware designs. In this article, we explore the application of data-driven optimizations to reduce both storage and computation requirements to the problem of signal recognition from a known dictionary. By starting with a high-level mathematical representation of a signal recognition problem, we perform optimizations across the layers of the system, exploiting mathematical structure to improve implementation efficiency. Specifically, we use Walsh wavelet packets in conjunction with a BestBasis algorithm to distinguish between spoken digits. The resulting transform matrices are quite sparse, and exhibit a rich algebraic structure that contains significant overlap across rows. As a consequence, dot-product computations of the transform matrix and signal vectors exhibit significant computation reuse, or repeated identical computations. We present an algorithm for identifying this computation reuse and scheduling of the row computations. We exploit this reuse to derive FPGA hardware implementations that reduce the amount of computation for an individual matrix by as much as 6.35× and an average of 2× for a single dot-product unit. The implementation that exploits reuse achieves a 2× computation reduction compared to three concurrently-executing simpler accumulator units with the same aggregate design area and outperforms software implementations on high-end desktop personal computers.
FPGA Acceleration of MultiFactor CDO Pricing
Authors: Kaganov Alexander , Lakhany Asif , Chow Paul
Published: June 2011

The last decade has seen a significant growth in the financial industry. The recent widespread use of Internet technology has increased the accessibility of the general population to financial data, thereby increasing the average portfolio size. This increase, compounded by the need for accurate real-time results, has led to a rising demand for faster risk simulations. Often, accurately pricing widespread instruments, such as Collateralized Debt Obligations (CDOs), can take excessively long due to their multifactor assets dependency. We present a hardware implementation for a MultiFactor Gaussian Copula (MFGC) CDO pricing algorithm. Through a detailed benchmark exploration we demonstrate how reconfigurable hardware could be used to exploit fine-grain parallelism. Our results show that our implementation mapped onto a Xilinx Virtex 5 (XC5VSX50T) FPGA is over 71 times faster than corresponding software running on a single core 3.4 GHz Intel Xeon processor.
A hybrid flash translation layer with adaptive merge for SSDs
Authors: Shim Gyudong , Park Youngwoo , Park Kyu Ho
Published: June 2011

The Flash Translation Layer (FTL) in Solid-State Disks (SSDs) maps logical addresses to physical addresses for disk drive virtualization. In order to reduce garbage collection overhead, we propose full associative striped block-level mapping. In addition, an adaptive merge is proposed to avoid excessive data block reconstructions during garbage collection. With these mechanisms, the write latency is improved up to 78% in comparison with the previous multichannel hybrid FTLs in a sample PC trace. The performance improvements stem from 52% reduced garbage collection.
Online availability upgrades for parity-based RAIDs through supplementary parity augmentations
Authors: Tian Lei , Cao Qiang , Jiang Hong , Feng Dan , Xie Changsheng , Xin Qin
Published: June 2011

In this article, we propose a simple but powerful online availability upgrade mechanism,
S
upplementary
P
arity
A
ugmentations(
SPA
), to address the availability issue in parity-based RAID systems. The basic idea of SPA is to store and update the supplementary parity units on one or a few newly augmented spare disks for online RAID systems in the operational mode, thus achieving the goals of improving the reconstruction performance while tolerating multiple disk failures and latent sector errors simultaneously. By applying the exclusive OR operations appropriately among supplementary parity, full parity, and data units, SPA can reconstruct the data on the failed disks with a fraction of the original overhead that is proportional to the supplementary parity coverage, thus significantly reducing the overhead of data regeneration and decreasing recovery time in parity-based RAID systems. Our extensive trace-driven simulation study shows that SPA can significantly improve the reconstruction performance of the RAID5 and RAID5+0 systems, at an acceptable performance overhead imposed in the operational mode. Moreover, our reliability analytical modeling and sequential Monte-Carlo simulation demonstrate that SPA is consistently more than double the MTTDL of the RAID5 system and improves the reliability of the RAID5+0 system noticeably.
On the competitive ratio of evaluating priced functions
Authors: Cicalese Ferdinando , Laber Eduardo Sany
Published: June 2011

Let
f
be a function on a set of variables
V
. For each
x
∈
V
, let
c(x)
be the cost of reading the value of
x
. An algorithm for evaluating
f
is a strategy for adaptively identifying and reading a set of variables
U
⊆
V
whose values uniquely determine the value of
f
. We are interested in finding algorithms which minimize the cost incurred to evaluate
f
in the above sense. Competitive analysis is employed to measure the performance of the algorithms. We address two variants of the above problem. We consider the basic model in which the evaluation algorithm knows the cost
c(x)
, for each
x
∈
V
. We also study a novel model where the costs of the variables are not known in advance and some
preemption
is allowed in the reading operations. This model has applications, for example, when reading a variable coincides with obtaining the output of a job on a CPU and the cost is the CPU time.

For the model where the costs of the variables are known, we present a
polynomial time
algorithm with the best possible competitive ratio γ

c

f

for each function
f
that is representable by a threshold tree and for each fixed cost function
c
(⋅). Remarkably, the best-known result for the same class of functions is a
pseudo-polynomial
algorithm with competitiveness 2 γ

c

f

. Still in the same model, we introduce the Linear Programming Approach (
LPA
), a framework that allows the design of efficient algorithms for evaluating functions. We show that different implementations of this approach lead in general to the best algorithms known so far—and in many cases to optimal algorithms—for different classes of functions considered before in the literature.

Via the
LPA
, we are able to determine exactly the optimal extremal competitiveness of monotone Boolean functions. Remarkably, the upper bound which leads to this result, holds for a much broader class of functions, which also includes the whole set of Boolean functions.

We also show how to extend the
LPA
(together with these results) to the model where the costs of the variables are not known beforehand. In particular, we show how to employ the extended
LPA
to design a polynomial-time optimal (with respect to competitiveness) algorithm for the class of monotone Boolean functions representable by threshold trees.
Market equilibrium under separable, piecewise-linear, concave utilities
Authors: Vazirani Vijay V. , Yannakakis Mihalis
Published: June 2011

We consider Fisher and Arrow--Debreu markets under additively separable, piecewise-linear, concave utility functions and obtain the following results. For both market models, if an equilibrium exists, there is one that is rational and can be written using polynomially many bits. There is no simple necessary and sufficient condition for the existence of an equilibrium: The problem of checking for existence of an equilibrium is NP-complete for both market models; the same holds for existence of an ε-approximate equilibrium, for ε =
O
(
n
−5
). Under standard (mild) sufficient conditions, the problem of finding an exact equilibrium is in PPAD for both market models. Finally, building on the techniques of Chen et al. [2009a] we prove that under these sufficient conditions, finding an equilibrium for Fisher markets is PPAD-hard.
Robust principal component analysis?
Authors: Candès Emmanuel J. , Li Xiaodong , Ma Yi , Wright John
Published: June 2011

This article is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components
exactly
by solving a very convenient convex program called
Principal Component Pursuit
; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the ℓ
1
norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces.
Crowdsourcing for search and data mining
Authors: Lease Matthew , Carvalho Vitor R. , Yilmaz Emine
Published: June 2011

The Crowdsourcing for Search and Data Mining (CSDM 2011) workshop was held on February 9, 2011 in Hong Kong, China, in conjunction with the Fourth ACM International Conference onWeb Search and Data Mining (WSDM2011). The workshop addressed recent advances in theory and empirical methods, as well as novel applications, in crowdsourcing for search and data mining. Three invited talks were presented, along with eight refereed papers. Workshop proceedings and presentation slides can be found online.
Report on the BooksOnline'10
Authors: Kazai Gabriella , Brusilovsky Peter
Published: June 2011

The BooksOnline Workshop series aims to foster the discussion and exchange of research ideas and initiatives addressing challenges and exploring opportunities around large collections of digital books and complementary media. The third workshop in the series, BooksOnline' 10 boosted a high quality program, including keynote addresses by James Crawford from Google Books and John Mark Ockerbloom from the University of Pennsylvania. From the accepted papers two main themes emerged: 1) Issues relating to building suitable infrastructure for online book collections and for the evaluation of the applications and services that make use of such collections, and 2) Opportunities relating to the social or collaborative reading and annotation of books and issues relating to the design of suitable eReaders. This paper provides a summary of the workshop and the accepted contributions.