bluuebunny/crossref_metadata_2025 huggingface dataset:
Structural signatures for tree data structures
Authors: Kundu Ashish , Bertino Elisa
Published: June 2014

Data sharing with multiple parties over a third-party distribution framework requires that both data integrity and confidentiality be assured. One of the most widely used data organization structures is the tree structure. When such structures encode sensitive information (such as in XML documents), it is crucial that integrity and confidentiality be assured not only for the content, but also for the structure. Digital signature schemes are commonly used to authenticate the integrity of the data. The most widely used such technique for tree structures is the Merkle hash technique, which however is known to be "not hiding", thus leading to unauthorized leakage of information. Most techniques in the literature are based on the Merkle hash technique and thus suffer from the problem of unauthorized information leakages. Assurance of integrity and confidentiality (no leakages) of tree-structured data is an important problem in the context of secure data publishing and content distribution systems.

In this paper, we propose a signature scheme for tree structures, which assures both confidentiality and integrity and is also efficient, especially in third-party distribution environments. Our integrity assurance technique, which we refer to as the "Structural signature scheme", is based on the structure of the tree as defined by tree traversals (pre-order, post-order, in-order) and is defined using a randomized notion of such traversal numbers. In addition to formally defining the technique, we prove that it protects against violations of content and structural integrity and information leakages. We also show through complexity and performance analysis that the structural signature scheme is efficient; with respect to the Merkle hash technique, it incurs comparable cost for signing the trees and incurs lower cost for user-side integrity verification.
Maintaining dynamic channel profiles on the web
Authors: Roitman Haggai , Carmel David , Yom-Tov Elad
Published: June 2014

This work addresses a novel problem of maintaining channel proflies on the Web. Such channel maintenance is essential for next generation of Web 2.0 applications that provide sophisticated search and discovery services over Web information channels. Maintaining a fresh channel profile is extremely difficult due to the the dynamic nature of the channel, especially under the constraint of a limited monitoring budget.

We propose a novel monitoring scheme that learns the channels' monitoring rates. The monitoring scheme is further extended to consider the content that is published on the channels. We describe a novelty detection filter that refines the monitoring rate according to the expected rate of novel content published on the channels. We further show how inter-channel profile similarities can be utilized to refine the channel monitoring rates.

Using real-world data of Web feeds we study the performance of the monitoring scheme. We experiment with several monitoring policies over a large set of Web feeds and show that a policy based on learning the monitoring rate of the channels, combined with novelty detection, outperforms alternative channel monitoring policies. Our results show that the suggested content-based policy is able to maintain high quality channel profiles under limited monitoring resources.
Hashed samples
Authors: Hadjieleftheriou Marios , Yu Xiaohui , Koudas Nick , Srivastava Divesh
Published: June 2014

We study selectivity estimation techniques for set similarity queries. A wide variety of similarity measures for sets have been proposed in the past. In this work we concentrate on the class of weighted similarity measures (e.g., TF/IDF and BM25 cosine similarity and variants) and design selectivity estimators based on a priori constructed samples. First, we study the pitfalls associated with straightforward applications of random sampling, and argue that care needs to be taken in how the samples are constructed; uniform random sampling yields very low accuracy, while query sensitive realtime sampling is more expensive than exact solutions (both in CPU and I/O cost). We show how to build robust samples a priori, based on existing synopses for distinct value estimation. We prove the accuracy of our technique theoretically, and verify its performance experimentally. Our algorithm is orders of magnitude faster than exact solutions and has very small space overhead.
Efficient search for the top-k probable nearest neighbors in uncertain databases
Authors: Beskales George , Soliman Mohamed A. , Ilyas Ihab F.
Published: June 2014

Uncertainty pervades many domains in our lives. Current real-life applications, e.g., location tracking using GPS devices or cell phones, multimedia feature extraction, and sensor data management, deal with different kinds of uncertainty. Finding the nearest neighbor objects to a given query point is an important query type in these applications.

In this paper, we study the problem of finding objects with the highest marginal probability of being the nearest neighbors to a query object. We adopt a general uncertainty model allowing for data and query uncertainty. Under this model, we define new query semantics, and provide several efficient evaluation algorithms. We analyze the cost factors involved in query evaluation, and present novel techniques to address the trade-offs among these factors. We give multiple extensions to our techniques including handling dependencies among data objects, and answering threshold queries. We conduct an extensive experimental study to evaluate our techniques on both real and synthetic data.
Type inference and type checking for queries on execution traces
Authors: Deutch Daniel , Milo Tova
Published: June 2014

This paper studies, for the first time, the management of type information for an important class of semi-structured data: nested DAGs (Directed Acyclic Graphs) that describe execution traces of business processes (BPs for short). Specifically, we consider here type inference and type checking for queries over BP execution traces. The queries that we consider select portions of the traces that are of interest to the user; the types describe the possible shape of the execution traces in the input/output of the query.

