bluuebunny/crossref_metadata_2025 huggingface dataset:
Systems for big-graphs
Authors: Khan Arijit , Elnikety Sameh
Published: May 2015

Graphs have become increasingly important to represent highly-interconnected structures and schema-less data including the World Wide Web, social networks, knowledge graphs, genome and scientific databases, medical and government records. The massive scale of graph data easily overwhelms the main memory and computation resources on commodity servers. In these cases, achieving low latency and high throughput requires partitioning the graph and processing the graph data in parallel across a cluster of servers. However, the software and and hardware advances that have worked well for developing parallel databases and scientific applications are not necessarily effective for big-graph problems. Graph processing poses interesting system challenges: graphs represent relationships which are usually irregular and unstructured; and therefore, the computation and data access patterns have poor locality. Hence, the last few years has seen an unprecedented interest in building systems for big-graphs by various communities including databases, systems, semantic web, machine learning, and operations research. In this tutorial, we discuss the design of the emerging systems for processing of big-graphs, key features of distributed graph algorithms, as well as graph partitioning and workload balancing techniques. We emphasize the current challenges and highlight some future research directions.
Causality and explanations in databases
Authors: Meliou Alexandra , Roy Sudeepa , Suciu Dan
Published: May 2015

With the surge in the availability of information, there is a great demand for tools that assist users in understanding their data. While today's exploration tools rely mostly on data visualization, users often want to go deeper and understand the underlying causes of a particular observation. This tutorial surveys research on causality and explanation for data-oriented applications. We will review and summarize the research thus far into causality and explanation in the database and AI communities, giving researchers a snapshot of the current state of the art on this topic, and propose a unified framework as well as directions for future research. We will cover both the theory of causality/explanation and some applications; we also discuss the connections with other topics in database research like provenance, deletion propagation, why-not queries, and OLAP techniques.
Datacenters as computers
Authors: Venkataraman Shivakumar , Agrawal Divyakant
Published: May 2015

In this collaborative keynote address, we will share Google's experience in building a scalable data infrastructure that leverages datacenters for managing Google's advertising data over the last decade. In order to support the massive online advertising platform at Google, the data infrastructure must simultaneously support both transactional and analytical workloads. The focus of this talk will be to highlight how the datacenter architecture and the cloud computing paradigm has enabled us to manage the exponential growth in data volumes and user queries, make our services highly available and fault tolerant to massive datacenter outages, and deliver results with very low latencies. We note that other Internet companies have also undergone similar growth in data volumes and user queries. In fact, this phenomenon has resulted in at least two new terms in the technology lexicon:
big data
and
cloud computing.
Cloud computing (and datacenters) have been largely responsible for scaling the data volumes from terabytes range just a few years ago to now reaching in the exabyte range over the next couple of years. Delivering solutions at this scale that are fault-tolerant, latency sensitive, and highly available requires a combination of research advances with engineering ingenuity at Google and elsewhere. Next, we will try to answer the following question: is a datacenter just another (very large) computer? Or, does it fundamentally change the design principles for data-centric applications and systems. We will conclude with some of the unique research challenges that need to be addressed in order to sustain continuous growth in data volumes while supporting high throughput and low latencies.
Breaking the chains
Authors: Markl Volker
Published: May 2015

Data management research, systems, and technologies have drastically improved the availability of data analysis capabilities, particularly for non-experts, due in part to
low-entry barriers
and
reduced ownership costs
(e.g., for data management infrastructures and applications). Major reasons for the widespread success of database systems and today's multi-billion dollar data management market include
data independence
, separating physical representation and storage from the actual information, and
declarative languages
, separating the program specification from its intended execution environment. In contrast, today's big data solutions do not offer data independence and declarative specification. As a result, big data technologies are mostly employed in newly-established companies with IT-savvy employees or in large well-established companies with big IT departments. We argue that current big data solutions will continue to fall short of widespread adoption, due to usability problems, despite the fact that in-situ data analytics technologies achieve a good degree of schema independence. In particular, we consider the lack of a declarative specification to be a major road-block, contributing to the scarcity in available data scientists available and limiting the application of big data to the IT-savvy industries. In particular, data scientists currently have to spend a lot of time on tuning their data analysis programs for specific data characteristics and a specific execution environment. We believe that the research community needs to bring the powerful concepts of declarative specification to current data analysis systems, in order to achieve the broad big data technology adoption and effectively deliver the promise that novel big data technologies offer.
Design and implementation of a real-time interactive analytics system for large spatio-temporal data
Authors: Zhang Shiming , Yang Yin , Fan Wei , Winslett Marianne
Published: May 2015

