bluuebunny/crossref_metadata_2025 huggingface dataset:
Optimizing I/O for big array analytics
Authors: Zhang Yi , Yang Jun
Published: June 2014

Big array analytics is becoming indispensable in answering important scientific and business questions. Most analysis tasks consist of multiple steps, each making one or multiple passes over the arrays to be analyzed and generating intermediate results. In the big data setting, I/O optimization is a key to efficient analytics. In this paper, we develop a framework and techniques for capturing a broad range of analysis tasks expressible in nested-loop forms, representing them in a declarative way, and optimizing their I/O by identifying sharing opportunities. Experiment results show that our optimizer is capable of finding execution plans that exploit nontrivial I/O sharing opportunities with significant savings.
Probabilistically bounded staleness for practical partial quorums
Authors: Bailis Peter , Venkataraman Shivaram , Franklin Michael J. , Hellerstein Joseph M. , Stoica Ion
Published: June 2014

Data store replication results in a fundamental trade-off between operation latency and data consistency. In this paper, we examine this trade-off in the context of quorum-replicated data stores. Under partial, or non-strict quorum replication, a data store waits for responses from a subset of replicas before answering a query, without guaranteeing that read and write replica sets intersect. As deployed in practice, these configurations provide only basic eventual consistency guarantees, with no limit to the recency of data returned. However, anecdotally, partial quorums are often "good enough" for practitioners given their latency benefits. In this work, we explain why partial quorums are regularly acceptable in practice, analyzing both the staleness of data they return and the latency benefits they offer. We introduce Probabilistically Bounded Staleness (PBS) consistency, which provides expected bounds on staleness with respect to both versions and wall clock time. We derive a closed-form solution for versioned staleness as well as model real-time staleness for representative Dynamo-style systems under internet-scale production workloads. Using PBS, we measure the latency-consistency trade-off for partial quorum systems. We quantitatively demonstrate how eventually consistent systems frequently return consistent data within tens of milliseconds while offering significant latency benefits.
On the spatiotemporal burstiness of terms
Authors: Lappas Theodoros , Vieira Marcos R. , Gunopulos Dimitrios , Tsotras Vassilis J.
Published: June 2014

Thousands of documents are made available to the users via the web on a daily basis. One of the most extensively studied problems in the context of such document streams is
burst identification
. Given a term
t
, a burst is generally exhibited when an unusually high frequency is observed for
t
. While spatial and temporal burstiness have been studied individually in the past, our work is the first to simultaneously track and measure
spatiotemporal term burstiness
. In addition, we use the mined burstiness information toward an efficient document-search engine: given a user's query of terms, our engine returns a ranked list of documents discussing influential events with a strong spatiotemporal impact. We demonstrate the efficiency of our methods with an extensive experimental evaluation on real and synthetic datasets.
Type-based detection of XML query-update independence
Authors: Bidoit-Tollu Nicole , Colazzo Dario , Ulliana Federico
Published: June 2014

This paper presents a novel static analysis technique to detect XML query-update independence, in the presence of a schema. Rather than types, our system infers
chains
of types. Each chain represents a path that can be traversed on a valid document during query/update evaluation. The resulting independence analysis is precise, although it raises a challenging issue: recursive schemas may lead to inference of infinitely many chains.

A sound and complete approximation technique ensuring a finite analysis in any case is presented, together with an efficient implementation performing the chain-based analysis in polynomial space and time.
Real time discovery of dense clusters in highly dynamic graphs
Authors: Agarwal Manoj K. , Ramamritham Krithi , Bhide Manish
Published: June 2014

Due to their
real time
nature, microblog streams are a rich source of dynamic information, for example, about
emerging events
. Existing techniques for discovering such events from a microblog stream in real time (such as Twitter trending topics), have several lacunae when used for discovering emerging events; extant graph based event detection techniques are not practical in microblog settings due to their complexity; and conventional techniques, which have been developed for blogs, web-pages, etc., involving the use of keyword search, are only useful for finding information about
known
events. Hence, in this paper, we present techniques to discover events that are unraveling in microblog message streams in real time so that such events can be reported as soon as they occur. We model the problem as discovering dense clusters in highly dynamic graphs. Despite many recent advances in graph analysis, ours is the first technique to identify dense clusters in massive and highly dynamic graphs in real time. Given the characteristics of microblog streams, in order to find clusters without missing any events, we propose and exploit a novel graph property which we call
short-cycle property
. Our algorithms find these clusters efficiently in spite of rapid changes to the microblog streams. Further we present a novel ranking function to identify the important events. Besides proving the correctness of our algorithms we show their practical utility by evaluating them using real world microblog data. These demonstrate our technique's ability to discover, with high precision and recall, emerging events in high intensity data streams in real time. Many recent web applications create data which can be represented as massive dynamic graphs. Our technique can be easily extended to discover, in real time, interesting patterns in such graphs.
Sketch-based querying of distributed sliding-window data streams
Authors: Papapetrou Odysseas , Garofalakis Minos , Deligiannakis Antonios
Published: June 2014

