bluuebunny/crossref_metadata_2025 huggingface dataset:
Record linkage with uniqueness constraints and erroneous values
Authors: Guo Songtao , Dong Xin Luna , Srivastava Divesh , Zajac Remi
Published: June 2014

Many data-management applications require integrating data from a variety of sources, where different sources may refer to the same real-world entity in different ways and some may even provide erroneous data. An important task in this process is to recognize and merge the various references that refer to the same entity. In practice, some attributes satisfy a
uniqueness
constraint---each real-world entity (or most entities) has a unique value for the attribute (
e.g.
, business contact phone, address, and email). Traditional techniques tackle this case by first linking records that are likely to refer to the same real-world entity, and then fusing the linked records and resolving conflicts if any. Such methods can fall short for three reasons: first, erroneous values from sources may prevent correct linking; second, the real world may contain exceptions to the uniqueness constraints and always enforcing uniqueness can miss correct values; third, locally resolving conflicts for linked records may overlook important global evidence.

This paper proposes a novel technique to solve this problem. The key component of our solution is to reduce the problem into a
k
-partite graph clustering problem and consider in clustering both similarity of attribute values and the sources that associate a pair of values in the same record. Thus, we perform global linkage and fusion simultaneously, and can identify incorrect values and differentiate them from alternative representations of the correct value from the beginning. In addition, we extend our algorithm to be tolerant to a few violations of the uniqueness constraints. Experimental results show accuracy and scalability of our technique.
On-the-fly entity-aware query processing in the presence of linkage
Authors: Ioannou Ekaterini , Nejdl Wolfgang , Niederée Claudia , Velegrakis Yannis
Published: June 2014

Entity linkage is central to almost every data integration and data cleaning scenario. Traditional techniques use some computed similarity among data structure to perform merges and then answer queries on the merged data. We describe a novel framework for entity linkage with uncertainty. Instead of using the linkage information to merge structures a-priori, possible linkages are stored alongside the data with their belief value. A new probabilistic query answering technique is used to take the probabilistic linkage into consideration. The framework introduces a series of novelties: (i) it performs merges at run time based not only on existing linkages but also on the given query; (ii) it allows results that may contain structures not explicitly represented in the data, but generated as a result of a reasoning on the linkages; and (iii) enables an evaluation of the query conditions that spans across linked structures, offering a functionality not currently supported by any traditional probabilistic databases. We formally define the semantics, describe an efficient implementation and report on the findings of our experimental evaluation.
Evaluation of entity resolution approaches on real-world match problems
Authors: Köpcke Hanna , Thor Andreas , Rahm Erhard
Published: June 2014

Despite the huge amount of recent research efforts on entity resolution (matching) there has not yet been a comparative evaluation on the relative effectiveness and efficiency of alternate approaches. We therefore present such an evaluation of existing implementations on challenging real-world match tasks. We consider approaches both with and without using machine learning to find suitable parameterization and combination of similarity functions. In addition to approaches from the research community we also consider a state-of-the-art commercial entity resolution implementation. Our results indicate significant quality and efficiency differences between different approaches. We also find that some challenging resolution tasks such as matching product entities from online shops are not sufficiently solved with conventional approaches based on the similarity of attribute values.
Advanced processing for ontological queries
Authors: Calì Andrea , Gottlob Georg , Pieris Andreas
Published: June 2014

Ontology-based data access is a powerful form of extending database technology, where a classical extensional database (EDB) is enhanced by an ontology that generates new intensional knowledge which may contribute to answer a query. The ontological integrity constraints for generating this intensional knowledge can be specified in description logics such as DL-Lite. It was recently shown that these formalisms allow for very efficient query-answering. They are, however, too weak to express simple and useful integrity constraints that involve joins. In this paper we introduce a more expressive formalism that takes joins into account, while still enjoying the same low query-answering complexity. In our framework, ontological constraints are expressed by sets of rules that are so-called
tuple-generating dependencies (TGDs)
. We propose the language of
sticky
sets of TGDs, which are sets of TGDs with a restriction on multiple occurrences of variables (including joins) in the rule bodies. We establish complexity results for answering conjunctive queries under sticky sets of TGDs, showing, in particular, that ontological conjunctive queries can be compiled into first-order and thus SQL queries over the given EDB instance. We also show how sticky sets of TGDs can be combined with functional dependencies. In summary, we obtain a highly expressive and effective ontological modeling language that unifies and generalizes both classical database constraints and important features of the most widespread tractable description logics.
Embellishing text search queries to protect user privacy
Authors: Pang HweeHwa , Ding Xuhua , Xiao Xiaokui
Published: June 2014