We formally define and characterize here three common classes of BP execution traces and their respective notions of type inference and type checking. We study the complexity of the two problems for query languages of varying expressive power and present efficient type inference/checking algorithms whenever possible. Our analysis offers a nearly complete picture of which combinations of trace classes and query features lead to PTIME algorithms and which to NP-complete or undecidable problems.
Accuracy estimate and optimization techniques for SimRank computation
Authors: Lizorkin Dmitry , Velikhov Pavel , Grinev Maxim , Turdakov Denis
Published: June 2014

The measure of similarity between objects is a very useful tool in many areas of computer science, including information retrieval. SimRank is a simple and intuitive measure of this kind, based on graph-theoretic model. SimRank is typically computed iteratively, in the spirit of PageRank. However, existing work on SimRank lacks accuracy estimation of iterative computation and has discouraging time complexity.

In this paper we present a technique to estimate the accuracy of computing SimRank iteratively. This technique provides a way to find out the number of iterations required to achieve a desired accuracy when computing SimRank. We also present optimization techniques that improve the computational complexity of the iterative algorithm from
O
(
n
4
) to
O
(
n
3
) in the worst case. We also introduce a threshold sieving heuristic and its accuracy estimation that further improves the efficiency of the method.

As a practical illustration of our techniques we computed SimRank scores on a subset of English Wikipedia corpus, consisting of the complete set of articles and category links.
Dependable cardinality forecasts for XQuery
Authors: Teubner Jens , Grust Torsten , Maneth Sebastian , Sakr Sherif
Published: June 2014

Though inevitable for effective cost-based query rewriting, the derivation of meaningful cardinality estimates has remained a notoriously hard problem in the context of XQuery. By basing the estimation on a relational representation of the XQuery syntax, we show how existing cardinality estimation techniques for XPath and proven relational estimation machinery can play together to yield dependable forecasts for arbitrary XQuery (sub)expressions. Our approach benefits from a light-weight form of data flow analysis.
Abstract domain identifiers
guide our query analyzer through the estimation process and allow for informed decisions even in case of deeply nested XQuery expressions. A variant of
projection paths
[15] provides a versatile interface into which existing techniques for XPath cardinality estimation can be plugged in seamlessly. We demonstrate an implementation of this interface based on
data guides.
Experiments show how our approach can equally cope with both, structure-and value-based queries. It is robust with respect to intermediate estimation errors, from which we typically found our implementation to recover gracefully.
Rose
Authors: Sears Russell , Callaghan Mark , Brewer Eric
Published: June 2014

Rose is a database storage engine for high-throughput replication. It targets seek-limited, write-intensive transaction processing workloads that perform near real-time decision support and analytical processing queries. Rose uses
log structured merge
(LSM) trees to create full database replicas using purely sequential I/O, allowing it to provide orders of magnitude more write throughput than B-tree based replicas. Also, LSM-trees cannot become fragmented and provide fast, predictable index scans.

Rose's write performance relies on replicas' ability to perform writes without looking up old values. LSM-tree lookups have performance comparable to B-tree lookups. If Rose read each value that it updated then its write throughput would also be comparable to a B-tree. Although we target replication, Rose provides high write throughput to any application that updates tuples without reading existing data, such as append-only, streaming and versioning databases.

We introduce a page compression format that takes advantage of LSM-tree's sequential, sorted data layout. It increases replication throughput by reducing sequential I/O, and enables efficient tree lookups by supporting small page sizes and doubling as an index of the values it stores. Any scheme that can compress data in a single pass and provide random access to compressed values could be used by Rose.

Replication environments have multiple readers but only one writer. This allows Rose to provide atomicity, consistency and isolation to concurrent transactions without resorting to rollback, blocking index requests or interfering with maintenance tasks.

Rose avoids random I/O during replication and scans, leaving more I/O capacity for queries than existing systems, and providing scalable, real-time replication of seek-bound workloads. Analytical models and experiments show that Rose provides orders of magnitude greater replication bandwidth over larger databases than conventional techniques.
Scalable query result caching for web applications
Authors: Garrod Charles , Manjhi Amit , Ailamaki Anastasia , Maggs Bruce , Mowry Todd , Olston Christopher , Tomasic Anthony
Published: June 2014

The backend database system is often the performance bottleneck when running web applications. A common approach to scale the database component is query result caching, but it faces the challenge of maintaining a high cache hit rate while efficiently ensuring cache consistency as the database is updated. In this paper we introduce Ferdinand, the first proxy-based cooperative query result cache with fully distributed consistency management. To maintain a high cache hit rate, Ferdinand uses both a local query result cache on each proxy server and a distributed cache. Consistency management is implemented with a highly scalable publish/subscribe system. We implement a fully functioning Ferdinand prototype and evaluate its performance compared to several alternative query-caching approaches, showing that our high cache hit rate and consistency management are both critical for Ferdinand's performance gains over existing systems.
Fault-tolerant stream processing using a distributed, replicated file system
Authors: Kwon YongChul , Balazinska Magdalena , Greenberg Albert
Published: June 2014