While traditional data-management systems focus on evaluating single, ad-hoc queries over static data sets in a centralized setting, several emerging applications require (possibly, continuous) answers to queries on
dynamic
data that is widely
distributed
and constantly updated. Furthermore, such query answers often need to discount data that is "stale", and operate solely on a
sliding window
of recent data arrivals (e.g., data updates occurring over the last 24 hours). Such
distributed data streaming
applications mandate novel algorithmic solutions that are both time- and space-efficient (to manage high-speed data streams), and also communication-efficient (to deal with physical data distribution). In this paper, we consider the problem of complex query answering over distributed, high-dimensional data streams in the sliding-window model. We introduce a novel sketching technique (termed
ECM-sketch
) that allows effective summarization of streaming data over both time-based and count-based sliding windows with probabilistic accuracy guarantees. Our sketch structure enables point as well as inner-product queries, and can be employed to address a broad range of problems, such as maintaining frequency statistics, finding heavy hitters, and computing quantiles in the sliding-window model. Focusing on distributed environments, we demonstrate how ECM-sketches of individual, local streams can be composed to generate a (low-error) ECM-sketch summary of the order-preserving aggregation of all streams; furthermore, we show how ECM-sketches can be exploited for continuous monitoring of sliding-window queries over distributed streams. Our extensive experimental study with two real-life data sets validates our theoretical claims and verifies the effectiveness of our techniques. To the best of our knowledge, ours is the first work to address efficient, guaranteed-error complex query answering over distributed data streams in the sliding-window model.
Spatial queries with two kNN predicates
Authors: Aly Ahmed M. , Aref Walid G. , Ouzzani Mourad
Published: June 2014

The widespread use of location-aware devices has led to countless location-based services in which a user query can be arbitrarily complex, i.e., one that embeds multiple spatial selection and join predicates. Amongst these predicates, the
k
-Nearest-Neighbor (
k
NN) predicate stands as one of the most important and widely used predicates. Unlike related research, this paper goes beyond the optimization of queries with single
k
NN predicates, and shows how queries with
two k
NN predicates can be optimized. In particular, the paper addresses the optimization of queries with: (i) two
k
NN-select predicates, (ii) two
k
NN-join predicates, and (iii) one
k
NN-join predicate and one
k
NN-select predicate. For each type of queries, conceptually correct query evaluation plans (QEPs) and new algorithms that optimize the query execution time are presented. Experimental results demonstrate that the proposed algorithms outperform the conceptually correct QEPs by orders of magnitude.
Labeling workflow views with fine-grained dependencies
Authors: Bao Zhuowei , Davidson Susan B. , Milo Tova
Published: June 2014

This paper considers the problem of efficiently answering reachability queries over
views
of provenance graphs, derived from executions of workflows that may include recursion. Such views include composite modules and model fine-grained dependencies between module inputs and outputs. A novel
view-adaptive
dynamic labeling scheme is developed for efficient query evaluation, in which view specifications are labeled statically (i.e. as they are created) and data items are labeled dynamically as they are produced during a workflow execution. Although the combination of fine-grained dependencies and recursive workflows entail, in general, long (linear-size) data labels, we show that for a large natural class of workflows and views, labels are
compact
(logarithmic-size) and reachability queries can be evaluated in constant time. Experimental results demonstrate the benefit of this approach over the state-of-the-art technique when applied for labeling multiple views.
Optimization of analytic window functions
Authors: Cao Yu , Chan Chee-Yong , Li Jie , Tan Kian-Lee
Published: June 2014

Analytic functions represent the state-of-the-art way of performing complex data analysis within a single SQL statement. In particular, an important class of analytic functions that has been frequently used in commercial systems to support OLAP and decision support applications is the class of
window functions
. A window function returns for each input tuple a value derived from applying a function over a window of neighboring tuples. However, existing window function evaluation approaches are based on a naive sorting scheme. In this paper, we study the problem of optimizing the evaluation of window functions. We propose several efficient techniques, and identify optimization opportunities that allow us to optimize the evaluation of a set of window functions. We have integrated our scheme into PostgreSQL. Our comprehensive experimental study on the TPC-DS datasets as well as synthetic datasets and queries demonstrate significant speedup over existing approaches.
Efficient indexing and querying over syntactically annotated trees
Authors: Chubak Pirooz , Rafiei Davood
Published: June 2014