Users of text search engines are increasingly wary that their activities may disclose confidential information about their business or personal profiles. It would be desirable for a search engine to perform document retrieval for users while protecting their intent. In this paper, we identify the privacy risks arising from semantically related search terms within a query, and from recurring high-specificity query terms in a search session. To counter the risks, we propose a solution for a similarity text retrieval system to offer anonymity and plausible deniability for the query terms, and hence the user intent, without degrading the system's precision-recall performance. The solution comprises a mechanism that embellishes each user query with decoy terms that exhibit similar specificity spread as the genuine terms, but point to plausible alternative topics. We also provide an accompanying retrieval scheme that enables the search engine to compute the encrypted document relevance scores from only the genuine search terms, yet remain oblivious to their distinction from the decoys. Empirical evaluation results are presented to substantiate the effectiveness of our solution.
Set similarity join on probabilistic data
Authors: Lian Xiang , Chen Lei
Published: June 2014

Set similarity join has played an important role in many real-world applications such as data cleaning, near duplication detection, data integration, and so on. In these applications, set data often contain noises and are thus uncertain and imprecise. In this paper, we model such probabilistic set data on two uncertainty levels, that is, set and element levels. Based on them, we investigate the problem of
probabilistic set similarity join
(PS
2
J) over two probabilistic set databases, under the
possible worlds
semantics. To efficiently process the PS
2
J operator, we first reduce our problem by condensing the possible worlds, and then propose effective pruning techniques, including Jaccard distance pruning, probability upper bound pruning, and aggregate pruning, which can filter out false alarms of probabilistic set pairs, with the help of indexes and our designed synopses. We demonstrate through extensive experiments the PS
2
J processing performance on both real and synthetic data.
Keyword++
Authors: Ganti Venkatesh , He Yeye , Xin Dong
Published: June 2014

Keyword search over entity databases (
e.g.
, product, movie databases) is an important problem. Current techniques for keyword search on databases may often return
incomplete
and
imprecise
results. On the one hand, they either require that relevant entities contain all (or most) of the query keywords, or that relevant entities and the query keywords occur together in several documents from a known collection. Neither of these requirements may be satisfied for a number of user queries. Hence results for such queries are likely to be incomplete in that highly relevant entities may not be returned. On the other hand, although some returned entities contain all (or most) of the query keywords, the intention of the keywords in the query could be different from that in the entities. Therefore, the results could also be imprecise.

To remedy this problem, in this paper, we propose a general framework that can improve an existing search interface by translating a keyword query to a structured query. Specifically, we leverage the keyword to attribute value associations discovered in the results returned by the original search interface. We show empirically that the translated structured queries alleviate the above problems.
An adaptive updating protocol for reducing moving object database workload
Authors: Chen Su , Ooi Beng Chin , Zhang Zhenjie
Published: June 2014

In the last decade, spatio-temporal database research focuses on the design of effective and efficient indexing structures in support of location-based queries such as predictive range queries and nearest neighbor queries. While a variety of indexing techniques have been proposed to accelerate the processing of updates and queries, not much attention has been paid to the updating protocol, which is another important factor affecting system performance. In this paper, we propose a generic and adaptive updating protocol for moving object databases with less number of updating messages between the objects and database server, thereby reducing the overall workload of the system. In contrast to the approach adopted by most conventional moving object database systems where the exact locations and velocities last disclosed are used to predict their motions, we propose the concept of
Spatio-Temporal Safe Region
to approximate possible future locations. Spatio-temporal safe regions provide larger space of tolerance for moving objects, freeing them from location and velocity updates as long as the errors remain predictable in the database. To answer predictive queries accurately, the server is allowed to probe the latest status of some moving objects when their safe regions are inadequate in returning the exact query results. Spatio-temporal safe regions are calculated and optimized by the database server with two contradictory objectives: reducing update workload while guaranteeing query accuracy and efficiency. To achieve this, we propose a cost model that estimates the composition of active and passive updates based on historical motion records and query distribution. We have conducted extensive experiments to evaluate our proposal on a variety of popular indexing structures. The results confirm the viability, robustness, accuracy and efficiency of our proposed protocol.
Efficient and effective similarity search over probabilistic data based on earth mover's distance
Authors: Xu Jia , Zhang Zhenjie , Tung Anthony K. H. , Yu Ge
Published: June 2014

