bluuebunny/crossref_metadata_2025_split huggingface dataset:
Efficient querying of inconsistent databases with binary integer programming
Authors: Kolaitis Phokion G. , Pema Enela , Tan Wang-Chiew 
Published: June 2014

An inconsistent database is a database that violates one or more integrity constraints. A typical approach for answering a query over an inconsistent database is to first clean the inconsistent database by transforming it to a consistent one and then apply the query to the consistent database. An alternative and more principled approach, known as consistent query answering, derives the answers to a query over an inconsistent database without changing the database, but by taking into account all possible repairs of the database.In this paper, we study the problem of consistent query answering over inconsistent databases for the class for conjunctive queries under primary key constraints. We develop a system, called EQUIP, that represents a fundamental departure from existing approaches for computing the consistent answers to queries in this class. At the heart of EQUIP is a technique, based on Binary Integer Programming (BIP), that repeatedly searches for repairs to eliminate candidate consistent answers until no further such candidates can be eliminated. We establish rigorously the correctness of the algorithms behind EQUIP and carry out an extensive experimental investigation that validates the effectiveness of our approach. Specifically, EQUIP exhibits good and stable performance on conjunctive queries under primary key constraints, it significantly outperforms existing systems for computing the consistent answers of such queries in the case in which the consistent answers are not first-order rewritable, and it scales well.
CorrectDB
Authors: Bajaj Sumeet , Sion Radu 
Published: June 2014

Clients of outsourced databases need Query Authentication (QA) guaranteeing the integrity (correctness and completeness), and authenticity of the query results returned by potentially compromised providers.Existing results provide QA assurances for a limited class of queries by deploying several software cryptographic constructs. Here, we show that, to achieve QA, however, it is significantly cheaper and more practical to deploy server-hosted, tamper-proof co-processors, despite their higher acquisition costs. Further, this provides the ability to handle arbitrary queries.To reach this insight, we extensively survey existing QA work and identify interdependencies and efficiency relationships. We then introduce CorrectDB, a new DBMS with full QA assurances, leveraging server-hosted, tamper-proof, trusted hardware in close proximity to the outsourced data.
Sharing data and work across concurrent analytical queries
Authors: Psaroudakis Iraklis , Athanassoulis Manos , Ailamaki Anastasia 
Published: June 2014

Today's data deluge enables organizations to collect massive data, and analyze it with an ever-increasing number of concurrent queries. Traditional data warehouses (DW) face a challenging problem in executing this task, due to their query-centric model: each query is optimized and executed independently. This model results in high contention for resources. Thus, modern DW depart from the query-centric model to execution models involving sharing of common data and work. Our goal is to show when and how a DW should employ sharing. We evaluate experimentally two sharing methodologies, based on their original prototype systems, that exploit work sharing opportunities among concurrent queries at run-time: Simultaneous Pipelining (SP), which shares intermediate results of common sub-plans, and Global Query Plans (GQP), which build and evaluate a single query plan with shared operators.
First, after a short review of sharing methodologies, we show that SP and GQP are orthogonal techniques. SP can be applied to shared operators of a GQP, reducing response times by 20%-48% in workloads with numerous common sub-plans. Second, we corroborate previous results on the negative impact of SP on performance for cases of low concurrency. We attribute this behavior to a bottleneck caused by the push-based communication model of SP. We show that pull-based communication for SP eliminates the overhead of sharing altogether for low concurrency, and scales better on multi-core machines than push-based SP, further reducing response times by 82%-86% for high concurrency. Third, we perform an experimental analysis of SP, GQP and their combination, and show when each one is beneficial. We identify a trade-off between low and high concurrency. In the former case, traditional query-centric operators with SP perform better, while in the latter case, GQP with shared operators enhanced by SP give the best results.
Skyline operator on anti-correlated distributions
Authors: Shang Haichuan , Kitsuregawa Masaru 
Published: June 2014

Finding the skyline in a multi-dimensional space is relevant to a wide range of applications. The skyline operator over a set of
d
-dimensional points selects the points that are not dominated by any other point on all dimensions. Therefore, it provides a minimal set of candidates for the users to make their personal trade-off among all optimal solutions.

The existing algorithms establish both the worst case complexity by discarding distributions and the average case complexity by assuming dimensional independence. However, the data in the real world is more likely to be anti-correlated. The cardinality and complexity analysis on dimensionally independent data is meaningless when dealing with anti-correlated data. Furthermore, the performance of the existing algorithms becomes impractical on anti-correlated data.
In this paper, we establish a cardinality model for anti-correlated distributions. We propose an accurate polynomial estimation for the expected value of the skyline cardinality. Because the high skyline cardinality downgrades the performance of most existing algorithms on anti-correlated data, we further develop a determination and elimination framework which extends the well-adopted elimination strategy. It achieves remarkable effectiveness and efficiency. The comprehensive experiments on both real datasets and benchmark synthetic datasets demonstrate that our approach significantly outperforms the state-of-the-art algorithms under a wide range of settings.
Improving flash write performance by using update frequency
Authors: Stoica Radu , Ailamaki Anastasia 
Published: June 2014

