bluuebunny/crossref_metadata_2025 huggingface dataset:
Finding frequent items in data streams
Authors: Cormode Graham , Hadjieleftheriou Marios
Published: June 2014

The frequent items problem is to process a stream of items and find all items occurring more than a given fraction of the time. It is one of the most heavily studied problems in data stream mining, dating back to the 1980s. Many applications rely directly or indirectly on finding the frequent items, and implementations are in use in large scale industrial systems. However, there has not been much comparison of the different methods under uniform experimental conditions. It is common to find papers touching on this topic in which important related work is mischaracterized, overlooked, or reinvented.

In this paper, we aim to present the most important algorithms for this problem in a common framework. We have created baseline implementations of the algorithms, and used these to perform a thorough experimental study of their properties. We give empirical evidence that there is considerable variation in the performance of frequent items algorithms. The best methods can be implemented to find frequent items with high accuracy using only tens of kilobytes of memory, at rates of millions of items per second on cheap modern hardware.
Challenges and techniques for effective and efficient similarity search in large video databases
Authors: Shao Jie , Shen Heng Tao , Zhou Xiaofang
Published: June 2014

Searching relevant visual information based on content features in large databases is an interesting and changeling topic that has drawn lots of attention from both the research community and industry. This paper gives an overview of our investigations on effective and efficient video similarity search. We briefly introduce some novel techniques developed for two specific tasks studied in this PhD project: video retrieval in a large collection of segmented video clips, and video subsequence identification from a long unsegmented stream. The proposed methods for processing these two types of similarity queries have shown encouraging performance and are being incorporated into our prototype system of video search named UQLIPS, which has demonstrated some marketing potentials for commercialisation.
Implementing filesystems by tree-aware DBMSs
Authors: Holupirek Alexander , Scholl Marc H.
Published: June 2014

With the rise of XML, the database community has been challenged by semi-structured data processing. Since the data type behind XML is the tree, state-of-the-art RDBMSs have learned to deal with such data (
e. g.
, [18, 5, 6, 16]). This paper introduces a Ph.D. project focused on the question in how far the tree-awareness of recent RDBMSs can be used to, once again, try to implement filesystems using database technology. Our main goal is to provide means to query the data stored in filesystems and to find ways to enhance/combine the data storage and query capabilities of operating systems using semi-structured database technology.

Two DBMSs with
relational
XML storage, built on top of the XPath accelerator numbering scheme [14], are the foundations for our work. With BaseX, an XML database, we establish a link between user, database and filesystem content. BaseX allows visual access to filesystem data stored in the database. An integrated query interface allows users to filter query results in interactive response time. Second, we establish a link between DBMS and OS. We implement a filesystem in userspace backed by the MonetDB/XQuery system, a well-known relational database system, which integrates the Pathfinder XQuery compiler [5] and the MonetDB kernel [4].

As a result, the DBMS is mounted as a conventional filesystem by the operating system kernel. Consequently, access via the established (virtual) filesystem interface as well as database enhanced access to the same data is provided.
Adaptive workflow scheduling under resource allocation constraints and network dynamics
Authors: Avanes Artin , Freytag Johann-Christoph
Published: June 2014

Workflow concepts are well suited for scenarios where many distributed entities work collaboratively together to achieve a common goal. Today, workflows are mostly used as computerized model for business processes executed in instances in commercial Workflow Management Systems. However, there are many other application domains where computer-supported cooperative work can be captured and organized by workflows. In this paper, we investigate the task of scheduling workflows in self-organizing wireless networks for disaster scenarios. Most research work in the field of workflow scheduling has been driven by temporal and causality constraints. We present an adaptive scheduling algorithm that finds a suitable execution sequence for workflow activities by additionally considering resource allocation constraints and dynamic topology changes. Our approach utilizes a multi-stage distribution algorithm which we extend with techniques to cope with network dynamics.
Privacy preserving document indexing infrastructure for a distributed environment
Authors: Zerr Sergej , Nejdl Wolfgang
Published: June 2014

To carry out work assignments, small groups distributed within a larger enterprise or collaborative community often need to share documents among themselves while shielding those documents from others' eyes. In this situation, users need an indexing facility that can quickly locate relevant documents that they are allowed to access, without (1) leaking information about the remaining documents, (2) imposing a large management burden as users, groups, and documents evolve, or (3) requiring users to agree on a central completely trusted authority. In order to achieve this aim user access levels and access control have to be reflected in the index structures and/or retrieval algorithms as well as in ranking the search results.