Probabilistic data is coming as a new deluge along with the technical advances on geographical tracking, multimedia processing, sensor network and RFID. While similarity search is an important functionality supporting the manipulation of probabilistic data, it raises new challenges to traditional relational database. The problem stems from the limited effectiveness of the distance metric supported by the existing database system. On the other hand, some complicated distance operators have proven their values for better distinguishing ability in the probabilistic domain. In this paper, we discuss the similarity search problem with the
Earth Mover's Distance
, which is the most successful distance metric on probabilistic histograms and an expensive operator with cubic complexity. We present a new database approach to answer range queries and k-nearest neighbor queries on probabilistic data, on the basis of Earth Mover's Distance. Our solution utilizes the primal-dual theory in linear programming and deploys
B
+
tree index structures for effective candidate pruning. Extensive experiments show that our proposal dramatically improves the scalability of probabilistic databases.
MCDB-R
Authors: Arumugam Subi , Xu Fei , Jampani Ravi , Jermaine Christopher , Perez Luis L. , Haas Peter J.
Published: June 2014

Enterprises often need to assess and manage the risk arising from uncertainty in their data. Such uncertainty is typically modeled as a probability distribution over the uncertain data values, specified by means of a complex (often predictive) stochastic model. The probability distribution over data values leads to a probability distribution over database query results, and risk assessment amounts to exploration of the upper or lower tail of a query-result distribution. In this paper, we extend the Monte Carlo Database System to efficiently obtain a set of samples from the tail of a query-result distribution by adapting recent "Gibbs cloning" ideas from the simulation literature to a database setting.
Scalable probabilistic databases with factor graphs and MCMC
Authors: Wick Michael , McCallum Andrew , Miklau Gerome
Published: June 2014

Incorporating probabilities into the semantics of incomplete databases has posed many challenges, forcing systems to sacrifice modeling power, scalability, or treatment of relational algebra operators. We propose an alternative approach where the underlying relational database always represents a single world, and an external factor graph encodes a distribution over possible worlds; Markov chain Monte Carlo (MCMC) inference is then used to recover this uncertainty to a desired level of fidelity. Our approach allows the efficient evaluation of arbitrary queries over probabilistic databases with arbitrary dependencies expressed by graphical models with structure that changes during inference. MCMC sampling provides efficiency by hypothesizing
modifications
to possible worlds rather than generating entire worlds from scratch. Queries are then run over the portions of the world that change, avoiding the onerous cost of running full queries over each sampled world. A significant innovation of this work is the connection between MCMC sampling and materialized view maintenance techniques: we find empirically that using view maintenance techniques is several orders of magnitude faster than naively querying each sampled world. We also demonstrate our system's ability to answer relational queries with aggregation, and demonstrate additional scalability through the use of parallelization on a real-world complex model of information extraction. This framework is sufficiently expressive to support probabilistic inference not only for answering queries, but also for inferring missing database content from raw evidence.
Explore or exploit?
Authors: Cheng Reynold , Lo Eric , Yang Xuan S. , Luk Ming-Hay , Li Xiang , Xie Xike
Published: June 2014

Data ambiguity is inherent in applications such as data integration, location-based services, and sensor monitoring. In many situations, it is possible to "clean", or remove, ambiguities from these databases. For example, the GPS location of a user is inexact due to measurement errors, but context information (e.g., what a user is doing) can be used to reduce the imprecision of the location value. In order to obtain a database with a higher quality, we study how to disambiguate a database by appropriately selecting candidates to clean. This problem is challenging because cleaning involves a cost, is limited by a budget, may fail, and may not remove all ambiguities. Moreover, the statistical information about how likely database objects can be cleaned may not be precisely known. We tackle these challenges by proposing two types of algorithms. The first type makes use of greedy heuristics to make sensible decisions; however, these algorithms do not make use of cleaning information and require user input for parameters to achieve high cleaning effectiveness. We propose the
Explore-Exploit
(or
EE
) algorithm, which gathers valuable information during the cleaning process to determine how the remaining cleaning budget should be invested.

We also study how to fine-tune the parameters of
EE
in order to achieve optimal cleaning effectiveness. Experimental evaluations on real and synthetic datasets validate the effectiveness and efficiency of our approaches.
Destabilizers and independence of XML updates
Authors: Benedikt Michael , Cheney James
Published: June 2014

Independence analysis is the problem of determining whether an update affects the result of a query, e.g. a constraint or materialized view. We develop a new, modular framework for static independence analysis that decomposes the problem into two orthogonal subproblems: approximating the
destabilizer
, that is, a finite representation of the set of updates that can change the result of the query, and testing whether the update and destabilizer overlap via an intersection analysis. Focusing on XML queries as the view language and the XQuery Update Facility as the update language, we present a syntactic query rewriting algorithm for translating queries to destabilizers, and show that intersection checking can be reduced to satisfiability problems for which efficient checkers already exist. We present an implementation based on an expressive tree satisfiability checker and a Satisfiability Modulo Order package, and give experiments confirming that the resulting analysis is both fast and effective.
Searching workflows with hierarchical views
Authors: Liu Ziyang , Shao Qihong , Chen Yi
Published: June 2014

