bluuebunny/crossref_metadata_2025 huggingface dataset:
Sketch-based geometric monitoring of distributed stream queries
Authors: Garofalakis Minos , Keren Daniel , Samoladas Vasilis
Published: June 2014

Emerging large-scale monitoring applications rely on continuous tracking of complex data-analysis queries over collections of massive, physically-distributed data streams. Thus, in addition to the space- and time-efficiency requirements of conventional stream processing (at each remote monitor site), effective solutions also need to guarantee communication efficiency (over the underlying communication network). The complexity of the monitored query adds to the difficulty of the problem -- this is especially true for nonlinear queries (e.g., joins), where no obvious solutions exist for distributing the monitor condition across sites. The recently proposed geometric method offers a generic methodology for splitting an arbitrary (non-linear) global threshold-monitoring task into a collection of local site constraints; still, the approach relies on maintaining the complete stream(s) at each site, thus raising serious efficiency concerns for massive data streams. In this paper, we propose novel algorithms for efficiently tracking a broad class of complex aggregate queries in such distributed-streams settings. Our tracking schemes rely on a novel combination of the geometric method with compact sketch summaries of local data streams, and maintain approximate answers with provable error guarantees, while optimizing space and processing costs at each remote site and communication cost across the network. One of our key technical insights for the effective use of the geometric method lies in exploiting a much lower-dimensional space for monitoring the sketch-based estimation query. Due to the complex, highly nonlinear nature of these estimates, efficiently monitoring the local geometric constraints poses challenging algorithmic issues for which we propose novel solutions. Experimental results on real-life data streams verify the effectiveness of our approach.
Hadoop GIS
Authors: Aji Ablimit , Wang Fusheng , Vo Hoang , Lee Rubao , Liu Qiaoling , Zhang Xiaodong , Saltz Joel
Published: June 2014

Support of high performance queries on large volumes of spatial data becomes increasingly important in many application domains, including geospatial problems in numerous fields, location based services, and emerging scientific applications that are increasingly data- and compute-intensive. The emergence of massive scale spatial data is due to the proliferation of cost effective and ubiquitous positioning technologies, development of high resolution imaging technologies, and contribution from a large number of community users. There are two major challenges for managing and querying massive spatial data to support spatial queries: the explosion of spatial data, and the high computational complexity of spatial queries. In this paper, we present Hadoop-GIS - a scalable and high performance spatial data warehousing system for running large scale spatial queries on Hadoop. Hadoop-GIS supports multiple types of spatial queries on MapReduce through spatial partitioning, customizable spatial query engine RESQUE, implicit parallel spatial query execution on MapReduce, and effective methods for amending query results through handling boundary objects. Hadoop-GIS utilizes global partition indexing and customizable on demand local spatial indexing to achieve efficient query processing. Hadoop-GIS is integrated into Hive to support declarative spatial queries with an integrated architecture. Our experiments have demonstrated the high efficiency of Hadoop-GIS on query response and high scalability to run on commodity clusters. Our comparative experiments have showed that performance of Hadoop-GIS is on par with parallel SDBMS and outperforms SDBMS for compute-intensive queries. Hadoop-GIS is available as a set of library for processing spatial queries, and as an integrated software package in Hive.
How to maximize the value of big data with the open source SpagoBI suite through a comprehensive approach
Authors: Franceschini Monica
Published: June 2014

This paper describes the approach adopted by SpagoBI suite (www.spagobi.org) to manage large volumes of heterogeneous structured and unstructured data, to perform real-time Business Intelligence on Big Data streaming and to give meaning to data through the semantic analysis. SpagoBI supplies meaningful data insights through the main concept of persistable and schedulable datasets, and using tools such as self-service BI, ad-hoc reporting, interactive dashboards and explorative analysis.
Big data integration
Authors: Dong Xin Luna , Srivastava Divesh
Published: June 2014

The Big Data era is upon us: data is being generated, collected and analyzed at an unprecedented scale, and data-driven decision making is sweeping through society. Since the value of data explodes when it can be linked and fused with other data, addressing the big data integration (BDI) challenge is critical to realizing the promise of Big Data.

BDI differs from traditional data integration in many dimensions: (i) the number of data sources, even for a single domain, has grown to be in the tens of thousands, (ii) many of the data sources are very dynamic, as a huge amount of newly collected data are continuously made available, (iii) the data sources are extremely heterogeneous in their structure, with considerable variety even for substantially similar entities, and (iv) the data sources are of widely differing qualities, with significant differences in the coverage, accuracy and timeliness of data provided. This tutorial explores the progress that has been made by the data integration community on the topics of schema mapping, record linkage and data fusion in addressing these novel challenges faced by big data integration, and identifies a range of open problems for the community.
Discovering denial constraints
Authors: Chu Xu , Ilyas Ihab F. , Papotti Paolo
Published: June 2014