My Ph.D. work focuses on building up an indexing infrastructure which supports confidential indexing, sharing and retrieval of unstructured information which is spread over a number of distributed access-controlled collections. In order to allow for effective and efficient indexing and retrieval in these settings, it considers aspects of confidentiality preservation within an outsourced inverted index, a DHT index structure in P2P networks as well as confidential top-k information retrieval.
GS-TMS
Authors: Miao Jiajia
Published: June 2014

Computer networks have become ubiquitous and integral part of the nation's critical infrastructure. How to grasp the real-time overall situation of the network security is very noteworthy to study. Current network security systems make great contributions in enhancing the network security. Nevertheless, these products are independent and autonomous, so they fail to share the results of the detected attacks. Consequently, such solutions cannot figure out an overview of the network security situation. In another perspective, building a new global monitoring system from scratch will suffer from redundant construction, more cost, and longer deploying time. To address the dilemma, we propose a novel solution called
GS-TMS
which reuses the log data generated by the existing widely-spread security systems. By introducing the data stream and data integration technologies, GS-TMS provides a desirable capability of quickly building a large-scale distributed network monitoring system. Furthermore, GS-TMS has additional notable advantages over current monitoring systems in scalability and flexibility.
Incompleteness in information integration
Authors: Kharlamov Evgeny , Nutt Werner
Published: June 2014

Information integration is becoming a critical problem for both businesses and individuals. The data, especially the one that comes from the Web, is naturally incomplete, that is, some data values may be unknown or lost because of communication problems, hidden due to privacy considerations. At the same time research in (virtual) integration in the community focusses on null-free sources and addresses limited forms of incompleteness only. In our work we aim to extend current results on virtual integration by considering various forms of incompleteness at the level of the sources, the integrated database and the queries (we call this
Incomplete Information Integration
, or III). More specifically, we aim to extend current query answering techniques for
local-, and global-as-view
integration to integration of tables with SQL nulls, Codd tables, etc. We also aim to consider incomplete answers as a natural extension of the classical approach. Our main research issues are (i) semantics of III, (ii) semantics of query answering in III, (iii) complexity of query answering, and (iv) algorithms (possibly approximate) to compute the answers.
StatAdvisor
Authors: El-Helw Amr , Ilyas Ihab F. , Zuzarte Calisto
Published: June 2014

Database statistics are crucial to cost-based optimizers for estimating the execution cost of a query plan. Using traditional basic statistics on base tables requires adopting unrealistic assumptions to estimate the cardinalities of intermediate results, which usually causes large estimation errors that can be several orders of magnitude. Modern commercial database systems support statistical or sample views, which give more accurate statistics on intermediate results and query sub-expressions. While previous research focused on creating and maintaining these advanced statistics, only little effort has been done towards automatically recommending the most beneficial statistical views to construct. In this paper, we present
StatAdvisor
, a system for recommending statistical views for a given SQL workload. The
StatAdvisor
addresses the special characteristics of statistical views with respect to view matching and benefit estimation, and introduces a novel plan-based candidate enumeration method, and a benefit-based analysis to determine the most useful statistical views. We present the basic concepts, architecture, and key features of
StatAdvisor
, and demonstrate its validity and benefits through an extensive experimental study using a prototype that we built in the IBM® DB2® database system as part of the
DB2 Design Advisor
tools.
Sort vs. Hash revisited
Authors: Kim Changkyu , Kaldewey Tim , Lee Victor W. , Sedlar Eric , Nguyen Anthony D. , Satish Nadathur , Chhugani Jatin , Di Blas Andrea , Dubey Pradeep
Published: June 2014

Join is an important database operation. As computer architectures evolve, the best join algorithm may change hand. This paper re-examines two popular join algorithms -- hash join and sort-merge join -- to determine if the latest computer architecture trends shift the tide that has favored hash join for many years. For a fair comparison, we implemented the most optimized parallel version of both algorithms on the latest Intel Core i7 platform. Both implementations scale well with the number of cores in the system and take advantages of latest processor features for performance. Our hash-based implementation achieves more than 100M tuples per second which is 17X faster than the best reported performance on CPUs and 8X faster than that reported for GPUs. Moreover, the performance of our hash join implementation is consistent over a wide range of input data sizes from 64K to 128M tuples and is not affected by data skew. We compare this implementation to our highly optimized sort-based implementation that achieves 47M to 80M tuples per second. We developed analytical models to study how both algorithms would scale with upcoming processor architecture trends. Our analysis projects that current architectural trends of wider SIMD, more cores, and smaller memory bandwidth per core imply better scalability potential for sort-merge join. Consequently, sort-merge join is likely to outperform hash join on upcoming chip multiprocessors. In summary, we offer multicore implementations of hash join and sort-merge join which consistently outperform all previously reported results. We further conclude that the tide that favors the hash join algorithm has not changed yet, but the change is just around the corner.
PLANET
Authors: Panda Biswanath , Herbach Joshua S. , Basu Sugato , Bayardo Roberto J.
Published: June 2014