Solid-state drives (SSDs) are quickly becoming the default storage medium as the cost of NAND flash memory continues to drop. However, flash memory introduces new challenges, as data cannot be eciently updated in-place. To overcome the technology's limitations, SSDs incorporate a software Flash Translation Layer (FTL) that implements out-of-place updates, typically by storing data in a log-structured fashion. Despite a large number of existing FTL algorithms, SSD performance, predictability, and lifetime remain an issue, especially for the write-intensive workloads specific to database applications.In this paper, we show how to design FTLs that are more efficient by using the I/O write skew to guide data placement on flash memory. We model the relationship between data placement and write performance for basic I/O write patterns and detail the most important concepts of writing to flash memory: i) the trade-o between the extra capacity available and write overhead, ii) the benefit of adapting data placement to write skew, iii) the impact of the cleaning policy, and iv) how to estimate the best achievable write performance for a given I/O workload. Based on the findings of the theoretical model, we propose a new principled data placement algorithm that can be incorporated into existing FTLs. We show the benefits of our data placement algorithm when running micro-benchmarks and real database I/O traces: our data placement algorithm reduces write overhead by 20% - 75% when compared to state-of-art techniques.
On the embeddability of random walk distances
Authors: Zhao Xiaohan , Chang Adelbert , Sarma Atish Das , Zheng Haitao , Zhao Ben Y. 
Published: June 2014

Analysis of large graphs is critical to the ongoing growth of search engines and social networks. One class of queries centers around node affinity, often quantified by random-walk distances between node pairs, including hitting time, commute time, and personalized PageRank (PPR). Despite the potential of these "metrics," they are rarely, if ever, used in practice, largely due to extremely high computational costs.
In this paper, we investigate methods to scalably and efficiently compute random-walk distances, by "embedding" graphs and distances into points and distances in geometric coordinate spaces. We show that while existing graph coordinate systems (GCS) can accurately estimate shortest path distances, they produce significant errors when embedding random-walk distances. Based on our observations, we propose a new graph embedding system that explicitly accounts for per-node graph properties that affect random walk. Extensive experiments on a range of graphs show that our new approach can accurately estimate both symmetric and asymmetric random-walk distances. Once a graph is embedded, our system can answer queries between any two nodes in 8 microseconds, orders of magnitude faster than existing methods. Finally, we show that our system produces estimates that can replace ground truth in applications with minimal impact on application output.
Understanding insights into the basic structure and essential issues of table placement methods in clusters
Authors: Huai Yin , Ma Siyuan , Lee Rubao , O'Malley Owen , Zhang Xiaodong 
Published: June 2014

A table placement method is a critical component in big data analytics on distributed systems. It determines the way how data values in a two-dimensional table are organized and stored in the underlying cluster. Based on Hadoop computing environments, several table placement methods have been proposed and implemented. However, a comprehensive and systematic study to understand, to compare, and to evaluate different table placement methods has not been done. Thus, it is highly desirable to gain important insights into the basic structure and essential issues of table placement methods in the context of big data processing infrastructures.
In this paper, we present such a study. The basic structure of a data placement method consists of three core operations: row reordering, table partitioning, and data packing. All the existing placement methods are formed by these core operations with variations made by the three key factors: (1) the size of a horizontal logical subset of a table (or the size of a row group), (2) the function of mapping columns to column groups, and (3) the function of packing columns or column groups in a row group into physical blocks. We have designed and implemented a benchmarking tool to provide insights into how variations of each factor affect the I/O performance of reading data of a table stored by a table placement method. Based on our results, we give suggested actions to optimize table reading performance. Results from large-scale experiments have also confirmed that our findings are valid for production workloads. Finally, we present ORC File as a case study to show the effectiveness of our findings and suggested actions.
Streaming similarity search over one billion tweets using parallel locality-sensitive hashing
Authors: Sundaram Narayanan , Turmukhametova Aizana , Satish Nadathur , Mostak Todd , Indyk Piotr , Madden Samuel , Dubey Pradeep 
Published: June 2014

