bluuebunny/crossref_metadata_2025 huggingface dataset:
YZStack
Authors: Wu Sai , Chen Chun , Chen Gang , Chen Ke , Shou Lidan , Cao Hui , Bai He
Published: May 2015

YZStack is our developing solution which implements many well-established big data techniques as selectable modules and allows users to customize their systems as a process of module selection. In particular, it includes an openstack based IaaS (Infrastructure as a Service) layer, a distributed file system based DaaS (Data as a Service) layer, a PaaS (Platform as a Service) layer equipped with parallel processing techniques and a SaaS (Software as a Service) layer with popular data analytic algorithms. Layers of YZStack are loosely connected, so that customization of one layer does not affect the other layers and their interactions. In this paper, we use a smart financial system developed for the Zhejiang Provincial Department of Finance to demonstrate how to leverage YZStack to speed up the implementation of big data system. We also introduce two popular applications of the financial system, economic prediction and detection of improper payment.
Uncertainty aware query execution time prediction
Authors: Wu Wentao , Wu Xi , Hacigümüş Hakan , Naughton Jeffrey F.
Published: May 2015

Predicting query execution time is a fundamental issue underlying many database management tasks. Existing predictors rely on information such as cardinality estimates and system performance constants that are difficult to know exactly. As a result, accurate prediction still remains elusive for many queries. However, existing predictors provide a single, point estimate of the true execution time, but fail to characterize the uncertainty in the prediction. In this paper, we take a first step towards providing uncertainty information along with query execution time predictions. We use the query optimizer's cost model to represent the query execution time as a function of the selectivities of operators in the query plan as well as the constants that describe the cost of CPU and I/O operations in the system. By treating these quantities as random variables rather than constants, we show that with low overhead we can infer the distribution of likely prediction errors. We further show that the estimated prediction errors by our proposed techniques are strongly correlated with the actual prediction errors.
BF-tree
Authors: Athanassoulis Manos , Ailamaki Anastasia
Published: May 2015

The increasing volume of time-based generated data and the shift in storage technologies suggest that we might need to reconsider indexing. Several workloads - like social and service monitoring - often include attributes with implicit clustering because of their time-dependent nature. In addition, solid state disks (SSD) (using flash or other low-level technologies) emerge as viable competitors of hard disk drives (HDD). Capacity and access times of storage devices create a trade-off between SSD and HDD. Slow random accesses in HDD have been replaced by efficient random accesses in SSD, but their available capacity is one or more orders of magnitude more expensive than the one of HDD. Indexing, however, is designed assuming HDD as secondary storage, thus minimizing random accesses at the expense of capacity. Indexing data using SSD as secondary storage requires treating capacity as a scarce resource.

To this end, we introduce approximate tree indexing, which employs probabilistic data structures (Bloom filters) to trade accuracy for size and produce smaller, yet powerful, tree indexes, which we name Bloom filter trees (BF-Trees). BF-Trees exploit pre-existing data ordering or partitioning to offer competitive search performance. We demonstrate, both by an analytical study and by experimental results, that by using workload knowledge and reducing indexing accuracy up to some extent, we can save substantially on capacity when indexing on ordered or partitioned attributes. In particular, in experiments with a synthetic workload, approximate indexing offers 2.22x-48x smaller index footprint with competitive response times, and in experiments with TPCH and a monitoring real-life dataset from an energy company, it offers 1.6x-4x smaller index footprint with competitive search times as well.
ADDICT
Authors: Tözün Pinar , Atta Islam , Ailamaki Anastasia , Moshovos Andreas
Published: May 2015

Recent studies highlight that traditional transaction processing systems utilize the micro-architectural features of modern processors very poorly. L1 instruction cache and long-latency data misses dominate execution time. As a result, more than half of the execution cycles are wasted on memory stalls. Previous works on reducing stall time aim at improving locality through either hardware or software techniques. However, exploiting hardware resources based on the hints given by the software-side has not been widely studied for data management systems.

In this paper, we observe that, independently of their high-level functionality, transactions running in parallel on a multicore system execute actions chosen from a limited sub-set of predefined database operations. Therefore, we initially perform a memory characterization study of modern transaction processing systems using standardized benchmarks. The analysis demonstrates that same-type transactions exhibit at most 6% overlap in their data footprints whereas there is up to 98% overlap in instructions.

Based on the findings, we design ADDICT, a transaction scheduling mechanism that aims at maximizing the instruction cache locality. ADDICT determines the most frequent actions of database operations, whose instruction footprint can fit in an L1 instruction cache, and assigns a core to execute each of these actions. Then, it schedules each action on its corresponding core. Our prototype implementation of ADDICT reduces L1 instruction misses by 85% and the long latency data misses by 20%. As a result, ADDICT leads up to a 50% reduction in the total execution time for the evaluated workloads.
Supervised meta-blocking
Authors: Papadakis George , Papastefanatos George , Koutrika Georgia
Published: May 2015