Classification and regression tree learning on massive datasets is a common data mining task at Google, yet many state of the art tree learning algorithms require training data to reside in memory on a single machine. While more scalable implementations of tree learning have been proposed, they typically require specialized parallel computing architectures. In contrast, the majority of Google's computing infrastructure is based on commodity hardware.

In this paper, we describe PLANET: a scalable distributed framework for learning tree models over large datasets. PLANET defines tree learning as a series of distributed computations, and implements each one using the
MapReduce
model of distributed computation. We show how this framework supports scalable construction of classification and regression trees, as well as ensembles of such models. We discuss the benefits and challenges of using a MapReduce compute cluster for tree learning, and demonstrate the scalability of this approach by applying it to a real world learning task from the domain of computational advertising.
Robust and distributed top-n frequent-pattern mining with SAP BW accelerator
Authors: Legler Thomas , Lehner Wolfgang , Schaffner Jan , Krüger Jens
Published: June 2014

Mining for association rules and frequent patterns is a central activity in data mining. However, most existing algorithms are only moderately suitable for real-world scenarios. Most strategies use parameters like minimum support, for which it can be very difficult to define a suitable value for unknown datasets. Since most untrained users are unable or unwilling to set such technical parameters, we address the problem of replacing the minimum-support parameter with top-
n
strategies. In our paper, we start by extending a top-
n
implementation of the ECLAT algorithm to improve its performance by using heuristic search strategy optimizations. Also, real-world datasets are often distributed and modern database architectures are switching from expensive SMPs to cheaper shared-nothing blade servers. Thus, most mining queries require distribution handling. Since partitioning can be forced by user-defined semantics, it is often forbidden to transform the data. Therefore, we developed an adaptive top-
n
frequent-pattern mining algorithm that simplifies the mining process on real distributions by relaxing some requirements on the results. We first combine the PARTITION and the TPUT algorithms to handle distributed top-
n
frequent-pattern mining. Then, we extend this new algorithm for distributions with real-world data characteristics. For frequent-pattern mining algorithms, equal distributions are important conditions, and tiny partitions can cause performance bottlenecks. Hence, we implemented an approach called MAST that defines a minimum absolute-support threshold. MAST prunes patterns with low chances of reaching the global top-
n
result set and high computing costs. In total, our approach simplifies the process of frequent-pattern mining for real customer scenarios and data sets. This may make frequent-pattern mining accessible for very new user groups. Finally, we present results of our algorithms when run on the SAP NetWeaver BW Acceleratorwith standard and real business datasets.
Efficient index compression in DB2 LUW
Authors: Bhattacharjee Bishwaranjan , Lim Lipyeow , Malkemus Timothy , Mihaila George , Ross Kenneth , Lau Sherman , McArthur Cathy , Toth Zoltan , Sherkat Reza
Published: June 2014

In database systems, the cost of data storage and retrieval are important components of the total cost and response time of the system. A popular mechanism to reduce the storage footprint is by compressing the data residing in tables and indexes. Compressing indexes efficiently, while maintaining response time requirements, is known to be challenging. This is especially true when designing for a workload spectrum covering both data warehousing and transaction processing environments. DB2 Linux, UNIX, Windows (LUW) recently introduced index compression for use in both environments. This uses techniques that are able to compress index data efficiently while incurring virtually no performance penalty for query processing. On the contrary, for certain operations, the performance is actually better. In this paper, we detail the design of index compression in DB2 LUW and discuss the challenges that were encountered in meeting the design goals. We also demonstrate its effectiveness by showing performance results on typical customer scenarios.
DBLP
Authors: Ley Michael
Published: June 2014

The DBLP Computer Science Bibliography evolved from an early small experimental Web server to a popular service for the computer science community. Many design decisions and details of the public XML-records behind DBLP never were documented. This paper is a review of the evolution of DBLP. The main perspective is data modeling. In DBLP persons play a central role, our discussion of person names may be applicable to many other data bases. All DBLP data are available for your own experiments. You may either download the complete set, or use a simple XML-based API described in an online appendix.
Query mesh
Authors: Nehme Rimma V. , Works Karen E. , Rundensteiner Elke A. , Bertino Elisa
Published: June 2014

