bluuebunny/crossref_metadata_2025 huggingface dataset:
Eddies
Authors: Avnur Ron , Hellerstein Joseph M.
Published: November 2005

In large federated and shared-nothing databases, resources can exhibit widely fluctuating characteristics. Assumptions made at the time a query is submitted will rarely hold throughout the duration of query processing. As a result, traditional static query optimization and execution techniques are ineffective in these environments.

In this paper we introduce a query processing mechanism called an
eddy
, which continuously reorders operators in a query plan as it runs. We characterize the
moments of symmetry
during which pipelined joins can be easily reordered, and the
synchronization barriers
that require inputs from different sources to be coordinated. By combining eddies with appropriate join algorithms, we merge the optimization and execution phases of query processing, allowing each tuple to have a flexible ordering of the query operators. This flexibility is controlled by a combination of fluid dynamics and a simple learning algorithm. Our initial implementation demonstrates promising results, with eddies performing nearly as well as a static optimizer/executor in static scenarios, and providing dramatic improvements in dynamic execution environments.
WSQ/DSQ
Authors: Goldman Roy , Widom Jennifer
Published: November 2005

We present WSQ/DSQ (pronounced “wisk-disk”), a new approach for combining the query facilities of traditional databases with existing search engines on the Web. WSQ, for
Web-Supported (Database) Queries
, leverages results from Web searches to enhance SQL queries over a relational database. DSQ, for
Database-Supported (Web) Queries
, uses information stored in the database to enhance and explain Web searches. This paper focuses primarily on WSQ, describing a simple, low-overhead way to support WSQ in a relational DBMS, and demonstrating the utility of WSQ with a number of interesting queries and results. The queries supported by WSQ are enabled by two
virtual tables
, whose tuples represent Web search results generated dynamically during query execution. WSQ query execution may involve many high-latency calls to one or more search engines, during which the query processor is idle. We present a lightweight technique called
asynchronous iteration
that can be integrated easily into a standard sequential query processor to enable concurrency between query processing and multiple Web search requests. Asynchronous iteration has broader applications than WSQ alone, and it opens up many interesting query optimization issues. We have developed a prototype implementation of WSQ by extending a DBMS with virtual tables and asynchronous iteration; performance results are reported.
A framework for expressing and combining preferences
Authors: Agrawal Rakesh , Wimmers Edward L.
Published: November 2005

The advent of the World Wide Web has created an explosion in the available on-line information. As the range of potential choices expand, the time and effort required to sort through them also expands. We propose a formal framework for expressing and combining user preferences to address this problem. Preferences can be used to focus search queries and to order the search results. A preference is expressed by the user for an entity which is described by a set of named fields; each field can take on values from a certain type. The * symbol may be used to match any element of that type. A set of preferences can be combined using a generic combine operator which is instantiated with a value function, thus providing a great deal of flexibility. Same preferences can be combined in more than one way and a combination of preferences yields another preference thus providing the closure property. We demonstrate the power of our framework by illustrating how a currently popular personalization system and a real-life application can be realized as special cases of our framework. We also discuss implementation of the framework in a relational setting.
Microsoft TerraServer
Authors: Barclay Tom , Gray Jim , Slutz Don
Published: November 2005

Microsoft® TerraServer stores aerial, satellite, and topographic images of the earth in a SQL database available via the Internet. It is the world's largest online atlas, combining eight terabytes of image data from the United States Geological Survey (USGS) and SPIN-2. Internet browsers provide intuitive spatial and text interfaces to the data. Users need no special hardware, software, or knowledge to locate and browse imagery. This paper describes how terabytes of “Internet unfriendly” geo-spatial images were scrubbed and edited into hundreds of millions of “Internet friendly” image tiles and loaded into a SQL data warehouse. All meta-data and imagery are stored in the SQL database.

TerraServer demonstrates that general-purpose relational database technology can manage large scale image repositories, and shows that web browsers can be a good geo-spatial image presentation system.
A data model and data structures for moving objects databases
Authors: Forlizzi Luca , Güting Ralf Hartmut , Nardelli Enrico , Schneider Markus
Published: November 2005

We consider spatio-temporal databases supporting spatial objects with continuously changing position and extent, termed
moving objects databases
. We formally define a data model for such databases that includes complex evolving spatial structures such as line networks or multi-component regions with holes. The data model is given as a collection of data types and operations which can be plugged as attribute types into any DBMS data model (e.g. relational, or object-oriented) to obtain a complete model and query language. A particular novel concept is the
sliced representation
which represents a temporal development as a set of
units
, where unit types for spatial and other data types represent certain “simple” functions of time. We also show how the model can be mapped into concrete physical data structures in a DBMS environment.
On effective multi-dimensional indexing for strings
Authors: Jagadish H. V. , Koudas Nick , Srivastava Divesh
Published: November 2005