We present SGuard, a new fault-tolerance technique for distributed stream processing engines (SPEs) running in clusters of commodity servers. SGuard is less disruptive to normal stream processing and leaves more resources available for normal stream processing than previous proposals. Like several previous schemes, SGuard is based on rollback recovery [18]: it checkpoints the state of stream processing nodes periodically and restarts failed nodes from their most recent checkpoints. In contrast to previous proposals, however, SGuard performs checkpoints asynchronously:
i.e.
, operators continue processing streams during the checkpoint thus reducing the potential disruption due to the checkpointing activity. Additionally, SGuard saves the checkpointed state into a new type of distributed and replicated file system (DFS) such as GFS [22] or HDFS [9], leaving more memory resources available for normal stream processing. To manage resource contention due to simultaneous checkpoints by different SPE nodes, SGuard adds a scheduler to the DFS. This scheduler coordinates large batches of write requests in a manner that reduces individual checkpoint times while maintaining good overall resource utilization. We demonstrate the effectiveness of the approach through measurements of a prototype implementation in the Borealis [2] open-source SPE using HDFS [9] as the DFS.
Dynamic partitioning of the cache hierarchy in shared data centers
Authors: Soundararajan Gokul , Chen Jin , Sharaf Mohamed A. , Amza Cristiana
Published: June 2014

Due to the imperative need to reduce the management costs of large data centers, operators multiplex several concurrent database applications on a server farm connected to shared network attached storage. Determining and enforcing per-application resource quotas in the resulting cache hierarchy, on the fly, poses a complex resource allocation problem spanning the database server and the storage server tiers. This problem is further complicated by the need to provide strict Quality of Service (QoS) guarantees to hosted applications.

In this paper, we design and implement a novel coordinated partitioning technique of the database buffer pool and storage cache between applications for any given cache replacement policy and per-application access pattern. We use statistical regression to dynamically determine the mapping between cache quota settings and the resulting per-application QoS. A resource controller embedded within the database engine actuates the partitioning of the two-level cache, converging towards the configuration with maximum application utility, expressed as the service provider revenue in that configuration, based on a set of latency sample points.

Our experimental evaluation, using the MySQL database engine, a server farm with consolidated storage, and two e-commerce benchmarks, shows the effectiveness of our technique in enforcing application QoS, as well as maximizing the revenue of the service provider in shared server farms.
Output perturbation with query relaxation
Authors: Xiao Xiaokui , Tao Yufei
Published: June 2014

Given a dataset containing sensitive personal information, a statistical database answers aggregate queries in a manner that preserves individual privacy. We consider the problem of constructing a statistical database using
output perturbation
, which protects privacy by injecting a small noise into each query result. We show that the state-of-the-art approach, ε-
differential privacy
, suffers from two severe deficiencies: it (i) incurs prohibitive computation overhead, and (ii) can answer only a limited number of queries, after which the statistical database has to be shut down. To remedy the problem, we develop a new technique that enforces ε-different privacy with economical cost. Our technique also incorporates a
query relaxation
mechanism, which removes the restriction on the number of permissible queries. The effectiveness and efficiency of our solution are verified through experiments with real data.
Transaction time indexing with version compression
Authors: Lomet David , Hong Mingsheng , Nehme Rimma , Zhang Rui
Published: June 2014

Immortal DB is a transaction time database system designed to enable high performance for temporal applications. It is built into a commercial database engine, Microsoft SQL Server. This paper describes how we integrated a temporal indexing technique, the TSB-tree, into Immortal DB to serve as the core access method. The TSB-tree provides high performance access and update for both current and historical data. A main challenge was integrating TSB-tree functionality while preserving original B+tree functionality, including concurrency control and recovery. We discuss the overall architecture, including our unique treatment of index terms, and practical issues such as uncommitted data and log management. Performance is a primary concern. To increase performance, versions are locally delta compressed, exploiting the commonality between adjacent versions of the same record. This technique is also applied to index terms in index pages. There is a tradeoff between query performance and storage space. We discuss optimizing performance regarding this tradeoff throughout the paper. The result of our efforts is a high-performance transaction time database system built
into
an RDBMS engine, which has not been achieved before. We include a thorough experimental study and analysis that confirms the very good performance that it achieves.
Managing and querying transaction-time databases under schema evolution
Authors: Moon Hyun J. , Curino Carlo A. , Deutsch Alin , Hou Chien-Yi , Zaniolo Carlo
Published: June 2014