Entity Resolution matches mentions of the same entity. Being an expensive task for large data, its performance can be improved by blocking, i.e., grouping similar entities and comparing only entities in the same group. Blocking improves the run-time of Entity Resolution, but it still involves unnecessary comparisons that limit its performance. Meta-blocking is the process of restructuring a block collection in order to prune such comparisons. Existing unsupervised meta-blocking methods use simple pruning rules, which offer a rather coarse-grained filtering technique that can be conservative (i.e., keeping too many unnecessary comparisons) or aggressive (i.e., pruning good comparisons). In this work, we introduce supervised meta-blocking techniques that learn classification models for distinguishing promising comparisons. For this task, we propose a small set of generic features that combine a low extraction cost with high discriminatory power. We show that supervised meta-blocking can achieve high performance with small training sets that can be manually created. We analytically compare our supervised approaches with baseline and competitor methods over 10 large-scale datasets, both real and synthetic.
Finish them!
Authors: Gao Yihan , Parameswaran Aditya
Published: May 2015

Given a batch of human computation tasks, a commonly ignored aspect is how the price (i.e., the reward paid to human workers) of these tasks must be set or varied in order to meet latency or cost constraints. Often, the price is set up-front and not modified, leading to either a much higher monetary cost than needed (if the price is set too high), or to a much larger latency than expected (if the price is set too low). Leveraging a pricing model from prior work, we develop algorithms to optimally set and then vary price over time in order to meet a (a) user-specified deadline while minimizing total monetary cost (b) user-specified monetary budget constraint while minimizing total elapsed time. We leverage techniques from decision theory (specifically, Markov Decision Processes) for both these problems, and demonstrate that our techniques lead to upto 30% reduction in cost over schemes proposed in prior work. Furthermore, we develop techniques to speed-up the computation, enabling users to leverage the price setting algorithms on-the-fly.
TransactiveDB
Authors: Catasta Michele , Tonon Alberto , Difallah Djellel Eddine , Demartini Gianluca , Aberer Karl , Cudre-Mauroux Philippe
Published: May 2015

Database Management Systems (DBMSs) have been rapidly evolving in the recent years, exploring ways to store multi-structured data or to involve human processes during query execution. In this paper, we outline a future avenue for DBMSs supporting transactive memory queries that can only be answered by a collection of individuals connected through a given interaction graph. We present TransactiveDB and its ecosystem, which allow users to pose queries in order to reconstruct collective human memories. We describe a set of new transactive operators including TUnion, TFill, TJoin, and TProjection. We also describe how TransactiveDB leverages transactive operators---by mixing query execution, social network analysis and human computation---in order to effectively and efficiently tap into the memories of all targeted users.
Blogel
Authors: Yan Da , Cheng James , Lu Yi , Ng Wilfred
Published: May 2015

The rapid growth in the volume of many real-world graphs (e.g., social networks, web graphs, and spatial networks) has led to the development of various vertex-centric distributed graph computing systems in recent years. However, real-world graphs from different domains have very different characteristics, which often create bottlenecks in vertex-centric parallel graph computation. We identify three such important characteristics from a wide spectrum of real-world graphs, namely (1)skewed degree distribution, (2)large diameter, and (3)(relatively) high density. Among them, only (1) has been studied by existing systems, but many real-world power-law graphs also exhibit the characteristics of (2) and (3). In this paper, we propose a block-centric framework, called Blogel, which naturally handles all the three adverse graph characteristics. Blogel programmers may think like a block and develop efficient algorithms for various graph problems. We propose parallel algorithms to partition an arbitrary graph into blocks efficiently, and block-centric programs are then run over these blocks. Our experiments on large real-world graphs verified that Blogel is able to achieve orders of magnitude performance improvements over the state-of-the-art distributed graph computing systems.
Efficient identification of implicit facts in incomplete OWL2-EL knowledge bases
Authors: Liagouris John , Terrovitis Manolis
Published: May 2015

Integrating incomplete and possibly inconsistent data from various sources is a challenge that arises in several application areas, especially in the management of scientific data. A rising trend for data integration is to model the data as axioms in the Web Ontology Language (OWL) and use inference rules to identify new facts. Although there are several approaches that employ OWL for data integration, there is little work on scalable algorithms able to handle large datasets that do not fit in main memory.

The main contribution of this paper is an algorithm that allows the effective use of OWL for integrating data in an environment with limited memory. The core idea is to exhaustively apply a set of complex inference rules on large disk-resident datasets. To the best of our knowledge, this is the first work that proposes an I/O-aware algorithm for tackling with such an expressive subset of OWL like the one we address here. Previous approaches considered either simpler models (e.g. RDFS) or main-memory algorithms. In the paper we detail the proposed algorithm, prove its correctness, and experimentally evaluate it on real and synthetic data.
SRS
Authors: Sun Yifang , Wang Wei , Qin Jianbin , Zhang Ying , Lin Xuemin
Published: May 2015