As databases have expanded in scope from storing purely business data to include XML documents, product catalogs, e-mail messages, and directory data, it has become increasingly important to search databases based on wild-card string matching: prefix matching, for example, is more common (and useful) than exact matching, for such data. In many cases, matches need to be on multiple attributes/dimensions, with correlations between the dimensions. Traditional multi-dimensional index structures, designed with (fixed length) numeric data in mind, are not suitable for matching unbounded length string data.

In this paper, we describe a general technique for adapting a multi-dimensional index structure for wild-card indexing of unbounded length string data. The key ideas are (a) a carefully developed mapping function from strings to rational numbers, (b) representing an unbounded length string in an index leaf page by a fixed length offset to an external key, and (c) storing multiple elided tries, one per dimension, in an index page to prune search during traversal of index pages. These basic ideas affect all index algorithms. In this paper, we present efficient algorithms for different types of string matching.

While our technique is applicable to a wide range of multi-dimensional index structures, we instantiate our generic techniques by adapting the 2-dimensional R-tree to string data. We demonstrate the space effectiveness and time benefits of using the string R-tree both analytically and experimentally.
Efficient and cost-effective techniques for browsing and indexing large video databases
Authors: Oh JungHwan , Hua Kien A.
Published: November 2005

We present in this paper a fully automatic content-based approach to organizing and indexing video data. Our methodology involves three steps:

Step 1: We segment each video into shots using a Camera-Tracking technique. This process also extracts the feature vector for each shot, which consists of two statistical variances

Var
BA

and

Var
OA

. These values capture how much things are changing in the background and foreground areas of the video shot.

Step 2: For each video, We apply a fully automatic method to build a browsing hierarchy using the shots identified in Step 1.

Step 3: Using the

Var
BA

and

Var
OA

values obtained in Step 1, we build an index table to support a variance-based video similarity model. That is, video scenes/shots are retrieved based on given values of

Var
BA

and

Var
OA

.

The above three inter-related techniques offer an integrated framework for modeling, browsing, and searching large video databases. Our experimental results indicate that they have many advantages over existing methods.
Approximating multi-dimensional aggregate range queries over real attributes
Authors: Gunopulos Dimitrios , Kollios George , Tsotras Vassilis J. , Domeniconi Carlotta
Published: November 2005

Finding approximate answers to multi-dimensional range queries over real valued attributes has significant applications in data exploration and database query optimization. In this paper we consider the following problem: given a table of
d
attributes whose domain is the real numbers, and a query that specifies a range in each dimension, find a good approximation of the number of records in the table that satisfy the query.

We present a new histogram technique that is designed to approximate the density of multi-dimensional datasets with real attributes. Our technique finds buckets of variable size, and allows the buckets to overlap. Overlapping buckets allow more efficient approximation of the density. The size of the cells is based on the local density of the data. This technique leads to a faster and more compact approximation of the data distribution. We also show how to generalize kernel density estimators, and how to apply them on the multi-dimensional query approximation problem.

Finally, we compare the accuracy of the proposed techniques with existing techniques using real and synthetic datasets.
Indexing images in Oracle8i
Authors: Annamalai Melliyal , Chopra Rajiv , DeFazio Samuel , Mavris Susan
Published: November 2005

Content-based retrieval of images is the ability to retrieve images that are similar to a query image. Oracle8i Visual Information Retrieval provides this facility based on technology licensed from Virage, Inc. This product is built on top of Oracle8i interMedia which enables storage, retrieval and management of images, audios and videos. Images are matched using attributes such as color, texture and structure and efficient content-based retrieval is provided using indexes of an image index type. The design of the index type is based on a multi-level filtering algorithm. The filters reduce the search space so that the expensive comparison algorithm operates on a small subset of the data. Bitmap indexes are used to evaluate the first filter resulting in a design which performs well and is scalable. The image index type is built using Oracle8i extensible indexing technology, allowing users to create, use, and drop instances of this index type as they would any other standard index. In this paper we present an overview of the product, the design of the image index type, and some performance results of our product.
λ-DB
Authors: Fegaras Leonidas , Srinivasan Chandrasekhar , Rajendran Arvind , Maier David
Published: November 2005