Integrity constraints (ICs) provide a valuable tool for enforcing correct application semantics. However, designing ICs requires experts and time. Proposals for automatic discovery have been made for some formalisms, such as functional dependencies and their extension conditional functional dependencies. Unfortunately, these dependencies cannot express many common business rules. For example, an American citizen cannot have lower salary and higher tax rate than another citizen in the same state. In this paper, we tackle the challenges of discovering dependencies in a more expressive integrity constraint language, namely Denial Constraints (DCs). DCs are expressive enough to overcome the limits of previous languages and, at the same time, have enough structure to allow efficient discovery and application in several scenarios. We lay out theoretical and practical foundations for DCs, including a set of sound inference rules and a linear algorithm for implication testing. We then develop an efficient instance-driven DC discovery algorithm and propose a novel scoring function to rank DCs for user validation. Using real-world and synthetic datasets, we experimentally evaluate scalability and effectiveness of our solution.
Diversified top-k graph pattern matching
Authors: Fan Wenfei , Wang Xin , Wu Yinghui
Published: June 2014

Graph pattern matching has been widely used in e.g., social data analysis. A number of matching algorithms have been developed that, given a graph patternQand a graphG, compute the setM(Q,G)of matches ofQinG. However, these algorithms often return an excessive number of matches, and are expensive on large real-life social graphs. Moreover, in practice many social queries are to find matches of a specific pattern node, rather than the entireM(Q,G).

This paper studies top-kgraph pattern matching. (1) We revise graph pattern matching defined in terms of simulation, by supporting a designated output nodeuo. GivenGandQ, it is to find those nodes inM(Q,G)that matchuo, instead of the large setM(Q,G). (2) We study two classes of functions for ranking the matches: relevance functions δr() based on, e.g., social impact, and distance functions δd() to cover diverse elements. (3) We develop two algorithms for computing top-kmatches ofuobased on δr(), with the early termination property, i.e., they find top-kmatches without computing the entireM(Q,G). (4) We also study diversified top-kmatching, a bi-criteria optimization problem based on both δr() and δd(). We show that its decision problem is NP-complete. Nonetheless, we provide an approximation algorithm with performance guarantees and a heuristic one with the early termination property. (5) Using real-life and synthetic data, we experimentally verify that our (diversified) top-kmatching algorithms are effective, and outperform traditional matching algorithms in efficiency.
Supporting distributed feed-following apps over edge devices
Authors: Chandramouli Badrish , Nath Suman , Zhou Wenchao
Published: June 2014

In feed-following applications such as Twitter and Facebook, users (consumers) follow a large number of other users (producers) to get personalized feeds, generated by blending producers- feeds. With the proliferation of Cloud-connected smart edge devices such as smartphones, producers and consumers of many feed-following applications reside on edge devices and the Cloud. An important design goal of such applications is to minimize communication (and energy) overhead of edge devices. In this paper, we abstract distributed feed-following applications as a view maintenance problem, with the goal of optimally placing the views on edge devices and in the Cloud to minimize communication overhead between edge devices and the Cloud. The view placement problem for general network topology is NP Hard; however, we show that for the special case of Cloud-edge topology, locally optimal solutions yield a globally optimal view placement solution. Based on this powerful result, we propose view placement algorithms that are highly efficient, yet provably minimize global network cost. Compared to existing works on feed-following applications, our algorithms are more general--they support views with selection, projection, correlation (join) and arbitrary black-box operators, and can even refer to other views. We have implemented our algorithms within a distributed feed-following architecture over real smartphones and the Cloud. Experiments over real datasets indicate that our algorithms are highly scalable and orders-of-magnitude more efficient than existing strategies for optimal placement. Further, our results show that optimal placements generated by our algorithms are often several factors better than simpler schemes.
Rank discovery from web databases
Authors: Thirumuruganathan Saravanan , Zhang Nan , Das Gautam
Published: June 2014

Many web databases are only accessible through a proprietary search interface which allows users to form a query by entering the desired values for a few attributes. After receiving a query, the system returns the top-kmatching tuples according to a pre-determined ranking function. Since the rank of a tuple largely determines the attention it receives from website users, ranking information for any tuple - not just the top-ranked ones - is often of significant interest to third parties such as sellers, customers, market researchers and investors. In this paper, we define a novel problem of rank discovery over hidden web databases. We introduce a taxonomy of ranking functions, and show that different types of ranking functions require fundamentally different approaches for rank discovery. Our technical contributions include principled and efficient randomized algorithms for estimating the rank of a given tuple, as well as negative results which demonstrate the inefficiency of any deterministic algorithm. We show extensive experimental results over real-world databases, including an online experiment at Amazon.com, which illustrates the effectiveness of our proposed techniques.
SPARSI
Authors: Rekatsinas Theodoros , Deshpande Amol , Machanavajjhala Ashwin
Published: June 2014