Workflows are prevalent in diverse applications, which can be scientific experiments, business processes, web services, or recipes. With the dramatically growing number of workflows, there is an increasing need for people to search a workflow repository using keywords and to retrieve the relevant ones. A workflow hierarchy is a three dimensional object containing multiple abstraction views of different granularity on the same workflow. This unique structure poses a new set of challenges compared to keyword search on tree or graph structures typically found in relational or XML data.

In this paper, we define an informative, self-contained and concise search result on workflows to be a projection of a workflow hierarchy on a two dimensional viewing plane inferred from user queries. We then design and develop an efficient keyword search engine for workflows. Experimental evaluation demonstrates the effectiveness of our approach.
Mining significant semantic locations from GPS data
Authors: Cao Xin , Cong Gao , Jensen Christian S.
Published: June 2014

With the increasing deployment and use of GPS-enabled devices, massive amounts of GPS data are becoming available. We propose a general framework for the mining of semantically meaningful, significant locations, e.g., shopping malls and restaurants, from such data.

We present techniques capable of extracting semantic locations from GPS data. We capture the relationships between locations and between locations and users with a graph. Significance is then assigned to locations using random walks over the graph that propagates significance among the locations. In doing so, mutual reinforcement between location significance and user authority is exploited for determining significance, as are aspects such as the number of visits to a location, the durations of the visits, and the distances users travel to reach locations. Studies using up to 100 million GPS records from a confined spatio-temporal region demonstrate that the proposal is effective and is capable of outperforming baseline methods and an extension of an existing proposal.
Boosting the accuracy of differentially private histograms through consistency
Authors: Hay Michael , Rastogi Vibhor , Miklau Gerome , Suciu Dan
Published: June 2014

We show that it is possible to significantly improve the accuracy of a general class of histogram queries while satisfying differential privacy. Our approach carefully chooses a set of queries to evaluate, and then exploits consistency constraints that should hold over the noisy output. In a post-processing phase, we compute the consistent input most likely to have produced the noisy output. The final output is differentially-private and consistent, but in addition, it is often much more accurate. We show, both theoretically and experimentally, that these techniques can be used for estimating the degree sequence of a graph very precisely, and for computing a histogram that can support arbitrary range queries accurately.
ρ-uncertainty
Authors: Cao Jianneng , Karras Panagiotis , Raïssi Chedy , Tan Kian-Lee
Published: June 2014

The publication of transaction data, such as market basket data, medical records, and query logs, serves the public benefit. Mining such data allows for the derivation of association rules that connect certain items to others with measurable confidence. Still, this type of data analysis poses a privacy threat; an adversary having partial information on a person's behavior may
confidently
associate that person to an item deemed to be
sensitive
. Ideally, an
anonymization
of such data should lead to an
inference-proof
version that prevents the association of individuals to sensitive items, while otherwise allowing for truthful associations to be derived. Original approaches to this problem were based on value
perturbation
, damaging data integrity. Recently, value
generalization
has been proposed as an alternative; still, approaches based on it have assumed
either
that all items are equally sensitive,
or
that some are sensitive and can be known to an adversary
only
by association, while others are non-sensitive and can be known directly. Yet in reality there
is
a distinction between sensitive and non-sensitive items, but an adversary may possess information on
any
of them. Most critically, no antecedent method aims at a clear
inference-proof
privacy guarantee. In this paper, we propose ρ-uncertainty, the
first
, to our knowledge, privacy concept that
inherently
safeguards against sensitive associations
without
constraining the nature of an adversary's knowledge and
without
falsifying data. The problem of achieving ρ-uncertainty with low information loss is challenging because it is
natural
. A trivial solution is to suppress all sensitive items. We develop more sophisticated schemes. In a broad experimental study, we show that the problem is solved non-trivially by a technique that combines generalization and suppression, which also achieves favorable results compared to a baseline perturbation-based scheme.
Minimizing minimality and maximizing utility
Authors: Cormode Graham , Srivastava Divesh , Li Ninghui , Li Tiancheng
Published: June 2014

The principle of
anonymization
for data sharing has become a very popular paradigm for the preservation of privacy of the data subjects. Since the introduction of
k
-anonymity, dozens of methods and enhanced privacy definitions have been proposed. However, over-eager attempts to minimize the information lost by the anonymization potentially allow private information to be inferred. Proof-of-concept of this "minimality attack" has been demonstrated for a variety of algorithms and definitions [16].