The λ-DB project at the University of Texas at Arlington aims at developing frameworks and prototype systems that address the new query optimization challenges for object-oriented and object-relational databases, such as query nesting, multiple collection types, methods, and arbitrary nesting of collections. We have already developed a theoretical framework for query optimization based on an effective calculus, called the monoid comprehension calculus [4]. The system reported here is a fully operational ODMG 2.0 [2] OODB management system, based on this framework. Our system can handle most ODL declarations and can process most OQL query forms. λ-DB is not ODMG compliant. Instead it supports its own C++ binding that provides a seamless integration between OQL and C++ with low impedance mismatch. It allows C++ variables to be used in queries and results of queries to be passed back to C++ programs. Programs expressed in our C++ binding are compiled by a preprocessor that performs query optimization at compile time, rather than run-time, as it is proposed by ODMG. In addition to compiled queries, λ-DB provides an interpreter that evaluates ad-hoc OQL queries at run-time.

The λ-DB system architecture is shown in Figure 1. The λ-DB evaluation engine is written in SDL (the SHORE Data Language) of the SHORE object management system [1], developed at the University of Wisconsin. ODL schemas are translated into SDL schemas in a straightforward way and are stored in the system catalog. The λ-DB OQL compiler is a C++ preprocessor that accepts a language called λ-OQL, which is C++ code with embedded DML commands to perform transactions, queries, updates, etc. The preprocessor translates λ-OQL programs into C++ code that contains calls to the λ-DB evaluation engine. We also provide a visual query formulation interface, called VOODOO, and a translator from visual queries to OQL text, which can be sent to the λ-DB OQL interpreter for evaluation.

Even though a lot of effort has been made to make the implementation of our system simple enough for other database researchers to use and extend, our system is quite sophisticated since it employs current state-of-the-art query optimization technologies as well as new advanced experimental optimization techniques which we have developed through the years, such as query unnesting [3]. The λ-DB OODBMS is available as an open source software through the web at http://lambda.uta.edu/lambda-DB.html
An approximate search engine for structural databases
Authors: Wang Jason T. L. , Wang Xiong , Shasha Dennis , Shapiro Bruce A. , Zhang Kaizhong , Ma Qicheng , Weinberg Zasha
Published: November 2005

When a person interested in a topic enters a keyword into a Web search engine, the response is nearly instantaneous (and sometimes overwhelming). The impressive speed is due to clever inverted index structures, caching, and a domain-independent knowledge of strings. Our project seeks to construct algorithms, data structures, and software that approach the speed of keyword-based search engines for queries on structural databases.

A structural database is one whose data objects include trees, graphs, or a set of interrelated labeled points in two, three, or higher dimensional space. Examples include databases holding (i) protein secondary and tertiary structure, (ii) phylogenetic trees, (iii) neuroanatomical networks, (iv) parse trees, (v) molecular diagrams, and (vi) XML documents. Comparison queries on such databases require solving variants of the graph isomorphism or subisomorphism problems (for which all known algorithms are exponential), so we have explored a large heuristic space.
javax.XXL
Authors: van den Bercken Jochen , Dittrich Jens-Peter , Seeger Bernhard
Published: November 2005

Therefore, index structures can easily be used in queries. A typical example is a join cursor which consumes the outputs of two underlying cursors. Most of our work is however not dedicated to the area of relational databases, but mainly refers to spatial and temporal data. For spatial databases, for example, we provide several implementations of spatial join algorithms [3]. The cursor-based processing is however the major advantage of XXL in contrast to approaches like LEDA [6] and TPIE [7]. For more information on XXL see
http://www.mathematik.uni-marburg.de/DBS/xxl
.

We will demonstrate the latest version of XXL using examples to show its core functionality. We will concentrate on three key aspects of XXL.

Usage:
We show how easily state-of-the-art spatial join-algorithms can be implemented in XXL using data from different sources.

Reuse:
We will demonstrate how to support different joins, e.g. spatial and temporal joins, using the same generic algorithm like Plug&Join [1].

Comparability:
We will demonstrate how XXL serves as an ideal testbed to compare query processing algorithms and index structures.
TIP
Authors: Yang Jun , Ying Huacheng C. , Widom Jennifer
Published: November 2005

Commercial relational database systems today provide only limited temporal support. To address the needs of applications requiring rich temporal data and queries, we have built TIP (T
emporal
I
nformation
P
rocessor
), a temporal extension to the Informix database system based on its DataBlade technology. Our TIP DataBlade extends Informix with a rich set of datatypes and routines that facilitate temporal modeling and querying. TIP provides both C and Java libraries for client applications to access a TIP-enabled database, and provides end-users with a GUI interface for querying and browsing temporal data.
AQR-toolkit
Authors: Liu Ling , Pu Calton , Buttler David , Han Wei , Paques Henrique , Tang Wei
Published: November 2005