The old problem of managing the history of database information is now made more urgent and complex by fast spreading web information systems, such as Wikipedia. Our
PRIMA
system addresses this difficult problem by introducing two key pieces of new technology. The first is a method for publishing the history of a relational database in XML, whereby the evolution of the schema and its underlying database are given a unified representation. This temporally grouped representation makes it easy to formulate sophisticated historical queries on any given schema version using standard XQuery. The second key piece of technology is that schema evolution is transparent to the user: she writes queries against the current schema while retrieving the data from one or more schema versions. The system then performs the labor-intensive and error-prone task of rewriting such queries into equivalent ones for the appropriate versions of the schema. This feature is particularly important for historical queries spanning over potentially hundreds of different schema versions and it is realized in
PRIMA
by (i) introducing Schema Modification Operators (SMOs) to represent the mappings between successive schema versions and (ii) an XML integrity constraint language (XIC) to efficiently rewrite the queries using the constraints established by the SMOs. The scalability of the approach has been tested against both synthetic data and real-world data from the Wikipedia DB schema evolution history.
On efficiently searching trajectories and archival data for historical similarities
Authors: Sherkat Reza , Rafiei Davood
Published: June 2014

We study the problem of efficiently evaluating similarity queries on histories, where a history is a
d
-dimensional time series for
d
≥ 1. While there are some solutions for time-series and spatio-temporal trajectories where typically
d
≤ 3, we are not aware of any work that examines the problem for larger values of
d.
In this paper, we address the problem in its general case and propose a class of summaries for histories with a few interesting properties. First, for commonly used distance functions such as the

L
p

-norm, LCSS, and DTW, the summaries can be used to efficiently prune some of the histories that cannot be in the answer set of the queries. Second, histories can be indexed based on their summaries, hence the qualifying candidates can be efficiently retrieved. To further reduce the number of unnecessary distance computations for false positives, we propose a finer level approximation of histories, and an algorithm to find an approximation with the least maximum distance estimation error. Experimental results confirm that the combination of our feature extraction approaches and the indexability of our summaries can improve upon existing methods and scales up for larger values of
d
and database sizes, based on our experiments on real and synthetic datasets of 17-dimensional histories.
A request-routing framework for SOA-based enterprise computing
Authors: Phan Thomas , Li Wen-Syan
Published: June 2014

Enterprises may use a service-oriented architecture (SOA) to provide a streamlined interface to their business processes. To scale up the system, each tier in a composite service usually deploys multiple servers for load distribution and fault tolerance. Such load distribution across multiple servers within the same tier can be viewed as horizontal load distribution. One limitation of this approach is that load cannot be further distributed when all servers in the same tier are fully loaded. In complex multi-tiered systems, a single business process may actually be implemented by multiple different computation pathways among the tiers, each with different components, in order to provide resiliency and scalability. Such SOA-based enterprise computing with multiple implementation options gives opportunities for vertical load distribution across tiers. In this paper, we propose a requestrouting framework for SOA-based enterprise computing that takes into consideration both horizontal and vertical load distribution. Through experimentation we show that our algorithm and methodology scale well up to a large system configuration comprising up to 1000 workflow requests to a complex composite service with multiple implementations. We also show that a combination of both horizontal and vertical load distributions gives the maximum flexibility to improve performance and fault tolerance.
Hexastore
Authors: Weiss Cathrin , Karras Panagiotis , Bernstein Abraham
Published: June 2014

Despite the intense interest towards realizing the Semantic Web vision, most existing RDF data management schemes are constrained in terms of efficiency and scalability. Still, the growing popularity of the RDF format arguably calls for an effort to offset these drawbacks. Viewed from a relational-database perspective, these constraints are derived from the very
nature
of the RDF data model, which is based on a
triple
format. Recent research has attempted to address these constraints using a vertical-partitioning approach, in which separate two-column tables are constructed for each property. However, as we show, this approach suffers from similar scalability drawbacks on queries that are not bound by RDF property value. In this paper, we propose an RDF storage scheme that uses the triple nature of RDF as an asset. This scheme enhances the vertical partitioning idea and takes it to its logical conclusion. RDF data is indexed in
six
possible ways, one for each possible ordering of the three RDF elements. Each instance of an RDF element is associated with two vectors; each such vector gathers elements of one of the other types, along with lists of the third-type resources attached to each vector element. Hence, a sextuple-indexing scheme emerges. This format allows for quick and scalable general-purpose query processing; it confers significant advantages (up to five orders of magnitude) compared to previous approaches for RDF data management, at the price of a worst-case five-fold increase in index space. We experimentally document the advantages of our approach on real-world and synthetic data sets with practical queries.
Identifying robust plans through plan diagram reduction
Authors: D. Harish , Darera Pooja N. , Haritsa Jayant R.
Published: June 2014