In this paper, we provide a comprehensive analysis and study of this attack, and demonstrate that with care its effect can be almost entirely countered. The attack allows an adversary to increase his (probabilistic) belief in certain facts about individuals over the data. We show that (a) a large class of algorithms are not affected by this attack, (b) for a class of algorithms that have a "symmetric" property, the attacker's belief increases by at most a small constant, and (c) even for an algorithm chosen to be highly susceptible to the attack, the attacker's belief when using the attack increases by at most a small constant factor. We also provide a series of experiments that show in all these cases that the confidence about the sensitive value of any individual remains low in practice, while the published data is still useful for its intended purpose. From this, we conclude that the impact of such method-based attacks can be minimized.
Graph homomorphism revisited for graph matching
Authors: Fan Wenfei , Li Jianzhong , Ma Shuai , Wang Hongzhi , Wu Yinghui
Published: June 2014

In a variety of emerging applications one needs to decide whether a graph
G matches
another
G

p

,
i.e.
, whether
G
has a topological structure similar to that of
G

p

. The traditional notions of graph homomorphism and isomorphism often fall short of capturing the structural similarity in these applications. This paper studies revisions of these notions, providing a full treatment from complexity to algorithms. (1) We propose
p-homomorphism (p
-hom) and 1-1
p
-hom, which extend graph homomorphism and subgraph isomorphism, respectively, by mapping
edges
from one graph to
paths
in another, and by measuring
the similarity of nodes
. (2) We introduce metrics to measure graph similarity, and several optimization problems for
p
-hom and 1-1
p
-hom. (3) We show that the decision problems for
p
-hom and 1-1
p
-hom are NP-complete even for DAGs, and that the optimization problems are approximation-hard. (4) Nevertheless, we provide approximation algorithms with
provable guarantees
on match quality. We experimentally verify the effectiveness of the revised notions and the efficiency of our algorithms in Web site matching, using real-life and synthetic data.
SAPPER
Authors: Zhang Shijie , Yang Jiong , Jin Wei
Published: June 2014

With the emergence of new applications, e.g., computational biology, new software engineering techniques, social networks, etc., more data is in the form of graphs. Locating occurrences of a query graph in a large database graph is an important research topic. Due to the existence of noise (e.g., missing edges) in the large database graph, we investigate the problem of approximate subgraph indexing, i.e., finding the occurrences of a query graph in a large database graph with (possible) missing edges. The SAPPER method is proposed to solve this problem. Utilizing the hybrid neighborhood unit structures in the index, SAPPER takes advantage of pre-generated random spanning trees and a carefully designed graph enumeration order. Real and synthetic data sets are employed to demonstrate the efficiency and scalability of our approximate subgraph indexing method.
Tree indexing on solid state drives
Authors: Li Yinan , He Bingsheng , Yang Robin Jun , Luo Qiong , Yi Ke
Published: June 2014

Large flash disks, or solid state drives (SSDs), have become an attractive alternative to magnetic hard disks, due to their high random read performance, low energy consumption and other features. However, writes, especially small random writes, on flash disks are inherently much slower than reads because of the erase-before-write mechanism.

To address this asymmetry of read-write speeds in tree indexing on the flash disk, we propose FD-tree, a tree index designed with the
logarithmic method
and
fractional cascading
techniques. With the logarithmic method, an FD-tree consists of the head tree -- a small B+-tree on the top, and a few levels of sorted runs of increasing sizes at the bottom. This design is write-optimized for the flash disk; in particular, an index search will potentially go through more levels or visit more nodes, but random writes are limited to a small area -- the head tree, and are subsequently transformed into sequential ones through merging into the lower runs. With the fractional cascading technique, we store pointers, called fences, in lower level runs to speed up the search. Given an FD-tree of
n
entries, we analytically show that it performs an update in
O
(log

B

n
) sequential I/Os and completes a search in
O
(log

B

n
) random I/Os, where
B
is the flash page size. We evaluate FD-tree in comparison with representative B+-tree variants under a variety of workloads on three commodity flash SSDs. Our results show that FD-tree has a similar search performance to the standard B+-tree, and a similar update performance to the write-optimized B+-tree variant. As a result, FD-tree dominates the other B+-tree index variants on the overall performance on flash disks as well as on magnetic disks.
Efficient B-tree based indexing for cloud data processing
Authors: Wu Sai , Jiang Dawei , Ooi Beng Chin , Wu Kun-Lung
Published: June 2014

A Cloud may be seen as a type of flexible computing infrastructure consisting of many compute nodes, where resizable computing capacities can be provided to different customers. To fully harness the power of the Cloud, efficient data management is needed to handle huge volumes of data and support a large number of concurrent end users. To achieve that, a scalable and high-throughput indexing scheme is generally required. Such an indexing scheme must not only incur a low maintenance cost but also support parallel search to improve scalability. In this paper, we present a novel, scalable B
+
-tree based indexing scheme for efficient data processing in the Cloud. Our approach can be summarized as follows. First, we build a local B
+
-tree index for each compute node which only indexes data residing on the node. Second, we organize the compute nodes as a structured overlay and publish a portion of the local B
+
-tree nodes to the overlay for efficient query processing. Finally, we propose an adaptive algorithm to select the published B
+
-tree nodes according to query patterns. We conduct extensive experiments on Amazon's EC2, and the results demonstrate that our indexing scheme is dynamic, efficient and scalable.
Fragments and loose associations
Authors: De Capitani di Vimercati Sabrina , Foresti Sara , Jajodia Sushil , Paraboschi Stefano , Samarati Pierangela
Published: June 2014