Query routing is an intelligent service that can direct query requests to appropriate servers that are capable of answering the queries. The goal of a query routing system is to provide efficient associative access to a large, heterogeneous, distributed collection of information providers by routing a user query to the most relevant information sources that can provide the best answer. Effective query routing not only minimizes the query response time and the overall processing cost, but also eliminates a lot of unnecessary communication overhead over the global networks and over the individual information sources.

The AQR-Toolkit divides the query routing task into two cooperating processes: query refinement and source selection. It is well known that a broadly defined query inevitably produces many false positives. Query refinement provides mechanisms to help the user formulate queries that will return more useful results and that can be processed efficiently. As a complimentary process, source selection reduces false negatives by identifying and locating a set of relevant information providers from a large collection of available sources. By pruning irrelevant information sources, source selection also reduces the overhead of contacting the information servers that do not contribute to the answer of the query.

The system architecture of AQR-Toolkit consists of a hierarchical network (a directed acyclic graph) with external information providers at the leaves and query routers as mediating nodes. The end-point information providers support query-based access to their documents. At a query router node, a user may browse and query the meta information about information providers registered at that query router or make use of the router's facilitates for query refinement and source selection.
Evolution and change in data management — issues and directions
Authors: Roddick John F. , Al-Jadir Lina , Bertossi Leopoldo , Dumas Marlon , Estrella Florida , Gregersen Heidi , Hornsby Kathleen , Lufter Jens , Mandreoli Federica , Männistö Tomi , Mayol Enric , Wedemeijer Lex
Published: November 2005

One of the fundamental aspects of information and database systems is that they change. Moreover, in so doing they evolve, although the manner and quality of this evolution is highly dependent on the mechanisms in place to handle it. While changes in data are handled well, changes in other aspects, such as structure, rules, constraints, the model, etc., are handled to varying levels of sophistication and completeness.

In order to study this in more detail a workshop on Evolution and Change in Data Management was held in Paris in November 1999. It brought together researchers from a wide range of disciplines with a common interest in handling the fundamental characteristics and the conceptual modelling of change in information and database systems. This short report of the workshop concentrates on some of the general lessons that emerged during the four days.
Incremental maintenance of recursive views using relational calculus/SQL
Authors: Dong Guozhu , Su Jianwen
Published: November 2005

Views are a central component of both traditional database systems and new applications such as data warehouses. Very often the desired views (e.g. the transitive closure) cannot be defined in the standard language of the underlying database system. Fortunately, it is often possible to incrementally maintain these views using the standard language. For example, transitive closure of acyclic graphs, and of undirected graphs, can be maintained in relational calculus after both single edge insertions and deletions. Many such results have been published in the theoretical database community. The purpose of this survey is to make these useful results known to the wider database research and development community.

There are many interesting issues involved in the maintenance of recursive views. A maintenance algorithm may be applicable to just one view, or to a class of views specified by a view definition language such as Datalog. The maintenance algorithm can be specified in a maintenance language of different expressiveness, such as the conjunctive queries, the relational calculus or SQL. Ideally, this maintenance language should be less expensive than the view definition language. The maintenance algorithm may allow updates of different kinds, such as just single tuple insertions, just single tuple deletions, special set-based insertions and/or deletions, or combinations thereof. The view maintenance algorithms may also need to maintain auxiliary relations to help maintain the views of interest. It is of interest to know the minimal arity necessary for these auxiliary relations and whether the auxiliary relations are deterministic. While many results are known about these issues for several settings, many further challenging research problems still remain to be solved.
Beyond document similarity
Authors: Paepcke Andreas , Garcia-Molina Hector , Rodriguez-Mula Gerard , Cho Junghoo
Published: November 2005

In the face of small, one or two word queries, high volumes of diverse documents on the Web are overwhelming search and ranking technologies that are based on document similarity measures. The increase of multimedia data within documents sharply exacerbates the shortcomings of these approaches. Recently, research prototypes and commercial experiments have added techniques that augment similarity-based search and ranking. These techniques rely on judgments about the 'value' of documents. Judgments are obtained directly from users, are derived by conjecture based on observations of user behavior, or are surmised from analyses of documents and collections. All these systems have been pursued independently, and no common understanding of the underlying processes has been presented. We survey existing value-based approaches, develop a reference architecture that helps compare the approaches, and categorize the constituent algorithms. We explain the options for collecting value metadata, and for using that metadata to improve search, ranking of results, and the enhancement of information browsing. Based on our survey and analysis, we then point to several open problems.
Diluting ACID
Authors: Kempster Tim , Stirling Colin , Thanisch Peter
Published: November 2005