We present SPARSI, a novel theoretical framework for partitioning sensitive data across multiple non-colluding adversaries. Most work in privacy-aware data sharing has considered disclosing summaries where the aggregate information about the data is preserved, but sensitive user information is protected. Nonetheless, there are applications, including online advertising, cloud computing and crowdsourcing markets, where detailed and fine-grained user data must be disclosed. We consider a new data sharing paradigm and introduce the problem of privacy-aware data partitioning, where a sensitive dataset must be partitioned among
k
untrusted parties (adversaries). The goal is to maximize the utility derived by partitioning and distributing the dataset, while minimizing the total amount of sensitive information disclosed. The data should be distributed so that an adversary, without colluding with other adversaries, cannot draw additional inferences about the private information, by linking together multiple pieces of information released to her. The assumption of no collusion is both reasonable and necessary in the above application domains that require release of private user information. SPARSI enables us to formally define privacy-aware data partitioning using the notion of sensitive properties for modeling private information and a hypergraph representation for describing the interdependencies between data entries and private information. We show that solving privacy-aware partitioning is, in general, NP-hard, but for specific information disclosure functions, good approximate solutions can be found using relaxation techniques. Finally, we present a local search algorithm applicable to generic information disclosure functions. We conduct a rigorous performance evaluation with real-world and synthetic datasets that illustrates the effectiveness of SPARSI at partitioning sensitive data while minimizing disclosure.
Scalable column concept determination for web tables using large knowledge bases
Authors: Deng Dong , Jiang Yu , Li Guoliang , Li Jian , Yu Cong
Published: June 2014

Tabular data on the Web has become a rich source of structured data that is useful for ordinary users to explore. Due to its potential, tables on the Web have recently attracted a number of studies with the goals of understanding the semantics of those Web tables and providing effective search and exploration mechanisms over them. An important part of table understanding and search is column concept determination, i.e., identifying the most appropriate concepts associated with the columns of the tables. The problem becomes especially challenging with the availability of increasingly rich knowledge bases that contain hundreds of millions of entities.

In this paper, we focus on an important instantiation of the column concept determination problem, namely, the concepts of a column are determined by fuzzy matching its cell values to the entities within a large knowledge base. We provide an efficient and scalable MapReduce-based solution that is scalable to both the number of tables and the size of the knowledge base and propose two novel techniques: knowledge concept aggregation and knowledge entity partition. We prove that both the problem of finding the optimal aggregation strategy and that of finding the optimal partition strategy are NP-hard, and propose efficient heuristic techniques by leveraging the hierarchy of the knowledge base. Experimental results on real-world datasets show that our method achieves high annotation quality and performance, and scales well.
Top-K structural diversity search in large networks
Authors: Huang Xin , Cheng Hong , Li Rong-Hua , Qin Lu , Yu Jeffrey Xu
Published: June 2014

Social contagion depicts a process of information (e.g., fads, opinions, news) diffusion in the online social networks. A recent study reports that in a social contagion process the probability of contagion is tightly controlled by the number of connected components in an individual's neighborhood. Such a number is termed structural diversity of an individual and it is shown to be a key predictor in the social contagion process. Based on this, a fundamental issue in a social network is to find top-kusers with the highest structural diversities. In this paper, we, for the first time, study the top-kstructural diversity search problem in a large network. Specifically, we develop an effective upper bound of structural diversity for pruning the search space. The upper bound can be incrementally refined in the search process. Based on such upper bound, we propose an efficient framework for top-kstructural diversity search. To further speed up the structural diversity evaluation in the search process, several carefully devised heuristic search strategies are proposed. Extensive experimental studies are conducted in 13 real-world large networks, and the results demonstrate the efficiency and effectiveness of the proposed methods.
QUEST
Authors: Bergamaschi Sonia , Guerra Francesco , Interlandi Matteo , Trillo-Lado Raquel , Velegrakis Yannis
Published: June 2014

We showcase QUEST (QUEry generator for STructured sources), a search engine for relational databases that combines semantic and machine learning techniques for transforming keyword queries into meaningful SQL queries. The search engine relies on two approaches: the forward, providing mappings of keywords into database terms (names of tables and attributes, and domains of attributes), and the backward, computing the paths joining the data structures identified in the forward step. The results provided by the two approaches are combined within a probabilistic framework based on the Dempster-Shafer Theory. We demonstrate QUEST capabilities, and we show how, thanks to the flexibility obtained by the probabilistic combination of different techniques, QUEST is able to compute high quality results even with few training data and/or with hidden data sources such as those found in the Deep Web.
GroupFinder
Authors: Bøgh Kenneth S. , Skovsgaard Anders , Jensen Christian S.
Published: June 2014