We propose a modeling of the problem of privacy-compliant data publishing that captures confidentiality constraints on one side and visibility requirements on the other side. Confidentiality constraints express the fact that some attributes, or associations among them, are sensitive and cannot be released. Visibility requirements express requests for views over data that should be provided. We propose a solution based on data fragmentation to split sensitive associations while ensuring visibility. In addition, we show how sensitive associations broken by fragmentation can be released in a sanitized form as
loose associations
formed in a way to guarantee a specified degree of privacy.
NET-FLi
Authors: Fusco Francesco , Stoecklin Marc Ph. , Vlachos Michail
Published: June 2014

The ever-increasing number of intrusions in public and commercial networks has created the need for high-speed archival solutions that continuously store streaming network data to enable forensic analysis and auditing. However, "turning back the clock" for post-attack analyses is not a trivial task. The first major challenge is that the solution has to sustain data archiving under extremely high-speed insertion rates. Moreover, the archives created need to be stored in a format that is compressed but still amenable to indexing. The above requirements make general-purpose databases unsuitable for this task, and, thus, dedicated solutions are required.

In this paper, we describe a prototype solution that satisfies all requirements for high-speed archival storage, indexing and data querying on network flow information. The superior performance of our approach is attributed to the on-the-fly compression and indexing scheme, which is based on compressed bitmap principles. Typical commercial solutions can currently process 20,000--60,000 flows per second. An evaluation of our prototype implementation on current commodity hardware using real-world traffic traces shows its ability to sustain insertion rates ranging from 500,000 to more than 1 million records per second. The system offers interactive query response times that enable administrators to perform complex analysis tasks on-the-fly. Our technique is directly amenable to parallel execution, allowing its application in domains that are challenged by large volumes of historical measurement data, such as network auditing, traffic behavior analysis and large-scale data visualization in service provider networks.
CODS
Authors: Liu Ziyang , Natarajan Sivaramakrishnan , He Bin , Hsiao Hui-I , Chen Yi
Published: June 2014

Database evolution is the process of updating the schema of a database or data warehouse (schema evolution) and evolving the data to the updated schema (data evolution). Database evolution is often necessitated in relational databases due to the changes of data or workload, the suboptimal initial schema design, or the availability of new knowledge of the database. It involves two steps: updating the database schema, and evolving the data to the new schema. Despite the capability of commercial RDBMSs to well optimize query processing, evolving the data during a database evolution through SQL queries is shown to be prohibitively costly. We designed and developed CODS, a platform for efficient
data level
data evolution in column oriented databases, which evolves the data to the new schema without materializing query results or unnecessary compression/decompression as occurred in traditional
query level
approaches. CODS ameliorates the efficiency of data evolution by orders of magnitude compared with commercial or open source RDBMSs.
Geospatial stream query processing using Microsoft SQL Server StreamInsight
Authors: Kazemitabar Seyed Jalal , Demiryurek Ugur , Ali Mohamed , Akdogan Afsin , Shahabi Cyrus
Published: June 2014

Microsoft SQL Server spatial libraries contain several components that handle geometrical and geographical data types. With advances in geo-sensing technologies, there has been an increasing demand for geospatial streaming applications. Microsoft SQL Server StreamInsight (
StreamInsight
, for brevity) is a platform for developing and deploying streaming applications that run continuous queries over high-rate streaming events. With its extensibility infrastructure, StreamInsight enables developers to integrate their domain expertise within the query pipeline in the form of user defined modules.

This demo utilizes the extensibility infrastructure in Microsoft StreamInsight to leverage its continuous query processing capabilities in two directions. The first direction integrates SQL spatial libraries into the continuous query pipeline of StreamInsight. StreamInsight provides a well-defined temporal model over incoming events while SQL spatial libraries cover the spatial properties of events to deliver a solution for spatiotemporal stream query processing. The second direction extends the system with an
analytical refinement and prediction
layer. This layer analyzes historical data that has been accumulated and summarized over the years to refine, smooth and adjust the current query output as well as predict the output in the near future. The demo scenario is based on transportation data in Los Angeles County.
Active complex event processing
Authors: Wang Di , Rundensteiner Elke A. , Wang Han , Ellison Richard T.
Published: June 2014