Estimates of predicate selectivities by database query optimizers often differ significantly from those actually encountered during query execution, leading to poor plan choices and inflated response times. In this paper, we investigate mitigating this problem by replacing selectivity error-sensitive plan choices with alternative plans that provide robust performance. Our approach is based on the recent observation that even the complex and dense "plan diagrams" associated with industrial-strength optimizers can be efficiently reduced to "anorexic" equivalents featuring only a few plans, without materially impacting query processing quality.

Extensive experimentation with a rich set of TPC-H and TPC-DS-based query templates in a variety of database environments indicate that plan diagram reduction typically retains plans that are substantially resistant to selectivity errors on the base relations. However, it can sometimes also be severely counter-productive, with the replacements performing much worse. We address this problem through a generalized mathematical characterization of plan cost behavior over the parameter space, which lends itself to efficient criteria of when it is safe to reduce. Our strategies are fully non-invasive and have been implemented in the Picasso optimizer visualization tool.
Sorting hierarchical data in external memory for archiving
Authors: Koltsidas Ioannis , Müller Heiko , Viglas Stratis D.
Published: June 2014

Sorting hierarchical data in external memory is necessary for a wide variety of applications including archiving scientific data and dealing with large XML datasets. The topic of sorting hierarchical data, however, has received little attention from the research community so far. In this paper we focus on sorting arbitrary hierarchical data that far exceed the size of physical memory. We propose HErMeS, an algorithm that generalizes the most widely-used techniques for sorting flat data in external memory. HErMeS efficiently exploits the hierarchical structure to minimize the number of disk accesses and optimize the use of available memory. We extract the theoretical bounds of the algorithm with respect to the structure of the hierarchical dataset. We then show how the algorithm can be used to support efficient archiving. We have conducted an experimental study using several workloads and comparing HErMeS to the state-of-the-art approaches. Our results show that our algorithm (
a
) meets its theoretical expectations, (
b
) allows for scalable database archiving, and (
c
) outperforms the competition by a significant factor. These results, we believe, prove our technique to be a viable and scalable solution to the problem of sorting hierarchical data in external memory.
Oracle SecureFiles System
Authors: Mukherjee Niloy , Aleti Bharath , Ganesh Amit , Kunchithapadam Krishna , Lynn Scott , Muthulingam Sujatha , Shergill Kam , Wang Shaoyu , Zhang Wei
Published: June 2014

Over the last decade, the nature of content stored on computer storage systems has evolved from being relational to being semi-structured, i.e., unstructured data accompanied by relational metadata. Average data volumes have increased from a few hundred megabytes to hundreds of terabytes. Simultaneously, data feed rates have also increased with increase in processor, storage and network bandwidths. Data growth trends seem to be following Moore's law and thereby imply an exponential explosion in content volumes and rates in the years to come. The near future poses requirements for data management systems to provide solutions that provide unlimited scalability in execution, availability, recoverability and storage usage of semi-structured content.

Traditionally, filesystems have been preferred over database management systems for providing storage solutions for unstructured data, while databases have been the preferred choice to manage relational data. Lack of consolidated semi-structured content management architecture compromises security, availability, recoverability, and manageability among other features. We introduce a system without compromises, the Oracle SecureFiles System, designed to provide highly scalable storage and access execution of unstructured and structured content as first-class objects within the Oracle relational database management system. Oracle SecureFiles breaks the performance barrier that has kept such content out of databases. The architecture provides capability to maximize utilization of storage usage through compression and de-duplication and achieves robustness by preserving transactional atomicity, durability, availability, read-consistent query-ability and security of the database management system.
Efficient implementation of sorting on multi-core SIMD CPU architecture
Authors: Chhugani Jatin , Nguyen Anthony D. , Lee Victor W. , Macy William , Hagog Mostafa , Chen Yen-Kuang , Baransi Akram , Kumar Sanjeev , Dubey Pradeep
Published: June 2014

Sorting a list of input numbers is one of the most fundamental problems in the field of computer science in general and high-throughput database applications in particular. Although literature abounds with various flavors of sorting algorithms, different architectures call for customized implementations to achieve faster sorting times.

This paper presents an efficient implementation and detailed analysis of
MergeSort
on current CPU architectures. Our SIMD implementation with 128-bit SSE is 3.3X faster than the scalar version. In addition, our algorithm performs an efficient multiway merge, and is not constrained by the memory bandwidth. Our multi-threaded, SIMD implementation sorts 64 million floating point numbers in
less than
0.5 seconds on a commodity 4-core Intel processor. This measured performance compares favorably with all previously published results.