In real-time interactive data analytics, the user expects to receive the results of each query within a short time period such as seconds. This is especially challenging when the data is big (e.g., on the scale of petabytes), and the analytics system runs on top of cloud infrastructure (e.g., thousands of interconnected commodity servers). We have been building such a system, called OceanRT, for managing large spatio-temporal data such as call logs and mobile web browsing records collected by a telecommunication company. Although there already exist systems for querying big data in real time, OceanRT's performance stands out due to several novel designs and components that address key efficiency and scalability issues that were largely overlooked in existing systems. First, OceanRT makes extensive use of software RDMA one-sided operations, which reduce networking costs without requiring specialized hardware. Second, OceanRT exploits the parallel computing capabilities of each node in the cloud through a novel architecture consisting of Access-Query Engines (AQEs) connected with minimal overhead. Third, OceanRT contains a novel storage scheme that optimizes for queries with joins and multi-dimensional selections, which are common for large spatio-temporal data. Experiments using the TPC-DS benchmark show that OceanRT is usually more than an order of magnitude faster than the current state-of-the-art systems.
Errata for "building efficient query engines in a high-level language"
Authors: Klonatos Yannis , Koch Christoph , Rompf Tiark , Chafi Hassan
Published: May 2015

This is in response to recent feedback from our peers that calls for a number of clarifications regarding the experimental section of our paper.
Auto-approximation of graph computing
Authors: Shang Zechao , Yu Jeffrey Xu
Published: May 2015

In the big data era, graph computing is one of the challenging issues because there are numerous large graph datasets emerging from real applications. A question is: do we need to know the final exact answer for a large graph? When it is impossible to know the exact answer in a limited time, is it possible to approximate the final answer in an automatic and systematic way without having to designing new approximate algorithms? The main idea behind the question is: it is more important to find out something meaningful quick from a large graph, and we should focus on finding a way of making use of large graphs instead of spending time on designing approximate algorithms. In this paper, we give an innovative approach which automatically and systematically synthesizes a program to approximate the original program. We show that we can give users some answers with reasonable accuracy and high efficiency for a wide spectrum of graph algorithms, without having to know the details of graph algorithms. We have conducted extensive experimental studies using many graph algorithms that are supported in the existing graph systems and large real graphs. Our extensive experimental results reveal that our automatically approximating approach is highly feasible.
Optimizing the chase
Authors: Konstantinidis George , Ambite José Luis
Published: May 2015

We are interested in scalable data integration and data exchange under constraints/dependencies. In data exchange the problem is how to materialize a target database instance, satisfying the source-to-target and target dependencies, that provides the certain answers. In data integration, the problem is how to rewrite a query over the target schema into a query over the source schemas that provides the certain answers. In both these problems we make use of the chase algorithm, the main tool to reason with dependencies. Our first contribution is to introduce the
frugal
chase, which produces smaller universal solutions than the standard chase, still remaining polynomial in data complexity. Our second contribution is to use the frugal chase to scale up query answering using views under LAV weakly acyclic target constraints, a useful language capturing RDF/S. The latter problem can be reduced to query rewriting using views without constraints by chasing the source-to-target mappings with the target constraints. We construct a compact graph-based representation of the mappings and the constraints and develop an efficient algorithm to run the frugal chase on this representation. We show experimentally that our approach scales to large problems, speeding up the compilation of the dependencies into the mappings by close to 2 and 3 orders of magnitude, compared to the standard and the core chase, respectively. Compared to the standard chase, we improve online query rewriting time by a factor of 3, while producing equivalent, but smaller, rewritings of the original query.
AsterixDB
Authors: Alsubaiee Sattam , Altowim Yasser , Altwaijry Hotham , Behm Alexander , Borkar Vinayak , Bu Yingyi , Carey Michael , Cetindil Inci , Cheelangi Madhusudan , Faraaz Khurram , Gabrielova Eugenia , Grover Raman , Heilbron Zachary , Kim Young-Seok , Li Chen , Li Guangqiang , Ok Ji Mahn , Onose Nicola , Pirzadeh Pouria , Tsotras Vassilis , Vernica Rares , Wen Jian , Westmann Till
Published: May 2015

AsterixDB is a new, full-function BDMS (Big Data Management System) with a feature set that distinguishes it from other platforms in today's open source Big Data ecosystem. Its features make it well-suited to applications like web data warehousing, social data storage and analysis, and other use cases related to Big Data. AsterixDB has a flexible NoSQL style data model; a query language that supports a wide range of queries; a scalable runtime; partitioned, LSM-based data storage and indexing (including B
+
-tree, R-tree, and text indexes); support for external as well as natively stored data; a rich set of built-in types; support for fuzzy, spatial, and temporal types and queries; a built-in notion of data feeds for ingestion of data; and transaction support akin to that of a NoSQL store.

Development of AsterixDB began in 2009 and led to a mid-2013 initial open source release. This paper is the first complete description of the resulting open source AsterixDB system. Covered herein are the system's data model, its query language, and its software architecture. Also included are a summary of the current status of the project and a first glimpse into how AsterixDB performs when compared to alternative technologies, including a parallel relational DBMS, a popular NoSQL store, and a popular Hadoop-based SQL data analytics platform, for things that both technologies can do. Also included is a brief description of some initial trials that the system has undergone and the lessons learned (and plans laid) based on those early "customer" engagements.
Trajectory simplification
Authors: Long Cheng , Wong Raymond Chi-Wing , Jagadish H. V.
Published: May 2015