Our analysis of many real-world event based applications has revealed that existing Complex Event Processing technology (CEP), while effective for efficient pattern matching on event stream, is limited in its capability of reacting in realtime to opportunities and risks detected or environmental changes. We are the first to tackle this problem by providing active rule support embedded directly within the CEP engine, henceforth called Active Complex Event Processing technology, or short, Active CEP. We design the Active CEP model and associated rule language that allows rules to be triggered by CEP system state changes and correctly executed during the continuous query process. Moreover we design an Active CEP infrastructure, that integrates the active rule component into the CEP kernel, allowing fine-grained and optimized rule processing. We demonstrate the power of Active CEP by applying it to the development of a collaborative project with UMass Medical School, which detects potential threads of infection and reminds healthcare workers to perform hygiene precautions in real-time.
Thirteen new players in the team
Authors: Schreiber Tom , Bonetti Simone , Grust Torsten , Mayr Manuel , Rittinger Jan
Published: June 2014

We demonstrate an efficient LINQ to SQL provider and its significant impact on the runtime performance of LINQ programs that process large data volumes. This alternative provider is based on Ferry, compilation technology that lets relational database systems participate in the evaluation of first-order functional programs over nested, ordered data structures. The Ferry-based provider seamlessly hooks into the .NET LINQ framework and generates SQL code that strictly adheres to the semantics of the LINQ data model. Ferry comes with strong code size guarantees and complete support for the LINQ Standard Query Operator family, enabling a truly interactive and compelling LINQ demonstration. A variety of inspection holes may be opened to learn about the internals of the Ferry-based LINQ to SQL provider.
Peer coordination through distributed triggers
Authors: Kantere Verena , Manoubi Maher , Kiringa Iluju , Sellis Timos , Mylopoulos John
Published: June 2014

This is a demonstration of data coordination in a peer data management system through the employment of distributed triggers. The latter express in a declarative manner individual security and consistency requirements of peers, that cannot be ensured by default in the P2P environment. Peers achieve to handle in a transparent way data changes that come from local and remote actions and events. The distributed triggers are implemented as an extension of the active functionality of a centralized commercial DBMS. The language and execution semantics of distributed triggers are integrated in the kernel of the DBMS such that the latter handles transparently and simultaneously both centralized and distributed triggers. Moreover, the management of distributed triggers is associated with a set of peer acquaintance and termination protocols which are incorporated in the centralized DBMS.
TimeTrails
Authors: Strötgen Jannik , Gertz Michael
Published: June 2014

Spatial and temporal data have become ubiquitous in many application domains such as the Geosciences or life sciences. Sophisticated database management systems are employed to manage such structured data. However, an important source of spatio-temporal information that has not been fully utilized are unstructured text documents. In documents, combinations of temporal and spatial expressions form events, which can be mapped to a database structure and organized into trajectories that can be explored. In this context, the coupling of information retrieval techniques with spatio-temporal database concepts leads to new ways for managing and exploring document collections.

In this demonstration, we present TimeTrails, a system for the extraction, querying, storage, and exploration of spatio-temporal information embedded in text documents. The user can query a document collection, and TimeTrails visualizes the spatio-temporal information extracted from relevant documents as document trajectories, resulting in a map-based view of documents. This view helps the user to explore the temporal and spatial content of documents in a meaningful way and to further restrict search results using spatial and temporal predicates.
XSACT
Authors: Liu Ziyang , Natarajan Sivaramakrishnan , Sun Peng , Booher Stephen , Meehan Tim , Winkler Robert , Chen Yi
Published: June 2014

Studies show that about 50% of web search is for information exploration purpose, where a user would like to investigate, compare, evaluate, and synthesize multiple relevant results. Due to the absence of general tools that can effectively analyze and differentiate multiple results, a user has to manually read and comprehend potentially large results in an exploratory search. Such a process is time consuming, labor intensive and error prone. With meta information embedded, keyword search on structured data provides the potential for automating or semi-automating the comparison of multiple results.

In this demo we present a system XSACT for differentiating search results on structured data. XSACT takes as input a set of structured results, and outputs a Differentiation Feature Set (DFS) for each result to highlight their differences within a size bound. The problem of generating DFSs with maximal differences is proved to be NP-hard. XSACT adopts efficient algorithms for DFS generation, and features a user-friendly interface that effectively interacts with the users to help them compare search results.
ObjectRunner
Authors: Abdessalem Talel , Cautis Bogdan , Derouiche Nora
Published: June 2014