Natural language text corpora are often available as sets of syntactically parsed trees. A wide range of expressive tree queries are possible over such parsed trees that open a new avenue in searching over natural language text. They not only allow for querying roles and relationships within sentences, but also improve search effectiveness compared to flat keyword queries. One major drawback of current systems supporting querying over parsed text is the performance of evaluating queries over large data. In this paper we propose a novel indexing scheme over unique subtrees as index keys. We also propose a novel
root-split
coding scheme that stores subtree structural information only partially, thus reducing index size and improving querying performance. Our extensive set of experiments show that
root-split
coding reduces the index size of any interval coding which stores individual node numbers by a factor of 50% to 80%, depending on the sizes of subtrees indexed. Moreover, We show that our index using
root-split
coding, outperforms previous approaches by at least an order of magnitude in terms of the response time of queries.
Injecting uncertainty in graphs for identity obfuscation
Authors: Boldi Paolo , Bonchi Francesco , Gionis Aristides , Tassa Tamir
Published: June 2014

Data collected nowadays by social-networking applications create fascinating opportunities for building novel services, as well as expanding our understanding about social structures and their dynamics. Unfortunately, publishing social-network graphs is considered an ill-advised practice due to privacy concerns. To alleviate this problem, several anonymization methods have been proposed, aiming at reducing the risk of a privacy breach on the published data, while still allowing to analyze them and draw relevant conclusions.

In this paper we introduce a new anonymization approach that is based on injecting
uncertainty
in social graphs and publishing the resulting
uncertain graphs
. While existing approaches obfuscate graph data by adding or removing edges entirely, we propose using a finer-grained perturbation that adds or removes edges
partially
: this way we can achieve the same desired level of obfuscation with smaller changes in the data, thus maintaining higher utility. Our experiments on real-world networks confirm that at the same level of identity obfuscation our method provides higher usefulness than existing randomized methods that publish standard graphs.
Measuring two-event structural correlations on graphs
Authors: Guan Ziyu , Yan Xifeng , Kaplan Lance M.
Published: June 2014

Real-life graphs usually have various kinds of events happening on them, e.g., product purchases in online social networks and intrusion alerts in computer networks. The occurrences of events on the same graph could be correlated, exhibiting either attraction or repulsion. Such structural correlations can reveal important relationships between different events. Unfortunately, correlation relationships on graph structures are not well studied and cannot be captured by traditional measures.

In this work, we design a novel measure for assessing two-event structural correlations on graphs. Given the occurrences of two events, we choose uniformly a sample of "reference nodes" from the vicinity of all event nodes and employ the Kendall's τ rank correlation measure to compute the average concordance of event density changes. Significance can be efficiently assessed by τ's nice property of being asymptotically normal under the null hypothesis. In order to compute the measure in large scale networks, we develop a scalable framework using different sampling strategies. The complexity of these strategies is analyzed. Experiments on real graph datasets with both synthetic and real events demonstrate that the proposed framework is not only efficacious, but also efficient and scalable.
sDTW
Authors: Candan K. Selçuk , Rossini Rosaria , Wang Xiaolan , Sapino Maria Luisa
Published: June 2014

Many applications generate and consume temporal data and retrieval of time series is a key processing step in many application domains. Dynamic time warping (DTW) distance between time series of size
N
and
M
is computed relying on a dynamic programming approach which creates and fills an
N x M
grid to search for an optimal
warp path
. Since this can be costly, various heuristics have been proposed to cut away the potentially unproductive portions of the DTW grid. In this paper, we argue that time series often carry structural features that can be used for identifying
locally relevant
constraints to eliminate redundant work. Relying on this observation, we propose
salient feature
based sDTW algorithms which first identify robust salient features in the given time series and then find a consistent alignment of these to establish the boundaries for the warp path search. More specifically, we propose alternative
fixed core&adaptive width, adaptive core&fixed width
, and
adaptive core&adaptive width
strategies which enforce different constraints reflecting the high level structural characteristics of the series in the data set. Experiment results show that the proposed sDTW algorithms help achieve much higher accuracy in DTW computation and time series retrieval than
fixed core & fixed width
algorithms that do not leverage local features of the given time series.
Multiple location profiling for users and relationships from social network and content
Authors: Li Rui , Wang Shengjie , Chang Kevin Chen-Chuan
Published: June 2014