Finding nearest neighbors has become an important operation on databases, with applications to text search, multimedia indexing, and many other areas. One popular algorithm for similarity search, especially for high dimensional data (where spatial indexes like kd-trees do not perform well) is Locality Sensitive Hashing (LSH), an approximation algorithm for finding similar objects.
In this paper, we describe a new variant of LSH, called Parallel LSH (PLSH) designed to be extremely efficient, capable of scaling out on multiple nodes and multiple cores, and which supports high-throughput streaming of new data. Our approach employs several novel ideas, including: cache-conscious hash table layout, using a 2-level merge algorithm for hash table construction; an efficient algorithm for duplicate elimination during hash-table querying; an insert-optimized hash table structure and efficient data expiration algorithm for streaming data; and a performance model that accurately estimates performance of the algorithm and can be used to optimize parameter settings. We show that on a workload where we perform similarity search on a dataset of > 1 Billion tweets, with hundreds of millions of new tweets per day, we can achieve query times of 1-2.5 ms. We show that this is an order of magnitude faster than existing indexing schemes, such as inverted indexes. To the best of our knowledge, this is the fastest implementation of LSH, with table construction times up to 3.7× faster and query times that are 8.3× faster than a basic implementation.
Anti-caching
Authors: DeBrabant Justin , Pavlo Andrew , Tu Stephen , Stonebraker Michael , Zdonik Stan 
Published: June 2014

The traditional wisdom for building disk-based relational database management systems (DBMS) is to organize data in heavily-encoded blocks stored on disk, with a main memory block cache. In order to improve performance given high disk latency, these systems use a multi-threaded architecture with dynamic record-level locking that allows multiple transactions to access the database at the same time. Previous research has shown that this results in substantial overhead for on-line transaction processing (OLTP) applications [15].
The next generation DBMSs seek to overcome these limitations with architecture based on main memory resident data. To overcome the restriction that all data fit in main memory, we propose a new technique, called anti-caching, where cold data is moved to disk in a transactionally-safe manner as the database grows in size. Because data initially resides in memory, an anti-caching architecture reverses the traditional storage hierarchy of disk-based systems. Main memory is now the primary storage device.
We implemented a prototype of our anti-caching proposal in a high-performance, main memory OLTP DBMS and performed a series of experiments across a range of database sizes, workload skews, and read/write mixes. We compared its performance with an open-source, disk-based DBMS optionally fronted by a distributed main memory cache. Our results show that for higher skewed workloads the anti-caching architecture has a performance advantage over either of the other architectures tested of up to 9× for a data size 8× larger than memory.
Aggregation and ordering in factorised databases
Authors: Bakibayev Nurzhan , Kočiský Tomáš , Olteanu Dan , Závodný Jakub 
Published: June 2014

A common approach to data analysis involves understanding and manipulating succinct representations of data. In earlier work, we put forward a succinct representation system for relational data called factorised databases and reported on the main-memory query engine FDB for select-project-join queries on such databases.
In this paper, we extend FDB to support a larger class of practical queries with aggregates and ordering. This requires novel optimisation and evaluation techniques. We show how factorisation coupled with partial aggregation can effectively reduce the number of operations needed for query evaluation. We also show how factorisations of query results can support enumeration of tuples in desired orders as efficiently as listing them from the unfactorised, sorted results.
We experimentally observe that FDB can outperform off-the-shelf relational engines by orders of magnitude.
Fast iterative graph computation with block updates
Authors: Xie Wenlei , Wang Guozhang , Bindel David , Demers Alan , Gehrke Johannes 
Published: June 2014

Scaling iterative graph processing applications to large graphs is an important problem. Performance is critical, as data scientists need to execute graph programs many times with varying parameters. The need for a high-level, high-performance programming model has inspired much research on graph programming frameworks.
In this paper, we show that the important class of computationally light graph applications - applications that perform little computation per vertex - has severe scalability problems across multiple cores as these applications hit an early "memory wall" that limits their speedup. We propose a novel block-oriented computation model, in which computation is iterated locally over blocks of highly connected nodes, significantly improving the amount of computation per cache miss. Following this model, we describe the design and implementation of a block-aware graph processing runtime that keeps the familiar vertex-centric programming paradigm while reaping the benefits of block-oriented execution. Our experiments show that block-oriented execution significantly improves the performance of our framework for several graph applications.
Regulation of meiotic entry and gonadal sex differentiation in the human: normal and disrupted signaling
Authors: Jørgensen Anne , Rajpert-De Meyts Ewa 
Published: June 2014