Trajectory data is central to many applications with moving objects. Raw trajectory data is usually very large, and so is simplified before it is stored and processed. Many trajectory simplification notions have been proposed, and among them, the direction-preserving trajectory simplification (DPTS) which aims at protecting the direction information has been shown to perform quite well. However, existing studies on DPTS require users to specify an error tolerance which users might not know how to set properly in some cases (e.g., the error tolerance could only be known at some future time and simply setting one error tolerance does not meet the needs since the simplified trajectories would usually be used in many different applications which accept different error tolerances). In these cases, a better solution is to minimize the error while achieving a pre-defined simplification size. For this purpose, in this paper, we define a problem called
Min-Error
and develop two exact algorithms and one 2-factor approximate algorithm for the problem. Extensive experiments on real datasets verified our algorithms.
Scaling up crowd-sourcing to very large datasets
Authors: Mozafari Barzan , Sarkar Purna , Franklin Michael , Jordan Michael , Madden Samuel
Published: May 2015

Crowd-sourcing has become a popular means of acquiring labeled data for many tasks where humans are more accurate than computers, such as image tagging, entity resolution, and sentiment analysis. However, due to the time and cost of human labor, solutions that rely solely on crowd-sourcing are often limited to small datasets (i.e., a few thousand items). This paper proposes algorithms for integrating machine learning into crowd-sourced databases in order to combine the accuracy of human labeling with the speed and cost-effectiveness of machine learning classifiers. By using
active learning
as our optimization strategy for labeling tasks in crowd-sourced databases, we can minimize the number of questions asked to the crowd, allowing crowd-sourced applications to
scale
(i.e., label much larger datasets at lower costs).

Designing active learning algorithms for a crowd-sourced database poses many practical challenges: such algorithms need to be generic, scalable, and easy to use, even for practitioners who are not machine learning experts. We draw on the theory of nonparametric bootstrap to design, to the best of our knowledge, the first active learning algorithms that meet all these requirements.

Our results, on 3 real-world datasets collected with Amazons Mechanical Turk, and on 15 UCI datasets, show that our methods on average ask 1--2 orders of magnitude fewer questions than the baseline, and 4.5--44
×
fewer than existing active learning algorithms.
Pregelix
Authors: Bu Yingyi , Borkar Vinayak , Jia Jianfeng , Carey Michael J. , Condie Tyson
Published: May 2015

There is a growing need for distributed graph processing systems that are capable of gracefully scaling to very large graph datasets. Unfortunately, this challenge has not been easily met due to the intense memory pressure imposed by process-centric, message passing designs that many graph processing systems follow. Pregelix is a new open source distributed graph processing system that is based on an iterative dataflow design that is better tuned to handle both in-memory and out-of-core workloads. As such, Pregelix offers improved performance characteristics and scaling properties over current open source systems (e.g., we have seen up to 15X speedup compared to Apache Giraph and up to 35X speedup compared to distributed GraphLab), and more effective use of available machine resources to support Big(ger) Graph Analytics.
Profiling R on a contemporary processor
Authors: Sridharan Shriram , Patel Jignesh M.
Published: May 2015

R is a popular data analysis language, but there is scant experimental data characterizing the run-time profile of R programs. This paper addresses this limitation by systematically cataloging where time is spent when running R programs. Our evaluation using four different workloads shows that when analyzing large datasets, R programs a) spend more than 85% of their time in processor stalls, which leads to slower execution times, b) trigger the garbage collector frequently, which leads to higher memory stalls, and c) create a large number of unnecessary temporary objects that causes R to swap to disk quickly even for datasets that are far smaller than the available main memory. Addressing these issues should allow R programs to run faster than they do today, and allow R to be used for analyzing even larger datasets. As outlined in this paper, the results presented in this paper motivate a number of future research investigations in the database, architecture, and programming language communities. All data and code that is used in this paper (which includes the R programs, and changes to the R source code for instrumentation) can be found at: http://quickstep.cs.wisc.edu/dissecting-R/.
Hear the whole story
Authors: Wu Ting , Chen Lei , Hui Pan , Zhang Chen Jason , Li Weikai
Published: May 2015

The recent surge in popularity of crowdsourcing has brought with it a new opportunity for engaging human intelligence in the process of data analysis. Crowdsourcing provides a fundamental mechanism for enabling online workers to participate in tasks that are either too difficult to be solved solely by a computer or too expensive to employ experts to perform. In the field of social science, four elements are required to form a wise crowd - Diversity of Opinion, Independence, Decentralization and Aggregation. However, while the other three elements are already studied and implemented in current crowdsourcing platforms, the 'Diversity of Opinion' has not been functionally enabled. In this paper, we address the algorithmic optimizations towards the
diversity of opinion
of crowdsourcing marketplaces.