Additionally, the paper demonstrates performance scalability of the proposed sorting algorithm with respect to certain salient architectural features of modern chip multiprocessor (CMP) architectures, including SIMD width and core-count. Based on our analytical models of various architectural configurations, we see excellent scalability of our implementation with SIMD width scaling up to 16X wider than current SSE width of 128-bits, and CMP core-count scaling well beyond 32 cores. Cycle-accurate simulation of Intel's upcoming x86 many-core Larrabee architecture confirms scalability of our proposed algorithm.
Efficiently approximating query optimizer plan diagrams
Authors: Dey Atreyee , Bhaumik Sourjya , D Harish , Haritsa Jayant R.
Published: June 2014

Given a parametrized n-dimensional SQL query template and a choice of query optimizer, a plan diagram is a color-coded pictorial enumeration of the execution plan choices of the optimizer over the query parameter space. These diagrams have proved to be a powerful metaphor for the analysis and redesign of modern optimizers, and are gaining currency in diverse industrial and academic institutions. However, their utility is adversely impacted by the impractically large computational overheads incurred when standard brute-force exhaustive approaches are used for producing fine-grained diagrams on high-dimensional query templates.

In this paper, we investigate strategies for efficiently producing close approximations to complex plan diagrams. Our techniques are customized to the features available in the optimizer's API, ranging from the generic optimizers that provide only the optimal plan for a query, to those that also support costing of sub-optimal plans and enumerating rank-ordered lists of plans. The techniques collectively feature both random and grid sampling, as well as inference techniques based on nearest-neighbor classifiers, parametric query optimization and plan cost monotonicity.

Extensive experimentation with a representative set of TPC-H and TPC-DS-based query templates on industrial-strength optimizers indicates that our techniques are capable of delivering 90% accurate diagrams while incurring less than 15% of the computational overheads of the exhaustive approach. In fact, for full-featured optimizers, we can guarantee zero error with less than 10% overheads. These approximation techniques have been implemented in the publicly available Picasso optimizer visualization tool.
Optimizer plan change management
Authors: Ziauddin Mohamed , Das Dinesh , Su Hong , Zhu Yali , Yagoub Khaled
Published: June 2014

Execution plans for SQL statements have a significant impact on the overall performance of database systems. New optimizer statistics, configuration parameter changes, software upgrades and hardware resource utilization are among a multitude of factors that may cause the query optimizer to generate new plans. While most of these plan changes are beneficial or benign, a few rogue plans can potentially wreak havoc on system performance or availability, affecting critical and time-sensitive business application needs. The normally desirable ability of a query optimizer to adapt to system changes may sometimes cause it to pick a sub-optimal plan compromising the stability of the system.

In this paper, we present the new SQL Plan Management feature in Oracle 11g. It provides a comprehensive solution for managing plan changes to provide stable and optimal performance for a set of SQL statements. Two of its most important goals are preventing sub-optimal plans from being executed while allowing new plans to be used if they are verifiably better than previous plans. This feature is tightly integrated with Oracle's query optimizer.

SQL Plan Management is available to users via both command-line and graphical interfaces. We describe the feature and then, using an industrial-strength application suite, present experimental results that show that SQL Plan Management provides stable and optimal performance for SQL statements with no performance regressions.
Towards a physical XML independent XQuery/SQL/XML engine
Authors: Liu Zhen Hua , Chandrasekar Sivasankaran , Baby Thomas , Chang Hui J.
Published: June 2014

There has been a lot of research and industrial effort on building XQuery engines with different kinds of XML storage and index models. However, most of these efforts focus on building either an efficient XQuery engine with one kind of XML storage, index, view model in mind or a general XQuery engine without any consideration of the underlying XML storage, index and view model. We need an underlying framework to build an XQuery engine that can work with and provide optimization for different XML storage, index and view models. Besides XQuery, RDBMSs also support SQL/XML, a standard language that integrates XML and relational processing. There are industrial efforts for building hybrid XQuery and SQL/XML engines that support both languages so that users can manage and query both relational and XML data on one platform. However, we need a theoretical framework to optimize both SQL/XML and XQuery languages in one RDBMS. In this paper, we show our industrial work of building a combined XQuery and SQL/XML engine that is able to work and provide optimization for different kinds of XML storage and index models in Oracle XMLDB. This work is based on
XML extended relational algebra
as the underlying tuple-based logical algebra and incorporates tree and automata based physical algebra into the logical tuple-based algebra so as to provide optimization for different physical XML formulations. This results in
logical and physical rewrite
techniques to optimize XQuery and SQL/XML over a variety of physical XML storage, index and view models, including schema aware object relational XML storage with relational indexes, binary XML storage with schema agnostic path-value-order key XMLIndex, SQL/XML view over relational data and relational view over XML. Furthermore, we show the approach of leveraging
cost based XML physical rewrite
strategy to evaluate different physical rewrite plans.
eXtract
Authors: Huang Yu , Liu Ziyang , Chen Yi
Published: June 2014