Several DBMS vendors have implemented the ANSI standard SQL isolation levels for transaction processing. This has created a gap between database practice and textbook accounts of transaction processing which simply equate isolation with serializability.

We extend the notion of conflict to cover lower isolation levels and we present improved characterisations of classes of schedules achieving these levels.
Generating spatiotemporal datasets on the WWW
Authors: Theodoridis Yannis , Nascimento Mario A.
Published: November 2005

Efficient storage, indexing and retrieval of time-evolving spatial data are some of the tasks that a Spatiotemporal Database Management System (STDBMS) must support. Aiming at designers of indexing methods and access structures, in this article we review the GSTD algorithm for generating spatiotemporal datasets according to several user-defined parameters, and introduce a WWW-based environment for generating and visualizing such datasets. The GSTD interface is available at two main sites: http://www.cti.gr/RD3/GSTD/ and http://www.cs.ualberta.ca/~mn/GSTD/.
Metadata standards for data warehousing
Authors: Vetterli Thomas , Vaduva Anca , Staudt Martin
Published: November 2005

Metadata has been identified as a key success factor in data warehouse projects. It captures all kinds of information necessary to analyse, design, build, use, and interpret the data warehouse contents. In order to spread the use of metadata, enable the interoperability between repositories, and tool integration within data warehousing architectures, a standard for metadata representation and exchange is needed. This paper considers two standards and compares them according to specific areas of interest within data warehousing. Despite their incontestable similarities, there are significant differences between the two standards which would make their unification difficult.
Comparative analysis of six XML schema languages
Authors: Lee Dongwon , Chu Wesley W.
Published: November 2005

As XML [5] is emerging as
the
data format of the internet era, there is an substantial increase of the amount of data in XML format. To better describe such XML data structures and constraints, several XML schema languages have been proposed. In this paper, we present a comparative analysis of six noteworthy XML schema languages.
Knowledge discovery in data warehouses
Authors: Palpanas Themistoklis
Published: November 2005

As the size of data warehouses increase to several hundreds of gigabytes or terabytes, the need for methods and tools that will automate the process of knowledge extraction, or guide the user to subsets of the dataset that are of particular interest, is becoming prominent. In this survey paper we explore the problem of identifying and extracting interesting knowledge from large collections of data residing in data warehouses, by using data mining techniques. Such techniques have the ability to identify patterns and build succinct models to describe the data. These models can also be used to achieve summarization and approximation. We review the associated work in the OLAP, data mining, and approximate query answering literature. We discuss the need for the traditional data mining techniques to adapt, and accommodate the specific characteristics of OLAP systems. We also examine the notion of
interestingness
of data, as a tool to guide the analysis process. We describe methods that have been proposed in the literature for determining what is interesting to the user and what is not, and how these approaches can be incorporated in the data mining algorithms.
Theory of answering queries using views
Authors: Halevy Alon Y.
Published: November 2005

The problem of answering queries using views is to find efficient methods of answering a query using a set of previously materialized views over the database, rather than accessing the database relations. The problem has recently received significant attention because of its relevance to a wide variety of data management problems, such as query optimization, the maintenance of physical data independence, data integration and data warehousing. This article surveys the theoretical issues concerning the problem of answering queries using views.
Moving up the food chain: supporting e-commerce applications on databases
Authors: Jhingran Anant
Published: November 2005

Database systems have enjoyed a tremendous market because they have served many applications really well -- transaction processing in the beginning, and then decision support. Today, with over 200% cumulative growth rate in certain segments of E-Commerce, it is clear that this new class of applications will be a strong driver for databases to grow, commercially, as well as from a Research perspective. This paper outlines some of the issues that I have learnt in dealing with E-Commerce applications that may well be the focus of some of the research in database systems over the course of next few years.
A vision for management of complex models
Authors: Bernstein Phillip A. , Halevy Alon Y. , Pottinger Rachel A.
Published: November 2005

Many problems encountered when building applications of database systems involve the manipulation of models. By "model," we mean a complex structure that represents a design artifact, such as a relational schema, object-oriented interface, UML model, XML DTD, web-site schema, semantic network, complex document, or software configuration. Many uses of models involve managing changes in models and transformations of data from one model into another. These uses require an explicit representation of "mappings" between models. We propose to make database systems easier to use for these applications by making "model" and "model mapping" first-class objects with special operations that simplify their use. We call this capability model management.In addition to making the case for model management, our main contribution is a sketch of a proposed data model. The data model consists of formal, object-oriented structures for representing models and model mappings, and of high-level algebraic operations on those structures, such as matching, differencing, merging, selection, inversion and instantiation. We focus on structure and semantics, not implementation.
Re-designing distance functions and distance-based applications for high dimensional data
Authors: Aggarwal Charu C.
Published: November 2005