Users' locations are important for many applications such as personalized search and localized content delivery. In this paper, we study the problem of profiling Twitter users' locations with their following network and tweets. We propose a multiple location profiling model (
MLP
), which has three key features: 1) it formally models how likely a user follows another user given their locations and how likely a user tweets a venue given his location, 2) it fundamentally captures that a user has multiple locations and his following relationships and tweeted venues can be related to any of his locations, and some of them are even noisy, and 3) it novelly utilizes the home locations of some users as partial supervision. As a result,
MLP
not only discovers users' locations
accurately
and
completely
, but also "explains" each following relationship by revealing users' true locations in the relationship. Experiments on a large-scale data set demonstrate those advantages. Particularly, 1) for predicting users' home locations,
MLP
successfully places 62% users and out-performs two state-of-the-art methods by 10% in accuracy, 2) for discovering users' multiple locations,
MLP
improves the baseline methods by 14% in recall, and 3) for explaining following relationships,
MLP
achieves 57% accuracy.
Flash-based extended cache for higher throughput and faster recovery
Authors: Kang Woon-Hak , Lee Sang-Won , Moon Bongki
Published: June 2014

Considering the current price gap between disk and flash memory drives, for applications dealing with large scale data, it will be economically more sensible to use flash memory drives to supplement disk drives rather than to replace them. This paper presents
FaCE
, which is a new low-overhead caching strategy that uses flash memory as an extension to the DRAM buffer.
FaCE
aims at improving the transaction throughput as well as shortening the recovery time from a system failure. To achieve the goals, we propose two novel algorithms for flash cache management, namely,
Multi-Version FIFO replacement
and
Group Second Chance
. One striking result from
FaCE
is that using a small flash memory drive as a caching device could deliver even higher throughput than using a large flash memory drive to store the entire database tables. This was possible due to
flash write optimization
as well as
disk access reduction
obtained by the
FaCE
caching methods. In addition,
FaCE
takes advantage of the non-volatility of flash memory to fully support database recovery by extending the scope of a persistent database to include the data pages stored in the flash cache. We have implemented
FaCE
in the PostgreSQL open source database server and demonstrated its effectiveness for TPC-C benchmarks.
Statistical distortion
Authors: Dasu Tamraparni , Loh Ji Meng
Published: June 2014

We introduce the notion of
statistical distortion
as an essential metric for measuring the effectiveness of data cleaning strategies. We use this metric to propose a widely applicable yet scalable experimental framework for evaluating data cleaning strategies along three dimensions: glitch improvement, statistical distortion and cost-related criteria. Existing metrics focus on glitch improvement and cost, but not on the statistical impact of data cleaning strategies. We illustrate our framework on real world data, with a comprehensive suite of experiments and analyses.
Data analytics opportunities in a smarter planet
Authors: Dietrich Brenda
Published: June 2014

New applications of computing are being enabled by instrumentation of physical entities, aggregation of data, and the analysis of the data. The resulting integration of information and control permits efficient and effective management of complex man-made systems. Examples include transportation systems, buildings, electrical grids, health care systems, governments, and supply chains. Achieving this vision requires extensive data integration and analysis, over diverse, rapidly changing, and often uncertain data. There are many challenges, requiring both new data management techniques as well as new mathematics, forcing new collaborations as the basis of the new "Data Science". Needs and opportunities will be discussed in the context of specific pilots and projects.
The unified logging infrastructure for data analytics at Twitter
Authors: Lee George , Lin Jimmy , Liu Chuang , Lorek Andrew , Ryaboy Dmitriy
Published: June 2014

In recent years, there has been a substantial amount of work on large-scale data analytics using Hadoop-based platforms running on large clusters of commodity machines. A less-explored topic is how those data, dominated by application logs, are collected and structured to begin with. In this paper, we present Twitter's production logging infrastructure and its evolution from application-specific logging to a unified "client events" log format, where messages are captured in common, well-formatted, flexible Thrift messages. Since most analytics tasks consider the user session as the basic unit of analysis, we pre-materialize "session sequences", which are compact summaries that can answer a large class of common queries quickly. The development of this infrastructure has streamlined log collection and data analysis, thereby improving our ability to rapidly experiment and iterate on various aspects of the service.
Muppet
Authors: Lam Wang , Liu Lu , Prasad Sts , Rajaraman Anand , Vacheri Zoheb , Doan AnHai
Published: June 2014

MapReduce has emerged as a popular method to process big data. In the past few years, however, not just big data, but fast data has also exploded in volume and availability. Examples of such data include sensor data streams, the Twitter Firehose, and Facebook updates. Numerous applications must process fast data. Can we provide a MapReduce-style framework so that developers can quickly write such applications and execute them over a cluster of machines, to achieve low latency and high scalability?