Snippets are used by almost every text search engine to complement ranking schemes in order to effectively handle user keyword search. Despite the fact that XML is a standard representation format of web data, research on generating result snippets for XML search remains untouched. In this work, we present eXtract, a system that efficiently generates self-contained result snippets within a given size bound which effectively summarize the query results and differentiate them from one another, according to which users can quickly assess the relevance of the query results.
Periscope/GQ
Authors: Tian Yuanyuan , Patel Jignesh M. , Nair Viji , Martini Sebastian , Kretzler Matthias
Published: June 2014

Real life data can often be modeled as graphs, in which nodes represent objects and edges between nodes indicate their relationships. Large graph datasets are common in many emerging applications. Examples span from social networks, biological networks to computer networks. To fully exploit the wealth of information encoded in graphs, systems for managing and analyzing graph data are critical. To address this need, we have designed and developed a graph querying toolkit, called Periscope/GQ. This toolkit is built on top of a traditional RDBMS. It provides a uniform schema for storing graphs in the database and supports various graph query operations, especially sophisticated operations, such as approximate graph matching, large graph alignment and graph summarization. Users can easily combine several operations to perform complex analysis on graphs. In addition, Periscope/GQ employs several novel indexing techniques to speed up query execution. This demonstration will highlight the use of Periscope/GQ in two application domains: life science and social networking.
SEDA
Authors: Balmin Andrey , Colby Latha , Curtmola Emiran , Li Quanzhong , Özcan Fatma , Srinivas Sharath , Vagena Zografoula
Published: June 2014

Keyword search in XML repositories is a powerful tool for interactive data exploration. Much work has recently been done on making XML search aware of relationship information embedded in XML document structure, but without a clear winner in all data and query scenarios. Furthermore, due to its imprecise nature, search results cannot easily be analyzed and summarized to gain more insights into the data. We address these shortcomings with
SEDA:
a system for Search, Exploration, Discovery, and Analysis of XML Data.
SEDA
is based on a paradigm of search and user interaction to help users start with simple keyword-style querying and perform rich analysis of XML data by leveraging both the content and structure of the data.
SEDA
is an interactive system that allows the user to refine her query iteratively to explore the XML data and discover interesting relationships.

SEDA
first employs a top-k algorithm to compute the most relevant top-k answers fast, and returns tuples of nodes ranked by relevance.
SEDA
provides several novel data structures and techniques for efficient top-k computation over graph-structured XML data.
SEDA
also computes all the contexts in which the query terms are found and all the connection paths that connect the query terms in the XML data. These two summaries enable the user to refine her query by disambiguating the contexts and connections relevant to her query. With the user feedback, the system has enough information to compute
all
query results, not just the top-k. From the complete results,
SEDA
automatically deduces a star schema, which is then instantiated with the query results and augmented with additional values required for a well-defined data cube. The tables computed at this step are input into an OLAP engine for further analysis.
Process spaceship
Authors: Motahari Hamid , Benatallah Boualem , Saint-Paul Regis , Casati Fabio , Andritsos Periklis
Published: June 2014

Business processes (BPs) are central to the operation of both public and private organizations. A business process is a set of coordinated tasks and activities to achieve a business objective or goal. Given the importance of BPs to overall efficiency and effectiveness, the competitiveness of organizations hinges on continuous BP improvement. In the nineties, the focus of BP improvement was on automation: workflow management systems (WfMSs) and other middleware technologies were used to reduce cost and improve efficiency by providing better system integration and automated enactment of operational business processes. Recently, the focus of business process has expanded to monitoring, analysis and understanding of business processes, and such techniques are incorporated in business process management systems (BPMSs).
P
3
N
Authors: Lupu Mihai , Tay Y. C.
Published: June 2014

A large number of peer-to-peer (P2P) networks have been introduced in the literature since their popular advent in the late 1990s. In particular, structured P2P overlays have gained much attention since 2001. They are noted mainly for their theoretical properties such as balancing of communication, storage and processing load, as well as elegance of design.
AlvisP2P
Authors: Luu Toan , Skobeltsyn Gleb , Klemm Fabius , Puh Maroje , Žarko Ivana Podnar , Rajman Martin , Aberer Karl
Published: June 2014

In this paper we present the
AlvisP2P
IR engine, which enables efficient retrieval with multi-keyword queries from a global document collection available in a P2P network. In such a network, each peer publishes its local index and invests a part of its local computing resources (storage, CPU, bandwidth) to maintain a fraction of a global P2P index. This investment is rewarded by the network-wide accessibility of the local documents via the global search facility.

The AlvisP2P engine uses an optimized overlay network and relies on novel indexing/retrieval mechanisms that ensure low bandwidth consumption, thus enabling unlimited network growth.