Nearest neighbor searches in high-dimensional space have many important applications in domains such as data mining, and multimedia databases. The problem is challenging due to the phenomenon called "curse of dimensionality". An alternative solution is to consider algorithms that returns a
c
-approximate nearest neighbor (
c
-ANN) with guaranteed probabilities. Locality Sensitive Hashing (LSH) is among the most widely adopted method, and it achieves high efficiency both in theory and practice. However, it is known to require an extremely high amount of space for indexing, hence limiting its scalability.

In this paper, we propose several surprisingly simple methods to answer
c
-ANN queries with theoretical guarantees requiring only a
single tiny
index. Our methods are highly flexible and support a variety of functionalities, such as finding the exact nearest neighbor with any given probability. In the experiment, our methods demonstrate superior performance against the state-of-the-art LSH-based methods, and scale up well to 1 billion high-dimensional points on a single commodity PC.
Top-k nearest neighbor search in uncertain data series
Authors: Dallachiesa Michele , Palpanas Themis , Ilyas Ihab F.
Published: May 2015

Many real applications consume data that is intrinsically uncertain, noisy and error-prone. In this study, we investigate the problem of finding the top-
k
nearest neighbors in uncertain data series, which occur in several different domains. We formalize the top-
k
nearest neighbor problem for uncertain data series, and describe a model for uncertain data series that captures both uncertainty and correlation. This distinguishes our approach from prior work that compromises the accuracy of the model by assuming independence of the value distribution at neighboring time-stamps. We introduce the
Holistic-PkNN
algorithm, which uses novel metric bounds for uncertain series and an efficient refinement strategy to reduce the overall number of required probability estimates. We evaluate our proposal under a variety of settings using a combination of synthetic and 45 real datasets from diverse domains. The results demonstrate the significant advantages of the proposed approach.
In-memory performance for big data
Authors: Graefe Goetz , Volos Haris , Kimura Hideaki , Kuno Harumi , Tucek Joseph , Lillibridge Mark , Veitch Alistair
Published: May 2015

When a working set fits into memory, the overhead imposed by the buffer pool renders traditional databases non-competitive with in-memory designs that sacrifice the benefits of a buffer pool. However, despite the large memory available with modern hardware, data skew, shifting workloads, and complex mixed workloads make it difficult to guarantee that a working set will fit in memory. Hence, some recent work has focused on enabling in-memory databases to protect performance when the working data set
almost
fits in memory. Contrary to those prior efforts, we enable buffer pool designs to match in-memory performance while supporting the "big data" workloads that continue to require secondary storage, thus providing the best of both worlds. We introduce here a novel buffer pool design that adapts pointer swizzling for references between system objects (as opposed to application objects), and uses it to practically eliminate buffer pool overheads for memoryresident data. Our implementation and experimental evaluation demonstrate that we achieve graceful performance degradation when the working set grows to exceed the buffer pool size, and graceful improvement when the working set shrinks towards and below the memory and buffer pool sizes.
Interpretable and informative explanations of outcomes
Authors: El Gebaly Kareem , Agrawal Parag , Golab Lukasz , Korn Flip , Srivastava Divesh
Published: May 2015

In this paper, we solve the following data summarization problem: given a multi-dimensional data set augmented with a binary attribute, how can we construct an interpretable and informative summary of the factors affecting the binary attribute in terms of the combinations of values of the dimension attributes? We refer to such summaries as explanation tables. We show the hardness of constructing optimally-informative explanation tables from data, and we propose effective and efficient heuristics. The proposed heuristics are based on sampling and include optimizations related to computing the information content of a summary from a sample of the data. Using real data sets, we demonstrate the advantages of explanation tables compared to related approaches that can be adapted to solve our problem, and we show significant performance benefits of our optimizations.
Constructing an interactive natural language interface for relational databases
Authors: Li Fei , Jagadish H. V.
Published: May 2015

Natural language has been the holy grail of query interface designers, but has generally been considered too hard to work with, except in limited specific circumstances. In this paper, we describe the architecture of an interactive natural language query interface for relational databases. Through a carefully limited interaction with the user, we are able to correctly interpret complex natural language queries, in a generic manner across a range of domains. By these means, a logically complex English language sentence is correctly translated into a SQL query, which may include aggregation, nesting, and various types of joins, among other things, and can be evaluated against an RDBMS. We have constructed a system, NaLIR (Natural Language Interface for Relational databases), embodying these ideas. Our experimental assessment, through user studies, demonstrates that NaLIR is good enough to be usable in practice: even naive users are able to specify quite complex ad-hoc queries.
Leveraging graph dimensions in online graph search
Authors: Zhu Yuanyuan , Yu Jeffrey Xu , Qin Lu
Published: May 2015

Graphs have been widely used due to its expressive power to model complicated relationships. However, given a graph database
D

g

= {
g
1
,
g
2
, · · ·,
g

n

}, it is challenging to process graph queries since a basic graph query usually involves costly graph operations such as maximum common subgraph and graph edit distance computation, which are NP-hard. In this paper, we study a novel
DS-preserved
mapping which maps graphs in a graph database
D

g

onto a multidimensional space
M

g