We propose to demonstrate a practical alternative approach to the current state-of-the-art query processing techniques, called the "
Query Mesh
" (or
QM
, for short). The main idea of
QM
is to compute multiple routes (i.e., query plans), each designed for a particular subset of data with distinct statistical properties. Based on the execution routes and the data characteristics, a
classifier
model is induced and is used to partition new data tuples to assign the best routes for their processing. We propose to demonstrate the
QM
framework in the streaming context using our demo application, called the "
Ubi-City
". We will illustrate the innovative features of
QM
, including: the
QM
optimization with the integrated machine learning component, the
QM
execution using the efficient "
Self-Routing Fabric
" infrastructure, and finally, the
QM
adaptive component that performs the online adaptation of
QM
with near-zero runtime overhead.
Artemis
Authors: Herschel Melanie , Hernández Mauricio A. , Tan Wang-Chiew
Published: June 2014

A central feature of relational database management systems is the ability to define multiple different views over an underlying database schema. Views provide a method of defining access control to the underlying database, since a view exposes a part of the database and hides the rest. Views also provide logical data independence to application programs that access the database. For most cases, the process of specifying the desired views in SQL is typically tedious and error-prone. While numerous tools exist to support developers in debugging program code, we are not aware of any tool that supports developers in verifying the correctness of their views defined in SQL.
Demonstration of the TrajStore system
Authors: Wu Eugene , Cudre-Mauroux Philippe , Madden Samuel
Published: June 2014

The proliferation of GPS devices has led to a substantial interest in location based services. In particular, modern vehicles can generate an incredible amount of drive data. However, current storage systems are not optimized for storing and querying such large spatial-temporal data sets. In this demonstration, we show the performance of the TrajStore system, a dynamic storage system optimized for quickly accessing data in a particular spatial-temporal region. In particular, TrajStore uses a novel adaptive indexing technique that dynamically adjusts itself to co-locate spatially close trajectories on disk, as well as a number of compression techniques in the storage layer that significantly reduce access time for a given index cell. In this demonstration, we will store a set of real world taxi cab drive traces in TrajStore, and users will be able to query the data through a map based interface.
Concise and expressive mappings with +Spicy
Authors: Mecca Giansalvatore , Papotti Paolo , Raunich Salvatore , Buoncristiano Marcello
Published: June 2014

We introduce the +Spicy mapping system. The system is based on a number of novel algorithms that contribute to increase the quality and expressiveness of mappings. +Spicy integrates the computation of core solutions in the mapping generation process in a highly efficient way, based on a natural rewriting of the given mappings. This allows for an efficient implementation of core computations using common runtime languages like SQL or XQuery and guarantees very good performances, orders of magnitude better than those of previous algorithms. The rewriting algorithm can be applied both to mappings generated by the system, or to pre-defined mappings provided as part of the input. To do this, the system was enriched with a set of expressive primitives, so that +Spicy is the first mapping system that brings together a sophisticate and expressive mapping generation algorithm with an efficient strategy to compute core solutions.
DEMo
Authors: Pichler Reinhard , Savenkov Vadim
Published: June 2014

Minimality is an important optimization criterion for solutions of data exchange problems, well captured by the notion of the core. Though tractability of core computation has been proved, it has not yet become a part of any industrial-strength system, still being highly computationally expensive. In this demonstration, we show how core computation can be used in a data exchange modeling tool, allowing data engineers to design more robust data transfer scenarios and better understand the sources of redundancy in the target database.
TIAMAT
Authors: Dai Chenyun , Ghinita Gabriel , Bertino Elisa , Byun Ji-Won , Li Ninghui
Published: June 2014

Releasing detailed data (
microdata
) about individuals poses a privacy threat, due to the presence of
quasi-identifier (QID)
attributes such as age or zip code. Several privacy paradigms have been proposed that preserve privacy by placing constraints on the value of released QIDs. However, in order to enforce these paradigms, data publishers need tools to assist them in selecting a suitable anonymization method and choosing the right system parameters. We developed
TIAMAT
, a tool for analysis of anonymization techniques which allows data publishers to assess the accuracy and overhead of existing anonymization techniques. The tool performs interactive, head-to-head comparison of anonymization techniques, as well as QID change-impact analysis. Other features include collection of attribute statistics, support for multiple information loss metrics and compatibility with commercial database engines.
iNextCube
Authors: Yu Yintao , Lin Cindy X. , Sun Yizhou , Chen Chen , Han Jiawei , Liao Binbin , Wu Tianyi , Zhai ChengXiang , Zhang Duo , Zhao Bo
Published: June 2014