In recent years, the detrimental effects of the curse of high dimensionality have been studied in great detail on several problems such as clustering, nearest neighbor search, and indexing. In high dimensional space the data becomes sparse, and traditional indexing and algorithmic techniques fail from the performance perspective. Recent research results show that in high dimensional space, the concept of proximity may not even be qualitatively meaningful [6]. In this paper, we try to outline the effects of generalizing low dimensional techniques to high dimensional applications and the natural effects of sparsity on distance based applications. We outline the guidelines required in order to re-design either the distance functions or the distance-based applications in a meaningful way for high dimensional domains. We provide novel perspectives and insights on some new lines of work for broadening application definitions in order to effectively deal with the dimensionality curse.
Quality of service in multimedia digital libraries
Authors: Bertino Elisa , Elmagarmid Ahmed K. , Hacid Mohand-Saïd
Published: November 2005

There is currently considerable interest in developing multimedia digital libraries. However, it has become clear that existing architectures for management systems do not support the particular requirements of continuous media types. This is particularly the case in the important area of quality of service support. In this correspondence, we discuss quality of service issues within digital libraries and present a reference architecture able to support some quality aspects.
Towards knowledge-based digital libraries
Authors: Feng Ling , Jeusfeld Marfred A. , Hoppenbrouwers Jeroen
Published: November 2005

From the standpoint of satisfying human's information needs, the current digital library (DL) systems suffer from the following two shortcomings: (i) inadequate high-level cognition support; (ii) inadequate knowledge sharing facilities. In this article, we introduce a two-layered digital library architecture to support different levels of human cognitive acts. The model moves beyond simple information searching and browsing across multiple repositories, to inquiry of knowledge about the contents of digital libraries. To address users' high- order cognitive requests, we propose an information space consisting of a knowledge subspace and a document subspace. We extend the traditional indexing and searching schema of digital libraries from
keyword-based
to
knowledge-based
by adding knowledge to the documents into the DL information space. The distinguished features of such enhanced DL systems in comparison with the traditional knowledge-based systems are also discussed.
Constraints for semistructured data and XML
Authors: Buneman Peter , Fan Wenfei , Siméon Jérôme , Weinstein Scott
Published: November 2005

Integrity constraints play a fundamental role in database design. We review initial work on the expression of integrity constraints for semistructured data and XML.
Report on XEWA-00
Authors: Critchlow Terence
Published: November 2005

The XEWA-00 workshop, held in December 2000 and sponsored by the IEEE Computer Society, was organized to bring together members of the bioinformatics community to determine if XML could simplify accessing large, heterogeneous, distributed collections of web-based data sources. The starting point for a series of breakout and group discussions was a proposed strawman of a grammar that described how to query a data source through its web interface. As a result of these discussions, the approach was validated, the strawman was refined, and several reference implementations are being generated as part of an ongoing effort. This article contains an overview of the workshop, including the proposed approach and a description of the strawman.
Efficient computation of Iceberg cubes with complex measures
Authors: Han Jiawei , Pei Jian , Dong Guozhu , Wang Ke
Published: November 2005

It is often too expensive to compute and materialize a complete high-dimensional data cube. Computing an iceberg cube, which contains only aggregates above certain thresholds, is an effective way to derive nontrivial multi-dimensional aggregations for OLAP and data mining.

In this paper, we study efficient methods for computing iceberg cubes with some popularly used complex measures, such as
average
, and develop a methodology that adopts a weaker but anti-monotonic condition for testing and pruning search space. In particular, for efficient computation of iceberg cubes with the
average
measure, we propose a
top-k average
pruning method and extend two previously studied methods, Apriori and BUC, to Top-
k
Apriori and Top-
k
BUC. To further improve the performance, an interesting hypertree structure, called H-tree, is designed and a new iceberg cubing method, called Top-
k
H-Cubing, is developed. Our performance study shows that Top-
k
BUC and Top-
k
H-Cubing are two promising candidates for scalable computation, and Top-
k
H-Cubing has better performance in most cases.
On computing correlated aggregates over continual data streams
Authors: Gehrke Johannes , Korn Flip , Srivastava Divesh
Published: November 2005

In many applications from telephone fraud detection to network management, data arrives in a stream, and there is a need to maintain a variety of statistical summary information about a large number of customers in an online fashion. At present, such applications maintain basic aggregates such as running extrema values (MIN, MAX), averages, standard deviations, etc., that can be computed over data streams with limited space in a straightforward way. However, many applications require knowledge of more complex aggregates relating different attributes, so-called
correlated aggregates
. As an example, one might be interested in computing the percentage of international phone calls that are longer than the average duration of a domestic phone call. Exact computation of this aggregate requires multiple passes over the data stream, which is infeasible.