under a structural dimension
M
using a mapping function φ(). The
DS-preserved
mapping preserves two things: distance and structure. By the distance-preserving, it means that any two graphs
g

i

and
g

j

in
D

g

must map to two data objects φ(
g

i

) and φ(
g

j

) in
M

g

, such that the distance,
d
(φ(
g

i

), φ(
g

j

)), between φ(
g

i

) and φ(
g

j

) in
M

g

approximates the graph dissimilarity δ(
g

i

,
g

j

) in
D

g

. By the structure-preserving, it further means that for a given unseen query graph
q
, the distance between
q
and any graph
g

i

in
D

g

needs to be preserved such that δ(
q
,
g

i

) ≈
d
(φ(
q
), φ(
g

i

)). We discuss the rationality of using graph dimension
M
for online graph processing, and show how to identify a small set of subgraphs to form
M
efficiently. We propose an iterative algorithm DSPM to compute the graph dimension, and discuss its optimization techniques. We also give an approximate algorithm DSPMap in order to handle a large graph database. We conduct extensive performance studies on both real and synthetic datasets to evaluate the top-
k
similarity query which is to find top-
k
similar graphs from
D

g

for a query graph, and show the effectiveness and efficiency of our approaches.
Selectivity estimation on streaming spatio-textual data using local correlations
Authors: Wang Xiaoyang , Zhang Ying , Zhang Wenjie , Lin Xuemin , Wang Wei
Published: May 2015

In this paper, we investigate the selectivity estimation problem for streaming spatio-textual data, which arises in many social network and geo-location applications. Specifically, given a set of continuously and rapidly arriving spatio-textual objects, each of which is described by a geo-location and a short text, we aim to accurately estimate the cardinality of a spatial keyword query on objects seen so far, where a spatial keyword query consists of a search region and a set of query keywords.

To the best of our knowledge, this is the first work to address this important problem. We first extend two existing techniques to solve this problem, and show their limitations. Inspired by two key observations on the "locality" of the correlations among query keywords, we propose a
local correlation
based method by utilizing an augmented adaptive space partition tree (
A
2
SP
-tree for short) to approximately learn a
local Bayesian network
on-the-fly for a given query and estimate its selectivity. A novel
local boosting
approach is presented to further enhance the learning accuracy of local Bayesian networks. Our comprehensive experiments on real-life datasets demonstrate the superior performance of the local correlation based algorithm in terms of estimation accuracy compared to other competitors.
Processing moving
k
NN queries using influential neighbor sets
Authors: Li Chuanwen , Gu Yu , Qi Jianzhong , Yu Ge , Zhang Rui , Yi Wang
Published: May 2015

The moving
k
nearest neighbor query, which computes one's
k
nearest neighbor set and maintains it while at move, is gaining importance due to the prevalent use of smart mobile devices such as smart phones. Safe region is a popular technique in processing the moving
k
nearest neighbor query. It is a region where the movement of the query object does not cause the current
k
nearest neighbor set to change. Processing a moving
k
nearest neighbor query is a continuing process of checking the validity of the safe region and recomputing it if invalidated. The size of the safe region largely decides the frequency of safe region recomputation and hence query processing efficiency. Existing moving
k
nearest neighbor algorithms lack efficiency due to either computing small safe regions and have to recompute frequently or computing large safe regions (i.e., an order-
k
Voronoi cell) with a high cost.

In this paper, we take a third approach. Instead of safe regions, we use a small set of safe guarding objects. We prove that, as long as the the current
k
nearest neighbors are closer to the query object than the safe guarding objects, the current
k
nearest neighbors stay valid and no recomputation is required. This way, we avoid the high cost of safe region recomputation. We also prove that, the region defined by the safe guarding objects is the largest possible safe region. This means that the recomputation frequency of our method is also minimized. We conduct extensive experiments comparing our method with the state-of-the-art method on both real and synthetic data sets. The results confirm the superiority of our method.
Rare time series motif discovery from unbounded streams
Authors: Begum Nurjahan , Keogh Eamonn
Published: May 2015

The detection of
time series motifs
, which are approximately repeated subsequences in time series streams, has been shown to have great utility as a subroutine in many higher-level data mining algorithms. However, this detection becomes much harder in cases where the motifs of interest are vanishingly rare or when faced with a never-ending stream of data. In this work we investigate algorithms to find such rare motifs. We demonstrate that under reasonable assumptions we must abandon any hope of an exact solution to the motif problem as it is normally defined; however, we introduce algorithms that allow us to solve the underlying problem with high probability.
MRCSI
Authors: Wandelt Sebastian , Leser Ulf
Published: May 2015