The notion of point-of-interest (PoI) has existed since paper road maps began to include markings of useful places such as gas stations, hotels, and tourist attractions. With the introduction of geopositioned mobile devices such as smartphones and mapping services such as Google Maps, the retrieval of PoIs relevant to a user's intent has became a problem of automated spatio-textual information retrieval. Over the last several years, substantial research has gone into the invention of functionality and efficient implementations for retrieving nearby PoIs. However, with a couple of exceptions existing proposals retrieve results at single-PoI granularity. We assume that a mobile device user issues queries consisting of keywords and an automatically supplied geo-position, and we target the common case where the user wishes to find nearby groups of PoIs that are relevant to the keywords. Such groups are relevant to users who wish to conveniently explore several options before making a decision such as to purchase a specific product. Specifically, we demonstrate a practical proposal for finding top-
k
PoI groups in response to a query. We show how problem parameter settings can be mapped to options that are meaningful to users. Further, although this kind of functionality is prone to combinatorial explosion, we will demonstrate that the functionality can be supported efficiently in practical settings.
Graph queries in a next-generation Datalog system
Authors: Shkapsky Alexander , Zeng Kai , Zaniolo Carlo
Published: June 2014

Recent theoretical advances have enabled the use of special monotonic aggregates in recursion. These special aggregates make possible the concise expression and efficient implementation of a rich new set of advanced applications. Among these applications, graph queries are particularly important because of their pervasiveness in data intensive application areas. In this demonstration, we present our Deductive Application Language (DeAL) System, the first of a new generation of Deductive Database Systems that support applications that could not be expressed using regular stratification, or could be expressed using XY-stratification (also supported in DeAL) but suffer from inefficient execution. Using example queries, we will (i) show how complex graph queries can be concisely expressed using DeAL and (ii) illustrate the formal semantics and efficient implementation of these powerful new monotonic constructs.
iRoad
Authors: Hendawi Abdeltawab M. , Bao Jie , Mokbel Mohamed F.
Published: June 2014

This demo presents the iRoad framework for evaluating predictive queries on moving objects for road networks. The main promise of the iRoad system is to support a variety of common predictive queries including predictive point query, predictive range query, predictive KNN query, and predictive aggregate query. The iRoad framework is equipped with a novel data structure, named reachability tree, employed to determine the reachable nodes for a moving object within a specified future time Τ. In fact, the reachability tree prunes the space around each object in order to significantly reduce the computation time. So, iRoad is able to scale up to handle real road networks with millions of nodes, and it can process heavy workloads on large numbers of moving objects. During the demo, audience will be able to interact with iRoad through a well designed Graphical User Interface to issue different types of predictive queries on a real road network, to obtain the predictive heatmap of the area of interest, to follow the creation and the dynamic update of the reachability tree around a specific moving object, and finally to examine the system efficiency and scalability.
Lazy ETL in action
Authors: Kargín Yağíz , Ivanova Milena , Zhang Ying , Manegold Stefan , Kersten Martin
Published: June 2014

Both scientific data and business data have analytical needs. Analysis takes place after a scientific data warehouse is eagerly filled with all data from external data sources (repositories). This is similar to the initial loading stage of Extract, Transform, and Load (ETL) processes that drive business intelligence. ETL can also help scientific data analysis. However, the initial loading is a time and resource consuming operation. It might not be entirely necessary, e.g. if the user is interested in only a subset of the data.

We propose to demonstrate Lazy ETL, a technique to lower costs for initial loading. With it, ETL is integrated into the query processing of the scientific data warehouse. For a query, only the required data items are extracted, transformed, and loaded transparently on-the-fly.

The demo is built around concrete implementations of Lazy ETL for seismic data analysis. The seismic data warehouse is ready for query processing, without waiting for long initial loading. The audience fires analytical queries to observe the internal mechanisms and modifications that realize each of the steps; lazy extraction, transformation, and loading.
EnviroMeter
Authors: Sathe Saket , Oviedo Arthur , Chakraborty Dipanjan , Aberer Karl
Published: June 2014