From a computational perspective, in order to build a wise crowd, we need to quantitatively modeling the diversity, and take it into consideration for constructing the crowd. In a crowdsourcing marketplace, we usually encounter two basic paradigms for worker selection: building a crowd to wait for tasks to come and selecting workers for a given task. Therefore, we propose our Similarity-driven Model (S-Model) and Task-driven Model (T-Model) for both of the paradigms. Under both of the models, we propose efficient and effective algorithms to enlist a budgeted number of workers, which have the optimal diversity. We have verified our solutions with extensive experiments on both synthetic datasets and real data sets.
Reverse k nearest neighbors query processing
Authors: Yang Shiyu , Cheema Muhammad Aamir , Lin Xuemin , Wang Wei
Published: May 2015

Given a set of users, a set of facilities and a query facility
q
, a reverse
k
nearest neighbors (R
k
NN) query returns every user
u
for which the query is one of its
k
closest facilities. R
k
NN queries have been extensively studied under a variety of settings and many sophisticated algorithms have been proposed to answer these queries. However, the existing experimental studies suffer from a few limitations. For example, some studies
estimate
the I/O cost by charging a fixed penalty per I/O and we show that this may be misleading. Also, the existing studies either use an extremely small buffer or no buffer at all which puts some algorithms at serious disadvantage. We show that the performance of these algorithms is significantly improved even when a small buffer (containing 100 pages) is used. Finally, in each of the existing studies, the proposed algorithm is mainly compared only with its predecessor assuming that it was the best algorithm at the time which is not necessarily true as shown in our experimental study. Motivated by these limitations, we present a comprehensive experimental study that addresses these limitations and compares some of the most notable algorithms under a wide variety of settings. Furthermore, we also present a carefully developed filtering strategy that significantly improves TPL which is one of the most popular R
k
NN algorithms. Specifically, the optimized version is up to 20 times faster than the original version and reduces its I/O cost up to two times.
Errata for "Crowdsourcing algorithms for entity resolution"
Authors: Vesdapunt Norases , Bellare Kedar , Dalvi Nilesh
Published: May 2015

We discovered that there was a duplicate figure in our paper. We accidentally put Figure 13(b) for Figure 12(b). We have provided the correct Figure 12(b) above (See Figure 1). Figure 1 plots the recall of various strategies as a function of the number of questions asked for Places dataset. There was no error in the discussion in our paper (See Section 6.2.1 in our paper for more details).
Event pattern matching over graph streams
Authors: Song Chunyao , Ge Tingjian , Chen Cindy , Wang Jie
Published: May 2015

A graph is a fundamental and general data structure underlying all data applications. Many applications today call for the management and query capabilities directly on graphs. Real time graph streams, as seen in road networks, social and communication networks, and web requests, are such applications. Event pattern matching requires the awareness of graph structures, which is different from traditional complex event processing. It also requires a focus on the dynamicity of the graph, time order constraints in patterns, and online query processing, which deviates significantly from previous work on subgraph matching as well. We study the semantics and efficient online algorithms for this important and intriguing problem, and evaluate our approaches with extensive experiments over real world datasets in four different domains.
Fast failure recovery in distributed graph processing systems
Authors: Shen Yanyan , Chen Gang , Jagadish H. V. , Lu Wei , Ooi Beng Chin , Tudor Bogdan Marius
Published: May 2015

Distributed graph processing systems increasingly require many compute nodes to cope with the requirements imposed by contemporary graph-based Big Data applications. However, increasing the number of compute nodes increases the chance of node failures. Therefore, provisioning an efficient failure recovery strategy is critical for distributed graph processing systems. This paper proposes a novel recovery mechanism for distributed graph processing systems that parallelizes the recovery process. The key idea is to partition the part of the graph that is lost during a failure among a subset of the remaining nodes. To do so, we augment the existing checkpoint-based and log-based recovery schemes with a partitioning mechanism that is sensitive to the total computation and communication cost of the recovery process. Our implementation on top of the widely used Giraph system outperforms checkpoint-based recovery by up to 30x on a cluster of 40 compute nodes.
Coordination avoidance in database systems
Authors: Bailis Peter , Fekete Alan , Franklin Michael J. , Ghodsi Ali , Hellerstein Joseph M. , Stoica Ion
Published: May 2015

Minimizing coordination, or blocking communication between concurrently executing operations, is key to maximizing scalability, availability, and high performance in database systems. However, uninhibited coordination-free execution can compromise application correctness, or consistency. When is coordination necessary for correctness? The classic use of serializable transactions is sufficient to maintain correctness but is not necessary for all applications, sacrificing potential scalability. In this paper, we develop a formal framework, invariant confluence, that determines whether an application requires coordination for correct execution. By operating on application-level invariants over database states (e.g., integrity constraints), invariant confluence analysis provides a necessary and sufficient condition for safe, coordination-free execution. When programmers specify their application invariants, this analysis allows databases to coordinate only when anomalies that might violate invariants are possible. We analyze the invariant confluence of common invariants and operations from real-world database systems (i.e., integrity constraints) and applications and show that many are invariant confluent and therefore achievable without coordination. We apply these results to a proof-of-concept coordination-avoiding database prototype and demonstrate sizable performance gains compared to serializable execution, notably a 25-fold improvement over prior TPC-C New-Order performance on a 200 server cluster.
QuickFOIL
Authors: Zeng Qiang , Patel Jignesh M. , Page David
Published: May 2015