Efficiently storing and searching collections of similar strings, such as large populations of genomes or long change histories of documents from Wikis, is a timely and challenging problem. Several recent proposals could drastically reduce space requirements by exploiting the similarity between strings in so-called reference-based compression. However, these indexes are usually not searchable any more, i.e., in these methods search efficiency is sacrificed for storage efficiency. We propose Multi-Reference Compressed Search Indexes (MRCSI) as a framework for efficiently compressing dissimilar string collections. In contrast to previous works which can use only a single reference for compression, MRCSI (a) uses multiple references for achieving increased compression rates, where the reference set need not be specified by the user but is determined automatically, and (b) supports efficient approximate string searching with edit distance constraints. We prove that finding the smallest MRCSI is NP-hard. We then propose three heuristics for computing MRCSIs achieving increasing compression ratios. Compared to state-of-the-art competitors, our methods target an interesting and novel sweet-spot between high compression ratio versus search efficiency.
Rapid sampling for visualizations with ordering guarantees
Authors: Kim Albert , Blais Eric , Parameswaran Aditya , Indyk Piotr , Madden Sam , Rubinfeld Ronitt
Published: May 2015

Visualizations are frequently used as a means to understand trends and gather insights from datasets, but often take a long time to generate. In this paper, we focus on the problem of
rapidly generating approximate visualizations while preserving crucial visual properties of interest to analysts.
Our primary focus will be on sampling algorithms that preserve the visual property of
ordering
; our techniques will also apply to some other visual properties. For instance, our algorithms can be used to generate an approximate visualization of a bar chart very rapidly, where the comparisons between any two bars are correct. We formally show that our sampling algorithms are generally applicable and provably optimal in theory, in that they do not take more samples than necessary to generate the visualizations with ordering guarantees. They also work well in practice, correctly ordering output groups while taking orders of magnitude fewer samples and much less time than conventional sampling schemes.
Optimal enumeration
Authors: Chang Lijun , Lin Xuemin , Zhang Wenjie , Yu Jeffrey Xu , Zhang Ying , Qin Lu
Published: May 2015

Driven by many real applications, graph pattern matching has attracted a great deal of attention recently. Consider that a twig-pattern matching may result in an extremely large number of matches in a graph; this may not only confuse users by providing too many results but also lead to high computational costs. In this paper, we study the problem of top-
k
tree pattern matching; that is, given a rooted tree
T
, compute its top-
k
matches in a directed graph
G
based on the twig-pattern matching semantics. We firstly present a novel and optimal enumeration paradigm based on the principle of Lawler's procedure. We show that our enumeration algorithm runs in
O
(
n

T

+ log
k
) time in each round where
n

T

is the number of nodes in
T.
Considering that the time complexity to output a match of
T
is
O
(
n

T

) and
n

T

≥ log
k
in practice, our enumeration technique is optimal. Moreover, the cost of generating top-1 match of
T
in our algorithm is
O
(
m

R

) where
m

R

is the number of edges in the transitive closure of a data graph
G
involving all relevant nodes to
T. O
(
m

R

) is also optimal in the worst case without pre-knowledge of
G.
Consequently, our algorithm is optimal with the running time
O
(
m

R

+
k
(
n

T

+ log
k
)) in contrast to the time complexity
O
(
m

R

log
k
+
kn

T

(log
k
+
d

T

)) of the existing technique where
d

T

is the maximal node degree in
T.
Secondly, a novel priority based access technique is proposed, which greatly reduces the number of edges accessed and results in a significant performance improvement. Finally, we apply our techniques to the general form of top-
k
graph pattern matching problem (i.e., query is a graph) to improve the existing techniques. Comprehensive empirical studies demonstrate that our techniques may improve the existing techniques by orders of magnitude.
UDA-GIST
Authors: Li Kun , Wang Daisy Zhe , Dobra Alin , Dudley Christopher
Published: May 2015

Enterprise applications need sophisticated in-database analytics in addition to traditional online analytical processing from a database. To meet customers' pressing demands, database vendors have been pushing advanced analytical techniques into databases. Most major DBMSes offer User-Defined Aggregate (UDA), a data-driven operator, to implement many of the analytical techniques in parallel. However, UDAs can not be used to implement statistical algorithms such as Markov chain Monte Carlo (MCMC), where most of the work is performed by iterative transitions over a large state that can not be naively partitioned due to data dependency. Typically, this type of statistical algorithm requires pre-processing to setup the large state in the first place and demands post-processing after the statistical inference. This paper presents General Iterative State Transition (GIST), a new database operator for parallel iterative state transitions over large states. GIST receives a state constructed by a UDA, and then performs rounds of transitions on the state until it converges. A final UDA performs post-processing and result extraction. We argue that the combination of UDA and GIST (UDA-GIST) unifies data-parallel and state-parallel processing in a single system, thus significantly extending the analytical capabilities of DBMSes. We exemplify the framework through two high-profile applications: cross-document coreference and image denoising. We show that the in-database framework allows us to tackle a 27 times larger problem than solved by the state-of-the-art for the first application and achieves 43 times speedup over the state-of-the-art for the second application.
Mining revenue-maximizing bundling configuration
Authors: Do Loc , Lauw Hady W. , Wang Ke
Published: May 2015