In this paper we report on our investigation of this question, as carried out at Kosmix and WalmartLabs. We describe MapUpdate, a framework like MapReduce, but specifically developed for fast data. We describe Muppet, our implementation of MapUpdate. Throughout the description we highlight the key challenges, argue why MapReduce is not well suited to address them, and briefly describe our current solutions. Finally, we describe our experience and lessons learned with Muppet, which has been used extensively at Kosmix and WalmartLabs to power a broad range of applications in social media and e-commerce.
MOIST
Authors: Jiang Junchen , Bao Hongji , Chang Edward Y. , Li Yuqian
Published: June 2014

Location-Based Service (LBS) is rapidly becoming the next ubiquitous technology for a wide range of mobile applications. To support applications that demand nearest-neighbor and history queries, an LBS spatial indexer must be able to efficiently update, query, archive and mine location records, which can be in contention with each other. In this work, we propose MOIST, whose baseline is a recursive spatial partitioning indexer built upon BigTable. To reduce update and query contention, MOIST groups nearby objects of similar trajectory into the same school, and keeps track of only the history of school leaders. This dynamic clustering scheme can eliminate redundant updates and hence reduce update latency. To improve history query processing, MOIST keeps some history data in memory, while it flushes aged data onto parallel disks in a locality-preserving way. Through experimental studies, we show that MOIST can support highly efficient nearest-neighbor and history queries and can scale well with an increasing number of users and update frequency.
Exploiting evidence from unstructured data to enhance master data management
Authors: Murthy Karin , Deshpande Prasad M. , Dey Atreyee , Halasipuram Ramanujam , Mohania Mukesh , Deepak P. , Reed Jennifer , Schumacher Scott
Published: June 2014

Master data management (MDM) integrates data from multiple structured data sources and builds a consolidated 360-degree view of business entities such as customers and products. Today's MDM systems are not prepared to integrate information from unstructured data sources, such as news reports, emails, call-center transcripts, and chat logs. However, those unstructured data sources may contain valuable information about the same entities known to MDM from the structured data sources. Integrating information from unstructured data into MDM is challenging as textual references to existing MDM entities are often incomplete and imprecise and the additional entity information extracted from text should not impact the trustworthiness of MDM data.

In this paper, we present an architecture for making MDM text-aware and showcase its implementation as IBM Info-Sphere MDM Extension for Unstructured Text Correlation, an add-on to IBM InfoSphere Master Data Management Standard Edition. We highlight how MDM benefits from additional evidence found in documents when doing entity resolution and relationship discovery. We experimentally demonstrate the feasibility of integrating information from unstructured data sources into MDM.
A demonstration of DBWipes
Authors: Wu Eugene , Madden Samuel , Stonebraker Michael
Published: June 2014

As data analytics becomes mainstream, and the complexity of the underlying data and computation grows, it will be increasingly important to provide tools that help analysts understand the underlying reasons when they encounter errors in the result. While data provenance has been a large step in providing tools to help debug complex workflows, its current form has limited utility when debugging aggregation operators that compute a single output from a large collection of inputs. Traditional provenance will return the entire input collection, which has very low precision. In contrast, users are seeking
precise descriptions
of the inputs that caused the errors. We propose a
Ranked Provenance System
, which identifies subsets of inputs that influenced the output error, describes each subset with human readable predicates and orders them by contribution to the error. In this demonstration, we will present DBWipes, a novel data cleaning system that allows users to execute aggregate queries, and interactively detect, understand, and clean errors in the query results. Conference attendees will explore anomalies in campaign donations from the current US presidential election and in readings from a 54-node sensor deployment.
Stethoscope
Authors: Gawade Mrunal , Kersten Martin
Published: June 2014

Searching for the performance bottleneck in an execution trace is an error prone and time consuming activity. Existing tools offer some comfort by providing a visual representation of trace for analysis. In this paper we present the Stethoscope, an interactive visual tool to inspect and analyze columnar database query performance, both online and offline. It's unique interactive animated interface capitalizes the large data-flow graph representation of a query execution plan, augmented with query execution trace information. We demonstrate features of Stethoscope for both online and offline analysis of long running queries. It helps in understanding where time goes, how optimizers perform, and how parallel processing on multi-core systems is exploited.
Demonstration of the FDB query engine for factorised databases
Authors: Bakibayev Nurzhan , Olteanu Dan , Závodný Jakub
Published: June 2014

FDB is an in-memory query engine for factorised databases, which are relational databases that use compact factorised representations at the physical layer to reduce data redundancy and boost query performance.

We demonstrate FDB using real data sets from IMDB, DBLP, and the NELL repository of facts learned from Web pages. The users can inspect factorisations as well as plans used by FDB to compute factorised results of select-project-join queries on factorised databases.
QueryMarket demonstration
Authors: Koutris Paraschos , Upadhyaya Prasang , Balazinska Magdalena , Howe Bill , Suciu Dan
Published: June 2014