Inductive Logic Programming (ILP) is a classic machine learning technique that learns first-order rules from relational-structured data. However, to-date most ILP systems can only be applied to small datasets (tens of thousands of examples). A long-standing challenge in the field is to scale ILP methods to larger data sets. This paper presents a method called QuickFOIL that addresses this limitation. QuickFOIL employs a new scoring function and a novel pruning strategy that enables the algorithm to find high-quality rules. QuickFOIL can also be implemented as an in-RDBMS algorithm. Such an implementation presents a host of query processing and optimization challenges that we address in this paper. Our empirical evaluation shows that QuickFOIL can scale to large datasets consisting of hundreds of millions tuples, and is often more than order of magnitude more efficient than other existing approaches.
Inferring continuous dynamic social influence and personal preference for temporal behavior prediction
Authors: Zhang Jun , Wang Chaokun , Wang Jianmin , Yu Jeffrey Xu
Published: May 2015

It is always attractive and challenging to explore the intricate behavior data and uncover people's motivations, preference and habits, which can greatly benefit many tasks including link prediction, item recommendation, etc. Traditional work usually studies people's behaviors without time information in a static or discrete manner, assuming the underlying factors stay invariant in a long period. However, we believe people's behaviors are dynamic, and the contributing factors including the social influence and personal preference for behaviors are
varying continuously over time.
Such continuous dynamics convey important knowledge about people's behavior patterns; ignoring them would lead to inaccurate models.

In this work, we address the continuous dynamic modeling of temporal behaviors. To model the fully continuous temporal dynamics of behaviors and the underlying factors, we propose the DP-Space, a dynamic preference probability space, which can capture their smooth variation in various shapes over time with flexible basis functions. Upon that we propose a generative dynamic behavior model, ConTyor, which considers the temporal item-adoption behaviors as joint effect of dynamic social influence and varying personal preference over continuous time. We also develop effective inference methods for ConTyor and present its applications.

We conduct a comprehensive experimental study using real-world datasets to evaluate the effectiveness of our model and the temporal modeling. Results verify that ConTyor outperforms existing state-of-the-art static and temporal models in behavior predictions. Moreover, in our detailed study on temporal modeling, we show that temporal modeling is superior to static approaches and modeling over continuous time is further better than that over discrete time. We also demonstrate that the ancient behavior data can still become important and beneficial if modeled well.
Scalable topical phrase mining from text corpora
Authors: El-Kishky Ahmed , Song Yanglei , Wang Chi , Voss Clare R. , Han Jiawei
Published: May 2015

While most topic modeling algorithms model text corpora with unigrams, human interpretation often relies on inherent grouping of terms into phrases. As such, we consider the problem of discovering topical phrases of mixed lengths. Existing work either performs post processing to the results of unigram-based topic models, or utilizes complex n-gram-discovery topic models. These methods generally produce low-quality topical phrases or suffer from poor scalability on even moderately-sized datasets. We propose a different approach that is both computationally efficient and effective. Our solution combines a novel phrase mining framework to segment a document into single and multi-word phrases, and a new topic model that operates on the induced document partition. Our approach discovers high quality topical phrases with negligible extra cost to the bag-of-words topic model in a variety of datasets including research publication titles, abstracts, reviews, and news articles.
DREAM
Authors: Hammoud Mohammad , Rabbou Dania Abed , Nouri Reza , Beheshti Seyed-Mehdi-Reza , Sakr Sherif
Published: May 2015

The Resource Description Framework (RDF) and SPARQL query language are gaining wide popularity and acceptance. In this paper, we present DREAM, a distributed and adaptive RDF system. As opposed to existing RDF systems, DREAM avoids partitioning RDF datasets and partitions only SPARQL queries. By not partitioning datasets, DREAM offers a general paradigm for different types of pattern matching queries, and entirely averts intermediate data shuffling (only auxiliary data are shuffled). Besides, by partitioning queries, DREAM presents an adaptive scheme, which automatically runs queries on various numbers of machines depending on their complexities. Hence, in essence DREAM combines the advantages of the state-of-the-art centralized and distributed RDF systems, whereby data communication is avoided and cluster resources are aggregated. Likewise, it precludes their disadvantages, wherein system resources are limited and communication overhead is typically hindering. DREAM achieves all its goals via employing a novel graph-based, rule-oriented query planner and a new cost model. We implemented DREAM and conducted comprehensive experiments on a private cluster and on the Amazon EC2 platform. Results show that DREAM can significantly outperform three related popular RDF systems.
Shared execution of recurring workloads in MapReduce
Authors: Lei Chuan , Zhuang Zhongfang , Rundensteiner Elke A. , Eltabakh Mohamed
Published: May 2015