Efficiently querying data collected from Large-area Community driven Sensor Networks (LCSNs) is a new and challenging problem. In our previous works, we proposed adaptive techniques for learning models (e.g., statistical, nonparametric, etc.) from such data, considering the fact that LCSN data is typically geo-temporally skewed. In this paper, we present a demonstration of EnviroMeter. EnviroMeter uses our adaptive model creation techniques for processing continuous queries on community-sensed environmental pollution data. Subsequently, it efficiently pushes current pollution updates to GPS-enabled smartphones (through its Android application) or displays it via a web-interface. We experimentally demonstrate that our model-based query processing approach is orders of magnitude efficient than processing the queries over indexed raw data.
A demonstration of iterative parallel array processing in support of telescope image analysis
Authors: Moyers Matthew , Soroush Emad , Wallace Spencer C. , Krughoff Simon , Vanderplas Jake , Balazinska Magdalena , Connolly Andrew
Published: June 2014

In this demonstration, we present AscotDB, a new tool for the analysis of telescope image data. AscotDB results from the integration of ASCOT, a Web-based tool for the collaborative analysis of telescope images and their metadata, and SciDB, a parallel array processing engine. We demonstrate the novel data exploration supported by this integrated tool on a 1 TB dataset comprising scientifically accurate, simulated telescope images. We also demonstrate novel iterative-processing features that we added to SciDB in order to support this use-case.
Mining and linking patterns across live data streams and stream archives
Authors: Yang Di , Zhao Kaiyu , Hasan Maryam , Lu Hanyuan , Rundensteiner Elke , Ward Matthew
Published: June 2014

We will demonstrate the visual analytics system V istreamT, that supports interactive mining of complex patterns within and across live data streams and stream pattern archives. Our system is equipped with both computational pattern mining and visualization techniques, which allow it to not only efficiently discover and manage patterns but also effectively convey the mining results to human analysts through visual displays. In our demonstration, we will illustrate that with V istreamT, analysts can easily submit, monitor and interact with a broad range of query types for pattern mining. This includes novel strategies for extracting complex patterns from streams in real time, summarizing neighbour-based patterns using multi-resolution compression strategies, selectively pushing patterns into the stream archive, validating the popularity or rarity of stream patterns by stream archive matching, and pattern evolution tracking to link patterns across time.
Complete approximations of incomplete queries
Authors: Savković Ognjen , Mirza Paramita , Tomasi Alex , Nutt Werner
Published: June 2014

We present a system that computes for a query that may be incomplete, complete approximations from above and from below.

We assume a setting where queries are posed over a partially complete database, that is, a database that is generally incomplete, but is known to contain complete information about specific aspects of its application domain. Which parts are complete, is described by a set of so-called table-completeness statements. Previous work led to a theoretical framework and an implementation that allowed one to determine whether in such a scenario a given conjunctive query is guaranteed to return a complete set of answers or not.

With the present demonstrator we show how to reformulate the original query in such a way that answers are guaranteed to be complete. If there exists a more general complete query, there is a unique most specific one, which we find. If there exists a more specific complete query, there may even be infinitely many. In this case, we find the least specific specializations whose size is bounded by a threshold provided by the user.

Generalizations are computed by a fixpoint iteration, employing an answer set programming engine. Specializations are found leveraging unification from logic programming.
User analytics with UbeOne
Authors: Koutrika Georgia , Lin Qian , Liu Jerry
Published: June 2014

As web and mobile applications become more sensitive to the user context, there is a shift from purely off-line processing of user actions (log analysis) to real-time user analytics that can generate information about the user context to be instantly leveraged by the application. Ubeone is a system that enables both real-time and aggregate analytics from user data. The system is designed as a set of lightweight, composeable mechanisms that can progressively and collectively analyze a user action, such as pinning, saving or printing a web page. We will demonstrate the system capabilities on analyzing a live feed of URLs printed through a proprietary, web browser plug-in. This is in fact the first analysis of web printing activity. We will also give a taste of how the system can enable instant recommendations based on the user context.
Automatic ontology-based user profile learning from heterogeneous web resources in a big data context
Authors: Hoppe Anett , Nicolle C. , Roxin A.
Published: June 2014

The Web has developed to the biggest source of information and entertainment in the world. By its size, its adaptability and flexibility, it challenged our current paradigms on information sharing in several areas. By offering everybody the opportunity to release own contents in a fast and cheap way, the Web already led to a revolution of the traditional publishing world and just now, it commences to change the perspective on advertisements. With the possibility to adapt the contents displayed on a page dynamically based on the viewer's context, campaigns launched to target rough customer groups will become an element of the past. However, this new ecosystem, that relates advertisements with the user, heavily relies on the quality of the underlying user profile. This profile has to be able to model any combination of user characteristics, the relations between its composing elements and the uncertainty that stems from the automated processing of real-world data. The work at hand describes the beginnings of a PhD project that aims to tackle those issues using a combination of data analysis, ontology engineering and processing of big data resources provided by an industrial partner. The final goal is to automatically construct and populate a profile ontology for each user identified by the system. This allows to associate these users to high-value audience segments in order to drive digital marketing.
Getting unique solution in data exchange
Authors: Ngo Nhung , Franconi Enrico
Published: June 2014