Nowadays, most business, administration, and/or scientific databases contain both structured attributes and text attributes. We call a database that consists of both multidimensional structured data and narrative text data as
multidimensional text database
. Searching, OLAP, and mining such databases pose many research challenges. To enhance the power of data analysis, interesting entities and relationships can be extracted from such databases to derive heterogeneous information networks, which in turn will substantially increase the power and flexibility of data exploration in such databases. Based on our previous studies on
TextCube
[1],
TopicCube
[2], and information network analysis, such as
RankClus
[3] and
NetClus
[4], we construct
iNextCube
, an
i
nformation-
N
etwork-
e
nhanced te
xt
Cube
. In this demo, we show the power of
iNextCube
in the search and analysis of two multidimensional text databases: (i) a DBLP-based CS bibliographic database, and (ii) an online news database.
Hive
Authors: Thusoo Ashish , Sarma Joydeep Sen , Jain Namit , Shao Zheng , Chakka Prasad , Anthony Suresh , Liu Hao , Wyckoff Pete , Murthy Raghotham
Published: June 2014

The size of data sets being collected and analyzed in the industry for business intelligence is growing rapidly, making traditional warehousing solutions prohibitively expensive.
Hadoop
[3] is a popular open-source map-reduce implementation which is being used as an alternative to store and process extremely large data sets on commodity hardware. However, the map-reduce programming model is very low level and requires developers to write custom programs which are hard to maintain and reuse.
Column-oriented database systems
Authors: Abadi Daniel J. , Boncz Peter A. , Harizopoulos Stavros
Published: June 2014

Column-oriented database systems (column-stores) have attracted a lot of attention in the past few years. Column-stores, in a nutshell, store each database table column separately, with attribute values belonging to the same column stored contiguously, compressed, and densely packed, as opposed to traditional database systems that store entire records (rows) one after the other. Reading a subset of a table's columns becomes faster, at the potential expense of excessive disk-head seeking from column to column for scattered reads or updates. After several dozens of research papers and at least a dozen of new column-store start-ups, several questions remain. Are these a new breed of systems or simply old wine in new bottles? How easily can a major row-based system achieve column-store performance? Are column-stores the answer to effortlessly support large-scale data-intensive applications? What are the new, exciting system research problems to tackle? What are the new applications that can be potentially enabled by column-stores? In this tutorial, we present an overview of column-oriented database system technology and address these and other related questions.
Similarity search on Bregman divergence
Authors: Zhang Zhenjie , Ooi Beng Chin , Parthasarathy Srinivasan , Tung Anthony K. H.
Published: June 2014

In this paper, we examine the problem of indexing over non-metric distance functions. In particular, we focus on a general class of distance functions, namely
Bregman Divergence
[6], to support nearest neighbor and range queries. Distance functions such as KL-divergence and Itakura-Saito distance, are special cases of Bregman divergence, with wide applications in statistics, speech recognition and time series analysis among others. Unlike in metric spaces, key properties such as triangle inequality and distance symmetry do not hold for such distance functions. A direct adaptation of existing indexing infrastructure developed for metric spaces is thus not possible. We devise a novel solution to handle this class of distance measures by expanding and mapping points in the original space to a new
extended
space. Subsequently, we show how state-of-the-art tree-based indexing methods, for low to moderate dimensional datasets, and vector approximation file (VA-file) methods, for high dimensional datasets, can be adapted on this
extended space
to answer such queries efficiently. Improved distance bounding techniques and distribution-based index optimization are also introduced to improve the performance of query answering and index construction respectively, which can be applied on both the R-trees and VA files. Extensive experiments are conducted to validate our approach on a variety of datasets and a range of Bregman divergence functions.
Indexing Boolean expressions
Authors: Whang Steven Euijong , Garcia-Molina Hector , Brower Chad , Shanmugasundaram Jayavel , Vassilvitskii Sergei , Vee Erik , Yerneni Ramana
Published: June 2014