With greater prevalence of social media, there is an increasing amount of user-generated data revealing consumer preferences for various products and services. Businesses seek to harness this wealth of data to improve their marketing strategies. Bundling, or selling two or more items for one price is a highly-practiced marketing strategy. In this paper, we address the bundle configuration problem from the data-driven perspective. Given a set of items in a seller's inventory, we seek to determine which items should belong to which bundle so as to maximize the total revenue, by mining consumer preferences data. We show that this problem is NP-hard when bundles are allowed to contain more than two items. Therefore, we describe an optimal solution for bundle sizes up to two items, and propose two heuristic solutions for bundles of any larger size. We investigate the effectiveness and the efficiency of the proposed algorithms through experimentations on real-life rating-based preferences data.
Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs
Authors: Ren Xuguang , Wang Junhu
Published: May 2015

Subgraph Isomorphism
is a fundamental problem in graph data processing. Most existing subgraph isomorphism algorithms are based on a backtracking framework which computes the solutions by incrementally matching all query vertices to candidate data vertices. However, we observe that extensive duplicate computation exists in these algorithms, and such duplicate computation can be avoided by exploiting relationships between data vertices. Motivated by this, we propose a novel approach,
BoostIso
, to reduce duplicate computation. Our extensive experiments with real datasets show that, after integrating our approach, most existing subgraph isomorphism algorithms can be speeded up significantly, especially for some graphs with intensive vertex relationships, where the improvement can be up to several orders of magnitude.
Approximate lifted inference with probabilistic databases
Authors: Gatterbauer Wolfgang , Suciu Dan
Published: May 2015

This paper proposes a new approach for approximate evaluation of #P-hard queries with probabilistic databases. In our approach, every query is evaluated entirely in the database engine by evaluating a fixed number of query plans, each providing an upper bound on the true probability, then taking their minimum. We provide an algorithm that takes into account important schema information to enumerate only the minimal necessary plans among all possible plans. Importantly, this algorithm is a strict generalization of all known results of PTIME self-join-free conjunctive queries: A query is safe if and only if our algorithm returns one single plan. We also apply three relational query optimization techniques to evaluate all minimal safe plans very fast. We give a detailed experimental evaluation of our approach and, in the process, provide a new way of thinking about the value of probabilistic methods over non-probabilistic methods for ranking query answers.
Preference-aware integration of temporal data
Authors: Alexe Bogdan , Roth Mary , Tan Wang-Chiew
Published: May 2015

A complete description of an entity is rarely contained in a single data source, but rather, it is often distributed across different data sources. Applications based on personal electronic health records, sentiment analysis, and financial records all illustrate that significant value can be derived from integrated, consistent, and queryable profiles of entities from different sources. Even more so, such integrated profiles are considerably enhanced if temporal information from different sources is carefully accounted for.

We develop a simple and yet versatile operator, called prawn, that is typically called as a final step of an entity integration workflow. Prawn is capable of consistently integrating and resolving temporal conflicts in data that may contain multiple dimensions of time based on a set of preference rules specified by a user (hence the name prawn for
preference-aware union
). In the event that not all conflicts can be resolved through preferences, one can enumerate each possible consistent interpretation of the result returned by prawn at a given time point through a polynomial-delay algorithm. In addition to providing algorithms for implementing prawn, we study and establish several desirable properties of prawn. First, prawn produces the same temporally integrated outcome, modulo representation of time, regardless of the order in which data sources are integrated. Second, prawn can be customized to integrate temporal data for different applications by specifying application-specific preference rules. Third, we show experimentally that our implementation of prawn is feasible on both "small" and "big" data platforms in that it is efficient in both storage and execution time. Finally, we demonstrate a fundamental advantage of prawn: we illustrate that standard query languages can be immediately used to pose useful temporal queries over the integrated and resolved entity repository.
The more the merrier
Authors: Then Manuel , Kaufmann Moritz , Chirigati Fernando , Hoang-Vu Tuan-Anh , Pham Kien , Kemper Alfons , Neumann Thomas , Vo Huy T.
Published: May 2015

Graph analytics on social networks, Web data, and communication networks has been widely used in a plethora of applications. Many graph analytics algorithms are based on breadth-first search (BFS) graph traversal, which is not only time-consuming for large datasets but also involves much redundant computation when executed multiple times from different start vertices. In this paper, we propose
Multi-Source BFS
(MS-BFS), an algorithm that is designed to run multiple concurrent BFSs over the same graph on a single CPU core while scaling up as the number of cores increases. MS-BFS leverages the properties of
small-world networks
, which apply to many real-world graphs, and enables efficient graph traversal that: (i) shares common computation across concurrent BFSs; (ii) greatly reduces the number of random memory accesses; and (iii) does not incur synchronization costs. We demonstrate how a real graph analytics application---all-vertices closeness centrality---can be efficiently solved with MS-BFS. Furthermore, we present an extensive experimental evaluation with both synthetic and real datasets, including Twitter and Wikipedia, showing that MS-BFS provides almost linear scalability with respect to the number of cores and excellent scalability for increasing graph sizes, outperforming state-of-the-art BFS algorithms by more than one order of magnitude when running a large number of BFSs.
Multi-objective parametric query optimization
Authors: Trummer Immanuel , Koch Christoph
Published: May 2015