A schema mapping is a high-level specification in which the relationship between two database schemas is described. In data exchange, schema mappings are one-way mappings that describe which data can be brought from source data to target data. Therefore, given a source instance and a mapping, there might be more than one valid target instance. This fact causes many problems in query answering over target data for non-conjunctive queries. To make query answering feasible for all queries, we focus on a methodology for extending the original schema mapping to guarantee the uniqueness of target instance corresponding to a source instance. To this end, we introduce a theoretical framework where the problem is transformed to an abduction problem, namely, definability abduction. We apply the framework to relational data exchange setting and solve the problem by pointing out minimal solutions according to a specific semantic minimality criterion.
Efficient error-tolerant query autocompletion
Authors: Xiao Chuan , Qin Jianbin , Wang Wei , Ishikawa Yoshiharu , Tsuda Koji , Sadakane Kunihiko
Published: June 2014

Query autocompletion is an important feature saving users many keystrokes from typing the entire query. In this paper we study the problem of query autocompletion that tolerates errors in users' input using edit distance constraints. Previous approaches index data strings in a trie, and continuously maintain all the prefixes of data strings whose edit distance from the query are within the threshold. The major inherent problem is that the number of such prefixes is huge for the first few characters of the query and is exponential in the alphabet size. This results in slow query response even if the entire query approximately matches only few prefixes.

In this paper, we propose a novel neighborhood generation-based algorithm, IncNGTrie, which can achieve up to two orders of magnitude speedup over existing methods for the error-tolerant query autocompletion problem. Our proposed algorithm only maintains a small set of active nodes, thus saving both space and time to process the query. We also study efficient duplicate removal which is a core problem in fetching query answers. In addition, we propose optimization techniques to reduce our index size, as well as discussions on several extensions to our method. The efficiency of our method is demonstrated against existing methods through extensive experiments on real datasets.
On the complexity of query result diversification
Authors: Deng Ting , Fan Wenfei
Published: June 2014

Query result diversification is a bi-criteria optimization problem for ranking query results. Given a databaseD, a queryQand a positive integerk, it is to find a set ofktuples fromQ(D)such that the tuples are as relevant as possible to the query, and at the same time, as diverse as possible to each other. Subsets ofQ(D)are ranked by an objective function defined in terms of relevance and diversity. Query result diversification has found a variety of applications in databases, information retrieval and operations research.

This paper studies the complexity of result diversification for relational queries. We identify three problems in connection with query result diversification, to determine whether there exists a set ofktuples that is ranked above a bound with respect to relevance and diversity, to assess the rank of a givenk-element set, and to count how manyk-element sets are ranked above a given bound. We study these problems for a variety of query languages and for three objective functions. We establish the upper and lower bounds of these problems, all matching, for both combined complexity and data complexity. We also investigate several special settings of these problems, identifying tractable cases.
Low-latency multi-datacenter databases using replicated commit
Authors: Mahmoud Hatem , Nawab Faisal , Pucher Alexander , Agrawal Divyakant , El Abbadi Amr
Published: June 2014

Web service providers have been using NoSQL datastores to provide scalability and availability for globally distributed data at the cost of sacrificing transactional guarantees. Recently, major web service providers like Google have moved towards building storage systems that provide ACID transactional guarantees for globally distributed data. For example, the newly published system, Spanner, uses Two-Phase Commit and Two-Phase Locking to provide atomicity and isolation for globally distributed data, running on top of Paxos to provide fault-tolerant log replication. We show in this paper that it is possible to provide the same ACID transactional guarantees for multi-datacenter databases with fewer cross-datacenter communication trips, compared to replicated logging. Instead of replicating the transactional log, we replicate the commit operation itself, by running Two-Phase Commit multiple times in different datacenters and using Paxos to reach consensus among datacenters as to whether the transaction should commit. Doing so not only replaces several inter-datacenter communication trips with intra-datacenter communication trips, but also allows us to integrate atomic commitment and isolation protocols with consistent replication protocols to further reduce the number of cross-datacenter communication trips needed for consistent replication; for example, by eliminating the need for an election phase in Paxos. We analyze our approach in terms of communication trips to compare it against the log replication approach, then we conduct an extensive experimental study to compare the performance and scalability of both approaches under various multi-datacenter setups.
Permuting data on random-access block storage
Authors: Thonangi Risi , Yang Jun
Published: June 2014

