bluuebunny/crossref_metadata_2025 huggingface dataset:
Keyword query cleaning
Authors: Pu Ken Q. , Yu Xiaohui
Published: June 2014

Unlike traditional database queries, keyword queries do not adhere to predefined syntax and are often dirty with irrelevant words from natural languages. This makes accurate and efficient keyword query processing over databases a very challenging task.

In this paper, we introduce the problem of
query cleaning
for keyword search queries in a database context and propose a set of effective and efficient solutions. Query cleaning involves semantic linkage and spelling corrections of database relevant query words, followed by segmentation of nearby query words such that each segment corresponds to a high quality data term. We define a quality metric of a keyword query, and propose a number of algorithms for cleaning keyword queries optimally. It is demonstrated that the basic optimal query cleaning problem can be solved using a dynamic programming algorithm. We further extend the basic algorithm to address incremental query cleaning and top-
k
optimal query cleaning. The incremental query cleaning is efficient and memory-bounded, hence is ideal for scenarios in which the keywords are streamed. The top-
k
query cleaning algorithm is guaranteed to return the best
k
cleaned keyword queries in ranked order. Extensive experiments are conducted on three real-life data sets, and the results confirm the effectiveness and efficiency of the proposed solutions.
Scalable ad-hoc entity extraction from text collections
Authors: Agrawal Sanjay , Chakrabarti Kaushik , Chaudhuri Surajit , Ganti Venkatesh
Published: June 2014

Supporting entity extraction from large document collections is important for enabling a variety of important data analysis tasks. In this paper, we introduce the "ad-hoc" entity extraction task where entities of interest are constrained to be from a list of entities that is specific to the task. In such scenarios, traditional entity extraction techniques that process
all
the documents for each ad-hoc entity extraction task can be significantly expensive. In this paper, we propose an efficient approach that leverages the inverted index on the documents to identify the subset of documents relevant to the task and processes only those documents. We demonstrate the efficiency of our techniques on real datasets.
Scheduling shared scans of large data files
Authors: Agrawal Parag , Kifer Daniel , Olston Christopher
Published: June 2014

We study how best to schedule scans of large data files, in the presence of many simultaneous requests to a common set of files. The objective is to maximize the overall rate of processing these files, by sharing scans of the same file as aggressively as possible, without imposing undue wait time on individual jobs. This scheduling problem arises in batch data processing environments such as Map-Reduce systems, some of which handle tens of thousands of processing requests daily, over a shared set of files.

As we demonstrate, conventional scheduling techniques such as shortest-job-first do not perform well in the presence of cross-job sharing opportunities. We derive a new family of scheduling policies specifically targeted to sharable workloads. Our scheduling policies revolve around the notion that, all else being equal, it is good to schedule nonsharable scans ahead of ones that can share IO work with future jobs, if the arrival rate of sharable future jobs is expected to be high. We evaluate our policies via simulation over varied synthetic and real workloads, and demonstrate significant performance gains compared with conventional scheduling approaches.
Online maintenance of very large random samples on flash storage
Authors: Nath Suman , Gibbons Phillip B.
Published: June 2014

Recent advances in flash media have made it an attractive alternative for data storage in a wide spectrum of computing devices, such as embedded sensors, mobile phones, PDA's, laptops, and even servers. However, flash media has many unique characteristics that make existing data management/analytics algorithms designed for magnetic disks perform poorly with flash storage. For example, while random (page) reads are as fast as sequential reads, random (page) writes and in-place data updates are orders of magnitude slower than sequential writes. In this paper, we consider an important fundamental problem that would seem to be particularly challenging for flash storage: efficiently maintaining a very large (100 MBs or more) random sample of a data stream (e.g., of sensor readings). First, we show that previous algorithms such as reservoir sampling and geometric file are not readily adapted to flash. Second, we propose B-FILE, an energy-efficient abstraction for flash media to store self-expiring items, and show how a B-FILE can be used to efficiently maintain a large sample in flash. Our solution is simple, has a small (RAM) memory footprint, and is designed to cope with flash constraints in order to reduce latency and energy consumption. Third, we provide techniques to maintain biased samples with a B-FILE and to query the large sample stored in a B-FILE for a subsample of an arbitrary size. Finally, we present an evaluation with flash media that shows our techniques are
several orders of magnitude faster and more energy-efficient
than (flash-friendly versions of) reservoir sampling and geometric file. A key finding of our study, of potential use to many flash algorithms beyond sampling, is that "semi-random" writes (as defined in the paper) on flash cards are over two orders of magnitude faster and more energy-efficient than random writes.
A skip-list approach for efficiently processing forecasting queries
Authors: Ge Tingjian , Zdonik Stan
Published: June 2014