Classical query optimization compares query plans according to one cost metric and associates each plan with a constant cost value. In this paper, we introduce the Multi-Objective Parametric Query Optimization (MPQ) problem where query plans are compared according to multiple cost metrics and the cost of a given plan according to a given metric is modeled as a function that depends on multiple parameters. The cost metrics may for instance include execution time or monetary fees; a parameter may represent the selectivity of a query predicate that is unspecified at optimization time.

MPQ generalizes parametric query optimization (which allows multiple parameters but only one cost metric) and multi-objective query optimization (which allows multiple cost metrics but no parameters). We formally analyze the novel MPQ problem and show why existing algorithms are inapplicable. We present a generic algorithm for MPQ and a specialized version for MPQ with piecewise-linear plan cost functions. We prove that both algorithms find all relevant query plans and experimentally evaluate the performance of our second algorithm in a Cloud computing scenario.
Deployment of query plans on multicores
Authors: Giceva Jana , Alonso Gustavo , Roscoe Timothy , Harris Tim
Published: May 2015

Efficient resource scheduling of multithreaded software on multicore hardware is difficult given the many parameters involved and the hardware heterogeneity of existing systems. In this paper we explore the efficient deployment of query plans over a multicore machine. We focus on shared query systems, and implement the proposed ideas using SharedDB.

The goal of the paper is to explore how to deliver maximum performance and predictability, while minimizing resource utilization when deploying query plans on multicore machines. We propose to use
resource activity vectors
to characterize the behavior of individual database operators. We then present a novel deployment algorithm which uses these vectors together with dataflow information from the query plan to optimally assign relational operators to physical cores. Experiments demonstrate that this approach significantly reduces resource requirements while preserving performance and is robust across different server architectures.
Faster set intersection with SIMD instructions by reducing branch mispredictions
Authors: Inoue Hiroshi , Ohara Moriyoshi , Taura Kenjiro
Published: May 2015

Set intersection is one of the most important operations for many applications such as Web search engines or database management systems. This paper describes our new algorithm to efficiently find set intersections with sorted arrays on modern processors with SIMD instructions and high branch misprediction penalties. Our algorithm efficiently exploits SIMD instructions and can drastically reduce branch mispredictions. Our algorithm extends a merge-based algorithm by reading multiple elements, instead of just one element, from each of two input arrays and compares all of the pairs of elements from the two arrays to find the elements with the same values. The key insight for our improvement is that we can reduce the number of costly hard-to-predict conditional branches by advancing a pointer by more than one element at a time. Although this algorithm increases the total number of comparisons, we can execute these comparisons more efficiently using the SIMD instructions and gain the benefits of the reduced branch misprediction overhead. Our algorithm is suitable to replace existing standard library functions, such as std::set_intersection in C++, thus accelerating many applications, because the algorithm is simple and requires no preprocessing to generate additional data structures. We implemented our algorithm on Xeon and POWER7+. The experimental results show our algorithm outperforms the std::set_intersection implementation delivered with gcc by up to 5.2x using SIMD instructions and by up to 2.1x even without using SIMD instructions for 32-bit and 64-bit integer datasets. Our SIMD algorithm also outperformed an existing algorithm that can leverage SIMD instructions.
Improving main memory hash joins on Intel Xeon Phi processors
Authors: Jha Saurabh , He Bingsheng , Lu Mian , Cheng Xuntao , Huynh Huynh Phung
Published: May 2015

Modern processor technologies have driven new designs and implementations in main-memory hash joins. Recently, Intel Many Integrated Core (MIC) co-processors (commonly known as Xeon Phi) embrace emerging x86 single-chip many-core techniques. Compared with contemporary multi-core CPUs, Xeon Phi has quite different architectural features: wider SIMD instructions, many cores and hardware contexts, as well as lower-frequency in-order cores. In this paper, we experimentally revisit the state-of-the-art hash join algorithms on Xeon Phi co-processors. In particular, we study two camps of hash join algorithms: hardware-conscious ones that advocate careful tailoring of the join algorithms to underlying hardware architectures and hardware-oblivious ones that omit such careful tailoring. For each camp, we study the impact of architectural features and software optimizations on Xeon Phi in comparison with results on multi-core CPUs. Our experiments show two major findings on Xeon Phi, which are quantitatively different from those on multi-core CPUs. First, the impact of architectural features and software optimizations has quite different behavior on Xeon Phi in comparison with those on the CPU, which calls for new optimization and tuning on Xeon Phi. Second, hardware oblivious algorithms can outperform hardware conscious algorithms on a wide parameter window. These two findings further shed light on the design and implementation of query processing on new-generation single-chip many-core technologies.
Sharing buffer pool memory in multi-tenant relational database-as-a-service
Authors: Narasayya Vivek , Menache Ishai , Singh Mohit , Li Feng , Syamala Manoj , Chaudhuri Surajit
Published: May 2015