Permutation is a fundamental operator for array data, with applications in, for example, changing matrix layouts and reorganizing data cubes. We consider the problem of permuting large quantities of data stored on secondary storage that supports fast random block accesses, such as solid state drives and distributed key-value stores. Faster random accesses open up interesting new opportunities for permutation. While external merge sort has often been used for permutation, it is an overkill that fails to exploit the property of permutation fully and carries unnecessary overhead in storing and comparing keys. We propose faster algorithms with lower memory requirements for a large, useful class of permutations. We also tackle practical challenges that traditional permutation algorithms have not dealt with, such as exploiting random block accesses more aggressively, considering the cost asymmetry between reads and writes, and handling arbitrary data dimension sizes (as opposed to perfect powers often assumed by previous work). As a result, our algorithms are faster and more broadly applicable.
Probabilistic query rewriting for efficient and effective keyword search on graph data
Authors: Zhang Lei , Tran Thanh , Rettinger Achim
Published: June 2014

The problem of rewriting keyword search queries on graph data has been studied recently, where the main goal is to clean user queries by rewriting keywords as valid tokens appearing in the data and grouping them into meaningful segments. The main solution to this problem employs heuristics for ranking query rewrites and a dynamic programming algorithm for computing them. Based on a broader set of queries defined by an existing benchmark, we show that the use of these heuristics does not yield good results. We propose a novel probabilistic framework, which enables the optimality of a query rewrite to be estimated in a more principled way. We show that our approach outperforms existing work in terms of effectiveness and efficiency of query rewriting. More importantly, we provide the first results indicating query rewriting can indeed improve overall keyword search runtime performance and result quality.
Instant loading for main memory databases
Authors: Mühlbauer Tobias , Rödiger Wolf , Seilbeck Robert , Reiser Angelika , Kemper Alfons , Neumann Thomas
Published: June 2014

eScience and big data analytics applications are facing the challenge of efficiently evaluating complex queries over vast amounts of structured text data archived in network storage solutions. To analyze such data in traditional disk-based database systems, it needs to be bulk loaded, an operation whose performance largely depends on the wire speed of the data source and the speed of the data sink, i.e., the disk. As the speed of network adapters and disks has stagnated in the past, loading has become a major bottleneck. The delays it is causing are now ubiquitous as text formats are a preferred storage format for reasons of portability.

But the game has changed: Ever increasing main memory capacities have fostered the development of in-memory database systems and very fast network infrastructures are on the verge of becoming economical. While hardware limitations for fast loading have disappeared, current approaches for main memory databases fail to saturate the now available wire speeds of tens of Gbit/s. With Instant Loading, we contribute a novel CSV loading approach that allows scalable bulk loading at wire speed. This is achieved by optimizing all phases of loading for modern super-scalar multi-core CPUs. Large main memory capacities and Instant Loading thereby facilitate a very efficient data staging processing model consisting of instantaneous load-work-unload cycles across data archives on a single node. Once data is loaded, updates and queries are efficiently processed with the flexibility, security, and high performance of relational main memory databases.
Scalable XML query processing using parallel pushdown transducers
Authors: Ogden Peter , Thomas David , Pietzuch Peter
Published: June 2014

In online social networking, network monitoring and financial applications, there is a need to query high rate streams of XML data, but methods for executing individual XPath queries on streaming XML data have not kept pace with multicore CPUs. For data-parallel processing, a single XML stream is typically split into well-formed fragments, which are then processed independently. Such an approach, however, introduces a sequential bottleneck and suffers from low cache locality, limiting its scalability across CPU cores.

We describe a data-parallel approach for the processing of streaming XPath queries based on pushdown transducers. Our approach permits XML data to be split into arbitrarilysized chunks, with each chunk processed by a parallel automaton instance. Since chunks may be malformed, our automata consider all possible starting states for XML elements and build mappings from starting to finishing states. These mappings can be constructed independently for each chunk by different CPU cores. For streaming queries from the XPathMark benchmark, we show a processing throughput of 2.5 GB/s, with near linear scaling up to 64 CPU cores.
Summarizing answer graphs induced by keyword queries
Authors: Wu Yinghui , Yang Shengqi , Srivatsa Mudhakar , Iyengar Arun , Yan Xifeng
Published: June 2014