We propose single-pass techniques for approximate computation of correlated aggregates over both landmark and sliding window views of a data stream of tuples, using a very limited amount of space. We consider both the case where the independent aggregate (average duration in the example above) is an extrema value and the case where it is an average value, with any standard aggregate as the dependent aggregate; these can be used as building blocks for more sophisticated aggregates. We present an extensive experimental study based on some real and a wide variety of synthetic data sets to demonstrate the accuracy of our techniques. We show that this effectiveness is explained by the fact that our techniques exploit monotonicity and convergence properties of aggregates over data streams.
Space-efficient online computation of quantile summaries
Authors: Greenwald Michael , Khanna Sanjeev
Published: November 2005

An ∈-approximate quantile summary of a sequence of
N
elements is a data structure that can answer quantile queries about the sequence to within a precision of ∈
N
.

We present a new online algorithm for computing∈-approximate quantile summaries of very large data sequences. The algorithm has a worst-case space requirement of
Ο
(1÷∈ log(∈
N
)). This improves upon the previous best result of
Ο
(1÷∈ log
2
(∈
N
)). Moreover, in contrast to earlier deterministic algorithms, our algorithm does not require a priori knowledge of the length of the input sequence.

Finally, the actual space bounds obtained on experimental data are significantly better than the worst case guarantees of our algorithm as well as the observed space requirements of earlier algorithms.
Data bubbles
Authors: Breunig Markus M. , Kriegel Hans-Peter , Kröger Peer , Sander Jörg
Published: November 2005

In this paper, we investigate how to scale hierarchical clustering methods (such as OPTICS) to extremely large databases by utilizing data compression methods (such as BIRCH or random sampling). We propose a three step procedure: 1) compress the data into suitable representative objects; 2) apply the hierarchical clustering algorithm only to these objects; 3) recover the clustering structure for the whole data set, based on the result for the compressed data. The key issue in this approach is to design compressed data items such that not only a hierarchical clustering algorithm can be applied, but also that they contain enough information to infer the clustering structure of the original data set in the third step. This is crucial because the results of hierarchical clustering algorithms, when applied naively to a random sample or to the clustering features (CFs) generated by BIRCH, deteriorate rapidly for higher compression rates. This is due to three key problems, which we identify. To solve these problems, we propose an efficient post-processing step and the concept of a Data Bubble as a special kind of compressed data item. Applying OPTICS to these Data Bubbles allows us to recover a very accurate approximation of the clustering structure of a large data set even for very high compression rates. A comprehensive performance and quality evaluation shows that we only trade very little quality of the clustering result for a great increase in performance.
Optimizing multidimensional index trees for main memory access
Authors: Kim Kihong , Cha Sang K. , Kwon Keunjoo
Published: November 2005

Recent studies have shown that cache-conscious indexes such as the CSB+-tree outperform conventional main memory indexes such as the T-tree. The key idea of these cache-conscious indexes is to eliminate most of child pointers from a node to increase the fanout of the tree. When the node size is chosen in the order of the cache block size, this pointer elimination effectively reduces the tree height, and thus improves the cache behavior of the index. However, the pointer elimination cannot be directly applied to multidimensional index structures such as the R-tree, where the size of a key, typically, an MBR (minimum bounding rectangle), is much larger than that of a pointer. Simple elimination of four-byte pointers does not help much to pack more entries in a node.

This paper proposes a cache-conscious version of the R-tree called the CR-tree. To pack more entries in a node, the CR-tree compresses MBR keys, which occupy almost 80% of index data in the two-dimensional case. It first represents the coordinates of an MBR key relatively to the lower left corner of its parent MBR to eliminate the leading O's from the relative coordinate representation. Then, it quantizes the relative coordinates with a fixed number of bits to further cut off the trailing less significant bits. Consequently, the CR-tree becomes significantly wider and smaller than the ordinary R-tree. Our experimental and analytical study shows that the two-dimensional CR-tree performs search up to 2.5 times faster than the ordinary R-tree while maintaining similar update performance and consuming about 60% less memory space.
Main-memory index structures with fixed-size partial keys
Authors: Bohannon Philip , Mcllroy Peter , Rastogi Rajeev
Published: November 2005