Increasingly data is being bought and sold online. To facilitate such transactions, online data market-places have emerged to provide a service for sellers to price views on their data, and buyers to buy such views. These marketplaces neither support the sale of ad-hoc queries (that are not one of the specified views), nor do they support queries that join datasets. We present QueryMarket, a prototype data marketplace that automatically extrapolates prices to ad-hoc queries, including those with joins, from the manually priced views. We call this capability "query-based pricing" and describe how it is superior to existing pricing methods, and how it provides more flexible pricing for the sellers. We then show how QueryMarket implements query-based pricing and how it generates explanations for the prices it computes.
Developing and analyzing XSDs through BonXai
Authors: Martens Wim , Niewerth Matthias , Neven Frank , Schwentick Thomas
Published: June 2014

BonXai is a versatile schema specification language expressively equivalent to XML Schema. It is not intended as a replacement for XML Schema but it can serve as an additional, user-friendly front-end. It offers a simple way and a lightweight syntax to specify the context of elements based on regular expressions rather than on types. In this demo we show the front-end capabilities of BonXai and exemplify its potential to offer a novel way to view existing XML Schema Definitions. In particular, we present several usage scenarios specifically targeted to showcase the ease of specifying, modifying, and understanding XML Schema Definitions through BonXai.
Manage and query generic moving objects in SECONDO
Authors: Xu Jianqiu , Güting Ralf Hartmut
Published: June 2014

In this demonstration, we introduce a system that is able to manage moving objects in all real world environments, e.g., road network, bus network and indoor. The complete trip of a person is managed by the system such as
Walk, Car, Walk
, and
Indoor
, where the precise locations of both outdoor and indoor movements are represented. Trajectories located in several environments are integrated into the same framework. The system supports the shortest path searching for start and end locations being in different environments, for example, from a room to a bus stop. A comprehensive and scalable set of moving objects is generated to simulate human movement in practice. Optimization methods are developed to efficiently answer novel queries regarding transportation modes and mobile environments. Most of these queries are not supported by existing methods because of the limitation of data representation.
Chronos
Authors: Li Pei , Tziviskou Christina , Wang Haidong , Dong Xin Luna , Liu Xiaoguang , Maurino Andrea , Srivastava Divesh
Published: June 2014

Many data sets containtemporal recordsover a long period of time; each record is associated with a time stamp and describes some aspects of a real-world entity at that particular time. From such data, users often wish to search for entities in a particular period and understand the history of one entity or all entities in the data set. A major challenge for enabling such search and exploration is to identify records that describe the same real-world entity over a long period of time; however, linking temporal records is hard given that the values that describe an entity can evolve over time (e.g., a person can move from one affiliation to another).

We demonstrate the Chronos system which offers users the useful tool for finding real-world entities over time and understanding history of entities in the bibliography domain. The core of Chronos is a temporal record-linkage algorithm, which is tolerant to value evolution over time. Our algorithm can obtain an F-measure of over 0.9 in linking author records and fix errors made byDBLP. We show how Chronos allows users to explore the history of authors, and how it helps users understand our linkage results by comparing our results with those of existing systems, highlighting differences in the results, explaining our decisions to users, and answering "what-if" questions.
TELEIOS
Authors: Koubarakis Manolis , Datcu Mihai , Kontoes Charalambos , Di Giammatteo Ugo , Manegold Stefan , Klien Eva
Published: June 2014

TELEIOS is a recent European project that addresses the need for scalable access to petabytes of Earth Observation data and the discovery and exploitation of knowledge that is hidden in them. TELEIOS builds on scientific database technologies (array databases, SciQL, data vaults) and Semantic Web technologies (stRDF and stSPARQL) implemented on top of a state of the art column store database system (MonetDB). We demonstrate a first prototype of the TELEIOS
Virtual Earth Observatory (VEO)
architecture, using a forest fire monitoring application as example.
Efficient big data processing in Hadoop MapReduce
Authors: Dittrich Jens , Quiané-Ruiz Jorge-Arnulfo
Published: June 2014

This tutorial is motivated by the clear need of many organizations, companies, and researchers to deal with big data volumes efficiently. Examples include web analytics applications, scientific applications, and social networks. A popular data processing engine for big data is Hadoop MapReduce. Early versions of Hadoop MapReduce suffered from severe performance problems. Today, this is becoming history. There are many techniques that can be used with Hadoop MapReduce jobs to boost performance by orders of magnitude. In this tutorial we teach such techniques. First, we will briefly familiarize the audience with Hadoop MapReduce and motivate its use for big data processing. Then, we will focus on different data management techniques, going from job optimization to physical data organization like data layouts and indexes. Throughout this tutorial, we will highlight the similarities and differences between Hadoop MapReduce and Parallel DBMS. Furthermore, we will point out unresolved research problems and open issues.
MapReduce algorithms for big data analysis
Authors: Shim Kyuseok
Published: June 2014