Keyword search has been popularly used to query graph data. Due to the lack of structure support, a keyword query might generate an excessive number of matches, referred to as "answer graphs", that could include different relationships among keywords. An ignored yet important task is to group and summarize answer graphs that share similar structures and contents for better query interpretation and result understanding. This paper studies the summarization problem for the answer graphs induced by a keyword query
Q
. (1) A notion of summary graph is proposed to characterize the summarization of answer graphs. Given
Q
and a set of answer graphs G, a summary graph preserves the relation of the keywords in
Q
by summarizing the paths connecting the keywords nodes in G. (2) A quality metric of summary graphs, called coverage ratio, is developed to measure information loss of summarization. (3) Based on the metric, a set of summarization problems are formulated, which aim to find minimized summary graphs with certain coverage ratio. (a) We show that the complexity of these summarization problems ranges from ptime to NP-complete. (b) We provide exact and heuristic summarization algorithms. (4) Using real-life and synthetic graphs, we experimentally verify the effectiveness and the efficiency of our techniques.
Query-driven approach to entity resolution
Authors: Altwaijry Hotham , Kalashnikov Dmitri V. , Mehrotra Sharad
Published: June 2014

This paper explores "on-the-fly" data cleaning in the context of a user query. A novel Query-Driven Approach (QDA) is developed that performs a minimal number of cleaning steps that are only necessary to answer a given selection query correctly. The comprehensive empirical evaluation of the proposed approach demonstrates its significant advantage in terms of efficiency over traditional techniques for query-driven applications.
Scaling queries over big RDF graphs with semantic hash partitioning
Authors: Lee Kisung , Liu Ling
Published: June 2014

Massive volumes of big RDF data are growing beyond the performance capacity of conventional RDF data management systems operating on a single node. Applications using large RDF data demand efficient data partitioning solutions for supporting RDF data access on a cluster of compute nodes. In this paper we present a novel semantic hash partitioning approach and implement a Semantic HAsh Partitioning-Enabled distributed RDF data management system, called Shape. This paper makes three original contributions. First, the semantic hash partitioning approach we propose extends the simple hash partitioning method through direction-based triple groups and direction-based triple replications. The latter enhances the former by controlled data replication through intelligent utilization of data access locality, such that queries over big RDF graphs can be processed with zero or very small amount of inter-machine communication cost. Second, we generate locality-optimized query execution plans that are more efficient than popular multi-node RDF data management systems by effectively minimizing the inter-machine communication cost for query processing. Third but not the least, we provide a suite of locality-aware optimization techniques to further reduce the partition size and cut down on the inter-machine communication cost during distributed query processing. Experimental results show that our system scales well and can process big RDF datasets more efficiently than existing approaches.
Parallel computation of skyline and reverse skyline queries using mapreduce
Authors: Park Yoonjae , Min Jun-Ki , Shim Kyuseok
Published: June 2014

The skyline operator and its variants such as dynamic skyline and reverse skyline operators have attracted considerable attention recently due to their broad applications. However, computations of such operators are challenging today since there is an increasing trend of applications to deal with big data. For such data-intensive applications, the MapReduce framework has been widely used recently.

In this paper, we propose efficient parallel algorithms for processing the skyline and its variants using MapReduce. We first build histograms to effectively prune out nonskyline (non-reverse skyline) points in advance. We next partition data based on the regions divided by the histograms and compute candidate (reverse) skyline points for each region independently using MapReduce. Finally, we check whether each candidate point is actually a (reverse) skyline point in every region independently. Our performance study confirms the effectiveness and scalability of the proposed algorithms.
Optimal Symmetric No-Trade Ranges in Asset Rebalancing Strategy with Transaction Costs
Authors: Hibiki Norio , Yamamoto Rei
Published: June 2014

There are many studies of optimal asset allocation with transaction costs in academic literatures. However, those are numerically solved for two-asset and three-asset cases. In contrast, the investment in five-asset classes (domestic bond and stock, international bond and stock, and cash) is at least required for practical pension fund management. Therefore, there are some real limitations to the continuous-time approach used in the previous literatures, which are the methods of solving the Hamilton-Bellman-Jacobi (HJB) equation for the stochastic control problem. In general, most investors use the rebalance rule with the no-trade ranges in practice which are constant and symmetric to the policy asset mix because it is easy to use the rule. In this paper, we propose the optimization model for the multiple asset allocation problem with transaction costs to determine the symmetric no-trade ranges of the policy asset mix using the derivative-free optimization (DFO) approach proposed by Hibiki et al. (2014). Specifically, we solve the five-asset problem with boundary constraints for cash for the Government Pension Investment Fund (GPIF) in Japan in a discrete-time and finite-period setting. We clarify the fact that we need to adjust the amounts of risky assets even within the no-trade range if the boundary constraints for cash are required, and we describe the simulation procedure in the discrete-time model. We examine the difference for various time intervals and horizons and conduct the sensitivity analysis for the various proportional transaction cost rates, the tracking error aversions, and the bounds for cash constraints. In addition, we compare the optimal time-dependent no-trade ranges with the constant no-trade ranges. The numerical results show the possibilities of applying the DFO model to the practical problem determining the symmetric no-trade ranges.