With the increasing complexity of data-intensive MapReduce workloads, Hadoop must often accommodate hundreds or even thousands of recurring analytics queries that periodically execute over frequently updated datasets, e.g., latest stock transactions, new log files, or recent news feeds. For many applications, such recurring queries come with user-specified service-level agreements (SLAs), commonly expressed as the maximum allowed latency for producing results before their merits decay. The recurring nature of these emerging workloads combined with their SLA constraints make it challenging to share and optimize their execution. While some recent efforts on multi-job optimization in MapReduce have emerged, they focus on only sharing work among ad-hoc jobs on static datasets. Unfortunately, these sharing techniques neither take the recurring nature of the queries into account nor guarantee the satisfaction of the SLA requirements. In this work, we propose the first scalable multi-query sharing engine tailored for recurring workloads in the MapReduce infrastructure, called
"Helix"
. Helix deploys new sliced window-alignment techniques to create sharing opportunities among recurring queries without introducing additional I/O overheads or unnecessary data scans. And then, Helix introduces a cost/benefit model for creating a sharing plan among the recurring queries, and a scheduling strategy for executing them to maximize the SLA satisfaction. Our experimental results over real-world datasets confirm that Helix significantly outperforms the state-of-art techniques by an order of magnitude.
Persistent B
+
-trees in non-volatile main memory
Authors: Chen Shimin , Jin Qin
Published: May 2015

Computer systems in the near future are expected to have Non-Volatile Main Memory (NVMM), enabled by a new generation of Non-Volatile Memory (NVM) technologies, such as Phase Change Memory (PCM), STT-MRAM, and Memristor. The non-volatility property has the promise to persist in-memory data structures for instantaneous failure recovery. However, realizing such promise requires a careful design to ensure that in-memory data structures are in known consistent states after failures.

This paper studies persistent in-memory B
+
-Trees as B
+
-Trees are widely used in database and data-intensive systems. While traditional techniques, such as undo-redo logging and shadowing, support persistent B
+
-Trees, we find that they incur drastic performance overhead because of extensive NVM writes and CPU cache flush operations. PCM-friendly B
+
-Trees with unsorted leaf nodes help mediate this issue, but the remaining overhead is still large. In this paper, we propose write atomic B
+
-Trees (wB
+
-Trees), a new type of main-memory B
+
-Trees, that aim to reduce such overhead as much as possible. wB
+
-Tree nodes employ a small indirect slot array and/or a bitmap so that most insertions and deletions do not require the movement of index entries. In this way, wB
+
-Trees can achieve node consistency either through atomic writes in the nodes or by redo-only logging. We model fast NVM using DRAM on a real machine and model PCM using a cycle-accurate simulator. Experimental results show that compared with previous persistent B
+
-Tree solutions, wB
+
-Trees achieve up to 8.8x speedups on DRAM-like fast NVM and up to 27.1x speedups on PCM for insertions and deletions while maintaining good search performance. Moreover, we replaced Memcached's internal hash index with tree indices. Our real machine Memcached experiments show that wB
+
-Trees achieve up to 3.8X improvements over previous persistent tree structures with undo-redo logging or shadowing.
Viral marketing meets social advertising
Authors: Aslay Cigdem , Lu Wei , Bonchi Francesco , Goyal Amit , Lakshmanan Laks V. S.
Published: May 2015

Social advertisement is one of the fastest growing sectors in the digital advertisement landscape: ads in the form of promoted posts are shown in the feed of users of a social networking platform, along with normal social posts; if a user clicks on a promoted post, the host (social network owner) is paid a fixed amount from the advertiser. In this context, allocating ads to users is typically performed by maximizing click-through-rate, i.e., the likelihood that the user will click on the ad. However, this simple strategy fails to leverage the fact the ads can propagate virally through the network, from endorsing users to their followers.

In this paper, we study the problem of allocating ads to users through the viral-marketing lenses. We show that allocation that takes into account the propensity of ads for viral propagation can achieve significantly better performance. However, uncontrolled virality could be undesirable for the host as it creates room for exploitation by the advertisers: hoping to tap uncontrolled virality, an advertiser might declare a lower budget for its marketing campaign, aiming at the same large outcome with a smaller cost.

This creates a challenging trade-off: on the one hand, the host aims at leveraging virality and the network effect to improve advertising efficacy, while on the other hand the host wants to avoid giving away free service due to uncontrolled virality. We formalize this as the problem of ad allocation with minimum regret, which we show is NP-hard and inapproximable w.r.t. any factor. However, we devise an algorithm that provides approximation guarantees w.r.t. the total budget of all advertisers. We develop a scalable version of our approximation algorithm, which we extensively test on four real-world data sets, confirming that our algorithm delivers high quality solutions, is scalable, and significantly outperforms several natural baselines.
ALID
Authors: Chu Lingyang , Wang Shuhui , Liu Siyuan , Huang Qingming , Pei Jian
Published: May 2015