There is a growing trend of applications that should handle big data. However, analyzing big data is a very challenging problem today. For such applications, the MapReduce framework has recently attracted a lot of attention. Google's MapReduce or its open-source equivalent Hadoop is a powerful tool for building such applications. In this tutorial, we will introduce the MapReduce framework based on Hadoop, discuss how to design efficient MapReduce algorithms and present the state-of-the-art in MapReduce algorithms for data mining, machine learning and similarity joins. The intended audience of this tutorial is professionals who plan to design and develop MapReduce algorithms and researchers who should be aware of the state-of-the-art in MapReduce algorithms available today for big data analysis.
Panel discussion on social networks and mobility in the cloud
Authors: El Abbadi Amr , Mokbel Mohamed F.
Published: June 2014

Social networks, mobility and the cloud represent special and unique opportunities for synergy among several existing and emerging communities that are now often evolving in isolated silos. All three areas hold much promise for the future of computing, and represent significant challenges for large scale data management. As these three areas evolve, their direct influence on significant decisions on each other becomes evident and critical. This panel will bring together a set of renowned researchers who will explore and discuss the synergy and tensions among critical and often intertwined research and application issues that arise in the context of social networks and mobility in a cloud infrastructure setting.
Less is more
Authors: Dong Xin Luna , Saha Barna , Srivastava Divesh
Published: June 2014

We are often thrilled by the abundance of information surrounding us and wish to integrate data from as many sources as possible. However, understanding, analyzing, and using these data are often hard. Too much data can introduce a huge integration cost, such as expenses for purchasing data and resources for integration and cleaning. Furthermore, including low-quality data can even deteriorate the quality of integration results instead of bringing the desired quality gain. Thus, "the more the better" does not always hold for data integration and often "less is more".

In this paper, we study how to select a subset of sources before integration such that we can balance the quality of integrated data and integration cost. Inspired by the Marginalism principle in economic theory, we wish to integrate a new source only if its marginal gain, often a function of improved integration quality, is higher than the marginal cost, associated with data-purchase expense and integration resources. As a first step towards this goal, we focus on data fusion tasks, where the goal is to resolve conflicts from different sources. We propose a randomized solution for selecting sources for fusion and show empirically its effectiveness and scalability on both real-world data and synthetic data.
Counting with the crowd
Authors: Marcus Adam , Karger David , Madden Samuel , Miller Robert , Oh Sewoong
Published: June 2014

In this paper, we address the problem of selectivity estimation in a crowdsourced database. Specifically, we develop several techniques for using workers on a crowdsourcing platform like Amazon's Mechanical Turk to estimate the fraction of items in a dataset (e.g., a collection of photos) that satisfy some property or predicate (e.g., photos of trees). We do this without explicitly iterating through every item in the dataset. This is important in crowd-sourced query optimization to support predicate ordering and in query evaluation, when performing a GROUP BY operation with a COUNT or AVG aggregate. We compare sampling item labels, a traditional approach, to showing workers a collection of items and asking them to estimate how many satisfy some predicate. Additionally, we develop techniques to eliminate spammers and colluding attackers trying to skew selectivity estimates when using this count estimation approach. We find that for images, counting can be much more effective than sampled labeling, reducing the amount of work necessary to arrive at an estimate that is within 1% of the true fraction by up to an order of magnitude, with lower worker latency. We also find that sampled labeling outperforms count estimation on a text processing task, presumably because people are better at quickly processing large batches of images than they are at reading strings of text. Our spammer detection technique, which is applicable to both the label- and count-based approaches, can improve accuracy by up to two orders of magnitude.
Memory efficient minimum substring partitioning
Authors: Li Yang , Kamousi Pegah , Han Fangqiu , Yang Shengqi , Yan Xifeng , Suri Subhash
Published: June 2014