Time series data is common in many settings including scientific and financial applications. In these applications, the amount of data is often very large. We seek to support prediction queries over time series data. Prediction relies on model building which can be too expensive to be practical if it is based on a large number of data points. We propose to use statistical tests of hypotheses to choose a proper subset of data points to use for a given prediction query interval. This involves two steps: choosing a proper history length and choosing the number of data points to use within this history. Further, we use an I/O conscious skip list data structure to provide samples of the original data set. Based on the statistics collected for a query workload, which we model as a probability mass function (PMF) over query intervals, we devise a randomized algorithm that selects a set of pre-built models (PM's) to construct, subject to some maintenance cost constraint when there are updates. Given this set of PM's, we discuss interesting query processing strategies for not only point queries, but also range, aggregation, and JOIN queries. We conduct a comprehensive empirical study on real world datasets to verify the effectiveness of our approaches and algorithms.
Efficient top-k processing over query-dependent functions
Authors: Guo Lin , Yahia Sihem Amer , Ramakrishnan Raghu , Shanmugasundaram Jayavel , Srivastava Utkarsh , Vee Erik
Published: June 2014

We study the efficient evaluation of top-k queries over data items, where the score of each item is dynamically computed by applying an item-specific function whose parameter value is specified in the query. For example, online retail stores rank items by price, which may be a function of the quantity being queried: "Stay 3 nights, get a 15% discount on double-bed rooms." Similarly, while ranking possible routes in online maps by predicted congestion level, the score (congestion) is a function of the time being queried, e.g., "At 5PM on a Friday in Palo Alto, the congestion level on 101 North is high." Since the parameter---the number of nights or the time the online map is queried, in the above examples---is only known at query time, and online applications have stringent response-time requirements, it is infeasible to evaluate every item-specific function to determine the item scores, especially when the number of items is large. Further, space considerations make it infeasible to pre-compute and store the score of each item for each value of the input parameter. In this paper, we develop a novel technique that compresses the (large) set of item scores for all parameter values by dividing the parameter range into intervals, taking into account the expected query workload. This compressed representation is then used to do top-k pruning of query results. Our experiments show that the proposed techniques are scalable and efficient.
TraClass
Authors: Lee Jae-Gil , Han Jiawei , Li Xiaolei , Gonzalez Hector
Published: June 2014

Trajectory classification,
i.e.
, model construction for predicting the class labels of moving objects based on their trajectories and other features, has many important, real-world applications. A number of methods have been reported in the literature, but due to using the
shapes
of
whole
trajectories for classification, they have limited classification capability when discriminative features appear at
parts of trajectories
or are
not relevant to the shapes of trajectories.
These situations are often observed in long trajectories spreading over large geographic areas.

Since an essential task for effective classification is generating discriminative features, a feature generation framework
TraClass
for trajectory data is proposed in this paper, which generates a hierarchy of features by partitioning trajectories and exploring two types of clustering: (1)
region-based
and (2)
trajectory-based.
The former captures the higher-level region-based features without using movement patterns, whereas the latter captures the lower-level trajectory-based features using movement patterns. The proposed framework overcomes the limitations of the previous studies because trajectory partitioning makes discriminative parts of trajectories identifiable, and the two types of clustering collaborate to find features of both
regions
and
sub-trajectories.
Experimental results demonstrate that
TraClass
generates high-quality features and achieves high classification accuracy from real trajectory data.
Discovering data quality rules
Authors: Chiang Fei , Miller Renée J.
Published: June 2014

Dirty data is a serious problem for businesses leading to incorrect decision making, inefficient daily operations, and ultimately wasting both time and money. Dirty data often arises when domain constraints and business rules, meant to preserve data consistency and accuracy, are enforced incompletely or not at all in application code.

In this work, we propose a new data-driven tool that can be used within an organization's data quality management process to suggest possible rules, and to identify conformant and non-conformant records. Data quality rules are known to be contextual, so we focus on the discovery of context-dependent rules. Specifically, we search for conditional functional dependencies (CFDs), that is, functional dependencies that hold only over a portion of the data. The output of our tool is a set of functional dependencies together with the context in which they hold (for example, a rule that states for CS graduate courses, the course number and term functionally determines the room and instructor). Since the input to our tool will likely be a dirty database, we also search for CFDs that almost hold. We return these rules together with the non-conformant records (as these are potentially dirty records).

We present effective algorithms for discovering CFDs and dirty values in a data instance. Our discovery algorithm searches for minimal CFDs among the data values and prunes redundant candidates. No universal objective measures of data quality or data quality rules are known. Hence, to avoid returning an unnecessarily large number of CFDs and only those that are most interesting, we evaluate a set of interest metrics and present comparative results using real datasets. We also present an experimental study showing the scalability of our techniques.
Google's Deep Web crawl
Authors: Madhavan Jayant , Ko David , Kot Łucja , Ganapathy Vignesh , Rasmussen Alex , Halevy Alon
Published: June 2014

The Deep Web, i.e., content hidden behind HTML forms, has long been acknowledged as a significant gap in search engine coverage. Since it represents a large portion of the structured data on the Web, accessing Deep-Web content has been a long-standing challenge for the database community. This paper describes a system for
surfacing
Deep-Web content, i.e., pre-computing submissions for each HTML form and adding the resulting HTML pages into a search engine index. The results of our surfacing have been incorporated into the Google search engine and today drive more than a thousand queries per second to Deep-Web content.

Surfacing the Deep Web poses several challenges. First, our goal is to index the content behind many millions of HTML forms that span many languages and hundreds of domains. This necessitates an approach that is completely automatic, highly scalable, and very efficient. Second, a large number of forms have text inputs and require valid inputs values to be submitted. We present an algorithm for selecting input values for text search inputs that accept keywords and an algorithm for identifying inputs which accept only values of a specific type. Third, HTML forms often have more than one input and hence a naive strategy of enumerating the entire Cartesian product of all possible inputs can result in a very large number of URLs being generated. We present an algorithm that efficiently navigates the search space of possible input combinations to identify only those that generate URLs suitable for inclusion into our web search index. We present an extensive experimental evaluation validating the effectiveness of our algorithms.
WebContent
Authors: Abiteboul S. , Allard T. , Chatalic P. , Gardarin G. , Ghitescu A. , Goasdoué F. , Manolescu I. , Nguyen B. , Ouazara M. , Somani A. , Travers N. , Vasile G. , Zoupanos S.
Published: June 2014

We present the WebContent platform for managing distributed repositories of XML and semantic Web data. The platform allows integrating various data processing building blocks (crawling, translation, semantic annotation, full-text search, structured XML querying, and semantic querying), presented as Web services, into a large-scale efficient platform. Calls to various services are combined inside ActiveXML [8] documents, which are XML documents including service calls. An ActiveXML optimizer is used to: (
i
) efficiently distribute computations among sites; (
ii
) perform XQuery-specific optimizations by leveraging an algebraic XQuery optimizer; and (
iii
) given an XML query, chose among several distributed indices the most appropriate in order to answer the query.
EasyTicket
Authors: Shao Qihong , Chen Yi , Tao Shu , Yan Xifeng , Anerousis Nikos
Published: June 2014

Managing problem tickets is a key issue in IT service industry. A large service provider may handle thousands of problem tickets from its customers on a daily basis. The efficiency of processing these tickets highly depends on ticket routing---transferring problem tickets among expert groups in search of the right resolver to the ticket. Despite that many ticket management systems are available, ticket routing in these systems is still manually operated by support personnel. In this demo, we introduce EasyTicket, a ticket routing recommendation engine that helps automate this process. By mining ticket history data, we model an enterprise social network that represents the functional relationships among various expert groups in ticket routing. Based on this network, our system then provides routing recommendations to new tickets. Our experimental studies on 1.4 million real-world problem tickets show that on average, EasyTicket can improve the efficiency of ticket routing by 35%.
XTreeNet
Authors: Curtmola Emiran , Deutsch Alin , Logothetis Dionysios , Ramakrishnan K. K. , Srivastava Divesh , Yocum Kenneth
Published: June 2014

We describe XTreeNet, a distributed query dissemination engine which facilitates democratization of publishing and efficient data search among members of online communities with powerful full-text queries. This demonstration shows XTreeNet in full action. XTreeNet serves as a proof of concept for democratic community search by proposing a distributed novel infrastructure in which data resides only with the publishers owning it. Expressive user queries are disseminated to publishers. Given the virtual nature of the global data collection (e.g., the union of all local data published in the community) our infrastructure efficiently locates the publishers that contain matching documents with a specified query, processes the complex full-text query at the publisher and returns all relevant documents to querier.
Comparing and evaluating mapping systems with STBenchmark
Authors: Alexe Bogdan , Tan Wang-Chiew , Velegrakis Yannis
Published: June 2014

Schema mappings are fundamental building blocks in many information integration applications. Designing mappings is a time-consuming process and for that reason many mapping systems have been developed to assist in the task of designing mappings. However, to the best of our knowledge, a benchmark for comparing and evaluating these systems has not yet been developed. We demonstrate STBenchmark, a benchmark that we have developed for evaluating mapping systems. Our demonstration will showcase the different aspects of mapping systems that STBenchmark evaluates, highlight the results of our comparison and evaluation of four mapping systems, as well as make a case for the need for a standard specification input mechanism to mapping systems in order to make progress towards the development of a uniform testbed or repository for schema mappings and data exchange tasks.
Ad-hoc data processing in the cloud
Authors: Logothetis Dionysios , Yocum Kenneth
Published: June 2014

Ad-hoc data processing has proven to be a critical paradigm for Internet companies processing large volumes of unstructured data. However, the emergence of cloud-based computing, where storage and CPU are outsourced to multiple third-parties across the globe, implies large collections of highly distributed and continuously evolving data. Our demonstration combines the power and simplicity of the MapReduce abstraction with a wide-scale distributed stream processor, Mortar. While our incremental MapReduce operators avoid data re-processing, the stream processor manages the placement and physical data flow of the operators across the wide area. We demonstrate a distributed web indexing engine against which users can submit and deploy continuous MapReduce jobs. A visualization component illustrates both the incremental indexing and index searches in real time.
Organizing and indexing non-convex regions
Authors: Perlman Eric , Burns Randal , Kazhdan Michael
Published: June 2014

We demonstrate data indexing and query processing techniques that improve the efficiency of comparing, correlating, and joining data contained in non-convex regions. We use computational geometry techniques to automatically characterize the region of space from which data are drawn, partition the region based on that characterization, and create an index from the partitions. Our motivating application performs distributed data analysis queries among federated database sites that store scientific data sets from the Chesapeake Bay. Our preliminary findings indicate that these techniques often reduce the number of I/Os needed to serve a query by a factor of five---depending on the geometry of the query region.
Capri/MR
Authors: Paquet Eric , Viktor Herna L
Published: June 2014

With the advent of high throughput systems to experimentally determine the three-dimensional (3-D) structure of proteins, molecular biologists are in urgent need of systems to automatically store, maintain and explore the vast structural databases that are thus being created. We have designed and implemented the Capri/MR system which makes it possible to identify families of protein structures, as contained in such very large 3-D protein structure databases. Our system is able to automatically index and search a database of proteins by three-dimensional shape, structural and/or physicochemical properties. For each of these diverse protein structure representations, we create a compact rotation and translation invariant index (or signature) which is placed in a database for future querying. A similarity search algorithm performs an exhaustive search against the entire database. Our search algorithm takes advantage of the compact signatures to rapidly find protein structures that are similar in 3-D shape and/or two-dimensional (2-D) properties. As a result, queries in our Capri/MR system run within a fraction of a second, and we are able to accurately group protein structures into the correct families, with very high precision and recall. In addition, our system dynamically processes new protein structures as they become available. We demonstrate the power of Capri/MR against the Protein Data Bank, which contains all known, experimentally determined, 3-D protein structures (48.000 as of January 2008). The main applications of our Capri/MR system lie in structural proteomics, protein evolution and mutation, as well as in drug design, in particular for studying the docking problem and the computer aided design of non-toxic drugs.
Ontologies and databases
Authors: Franconi Enrico
Published: June 2014

After an introduction where the notion of ontology will be introduced in a rigorous way as a set of
constraints
over legal
database instances
playing the role of a
conceptual model
or of a set of
dependencies
, the tutorial will be divided in three parts. In the first part, we will discuss, mostly driven by examples, the role of ontologies in information systems design and the advantages and the challenges when adopting a formal approach based on logics. In the second part, a real-world tool for ontology design will be used to see the "logic" in action. In the third and most important part, we will discuss the use for information access of ontologies in data intensive scenarios based on database technologies, based on a scenario where a logic-based ontology mediates between the user information need and the data structured in the source database. The tutorial will emphasise the advantages of adopting a logic-based approach to the use of ontologies in data intensive applications, and the challenges that the research should still face to make this approach feasible and scalable in association with current database technology.

The audience can be of both database researchers and practitioners, since I will try to explain all the concepts through examples and the central demo, although the concepts that the audience will at the end get will be non-trivial ones. The main goal of this tutorial is to let the audience understand haw these novel technologies are non-trivial, but useful in perspective and worthwhile researching; I will also show that there are already some data intensive scenarios where a rigorous ontology-based approach is already applicable with success; at the same time, I will warn about the wrong usages of ontology-based technologies.
Column-store support for RDF data management
Authors: Sidirourgos Lefteris , Goncalves Romulo , Kersten Martin , Nes Niels , Manegold Stefan
Published: June 2014

This paper reports on the results of an independent evaluation of the techniques presented in the VLDB 2007 paper "Scalable Semantic Web Data Management Using Vertical Partitioning", authored by D. Abadi, A. Marcus, S. R. Madden, and K. Hollenbach [1]. We revisit the proposed benchmark and examine both the data and query space coverage. The benchmark is extended to cover a larger portion of the query space in a canonical way. Repeatability of the experiments is assessed using the code base obtained from the authors. Inspired by the proposed
vertically-partitioned
storage solution for RDF data and the performance figures using a column-store, we conduct a complementary analysis of state-of-the-art RDF storage solutions. To this end, we employ MonetDB/SQL, a fully-functional open source column-store, and a well-known -- for its performance -- commercial row-store DBMS. We implement two relational RDF storage solutions --
triple-store
and
vertically-partitioned
-- in both systems. This allows us to expand the scope of [1] with the performance characterization along both dimensions -- triple-store vs. vertically-partitioned and row-store vs. column-store -- individually, before analyzing their combined effects. A detailed report of the experimental test-bed, as well as an in-depth analysis of the parameters involved, clarify the scope of the solution originally presented and position the results in a broader context by covering more systems.
Prefix based numbering schemes for XML
Authors: Sans Virginie , Laurent Dominique
Published: June 2014

Commonly used in network routing, programming, classification and knowledge representation systems, labeling schemes have also interested the XML community. We thus motivate and describe numbering schemes, their applications, and the trade off between storage capacities and runtime performance. We present a taxonomy of numbering schemes for XML based on the types of supported queries (ancestor, adjacent, etc), the encoding technique, and whether the scheme offers robustness properties according to updates. We describe some of the numbering techniques proposed for XML. We focus on prefix-based schemes. We give a qualitative comparison of the existing numbering schemes, discussing their advantages and drawbacks. Then, we compare their storage requirement and performances. Finally, we consider the new research directions that are likely to benefit from numbering scheme techniques.
Dwarfs in the rearview mirror
Authors: Dittrich Jens , Blunschi Lukas , Salles Marcos Antonio Vaz
Published: June 2014

Online-Analytical Processing (OLAP) has been a field of competing technologies for the past ten years. One of the still unsolved challenges of OLAP is how to provide quick response times on
any
Terabyte-sized business data problem. Recently, a very clever multi-dimensional index structure termed Dwarf [26] has been proposed offering excellent query response times as well as unmatched index compression rates. The proposed index seems to scale well for both large data sets as well as high dimensions. Motivated by these surprisingly excellent results, we take a look into the rearview mirror. We have re-implemented the Dwarf index from scratch and make three contributions. First, we successfully repeat several of the experiments of the original paper. Second, we substantially correct some of the experimental results reported by the inventors. Some of our results differ by orders of magnitude. To better understand these differences, we provide additional experiments that better explain the behavior of the Dwarf index. Third, we provide
missing
experiments comparing Dwarf to baseline query processing strategies. This should give practitioners a better guideline to understand for which cases Dwarf indexes could be useful in practice.
Towards efficient main-memory use for optimum tree index update
Authors: Biveinis Laurynas , Šaltenis Simonas
Published: June 2014

An emerging class of database applications is characterized by frequent updates of low-dimensional data, e.g. coming from sensors that sample continuous real world phenomena. Traditional persistency requirements can be weakened in this setting of frequent updates, emphasizing a role of the main-memory in external storage index structures and enabling a higher update throughput. Moreover, in order for an index to be suitable for practical applications, efficient past-state queries should be supported without significantly penalizing other operations.

These issues are not adequately addressed in the database research. We report on the R
R
-tree---our first step towards resolving them. Based on this, we outline a number of concrete short-term and more abstract longer-term future research directions.
Community-driven data grids
Authors: Scholl Tobias , Kemper Alfons
Published: June 2014

Beyond already existing huge data volumes, e-science communities face major challenges in managing the anticipated data deluge of forthcoming projects.
Community-driven data grids
target at domain-specific federations and provide a distributed, collaborative data management by employing dominant data characteristics (e. g., data skew) and query patterns to optimize the overall throughput. By combining well-established techniques for data partitioning and replication with Peer-to-Peer (P2P) technologies we can address several challenging problems: data load balancing, handling of query hot spots, and the adaption to short-term burst as well as long-term load redistributions.
Efficient outer join data skew handling in parallel DBMS
Authors: Xu Yu , Kostamaa Pekka
Published: June 2014

Large enterprises have been relying on parallel database management systems (
PDBMS
) to process their ever-increasing data volume and complex queries. The scalability and performance of a PDBMS comes from load balancing on all nodes in the system. Skewed processing will significantly slow down query response time and degrade the overall system performance. Business intelligence tools used by enterprises frequently generate a large number of outer joins and require high performance from the underlying database systems. Although extensive research has been done on handling skewed processing for inner joins in PDBMS, there is no known research on data skew handling for parallel outer joins. We propose a simple and efficient outer join algorithm called OJSO (Outer Join Skew Optimization) to improve the performance and scalability of parallel outer joins. Our experimental results show that the OJSO algorithm significantly speeds up query elapsed time in the presence of data skew.
Building a high-level dataflow system on top of Map-Reduce
Authors: Gates Alan F. , Natkovich Olga , Chopra Shubham , Kamath Pradeep , Narayanamurthy Shravan M. , Olston Christopher , Reed Benjamin , Srinivasan Santhosh , Srivastava Utkarsh
Published: June 2014

Increasingly, organizations capture, transform and analyze enormous data sets. Prominent examples include internet companies and e-science. The
Map-Reduce
scalable dataflow paradigm has become popular for these applications. Its simple, explicit dataflow programming model is favored by some over the traditional high-level declarative approach: SQL. On the other hand, the extreme simplicity of Map-Reduce leads to much low-level hacking to deal with the many-step, branching dataflows that arise in practice. Moreover, users must repeatedly code standard operations such as
join
by hand. These practices waste time, introduce bugs, harm readability, and impede optimizations.

Pig
is a high-level dataflow system that aims at a sweet spot between SQL and Map-Reduce. Pig offers SQL-style high-level data manipulation constructs, which can be assembled in an explicit dataflow and interleaved with custom Map- and Reduce-style functions or executables. Pig programs are compiled into sequences of Map-Reduce jobs, and executed in the
Hadoop
Map-Reduce environment. Both Pig and Hadoop are open-source projects administered by the Apache Software Foundation.

This paper describes the challenges we faced in developing Pig, and reports performance comparisons between Pig execution and raw Map-Reduce execution.
1,000 tables under the form
Authors: Dieu Nicolas , Dragusanu Adrian , Fabret Françoise , Llirbat François , Simon Eric
Published: June 2014

The goal of operational Business Intelligence (BI) is to help organizations improve the efficiency of their business by giving every "operational worker" insights needed to make better operational decisions, and aligning day-to-day operations with strategic goals. Operational BI reporting contributes to this goal by embedding analytics and reporting information into workflow applications so that the business user has all required information (contextual and business data) in order to make good decisions. EII systems facilitate the construction of operational BI reports by enabling the creation and querying of customized virtual database schemas over a set of distributed and heterogeneous data sources with a low TCO. Queries over these virtual databases feed the operational BI reports. We describe the characteristics of operational BI reporting applications and show that they increase the complexity of the source to target mapping defined between source data and virtual databases. We show that this complexity yields the execution of "mega queries", i.e., queries with possible a 1,000 tables in their FROM clause. We present some key optimization methods that have been successfully implemented in SAP Business Objects Data Federator system to deal with mega queries.
Storing scientific workflows in a database
Authors: Lacroix Zoé , Legendre Christophe , Mousses Spyro
Published: June 2014

The use of workflow models to integrate intelligently complex experimental and analytical processes is becoming more and more critical to support scientific discovery. Storing and providing querying capabilities to retrieve, import, re-use, adapt, and reason about workflows are becoming necessary components to workflow architectures supporting collaborative and translational research. We report on the evaluation of ProtocolDB a database that supports workflow design and storage conducted at the Translational Genomics Research Institute (TGen).
Scalable web data extraction for online market intelligence
Authors: Baumgartner Robert , Gottlob Georg , Herzog Marcus
Published: June 2014

Online market intelligence (OMI), in particular competitive intelligence for product pricing, is a very important application area for Web data extraction. However, OMI presents non-trivial challenges to data extraction technology. Sophisticated and highly parameterized navigation and extraction tasks are required. On-the-fly data cleansing is necessary in order two identify identical products from different suppliers. It must be possible to smoothly define data flow scenarios that merge and filter streams of extracted data stemming from several Web sites and store the resulting data into a data warehouse, where the data is subjected to market intelligence analytics. Finally, the system must be highly scalable, in order to be able to extract and process massive amounts of data in a short time. Lixto (www.lixto.com), a company offering data extraction tools and services, has been providing OMI solutions for several customers. In this paper we show how Lixto has tackled each of the above challenges by improving and extending its original data extraction software. Most importantly, we show how high scalability is achieved through cloud computing. This paper also features a case study from the computers and electronics market.
Oracle Database Replay
Authors: Colle Romain , Galanis Leonidas , Buranawatanachoke Supiti , Papadomanolakis Stratos , Wang Yujun
Published: June 2014

This demonstration presents Oracle Database Replay, a novel approach to testing changes to the relational database management system component of an information system (software upgrades, hardware changes etc). Database Replay makes it possible to subject a test system to a real production workload, which helps identify all potential problems before implementing the planned changes on the production system. Any interesting workload period of a production database system can be captured with minimal overhead. The captured workload is used to drive a test system while maintaining the concurrency and load characteristics of the real production workload.

The demonstration showcases how important maintaining the concurrency and load characteristics of the real workload is. The current testing solutions do not allow for synchronization based on data dependencies. Without proper synchronization the demonstration workload does not perform the work required and does not exercise the test system appropriately, leading to poor coverage and inadequate load. Thus many issues remain undetected. Database replay with its data based synchronization makes testing realistic and leads to the discovery of potential problems.
Microsoft CEP server and online behavioral targeting
Authors: Ali M. H. , Gerea C. , Raman B. S. , Sezgin B. , Tarnavski T. , Verona T. , Wang P. , Zabback P. , Ananthanarayan A. , Kirilov A. , Lu M. , Raizman A. , Krishnan R. , Schindlauer R. , Grabs T. , Bjeletich S. , Chandramouli B. , Goldstein J. , Bhat S. , Li Ying , Di Nicola V. , Wang X. , Maier David , Grell S. , Nano O. , Santos I.
Published: June 2014

In this demo, we present the
Microsoft Complex Event Processing
(CEP) Server,
Microsoft CEP
for short.
Microsoft CEP
is an event stream processing system featured by its declarative query language and its multiple consistency levels of stream query processing. Query composability, query fusing, and operator sharing are key features in the
Microsoft CEP
query processor. Moreover, the debugging and supportability tools of
Microsoft CEP
provide visibility of system internals to users.

Web click analysis has been crucial to behavior-based online marketing. Streams of web click events provide a typical workload for a CEP server. Meanwhile, a
CEP
server with its processing capabilities plays a key role in web click analysis. This demo highlights the features of
Microsoft CEP
under a workload of web click events.
RankIE
Authors: Brauer Falk , Barczynski Wojciech , Hackenbroich Gregor , Schramm Marcus , Mocan Adrian , Förster Felix
Published: June 2014

Developer communities built around software products, like the SAP Community Network, provide a knowledge base for reocurring problems and their solutions. Due to the large amount of content maintained in such communities, e.g., in forums, finding relevant solutions is a major challenge beyond the scope of common keyword-based search engines. In fact, it is measured that around 50% of the forum questions of our particular scenario have already been answered at the time they are posted.

We target this challenge by an entity aware search, which exploits structured knowledge, such as domain-specific ontologies, for both query interpretation and creation of document indexes. The system takes a natural language query as input, interprets it as an entity graph, matches this graph with pre-processed content and supports the user in refining his query based on the top-k relevant entities. Results are presented in a user interface that supports faceted search based on entities. Additionally, the user interface is structured according to possible search intentions of users. The evaluation of our system on the SCN scenario yields that the
top 5
entities in user queries are recognized with a precision of 83% compared to 61% of state of the art algorithms.
Goal-oriented web-site navigation for on-line shoppers
Authors: Deutch Daniel , Milo Tova , Yam Tom
Published: June 2014

Web-sites for on-line shopping typically offer a vast number of product options and combinations thereof. While this is very useful, it often makes the navigation in the site and the identification of the "ideal" purchase (where the notion of ideal differs among users) a confusing, non-trivial experience. This demonstration presents ShopIT (ShoppIng assitanT), a system that assists on-line shoppers by suggesting the most effective navigation paths for their specified criteria and preferences. The suggestions are continually adapted to choices/decisions taken by the users while navigating. ShopITis based on a set of novel, adaptive, provably optimal algorithms for TOP-K query evaluation.
How best to build web-scale data managers?
Authors: Bernstein Philip A. , Abadi Daniel J. , Cafarella Michael J. , Hellerstein Joseph M. , Kossmann Donald , Madden Samuel
Published: June 2014

Many of the largest database-driven web sites use custom web-scale data managers (WDMs). On the surface, these WDMs are being applied to problems that are well-suited for relational database systems. Some examples are the following:

• Map-Reduce [5], Hadoop [7], and Dryad [9] are used to process queries on large data sets using sequential scan and aggregation. Hive [8] is a data warehouse built on Hadoop.

• Google's Bigtable [3] is used to store a replicated table of rows of semi-structured data.

• Amazon's Dynamo [6] is used to store partitioned, replicated databases of key-value pairs. Cassandra [2] is similar.

• Object caching systems are used instead of a persistent store, such as memcached [10], Oracle's Coherence, and Microsoft's Velocity project.
Data visualization and social data analysis
Authors: Heer Jeffrey , Hellerstein Joseph M.
Published: June 2014

Analysts in all areas of human knowledge, from science and engineering to economics, social science and journalism are drowning in data. New technologies for sensing, simulation, and communication are helping people to both collect and produce data at exponential rates.
Efficient approximate search on string collections
Authors: Hadjieleftheriou Marios , Li Chen
Published: June 2014

This tutorial provides a comprehensive overview of recent research progress on the important problem of approximate search in string collections. We identify existing indexes, search algorithms, filtering strategies, selectivity-estimation techniques and other work, and comment on their respective merits and limitations.
Managing massive time series streams with multi-scale compressed trickles
Authors: Reeves Galen , Liu Jie , Nath Suman , Zhao Feng
Published: June 2014

We present Cypress, a novel framework to archive and query massive time series streams such as those generated by sensor networks, data centers, and scientific computing. Cypress applies multi-scale analysis to decompose time series and to obtain sparse representations in various domains (e.g. frequency domain and time domain). Relying on the sparsity, the time series streams can be archived with reduced storage space. We then show that many statistical queries such as trend, histogram and correlations can be answered directly from compressed data rather than from reconstructed raw data. Our evaluation with server utilization data collected from real data centers shows significant benefit of our framework.
Promotion analysis in multi-dimensional space
Authors: Wu Tianyi , Xin Dong , Mei Qiaozhu , Han Jiawei
Published: June 2014

Promotion is one of the key ingredients in marketing. It is often desirable to find merit in an object (e.g., product, person, organization, or service) and promote it in an appropriate community. In this paper, we propose a novel functionality, called
promotion analysis through ranking
, for promoting a given object by leveraging highly ranked results. Since the object may not be highly ranked in the global space, our goal is to discover
promotive
subspaces in which the object becomes prominent. To achieve this goal, the notion of
promotiveness
is formulated. We show that this functionality is practical and useful in a wide variety of applications such as business intelligence. However, computing promotive subspaces is challenging due to the explosion of search space and high aggregation cost. For efficient computation, we propose a PromoRank framework, and develop three efficient optimization techniques, namely subspace pruning, object pruning, and promotion cube, which are seamlessly integrated into the framework. Our empirical evaluation on two real data sets confirms the effectiveness of promotion analysis, and that our proposed algorithms significantly outperform baseline solutions.
Using trees to depict a forest
Authors: Liu Bin , Jagadish H. V.
Published: June 2014

When a database query has a large number of results, the user can only be shown one page of results at a time. One popular approach is to rank results such that the "best" results appear first. However, standard database query results comprise a set of tuples, with no associated ranking. It is typical to allow users the ability to sort results on selected attributes, but no actual ranking is defined.

An alternative approach to the first page is not to try to show the best results, but instead to help users learn what is available in the whole result set and direct them to finding what they need. In this paper, we demonstrate through a user study that a page comprising one representative from each of
k
clusters (generated through a
k
-medoid clustering) is superior to multiple alternative candidate methods for generating representatives of a data set.

Users often refine query specifications based on returned results. Traditional clustering may lead to completely new representatives after a refinement step. Furthermore, clustering can be computationally expensive. We propose a tree-based method for efficiently generating the representatives, and smoothly adapting them with query refinement. Experiments show that our algorithms outperform the state-of-the-art in both result quality and efficiency.
Reference-based alignment in large sequence databases
Authors: Papapetrou Panagiotis , Athitsos Vassilis , Kollios George , Gunopulos Dimitrios
Published: June 2014

This paper introduces a novel method, called Reference-Based String Alignment (RBSA), that speeds up retrieval of optimal subsequence matches in large databases of sequences under the edit distance and the Smith-Waterman similarity measure. RBSA operates using the assumption that the optimal match deviates by a relatively small amount from the query, an amount that does not exceed a prespecified fraction of the query length. RBSA has an exact version that guarantees no false dismissals and can handle large queries efficiently. An approximate version of RBSA is also described, that achieves significant additional improvements over the exact version, with negligible losses in retrieval accuracy. RBSA performs filtering of candidate matches using precomputed alignment scores between the database sequence and a set of fixed-length reference sequences. At query time, the query sequence is partitioned into segments of length equal to that of the reference sequences. For each of those segments, the alignment scores between the segment and the reference sequences are used to efficiently identify a relatively small number of candidate subsequence matches. An alphabet collapsing technique is employed to improve the pruning power of the filter step. In our experimental evaluation, RBSA significantly outperforms state-of-the-art biological sequence alignment methods, such as q-grams, BLAST, and BWT.