We present in this paper ObjectRunner, a system for extracting, integrating and querying structured data from the Web. Our system harvests real-world items from template-based HTML pages (the so-called structured Web). It illustrates a two-phase querying of the Web, in which an intentional description of the targeted data is first provided, in a flexible and widely applicable manner. ObjectRunner follows then a lightweight, best-effort approach, leveraging both the input description and the source structure. This process is domain-independent, in the sense that it applies to any relation, either flat or nested, describing real-world items. We advocate via our prototype that fully automatic extraction and integration of structured data can be done fast and effectively, when the redundancy of the Web meets knowledge over the to-be-extracted data. We present the technical details and the overall platform through several application scenarios on real-life Web sources.
InZeit
Authors: Setty Vinay , Bedathur Srikanta , Berberich Klaus , Weikum Gerhard
Published: June 2014

Web archives are useful resources to find out about the temporal evolution of persons, organizations, products, or other topics. However, even when advanced text search functionality is available, gaining insights into the temporal evolution of a topic can be a tedious task and often requires sifting through many documents.

The demonstrated system named InZeit (pronounced "insight") assists users by determining insightful time points for a given query. These are the time points at which the top-
k
time-travel query result changes substantially and for which the user should therefore inspect query results. InZeit determines the
m
most insightful time points efficiently using an extended segment tree for in-memory bookkeeping.
SOLOMON
Authors: Dong Xin Luna , Berti-Equille Laure , Hu Yifan , Srivastava Divesh
Published: June 2014

We live in the Information Era, with access to a huge amount of information from a variety of data sources. However, data sources are of different qualities, often providing conflicting, out-of-date and incomplete data. Data sources can also easily copy, reformat and modify data from other sources, propagating erroneous data. These issues make the identification of high quality information and sources non-trivial.

We demonstrate the Solomon system, whose core is a module that detects copying between sources. We demonstrate that we can effectively detect copying relationship between data sources, leverage the results in truth discovery, and provide a user-friendly interface to facilitate users in identifying sources that best suit their information needs.
Keymantic
Authors: Bergamaschi Sonia , Domnori Elton , Guerra Francesco , Orsini Mirko , Lado Raquel Trillo , Velegrakis Yannis
Published: June 2014

We propose the demonstration of
Keymantic
, a system for keyword-based searching in relational databases that does not require a-priori knowledge of instances held in a database. It finds numerous applications in situations where traditional keyword-based searching techniques are inapplicable due to the unavailability of the database contents for the construction of the required indexes.
Distributed caching platforms
Authors: Nori Anil K.
Published: June 2014

With the advances in processing, memory, and connectivity technologies, applications are becoming increasingly distributed, data-centric, and web based. These applications demand support for large number of users at high performance, requiring extreme scale, high availability, and low latency data access. Such applications are known as Extreme Transaction Processing (XTP) applications. Distributed Caching Platforms exploit the advances in the memory and networking technologies to fuse memory on multiple machines into a single unified global memory providing data access at low latencies. These Distributed Caching Platforms are evolving into in-memory data platforms for XTP applications. This tutorial provides a comprehensive overview of Distributed Caching Platform technologies and their usage.
Techniques for similarity searching in multimedia databases
Authors: Samet Hanan
Published: June 2014

Techniques for similarity searching in multimedia databases are reviewed. This includes a discussion of the curse of dimensionality, as well as multidimensional indexing, distance-based indexing, and the actual search process which is realized by nearest neighbor finding.
Similarity search and mining in uncertain databases
Authors: Renz Matthias , Cheng Reynold , Kriegel Hans-Peter
Published: June 2014

Managing, searching and mining uncertain data has achieved much attention in the database community recently due to new sensor technologies and new ways of collecting data. There is a number of challenges in terms of collecting, modelling, representing, querying, indexing and mining uncertain data. In its scope, the diversity of approaches addressing these topics is very high because the underlying assumptions of uncertainty are different across different papers. This tutorial provides a comprehensive and comparative overview of general techniques for the key topics in the fields of querying, indexing and mining uncertain data. In particular, it identifies the most generic types of probabilistic similarity queries and discusses general algorithmic methods to answer such queries efficiently. In addition, the tutorial sketches probabilistic methods for important data mining applications in the context of uncertain data with special emphasis on probabilistic clustering and probabilistic pattern mining. The intended audience of this tutorial ranges from novice researchers to advanced experts as well as practitioners from any application domain dealing with uncertain data retrieval and mining.
Cloud databases
Authors: Abadi Daniel J. , Carey Michael , Chaudhuri Surajit , Garcia-Molina Hector , Patel Jignesh M. , Ramakrishnan Raghu
Published: June 2014

The panelists will discuss what characterizes data management in the cloud, and how this differs from the broad range of applications that conventional database management systems have supported over the past few decades. They will examine whether we need to develop new technologies to address demonstrably new challenges, or whether we can largely re-position existing systems and approaches. The discussion will cover data analysis in the cloud using Map-Reduce based systems such as Hadoop, and cloud data serving (and so-called "No SQL" systems).