We consider the problem of efficiently indexing Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF) Boolean expressions over a high-dimensional multi-valued attribute space. The goal is to rapidly find the set of Boolean expressions that evaluate to true for a given assignment of values to attributes. A solution to this problem has applications in online advertising (where a Boolean expression represents an advertiser's user targeting requirements, and an assignment of values to attributes represents the characteristics of a user visiting an online page) and in general any publish/subscribe system (where a Boolean expression represents a subscription, and an assignment of values to attributes represents an event). All existing solutions that we are aware of can only index a specialized sub-set of conjunctive and/or disjunctive expressions, and cannot efficiently handle general DNF and CNF expressions (including NOTs) over multi-valued attributes.

In this paper, we present a novel solution based on the inverted list data structure that enables us to index arbitrarily complex DNF and CNF Boolean expressions over multi-valued attributes. An interesting aspect of our solution is that, by virtue of leveraging inverted lists traditionally used for ranked information retrieval, we can efficiently return the top-N matching Boolean expressions. This capability enables emerging applications such as
ranked
publish/subscribe systems [16], where only the top subscriptions that match an event are desired. For example, in online advertising there is a limit on the number of advertisements that can be shown on a given page and only the "best" advertisements can be displayed. We have evaluated our proposed technique based on data from an online advertising application, and the results show a dramatic performance improvement over prior techniques.
Online piece-wise linear approximation of numerical streams with precision guarantees
Authors: Elmeleegy Hazem , Elmagarmid Ahmed K. , Cecchet Emmanuel , Aref Walid G. , Zwaenepoel Willy
Published: June 2014

Continuous "always-on" monitoring is beneficial for a number of applications, but potentially imposes a high load in terms of communication, storage and power consumption when a large number of variables need to be monitored. We introduce two new filtering techniques, swing filters and slide filters, that represent within a prescribed precision a time-varying numerical signal by a piecewise linear function, consisting of connected line segments for swing filters and (mostly) disconnected line segments for slide filters. We demonstrate the effectiveness of swing and slide filters in terms of their compression power by applying them to a real-life data set plus a variety of synthetic data sets. For nearly all combinations of signal behavior and precision requirements, the proposed techniques outperform the earlier approaches for online filtering in terms of data reduction. The slide filter, in particular, consistently dominates all other filters, with up to twofold improvement over the best of the previous techniques.
Enabling ε-approximate querying in sensor networks
Authors: Yu Liu , Li Jianzhong , Gao Hong , Fang Xiaolin
Published: June 2014

Data approximation is a popular means to support energy-efficient query processing in sensor networks. Conventional data approximation methods require users to specify fixed error bounds
a prior
to address the trade-off between result accuracy and energy efficiency of queries. We argue that this can be infeasible and inefficient when, as in many real-world scenarios, users are unable to determine
in advance
what error bounds can lead to affordable cost in query processing. We envision ε-
approximate querying (EAQ)
to bridge the gap.
EAQ
is a uniform data access scheme underlying various queries in sensor networks. It allows users or query executors to incrementally 'refine' previously obtained approximate data to reach arbitrary accuracy.
EAQ
not only grants more flexibility to in-network query processing, but also minimizes energy consumption through communicating data upto a
just-sufficient
level. To enable the
EAQ
scheme, we propose a novel
data shuffling
algorithm. The algorithm converts sensed datasets into special representations called
multi-version array (MVA)
. From prefixes of
MVA
, we can recover approximate versions of the entire dataset, where all individual data items have guaranteed error bounds. The
EAQ
scheme supports efficient and flexible processing of various queries including
spatial window
query,
value range
query, and queries with
QoS
constraints. The effectiveness and efficiency of the
EAQ
scheme are evaluated in a real sensor network testbed.
Consistency rationing in the cloud
Authors: Kraska Tim , Hentschel Martin , Alonso Gustavo , Kossmann Donald
Published: June 2014

Cloud storage solutions promise high scalability and low cost. Existing solutions, however, differ in the degree of consistency they provide. Our experience using such systems indicates that there is a non-trivial trade-off between cost, consistency and availability. High consistency implies high cost per transaction and, in some situations, reduced availability. Low consistency is cheaper but it might result in higher operational cost because of, e.g., overselling of products in a Web shop.

In this paper, we present a new transaction paradigm, that not only allows designers to define the consistency guarantees on the data instead at the transaction level, but also allows to automatically switch consistency guarantees at runtime. We present a number of techniques that let the system dynamically adapt the consistency level by monitoring the data and/or gathering temporal statistics of the data. We demonstrate the feasibility and potential of the ideas through extensive experiments on a first prototype implemented on Amazon's S3 and running the TPC-W benchmark. Our experiments indicate that the adaptive strategies presented in the paper result in a significant reduction in response time and costs including the cost penalties of inconsistencies.
Structured search result differentiation
Authors: Liu Ziyang , Sun Peng , 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 paper we present an approach for differentiating search results on structured data. We define the differentiability of query results and quantify the degree of difference. Then we define the problem of identifying a limited number of valid features in a result that can maximally differentiate this result from the others, which is proved to be NP-hard. We propose two local optimality conditions, namely single-swap and multi-swap. Efficient algorithms are designed to achieve local optimality. To show the applicability of our approach, we implemented a system XRed for XML result differentiation. Our empirical evaluation verifies the effectiveness and efficiency of the proposed approach.
A hierarchical approach to model web query interfaces for web source integration
Authors: Dragut Eduard C. , Kabisch Thomas , Yu Clement , Leser Ulf
Published: June 2014

Much data in the Web is hidden behind Web query interfaces. In most cases the only means to "surface" the content of a Web database is by formulating complex queries on such interfaces. Applications such as Deep Web crawling and Web database integration require an automatic usage of these interfaces. Therefore, an important problem to be addressed is the automatic extraction of query interfaces into an appropriate model. We hypothesize the existence of a set of domain-independent "commonsense design rules" that guides the creation of Web query interfaces. These rules transform query interfaces into schema trees. In this paper we describe a Web query interface extraction algorithm, which combines HTML tokens and the geometric layout of these tokens within a Web page. Tokens are classified into several classes out of which the most significant ones are text tokens and field tokens. A tree structure is derived for text tokens using their geometric layout. Another tree structure is derived for the field tokens. The hierarchical representation of a query interface is obtained by iteratively merging these two trees. Thus, we convert the extraction problem into an integration problem. Our experiments show the promise of our algorithm: it outperforms the previous approaches on extracting query interfaces on about 6.5% in accuracy as evaluated over three corpora with more than 500 Deep Web interfaces from 15 different domains.
Efficient retrieval of the top-k most relevant spatial web objects
Authors: Cong Gao , Jensen Christian S. , Wu Dingming
Published: June 2014

The conventional Internet is acquiring a geo-spatial dimension. Web documents are being geo-tagged, and geo-referenced objects such as points of interest are being associated with descriptive text documents. The resulting fusion of geo-location and documents enables a new kind of top-
k
query that takes into account both location proximity and text relevancy. To our knowledge, only naive techniques exist that are capable of computing a general web information retrieval query while also taking location into account.

This paper proposes a new indexing framework for location-aware top-
k
text retrieval. The framework leverages the inverted file for text retrieval and the R-tree for spatial proximity querying. Several indexing approaches are explored within the framework. The framework encompasses algorithms that utilize the proposed indexes for computing the top-
k
query, thus taking into account both text relevancy and location proximity to prune the search space. Results of empirical studies with an implementation of the framework demonstrate that the paper's proposal offers scalability and is capable of excellent performance.
Stop word and related problems in web interface integration
Authors: Dragut Eduard , Fang Fang , Sistla Prasad , Yu Clement , Meng Weiyi
Published: June 2014

The goal of recent research projects on integrating Web databases has been to enable uniform access to the large amount of data behind query interfaces. Among the tasks addressed are: source discovery, query interface extraction, schema matching, etc. There are also a number of tasks that are commonly ignored or assumed to be apriori solved either manually or by some oracle. These tasks include (1) finding the set of stop words and (2) handling occurrences of "semantic enrichment words" within labels. These two subproblems have a direct impact on determining the synonymy and hyponymy relationships between labels. In (1), a word like "from" is a stop word in general but it is a content word in domains such as Airline and Real Estate. We formulate the
stop word problem
, prove its complexity and provide an approximation algorithm. In (2), we study the impact of words like AND and OR on establishing semantic relationships between labels (e.g. "departure date and time" is a hypernym of "departure date"). In addition, we develop a theoretical framework to differentiate synonymy relationship from hyponymy relationship among labels involving multiple words. We scrutinize its strength and limitations both analytically and experimentally. We use real data from the Web in our experiments. We analyze over 2300 labels of 220 user interfaces in 9 distinct domains.
Reasoning about record matching rules
Authors: Fan Wenfei , Jia Xibei , Li Jianzhong , Ma Shuai
Published: June 2014

To accurately match records it is often necessary to utilize the semantics of the data. Functional dependencies (FDs) have proven useful in identifying tuples in a clean relation, based on the semantics of the data. For all the reasons that FDs and their inference are needed, it is also important to develop dependencies and their reasoning techniques for matching tuples from
unreliable
data sources. This paper investigates dependencies and their reasoning for record matching. (a) We introduce a class of
matching dependencies
(MDs) for specifying the semantics of data in unreliable relations, defined in terms of
similarity metrics
and a
dynamic semantics
. (b) We identify a special case of MDs, referred to as
relative candidate keys
(RCKs), to determine what attributes to compare and how to compare them when matching records across possibly different relations. (c) We propose a mechanism for inferring MDs, a departure from traditional implication analysis, such that when we cannot match records by comparing attributes that contain errors, we may still find matches by using other, more reliable attributes. (d) We provide an
O
(
n
2
) time algorithm for inferring MDs, and an effective algorithm for deducing a set of RCKs from MDs. (e) We experimentally verify that the algorithms help matching tools efficiently identify keys at compile time for matching, blocking or windowing, and that the techniques effectively improve both the quality and efficiency of various record matching methods.
Distributed online aggregations
Authors: Wu Sai , Jiang Shouxu , Ooi Beng Chin , Tan Kian-Lee
Published: June 2014

In many decision making applications, users typically issue aggregate queries. To evaluate these computationally expensive queries,
online aggregation
has been developed to provide approximate answers (with their respective confidence intervals) quickly, and to continuously refine the answers. In this paper, we extend the online aggregation technique to a distributed context where sites are maintained in a DHT (Distributed Hash Table) network. Our Distributed Online Aggregation (DoA) scheme iteratively and progressively produces approximate aggregate answers as follows: in each iteration, a small set of random samples are retrieved from the data sites and distributed to the processing sites; at each processing site, a local aggregate is computed based on the allocated samples; at a coordinator site, these local aggregates are combined into a global aggregate. DoA adaptively grows the number of processing nodes as the sample size increases. To further reduce the sampling overhead, the samples are retained as a precomputed synopsis over the network to be used for processing future queries. We also study how these synopsis can be maintained incrementally. We have conducted extensive experiments on PlanetLab. The results show that our DoA scheme reduces the initial waiting time significantly and provides high quality approximate answers with running confidence intervals progressively.
Segment-based recovery
Authors: Sears Russell , Brewer Eric
Published: June 2014

Although existing write-ahead logging algorithms scale to conventional database workloads, their communication and synchronization overheads limit their usefulness for modern applications and distributed systems. We revisit write-ahead logging with an eye toward finer-grained concurrency and an increased range of workloads, then remove two core assumptions: that pages are the unit of recovery and that times-tamps (LSNs) should be stored on each page.

Recovering individual application-level objects (rather than pages) simplifies the handing of systems with object sizes that differ from the page size.

We show how to remove the need for LSNs on the page, which in turn enables DMA or zero-copy I/O for large objects, increases concurrency, and reduces communication between the application, buffer manager and log manager. Our experiments show that the looser coupling significantly reduces the impact of latency among the components. This makes the approach particularly applicable to large scale distributed systems, and enables a "cross pollination" of ideas from distributed systems and transactional storage.

However, these advantages come at a cost; segments are incompatible with physiological redo, preventing a number of important optimizations. We show how allocation enables (or prevents) mixing of ARIES pages (and physiological redo) with segments. We present an allocation policy that avoids undesirable interactions that complicate other combinations of ARIES and LSN-free pages, and then present a proof that both approaches and our combination are correct.

Many optimizations presented here were proposed in the past. However, we believe this is the first unified approach.
Integrating conflicting data
Authors: Dong Xin Luna , Berti-Equille Laure , Srivastava Divesh
Published: June 2014

Many data management applications, such as setting up Web portals, managing enterprise data, managing community data, and sharing scientific data, require integrating data from multiple sources. Each of these sources provides a set of values and different sources can often provide conflicting values. To present quality data to users, it is critical that data integration systems can resolve conflicts and discover true values. Typically, we expect a true value to be provided by more sources than any particular false one, so we can take the value provided by the majority of the sources as the truth. Unfortunately, a false value can be spread through copying and that makes truth discovery extremely tricky. In this paper, we consider how to find true values from conflicting information when there are a large number of sources, among which some may copy from others.

We present a novel approach that considers
dependence
between data sources in truth discovery. Intuitively, if two data sources provide a large number of common values and many of these values are rarely provided by other sources (
e.g.
, particular false values), it is very likely that one copies from the other. We apply Bayesian analysis to decide dependence between sources and design an algorithm that iteratively detects dependence and discovers truth from conflicting information. We also extend our model by considering
accuracy
of data sources and
similarity
between values. Our experiments on synthetic data as well as real-world data show that our algorithm can significantly improve accuracy of truth discovery and is scalable when there are a large number of data sources.
Truth discovery and copying detection in a dynamic world
Authors: Dong Xin Luna , Berti-Equille Laure , Srivastava Divesh
Published: June 2014

Modern information management applications often require integrating data from a variety of data sources, some of which may copy or buy data from other sources. When these data sources model a dynamically changing world (
e.g.
, people's contact information changes over time, restaurants open and go out of business), sources often provide out-of-date data. Errors can also creep into data when sources are updated often. Given out-of-date and erroneous data provided by different, possibly dependent, sources, it is challenging for data integration systems to provide the true values. Straightforward ways to resolve such inconsistencies (
e.g.
, voting) may lead to noisy results, often with detrimental consequences.

In this paper, we study the problem of finding true values and determining the copying relationship between sources, when the update history of the sources is known. We model the quality of sources over time by their
coverage, exactness
and
freshness
. Based on these measures, we conduct a probabilistic analysis. First, we develop a Hidden Markov Model that decides whether a source is a copier of another source and identifies the specific moments at which it copies. Second, we develop a Bayesian model that aggregates information from the sources to decide the true value for a data item, and the evolution of the true values over time. Experimental results on both real-world and synthetic data show high accuracy and scalability of our techniques.