Detecting dominant clusters is important in many analytic applications. The state-of-the-art methods find dense subgraphs on the affinity graph as dominant clusters. However, the time and space complexities of those methods are dominated by the construction of affinity graph, which is quadratic with respect to the number of data points, and thus are impractical on large data sets. To tackle the challenge, in this paper, we apply
Evolutionary Game Theory
(EGT) and develop a scalable algorithm, Approximate Localized Infection Immunization Dynamics (ALID). The major idea is to perform Localized Infection Immunization Dynamics (LID) to find dense subgraphs within local ranges of the affinity graph. LID is further scaled up with guaranteed high efficiency and detection quality by an estimated Region of Interest (ROI) and a Candidate Infective Vertex Search method (CIVS). ALID only constructs small local affinity graphs and has time complexity
O
(
C
(
a
*
+
δ
)
n
) and space complexity
O
(
a
*
(
a
*
+
δ
)), where
a
*
is the size of the largest dominant cluster, and
C
«
n
and
δ
«
n
are small constants. We demonstrate by extensive experiments on both synthetic data and real world data that ALID achieves the state-of-the-art detection quality with much lower time and space cost on single machine. We also demonstrate the encouraging parallelization performance of ALID by implementing the Parallel ALID (PALID) on
Apache Spark.
PALID processes 50 million SIFT data points in 2.29 hours, achieving a speedup ratio of 7.51 with 8 executors.
Development of ZP Method for Seurop Pig Carcass Grading in Poland
Authors: Lisiak Dariusz , Borzuta Karol , Janiszewski Piotr , Grześkowiak Eugenia , Powałowski Krzysztof , Samardakiewicz Łukasz , Lisiak Beata
Published: May 2015

In the present study, ZP method for lean meat content (LMC) evaluation in pig carcasses was tested. The experiment was carried out on 141 pigs selected from animals delivered for slaughter to the SKIBA S.A. meat plant located in Chojnice. The selected pigs originated from three country regions, and differed in respect of subcutaneous fat thickness (7-32 mm), carcass weight (60-120 kg) and sex (50% gilts and 50% castrated males). The main result of the study was a rectilinear regression equation for lean meat content assessment. Two linear measurements were used in the equation, i.e. backfat thickness measured on sacral vertebra and thickness of the muscle layer located between the beginning of the cross section of gluteus medius and back edge of the spinal cord. The evaluation error RMSEP was 2.33% and did not exceed the limit defined in EU regulations. Based on the Commission Decision 2011/506/EU the ZP method was approved to be used for pig carcass grading in Poland. A special measuring template was developed for the industrial use of the ZP method.
Pig behaviour in relation to weather conditions – a review
Authors: Olczak Katarzyna , Nowicki Jacek , Klocek Czesław
Published: May 2015

Weather conditions (temperature, humidity, solar radiation, air pressure, wind strength, wind direction and precipitation) have a significant impact on the behaviour of farm animals. Pigs have developed a wide range of thermoregulatory behaviours that are particular for this species. With increases in temperature the most characteristic behaviour for pigs is decreased activity and increased wallowing in wet surfaces. In addition to this, rooting and wallowing are highly influenced by temperature and humidity. The lack of possibility to express these behaviours leads to development of stereotypies. Interestingly, low temperatures do not increase the use of shelter if not in combination with wind or precipitation. Furthermore, wild pigs build stronger nests in severe conditions. Also, resting behaviour and reproduction may be disturbed by high temperatures. There is a negative impact of foehn wind on boars’ libido and semen parameters.
Iodine concentration in Polish consumer milk
Authors: Śliwiński Bogdan , Brzóska Franciszek , Szybiński Zbigniew
Published: May 2015

The aim of this study was monitoring the iodine concentration in Polish consumer milk in the years 2011-2012. The test material used in this study consisted of consumer UHT pasteurized milk with extended shelf life. Six randomly selected cartons of milk with different fat content (from 0.5% to 3.2%) were each purchased from large-sized stores located in 16 cities during the summer and in 13 cities during the cow’s winter feeding period. In total, 167 milk samples were collected. During the summer season, the milk’s iodine content averaged 143 μg iodine kg-1 and ranged from 103 to 196 μg iodine kg-1 (n=96 samples), with a standard deviation (SD) of ±31 and coefficient variability (CV) of 44%. During the winter season, the milk’s iodine content averaged 183 μg iodine kg-1 and ranged from 141 to 236 μg iodine kg-1 (n=77 samples), with a standard deviation (SD) of ±5 and coefficient of variability (%) (CV) of 26%. Iodine levels in Polish consumer milk increased from the last monitoring (2007-2008) from 100 to 143 μg iodine kg-1 in the summer season, and from 147 to 183 μg iodine kg-1 in the winter season (increases of 47% and 24%, respectively).
The efficacy of selected feed additives in the prevention of broiler chicken coccidiosis under natural exposure to Eimeria spp
Authors: Arczewska-Włosek Anna , Świątkiewicz Sylwester
Published: May 2015