The performance of main-memory index structures is increasingly determined by the number of CPU cache misses incurred when traversing the index. When keys are stored indirectly, as is standard in main-memory databases, the cost of key retrieval in terms of cache misses can dominate the cost of an index traversal. Yet it is inefficient in both time and space to store even moderate sized keys directly in index nodes. In this paper, we investigate the performance of tree structures suitable for OLTP workloads in the face of expensive cache misses and non-trivial key sizes. We propose two index structures, pkT-trees and pkB-trees, which significantly reduce cache misses by storing
partial-key information
in the index. We show that a small, fixed amount of key information allows most cache misses to be avoided, allowing for a simple node structure and efficient implementation. Finally, we study the performance and cache behavior of partial-key trees by comparing them with other main-memory tree structures for a wide variety of key sizes and key value distributions.
Independence is good
Authors: Deshpande Amol , Garofalakis Minos , Rastogi Rajeev
Published: November 2005

Approximating the joint data distribution of a multi-dimensional data set through a compact and accurate histogram synopsis is a fundamental problem arising in numerous practical scenarios, including query optimization and approximate query answering. Existing solutions either rely on simplistic independence assumptions or try to directly approximate the full joint data distribution over the complete set of attributes. Unfortunately, both approaches are doomed to fail for high-dimensional data sets with complex correlation patterns between attributes. In this paper, we propose a novel approach to histogram-based synopses that employs the solid foundation of statistical interaction models to explicitly identify and exploit the statistical characteristics of the data. Abstractly, our key idea is to break the synopsis into (1) a statistical interaction model that accurately captures significant correlation and independence patterns in data, and (2) a collection of histograms on low-dimensional marginals that, based on the model, can provide accurate approximations of the overall joint data distribution. Extensive experimental results with several real-life data sets verify the effectiveness of our approach. An important aspect of our general, model-based methodology is that it can be used to enhance the performance of other synopsis techniques that are based on data-space partitioning (e.g., wavelets) by providing an effective tool to deal with the “dimensionality curse”.
Dynamic buffer allocation in video-on-demand systems
Authors: Lee Sang-Ho , Whang Kyu-Young , Moon Yang-Sae , Song Il-Yeol
Published: November 2005

In video-on-demand (VOD) systems, as the size of the buffer allocated to user requests increases, initial latency and memory requirements increase. Hence, the buffer size must be minimized. The existing static buffer allocation scheme, however, determines the buffer size based on the assumption that the system is in the fully loaded state. Thus, when the system is in a partially loaded state, the scheme allocates a buffer larger than necessary to a user request. This paper proposes a dynamic buffer allocation scheme that allocates to user requests buffers of the minimum size in a partially loaded state as well as in the fully loaded state. The inherent difficulty in determining the buffer size in the dynamic buffer allocation scheme is that the size of the buffer currently being allocated is dependent on the number of and the sizes of the buffers to be allocated in the next service period. We solve this problem by the
predict-and-enforce strategy
, where we predict the number and the sizes of future buffers based on
inertia assumptions
and enforce these assumptions at runtime. Any violation of these assumptions is resolved by deferring service to the violating new user request until the assumptions are satisfied. Since the size of the current buffer is dependent on the sizes of the future buffers, the size is represented by a recurrence equation. We provide a solution to this equation, which can be computed at the system initialization time for runtime efficiency. We have performed extensive analysis and simulation. The results show that the dynamic buffer allocation scheme reduces initial latency (averaged over the number of user requests in service from one to the maximum capacity) to 1 ÷ 29.4 ≁ 1 ÷ 11.0 of that for the static one and, by reducing the memory requirement, increases the number of concurrent user requests to 2.36 ∼ 3.25 times that of the static one when averaged over the amount of system memory available. These results demonstrate that the dynamic buffer allocation scheme significantly improves the performance and capacity of VOD systems.
Updating XML
Authors: Tatarinov Igor , Ives Zachary G. , Halevy Alon Y. , Weld Daniel S.
Published: November 2005

As XML has developed over the past few years, its role has expanded beyond its original domain as a semantics-preserving markup language for online documents, and it is now also the
de facto
format for interchanging data between heterogeneous systems. Data sources expert XML “views” over their data, and other system can directly import or query these views. As a result, there has been great interest in languages and systems for expressing queries over XML data, whether the XML is stored in a repository or generated as a view over some other data storage format.

Clearly, in order to fully evolve XML into a universal data representation and sharing format, we must allow users to specify updates to XML documents and must develop techniques to process them efficiently. Update capabilities are important not only for modifying XML documents, but also for propagating changes through XML view and for expressing and transmitting changes to documents. This paper begins by proposing a set of basic update operations for both ordered and unordered XML data. We next describe extensions to the proposed standard XML query language, XQuery, to incorporate the update operations. We then consider alternative methods for implementing update operations when the XML data is mapped into a relational database. Finally, we describe an experimental evaluation of the alternative techniques for implementing our extensions.