Relational database-as-a-service (DaaS) providers need to rely on multi-tenancy and resource sharing among tenants, since statically reserving resources for a tenant is not cost effective. A major consequence of resource sharing is that the performance of one tenant can be adversely affected by resource demands of other co-located tenants. One such resource that is essential for good performance of a tenant's workload is
buffer pool memory.
In this paper, we study the problem of how to effectively share buffer pool memory in multi-tenant relational DaaS. We first develop an SLA framework that defines and enforces accountability of the service provider to the tenant even when buffer pool memory is not statically reserved on behalf of the tenant. Next, we present a novel buffer pool page replacement algorithm (MT-LRU) that builds upon theoretical concepts from weighted online caching, and is designed for multi-tenant scenarios involving SLAs and overbooking. MT-LRU generalizes the LRU-K algorithm which is commonly used in relational database systems. We have prototyped our techniques inside a commercial DaaS engine and extensive experiments demonstrate the effectiveness of our solution.
Inbreeding in Pembroke Welsh Corgi Population in Poland
Authors: Świderek Wiesław Piotr , Fiszdon Katarzyna , Kacprzak Natalia
Published: May 2015

The objective of this study was to determine changes in the coefficients of inbreeding for a comparatively new Polish population of Pembroke Welsh Corgis. Calculations were based on 780 pedigrees of dogs born between 1979 and 2010 and registered with the Polish Kennel Club. The mean inbreeding coefficients for animals born during those years varied from 0.4% to 8.93%. The lowest individual inbreeding coefficient was 0.06%, whereas the highest reached 25.1%.
The Influence of WPC 80 Additive on the Stability of Water-In-Oil Emulsions
Authors: Tabaszewska Małgorzata , Grega Tadeusz , Najgebauer-Lejko Dorota , Jaworska Grażyna
Published: May 2015

The effect of 0, 1.5, 5, 10 and 15 (g 100 g-1 of emulsion) WPC 80 additive (80% whey protein concentrate) on the pH, physical, oxidative and microbiological stability of the water-in-oil emulsion was studied during 16-week storage at ~20°C at 4-week intervals. All determined features were significantly affected by the supplementation. The most beneficial as regards storage stability was the emulsion with 5% of WPC 80. This treatment was the most resistant to oxidative changes showing low increase of the concentration of conjugated diene hydroperoxides (from 0.92 to 1.04 mg g-1) and of the thiobarbituric acid reactive substances (from 0.83 to 1.37 mg malondialdehyde g-1) as well as only slight increment (by 0.47 log CFU g-1) of the microorganisms number during storage. Thus, the results of the present study revealed that whey proteins can be applied in the proper amount to produce cosmetic emulsions composed of natural ingredients and with reasonable storage stability.
Guanine Nucleotide Binding Protein (GNAS Complex Locus) Gene Produces Biallelically Expressed and Paternally Expressed Transcripts in Pigs
Authors: Oczkowicz Maria , Piestrzyńska-Kajtoch Agata , Ropka-Molik Katarzyna
Published: May 2015

Imprinted loci are a subset of genes expressed only from one parental allele. Guanine nucleotide binding protein (GNAS complex locus) produces a few different proteins and noncoding RNAs. It is imprinted in mice and humans, while in pigs imprinting status of only one of them - NESP55 (neuroendocrine secretory protein-55) has been established. In the present study we aimed to establish imprinting status of the other two GNAS transcripts. We collected a panel of tissues (muscle, liver, kidney cortex, heart, fat, ovary, brain, blood) from the animals (aged 40-210 days) heterozygous in rs#333005482 polymorphism. We performed several RT -PCRs (Reverse Transcription Polymerase Chain Reactions) with variant specific primers and sequenced the cDNA products obtained. We observed only paternal allele in all tissues at all developmental stages after sequencing with primers specific to variant 8 of GNAS gene and both alleles when sequencing with primers specific to variant 6. Our results show for the first time that, in pigs, GNAS complex locus produces biallelically expressed and paternally expressed transcripts, in the same way as previously demonstrated in mice and humans
Red deer farming: breeding practice, trends and potential in Poland – A Review
Authors: Kuba Jarosław , Landete-Castillejos Tomas , Udała Jan
Published: May 2015

Red deer farming has started to play a greater role in modern agriculture and today is an interesting alternative for pig or cattle breeders. With regard to the low effort and high efficiency of maintenance, it may be expected that keeping these animals in fenced enclosures will be more popular over time. This trend is warranted by the fact that the demand on two main deer products: venison and antlers, is constantly rising, due to the quality of deer meat and prices of antler hunting trophies. Several countries of the world have already realized the scale of advantages to be derived from deer farming and today are world leaders in this area. Despite this expansion, the market still remains opened for deer products. Poland is a country with the climatic conditions, vast plain areas and varied vegetation that are fully sufficient to undertake large-scale deer farming, and to become a European leader. Therefore the aim of this review is to detail deer farming within the Polish framework and environmental conditions, and to illustrate its potential in sustainable modern agriculture and the economy.