AbstractMeiosis is a unique type of cell division that is performed only by germ cells to form haploid gametes. The switch from mitosis to meiosis exhibits a distinct sex-specific difference in timing, with female germ cells entering meiosis during fetal development and male germ cells at puberty when spermatogenesis is initiated. During early fetal development, bipotential primordial germ cells migrate to the forming gonad where they remain sexually indifferent until the sex-specific differentiation of germ cells is initiated by cues from the somatic cells. This irreversible step in gonadal sex differentiation involves the initiation of meiosis in fetal ovaries and prevention of meiosis in the germ cells of fetal testes. During the last decade, major advances in the understanding of meiosis regulation have been accomplished, with the discovery of retinoic acid as an inducer of meiosis being the most prominent finding. Knowledge about the molecular mechanisms regulating meiosis signaling has mainly been established by studies in rodents, while this has not yet been extensively investigated in humans. In this review, the current knowledge about the regulation of meiosis signaling is summarized and placed in the context of fetal gonad development and germ cell differentiation, with emphasis on results obtained in humans. Furthermore, the consequences of dysregulated meiosis signaling in humans are briefly discussed in the context of selected pathologies, including testicular germ cell cancer and some forms of male infertility.
Decomposable Leavitt path algebras for arbitrary graphs
Authors: Aranda Pino Gonzalo , Nasr-Isfahani Alireza 
Published: June 2014

Abstract
For any field K and for a completely arbitrary graph E, we characterize the Leavitt path algebras L

K
(E) that are indecomposable (as a direct sum of two-sided ideals) in terms of the underlying graph. When the algebra decomposes, it actually does so as a direct sum of Leavitt path algebras for some suitable graphs. Under certain finiteness conditions, a unique indecomposable decomposition exists.
Response of Sunflower Cultivars to Deficit Irrigation
Authors: Safahani Langeroodi Ali Reza , Kamkar Behnam , Teixeira da Silva Jaime A. , Ataei Mehrdad 
Published: June 2014

Abstract
A 2-year study was conducted to determine the response of four sunflower cultivars (Master, Lakumka, Favorite and Berezanski) to different irrigation regimes: 45 (control), 60, 75 and 90% (I1–I4) of maximum allowable depletion (MAD) of available soil water (ASW). Severe deficit irrigation (I3 and I4) significantly decreased water-use efficiency, radiation use efficiency, yield and yield-related components. The results also showed that water deficit, compared to full-irrigated treatment (I1), increased the activity of all antioxidant enzymes in leaves. Master had the highest seed yield in full and limited irrigation as well as the highest antioxidant enzymes content. Sunflower plants extracted most of the soil moisture from 0 to 50 cm soil layer. Therefore, it is recommended that only the 0–50 cm soil profile be considered for scheduling irrigation. Measured and simulated results revealed a special irrigation regime threshold for each cultivar with respect to seed yield. The response rate to irrigation regime ceased in higher irrigation rates as I
join (65, 63, 65 and 70% MAD for Master, Lakumka, Favorite and Berezanski, respectively). Moreover, all estimated I
join for all cultivars were higher than the current recommendation of 50% MAD. This shows the ability to sustain the yield of these sunflower cultivars in the study region under deficit irrigation. The seed yield of all four cultivars tended to respond similarly to irrigation in both years, but Master was more efficient than the remaining three cultivars with respect to the response to diverse treatments.
Comparison of Heat Treatments on the Toughness of 1.7Ni-1.5Cu-0.5Mo Pre-alloyed P/M Steels
Authors: Güral Ahmet , Türkan Mustafa 
Published: June 2014

AbstractEffects of quenching plus tempering and intercritical annealing plus quenching heat treatments on the impact toughness properties of 1.7Ni-1.5Cu-0.5Mo pre-alloyed powder metallurgy steels with 0.2 (in mass%) graphite were investigated. Specimens were prepared by pressing at 670 MPa and sintering at 1250 °C. Different heat treatments, namely quenching and tempering, directly intercritically annealing and fully austenization plus intercritically annealing were carried out on the sintered specimens. The results showed that the impact toughness decreased with increasing intercritical annealing temperature in ferrite plus martensite dual phase powder metallurgy steels and with increasing tempering temperature in the quenched plus tempered specimens. Besides, impact toughness of fully austenizated plus intercritically annealed specimens was higher than those of quenched plus tempered and directly intercritically annealed specimens at the same hardness levels.
Deadenylation—a piece of PANcake
Authors: Stubbs Milton T , Wahle Elmar 
Published: June 2014

Pan is a poly(A)‐specific 3′ exoribonuclease that, together with the CCR4‐NOT complex, is responsible for initiating and controlling mRNA decay by degradation of the poly(A) tail. Now, more than twenty years after the enzyme's discovery, a surge of recent papers, including one in this issue of The EMBO Journal (Wolf et al, ) has revealed details of its unusual asymmetric structure and aspects of its mode of substrate binding.