The aim of this study was to investigate, under conditions similar to commercial broiler production, the effect of the herbal extract blend (HE) at a quantity of 1 g per kg feed (200 mg of each herbal extract, Allium sativum, Salvia officinalis, Echinacea purpurea, Thymus vulgaris and Origanum

vulgare), used individually or in combination with mannan oligosaccharide (MOS; 1 g per kg feed) or chitosan (3 ml containing 2% deacetylated chitin per kg feed) on the performance parameters of broiler chickens, the results of the slaughter analysis, litter moisture and the number of oocysts excreted in feces. The experiment was conducted on 4,500 broiler chickens of both sexes kept in straw-bedded pens. Chickens were randomly assigned to 5 experimental treatments with 5 replicates (pens) of 180 birds. The experimental design included negative and positive (diclazuril, 1 mg per kg feed) control groups. The examined herbal extract blend used individually during natural exposure to the coccidia improved, compared to the negative control diet, the performance parameters to a greater extent than coccidiostat, lowered the litter moisture content and reduced the oocyst output. Combined dietary supplementation with a herbal extract blend of chitosan or mannan oligosaccharide did not result in further improvement.
Application of The UV-Irradiated Homologous and Heterologous Sperm for Activa Tion of the Rainbow Trout (Oncorhynchus Mykiss) Eggs and Production of the Gynogenetic Stocks
Authors: Dobosz Stefan , Dębowska Marta , Krom Janusz , Jankun Małgorzata , Zalewski Tomasz , Ocalewicz Konrad
Published: May 2015

Meiotic gynogenetic development of the rainbow trout (Oncorhynchus mykiss, Walbaum 1792) was induced in the course of egg activation performed by the UV-irradiated homologous and heterologous (European grayling Thymallus thymallus Linnaeus, 1758) spermatozoa. To recover diploidy in the gynogenetic zygotes, activated eggs were subjected to the high pressure shock in order to inhibit extrusion of the second polar body. Gynogenetic rainbow trout progeny hatched from the eggs activated by the irradiated rainbow trout and grayling milt with similar hatching rates of 28.19% and 29.22%, respectively. However, gynogenetic rainbow trout produced with grayling semen had shown lower survival than gynogenotes provided with the homologous spermatozoa during two years of rearing. Viable hybrids are not produced between rainbow trout and grayling which ensured that fish obtained in this experiment were true gynogenetic progenies. A Robertsonian polymorphism characteristic for the rainbow trout from the studied strain was also observed among the gynogenetic specimens that exhibited diploid chromosome number ranging from 58 to 62 and stable chromosome arm number (FN= 104). No radiation-induced fragments of the paternal chromosomes were observed in the gynogenetic individuals. Fish produced in both experimental variants were genotypic (XX) and phenotypic (gonads) females. The results confirmed that the gynogenetic protocol used in the present research is an efficient means of producing all-female gynogenetic rainbow trout stocks.
Cognition-based multimedia classifier learning
Authors: Kuo Jenny Yichun
Published: May 2015

In a classifier language like Chinese, all the noun phrases with numerals or demonstratives must go with classifiers, for example, liǎng zhī bǐ 兩枝筆 ‘two CL pen.’ Classifiers vary depending on the nouns. This poses a big challenge for learners of Chinese as second language. Cognition-based multimedia and paper materials for Chinese material classifiers were developed and proved to be effective for learners of Chinese as a second language. The experimental group (N = 15) used the multimedia program and the control group (N= 20) received the same information on paper. Both groups made significant progress after a 10-week treatment. The results suggest cognitive principles are helpful for classifier learning in either multimedia or paper format.
Demand-Side Factors Associated with the Purchase of Long-Term Care Insurance
Authors: Unruh Mark A. , Stevenson David G. , Frank Richard G. , Cohen Marc A. , Grabowski David C.
Published: May 2015

Demand-side barriers are known to be important toward explaining the limited purchase of private long-term care insurance (LTCI). In this study, we examine several factors associated with the demand for LTCI including the availability of less costly substitutes (e.g., Medicaid, family), consumer information, and risk perception. Using buyer surveys from 2000, 2005, and 2010, our results suggest that, among individuals not eliminated through medical underwriting, consumer risk perception and the presence of lower cost, imperfect substitutes are strongly associated with the limited purchase of LTCI. These factors were also predictive of the generosity of coverage purchased. If policymakers seek to stimulate demand for LTCI, new public policies might include Medicaid reform, integrating LTCI with Medicare Advantage plans, enhanced LTCI offerings through employers, and targeted informational campaigns.