Massively parallel DNA sequencing technologies are revolutionizing genomics research. Billions of short reads generated at low costs can be assembled for reconstructing the whole genomes. Unfortunately, the large memory footprint of the existing de novo assembly algorithms makes it challenging to get the assembly done for higher eukaryotes like mammals. In this work, we investigate the memory issue of constructing de Bruijn graph, a core task in leading assembly algorithms, which often consumes several hundreds of gigabytes memory for large genomes. We propose a disk-based partition method, called Minimum Substring Partitioning (MSP), to complete the task using less than 10 gigabytes memory, without runtime slowdown. MSP breaks the short reads into multiple small disjoint partitions so that each partition can be loaded into memory, processed individually and later merged with others to form a de Bruijn graph. By leveraging the overlaps among the k-mers (substring of length k), MSP achieves astonishing compression ratio: The total size of partitions is reduced from Θ(kn) to Θ(n), wherenis the size of the short read database, andkis the length of ak-mer. Experimental results show that our method can build de Bruijn graphs using a commodity computer for any large-volume sequence dataset.
NeMa
Authors: Khan Arijit , Wu Yinghui , Aggarwal Charu C. , Yan Xifeng
Published: June 2014

It is increasingly common to find real-life data represented as networks of labeled, heterogeneous entities. To query these networks, one often needs to identify the matches of a given query graph in a (typically large) network modeled as a target graph. Due to noise and the lack of fixed schema in the target graph, the query graph can substantially differ from its matches in the target graph in both structure and node labels, thus bringing challenges to the graph querying tasks. In this paper, we propose NeMa (Network Match), a neighborhood-based subgraph matching technique for querying real-life networks. (1) To measure the quality of the match, we propose a novel subgraph matching cost metric that aggregates the costs of matching individual nodes, and unifies both structure and node label similarities. (2) Based on the metric, we formulate the minimum cost subgraph matching problem. Given a query graph and a target graph, the problem is to identify the (top-
k
) matches of the query graph with minimum costs in the target graph. We show that the problem is NP-hard, and also hard to approximate. (3) We propose a heuristic algorithm for solving the problem based on an inference model. In addition, we propose optimization techniques to improve the efficiency of our method. (4) We empirically verify that NeMa is both effective and efficient compared to the keyword search and various state-of-the-art graph querying techniques.
Scaling factorization machines to relational data
Authors: Rendle Steffen
Published: June 2014

The most common approach in predictive modeling is to describe cases with feature vectors (aka design matrix). Many machine learning methods such as linear regression or support vector machines rely on this representation. However, when the underlying data has strong relational patterns, especially relations with high cardinality, the design matrix can get very large which can make learning and prediction slow or even infeasible.

This work solves this issue by making use of repeating patterns in the design matrix which stem from the underlying relational structure of the data. It is shown how coordinate descent learning and Bayesian Markov Chain Monte Carlo inference can be scaled for linear regression and factorization machine models. Empirically, it is shown on two large scale and very competitive datasets (Netflix prize, KDDCup 2012), that (1) standard learning algorithms based on the design matrix representation cannot scale to relational predictor variables, (2) the proposed new algorithms scale and (3) the predictive quality of the proposed generic feature-based approach is as good as the best specialized models that have been tailored to the respective tasks.
Query optimization over crowdsourced data
Authors: Park Hyunjung , Widom Jennifer
Published: June 2014

Deco is a comprehensive system for answering declarative queries posed over stored relational data together with data obtained on-demand from the crowd. In this paper we describe Deco's cost-based query optimizer, building on Deco's data model, query language, and query execution engine presented earlier. Deco's objective in query optimization is to find the best query plan to answer a query, in terms of estimated monetary cost. Deco's query semantics and plan execution strategies require several fundamental changes to traditional query optimization. Novel techniques incorporated into Deco's query optimizer include a cost model distinguishing between "free" existing data versus paid new data, a cardinality estimation algorithm coping with changes to the database state during query execution, and a plan enumeration algorithm maximizing reuse of common subplans in a setting that makes reuse challenging. We experimentally evaluate Deco's query optimizer, focusing on the accuracy of cost estimation and the efficiency of plan enumeration.
Efficient recovery of missing events
Authors: Wang Jianmin , Song Shaoxu , Zhu Xiaochen , Lin Xuemin
Published: June 2014

For various entering and transmission issues raised by human or system, missing events often occur in event data, which record execution logs of business processes. Without recovering these missing events, applications such as provenance analysis or complex event processing built upon event data are not reliable. Following the minimum change discipline in improving data quality, it is also rational to find a recovery that minimally differs from the original data. Existing recovery approaches fall short of efficiency owing to enumerating and searching over all the possible sequences of events. In this paper, we study the efficient techniques for recovering missing events. According to our theoretical results, the recovery problem is proved to be NP-hard. Nevertheless, we are able to concisely represent the space of event sequences in a branching framework. Advanced indexing and pruning techniques are developed to further improve the recovery efficiency. Our proposed efficient techniques make it possible to find top-k recoveries. The experimental results demonstrate that our minimum recovery approach achieves high accuracy, and significantly outperforms the state-of-the-art technique for up to 5 orders of magnitudes improvement in time performance.