Our demonstration shows how an easy-to-install AlvisP2P client can be used to join an existing P2P network, index local (text or even multimedia) documents with collection-specific indexing mechanisms, and control access rights to them.
AJAXSearch
Authors: Duda Cristian , Frey Gianni , Kossmann Donald , Zhou Chong
Published: June 2014

Current search engines such as Google and Yahoo! are prevalent for searching the Web. Search in dynamic pages, however, is either inexistent or far from perfect. AJAX and Rich Internet Application are such applications. They are increasingly frequent on the Web (in YouTube, Amazon, GMail, Yahoo!Mail) or mobile devices and are offering a high degree of interactivity to the user, by seamlessly loading content from the server without the need to refresh the page. Current search engines cannot correctly index AJAX applications. This produces false positives and false negatives, because search engines do not understand the application logic that loads content dynamically. Crawling an AJAX application is a difficult problem. Since the user invokes events on the page, crawling must identify the different
application states
generated by the client-side logic. This demo sets the stage for this new type of search and shows that a search engine for AJAX can be built. Among others, the challenges, as opposed to traditional search engines, are: automatically identifying states by triggering events, efficiently crawling application states, avoiding the invocation of potentially very numerous events, scalability in the number of events, duplicate elimination of states, result presentation and aggregation, ranking. The demo presents the AJAX search engine: crawler, indexer and query processor, applied on a real application and showcases challenges and solutions.
ManyAspects
Authors: Liu Kun , Terzi Evimaria , Grandison Tyrone
Published: June 2014

We demonstrate ManyAspects -- a document-summarization system that ingests a document and automatically highlights a small set of sentences that are expected to cover the different aspects of the document. The sentences are picked using simple coverage and orthogonality criteria. With ManyAspects, you get a concise yet comprehensive overview of the document without having to spend lots of time drilling down into the details. The system can handle both plain text and syndication feeds (RSS and Atom). It can run either as a stand-alone application or be integrated with Web 2.0 forums to pinpoint different opinions on online discussions for blogs, products, movies, etc. For comparative analysis and exploratory flexibility, the system includes other off-the-shelf text-summarization methods, e.g. k-median clustering and singular value decomposition. Thus, the system allows the user to explore the content of the input document in many different ways.
An effective and versatile keyword search engine on heterogenous data sources
Authors: Li Guoliang , Feng Jianhua , Wang Jianyong , Zhou Lizhu
Published: June 2014

We present EASE, an effective and versatile keyword search engine that enables users to easily access the heterogenous data composed of unstructured, semi-structured and structured data, without the need of learning XPath/XQuery or SQL languages. EASE addresses a challenge in keyword search that has been neglected in the literature: how to efficiently and adaptively process keyword queries on the heterogenous data. To provide such capability, EASE models unstructured, semi-structured and structured data as graphs, summarizes the graphs, and constructs graph indices instead of using traditional inverted indices for effective keyword search. EASE adopts an extended inverted index to facilitate keyword-based search, and employs a novel ranking mechanism for enhancing search effectiveness.
RIDE
Authors: Katsis Yannis , Deutsch Alin , Papakonstantinou Yannis , Zhao Keliang
Published: June 2014

Modern Internet communities need to integrate and query structured information. Employing current information integration infrastructure, data integration is still a very costly effort, since source registration is performed by a central authority which becomes a bottleneck. We propose the community-based integration paradigm which pushes the source registration task to the independent community members. This creates new challenges caused by each member's lack of a global overview on how her data interacts with the application queries of the community and the data from other sources. How can the source owner maximize the visibility of her data to existing applications, while minimizing the clean-up and reformatting cost associated with publishing? Does her data contradict (or could it contradict in the future) the data of other sources?
Large-scale collaborative analysis and extraction of web data
Authors: Weigel Felix , Panda Biswanath , Riedewald Mirek , Gehrke Johannes , Calimlim Manuel
Published: June 2014

Archived web data is a great resource for scientific research, but poses serious challenges in data processing and management. We demonstrate the
Web Lab Collaboration Server
, a platform and service for large-scale collaborative web data analysis in a distributed computing environment, and show how it seamlessly supports non-technical users during search, data extraction and analysis.
AuditGuard
Authors: Lu Wentian , Miklau Gerome
Published: June 2014

Auditing the changes to a database is critical for identifying malicious behavior, maintaining data quality, and improving system performance. But an accurate audit log is a historical record of the past that can also pose a serious threat to privacy. In many domains, retention policies govern how long data can be preserved by an institution. Regulations like FERPA and HIPAA (in the U.S.) or the Directive of Data Protection (in the EU), require strict retention periods to be observed, mandating the disposal of past data. In addition, institutions often adopt their own retention policies, choosing to remove sensitive data after a period of time to avoid its unintended release, or to avoid disclosure that could be forced by subpeona.