bluuebunny/crossref_metadata_2025 huggingface dataset:
An array-based algorithm for simultaneous multidimensional aggregates
Authors: Zhao Yihong , Deshpande Prasad M. , Naughton Jeffrey F.
Published: November 2005

Computing multiple related group-bys and aggregates is one of the core operations of On-Line Analytical Processing (OLAP) applications. Recently, Gray et al. [GBLP95] proposed the “Cube” operator, which computes group-by aggregations over all possible subsets of the specified dimensions. The rapid acceptance of the importance of this operator has led to a variant of the Cube being proposed for the SQL standard. Several efficient algorithms for Relational OLAP (ROLAP) have been developed to compute the Cube. However, to our knowledge there is nothing in the literature on how to compute the Cube for Multidimensional OLAP (MOLAP) systems, which store their data in sparse arrays rather than in tables. In this paper, we present a MOLAP algorithm to compute the Cube, and compare it to a leading ROLAP algorithm. The comparison between the two is interesting, since although they are computing the same function, one is value-based (the ROLAP algorithm) whereas the other is position-based (the MOLAP algorithm). Our tests show that, given appropriate compression techniques, the MOLAP algorithm is significantly faster than the ROLAP algorithm. In fact, the difference is so pronounced that this MOLAP algorithm may be useful for ROLAP systems as well as MOLAP systems, since in many cases, instead of cubing a table directly, it is faster to first convert the table to an array, cube the array, then convert the result back to a table.
Beyond market baskets
Authors: Brin Sergey , Motwani Rajeev , Silverstein Craig
Published: November 2005

One of the most well-studied problems in data mining is mining for association rules in market basket data. Association rules, whose significance is measured via support and confidence, are intended to identify rules of the type, “A customer purchasing item A often also purchases item B.” Motivated by the goal of generalizing beyond market baskets and the association rules used with them, we develop the notion of mining rules that identify correlations (generalizing associations), and we consider both the absence and presence of items as a basis for generating rules. We propose measuring significance of associations via the chi-squared test for correlation from classical statistics. This leads to a measure that is upward closed in the itemset lattice, enabling us to reduce the mining problem to the search for a border between correlated and uncorrelated itemsets in the lattice. We develop pruning strategies and devise an efficient algorithm for the resulting problem. We demonstrate its effectiveness by testing it on census data and finding term dependence in a corpus of text documents, as well as on synthetic data.
Scalable parallel data mining for association rules
Authors: Han Eui-Hong , Karypis George , Kumar Vipin
Published: November 2005

One of the important problems in data mining is discovering association rules from databases of transactions where each transaction consists of a set of items. The most time consuming operation in this discovery process is the computation of the frequency of the occurrences of interesting subset of items (called candidates) in the database of transactions. To prune the exponentially large space of candidates, most existing algorithms, consider only those candidates that have a user defined minimum support. Even with the pruning, the task of finding all association rules requires a lot of computation power and time. Parallel computers offer a potential solution to the computation requirement of this task, provided efficient and scalable parallel algorithms can be designed. In this paper, we present two new parallel algorithms for mining association rules. The
Intelligent Data Distribution
algorithm efficiently uses aggregate memory of the parallel computer by employing intelligent candidate partitioning scheme and uses efficient communication mechanism to move data among the processors. The
Hybrid Distribution
algorithm further improves upon the
Intelligent Data Distribution
algorithm by dynamically partitioning the candidate set to maintain good load balance. The experimental results on a Cray T3D parallel computer show that the
Hybrid Distribution
algorithm scales linearly and exploits the aggregate memory better and can generate more association rules with a single scan of database per pass.
A toolkit for negotiation support interfaces to multi-dimensional data
Authors: Gebhardt Michael , Jarke Matthias , Jacobs Stephan
Published: November 2005

CoDecide is an experimental user interface toolkit that offers an extension to spreadsheet concepts specifically geared towards support for cooperative analysis of the kinds of multi-dimensional data encountered in data warehousing. It is distinguished from previous proposals by direct support for drill-down/roll-up analysis without redesign of an interface; more importantly, CoDecide can link multiple views on a data cube for synchronous or asynchronoous cooperation by multiple analysts, through a conceptual model visualizing the problem dimensions on so-called tapes. Tapes generalize the ideas of ranging and pivoting in current data warehouses for the multi-perspective and multi-user case. CoDecide allows the rapid composition of multi-matrix interfaces and their linkage to underlying data sources. A LAN version of CoDecide has been used in a number of design decision support applications. A WWW version representing externally materialized views on databases is currently under development.
Efficient view maintenance at data warehouses
Authors: Agrawal D. , El Abbadi A. , Singh A. , Yurek T.
Published: November 2005

We present incremental view maintenance algorithms for a data warehouse derived from multiple distributed autonomous data sources. We begin with a detailed framework for analyzing view maintenance algorithms for multiple data sources with concurrent updates. Earlier approaches for view maintenance in the presence of concurrent updates typically require two types of messages: one to compute the view change due to the initial update and the other to compensate the view change due to interfering concurrent updates. The algorithms developed in this paper instead perform the compensation locally by using the information that is already available at the data warehouse. The first algorithm, termed SWEEP, ensures complete consistency of the view at the data warehouse in the presence of concurrent updates. Previous algorithms for incremental view maintenance either required a quiescent state at the data warehouse or required an exponential number of messages in terms of the data sources. In contrast, this algorithm does not require that the data warehouse be in a quiescent state for incorporating the new views and also the message complexity is linear in the number of data sources. The second algorithm, termed Nested SWEEP, attempts to compute a composite view change for multiple updates that occur concurrently while maintaining strong consistency.
Eliminating costly redundant computations from SQL trigger executions
Authors: Llirbat François , Fabret Françoise , Simon Eric
Published: November 2005

Active database systems are now in widespread use. The use of triggers in these systems, however, is difficult because of the complex interaction between triggers, transactions, and application programs. Repeated calculations of rules may incur costly redundant computations in rule conditions and actions. In this paper, we focus on active relational database systems supporting SQL triggers. In this context, we provide a powerful and complete solution to eliminate redundant computations of SQL triggers when they are costly. We define a model to describe programs, rules and their interactions. We provide algorithms to extract invariant subqueries from trigger's condition and action. We define heuristics to memorize the most “profitable” invariants. Finally, we develop a rewriting technique that enables to generate and execute the optimized code of SQL triggers.
Temporal aggregation in active database rules
Authors: Motakis Iakovos , Zaniolo Carlo
Published: November 2005

An important feature of many advanced active database prototypes is support for rules triggered by complex patterns of events. Their composite event languages provide powerful primitives for event-based temporal reasoning. In fact, with one important exception, their expressive power matches and surpasses that of sophisticated languages offered by Time Series Management Systems (TSMS), which have been extensively used for temporal data analysis and knowledge discovery. This exception pertains to temporal aggregation, for which, current active database systems offer only minimal support, if any.

In this paper, we introduce the language TREPL, which addresses this problem. The TREPL prototype, under development at UCLA, offers primitives for temporal aggregation that exceed the capabilities of state-of-the-art composite event languages, and are comparable to those of TSMS languages. TREPL also demonstrates a rigorous and general approach to the definition of composite event language semantics. The meaning of a TREPL rule is formally defined by mapping it into a set of
Datalog

1
S

rules, whose logic-based semantics characterizes the behavior of the original rule. This approach handles naturally temporal aggregates, including user-defined ones, and is also applicable to other composite event languages, such as ODE, Snoop and SAMOS.
Secure transaction processing in firm real-time database systems
Authors: George Binto , Haritsa Jayant
Published: November 2005

Many real-time database applications arise in safety-critical installations and military systems where enforcing security is crucial to the success of the enterprise. A secure real-time database system has to simultaneously satisfy who requirements guarantee data security and minimize the number of missed transaction deadlines. We investigate here the performance implications, in terms of missed deadlines, of guaranteeing security in a real-time database system. In particular, we focus on the
concurrency control
aspects of this issue.

Our main contributions are the following: First, we identify which among the previously proposed real-time concurrency control protocols are capable of providing protection against both direct and indirect (covert channels) means of unauthorized access to data. Second, using a detailed simulation model of a firm-deadline real-time database system, we profile the real-time performance of a representative set of these secure concurrency control protocols. Our experiments show that a prioritized optimistic concurrency control protocol. OPT-WAIT, provides the best overall performance. Third, we propose and evaluate a novel
dual
approach to secure transaction concurrency control that allows the real-time database system to
simultaneously
use different concurrency control mechanisms for guaranteeing security and for improving real-time performance. By appropriately choosing these different mechanisms, we have been able to design
hybrid
concurrency control algorithms that provide even better performance than OPT-WAIT.
MDM
Authors: Atzeni Paolo , Torlone Riccardo
Published: November 2005

MDM is a tool that enables the users to define schemes of different data models and to perform translations of schemes from one model to another. These functionalities can be at the basis of a customizable and integrated CASE environment supporting the analysis and design of information systems. MDM has two main components: the
Model Manager
and the
Schema Manager
. The Model Manager supports a specialized user, the
model engineer
, in the definition of a variety of models, on the basis of a limited set of
metaconstructs
covering almost all known conceptual models. The Schema Manager allows designers to create and modify schemes over the defined models, and to generate at each time a translation of a scheme into any of the data models currently available. Translations between models are automatically derived, at definition time, by combining a predefined set of elementary transformations, which implement the standard translations between simple combinations of constructs.
OGDI
Authors: Clément Gilles , Larouche Christian , Gouin Denis , Morin Paul , Kucera Henry
Published: November 2005

The growth of the geomatics industry is stunted by the difficulty of obtaining and transforming suitable spatial data. This paper describes a remedy: the Open Geospatial Datastore Interface (OGDI), which permits application software to access a variety of spatial data products. The discussion compares the OGDI approach to other standards efforts and describes the characteristics and use of OGDI, which is in the public domain.
Treating non-compatibility problem from matter element analysis to extenics
Authors: Ng David K. W. , Cai Wen
Published: November 2005

Cai Wen's land mark article "Extension Set and Non-compatible Problems" was published in 1983, and thus proclaimed the birth of extenics. Its objectives were to study contradictory (non-compromising and non-compatible) problems in the real world. Its theoretical foundations are matter element theory and extension set theory. Extension control, extension information, extension system, extension logic,
etc.
, are part of this theoretical system. Its practical methodology includes extension engineering methods which further includes the concepts of extension characteristic analysis, transforming bridge, extension cognition, extension decision, extension forecast,
etc.
Basically, the theoretical system and the practical methodology of extenics are introduced in this article.
Management of semistructured data
Authors: Suciu Dan
Published: November 2005

A huge amount of data is available today on the Internet, or on the private Intranets of many companies. This data is structured in a multitude of ways. At an extreme we find data coming from traditional relational or object-oriented databases, with a completely known structure. At another extreme we have data which is fully unstructured, such as images, sounds, and raw text. But most of the data falls somewhere in between these two extremes, for a variety of reasons: the data may be structured, but the structure is not know to the user; the user may know the structure, but chooses to ignore it, for browsing purposes; the structure may be implicit, such as in formatted text, and is not as rigid and regular as in traditional databases; the data may be in non-traditional formats, such as the ASN.1 exchange format; the schema of the data is huge and changes often, so that we may prefer to ignore it. Several researchers have worked recently on problems related to data fitting this description, and have coined the term
semistructured data
for it. Two recent tutorials [Abi97, Bun97] contain an excellent introduction to semistructured data and a comprehensive bibliography on this new research topic.
Research issues in federated database systems
Authors: Conrad S. , Eaglestone B. , Hasselbring W. , Roantree M. , Schöhoff M. , Strässler M. , Vermeer M. , Saltor F.
Published: November 2005

In June 1997, an international workshop on engineering of federated database systems has been held in Barcelona in conjunction with the 9th Conference on Advanced Information Systems Engineering (CAiSE'97). This paper reports on the results of this workshop and summarises the identified open issues for future research in this area
.
The five-minute rule ten years later, and other computer storage rules of thumb
Authors: Gray Jim , Graefe Goetz
Published: November 2005

Simple economic and performance arguments suggest appropriate lifetimes for main memory pages and suggest optimal page sizes. The fundamental tradeoffs are the prices and bandwidths of RAMs and disks. The analysis indicates that with today's technology, five minutes is a good lifetime for randomly accessed pages, one minute is a good lifetime for two-pass sequentially accessed pages, and 16 KB is a good size for index pages. These rules-of-thumb change in predictable ways as technology ratios change. They also motivate the importance of the new
Kaps, Maps, Scans
, and
$/Kaps, $/Maps, $/TBscan
metrics.
The database and information system research group at the University of ULM
Authors: Dadam Peter , Klas Wolfgang
Published: November 2005

The University of Ulm was founded in 1967 with focus on medicine and natural sciences. In 1989 the University established two new faculties: Engineering Sciences and Computer Science. This enlargement took place within the framework of the so-called
Science City Ulm
. In a joint effort, the State of Baden-Württemberg, industrial companies, the University, and the City of Ulm successfully established a research and development infrastructure at or nearby the university campus consisting of the university's research labs, university-related research institutes like the Research Institute for Applied Knowledge Processing (FAW), and industrial research and development labs, especially a large research center of Daimler-Benz AG.

Today, the Faculty of Computer Science consists of seven divisions (called 'departments'), each of which equipped with two professor positions:

Theoretical Computer Science

Artificial Intelligence

Distributed Systems

Databases and Information Systems

Software Technology and Compiler Construction

Computer Structures

Neural Information Processing.

The Dept. of Databases and Information Systems (DBIS) became operational at the beginning of 1990 when Peter Dadam joined the faculty. He came from the IBM Heidelberg Science Center (HDSC) where he managed the research department for
Advanced Information Management
(AIM). At the HDSC he was working on advanced database technology and applications and contributed to the development of the AIM-P system (see [1]). The second professor position was first occupied by Marc Scholl, who belonged to the DBIS department from 1992 to 1994. In 1996 Wolfgang Klas joined the DBIS department as second professor. He came from the GMD Institute for Integrated Publication and Information Systems (IPSI) where he managed the research division
Distributed Multimedia Information Systems
and was working on advanced object-oriented database systems technology, interoperable database systems, and multimedia information systems.

At present, the DBIS team consists of the teaching and research assistants Thomas Bauer, Susanne Boll, Christian Heinlein, Clemens Hensinger, Erich Müller, Manfred Reichert, Birgit Schultheiβ, the system engineer Rudi Seifert, the secretary Christiane Köppl, and the doctoral students Thomas Beuter and Anita Krämer.

In the following, we concentrate on the research and development work performed previously and presently in the research groups of Peter Dadam and of Wolfgang Klas. For references to Marc Scholl's work please visit http://www.informatik.uni-konstanz.de/dbis.
PREDATOR
Authors: Seshadri Praveen
Published: November 2005

This paper describes PREDATOR, a freely available object-relational database system that has been developed at Cornell University. A major motivation in developing PREDATOR was to create a modern code base that could act as a research vehicle for the database community. Pursuing this goal, this paper briefly describes several features of the system that should make it attractive for database research and education.
Mining fuzzy association rules in databases
Authors: Kuok Chan Man , Fu Ada , Wong Man Hon
Published: November 2005

Data mining is the discovery of previously unknown, potentially useful and hidden knowledge in databases. In this paper, we concentrate on the discovery of association rules. Many algorithms have been proposed to find association rules in databases with binary attributes. We introduce the fuzzy association rules of the form, 'If
X
is
A
then
Y
is
B
', to deal with quantitative attributes.
X, Y
are set of attributes and
A, B
are fuzzy sets which describe
X
and
Y
respectively. Using the fuzzy set concept, the discovered rules are more understandable to human. Moreover, fuzzy sets handle numerical values better than existing methods because fuzzy sets soften the effect of sharp boundaries.
An extensible notation for spatiotemporal index queries
Authors: Tsotras Vassilis J. , Jensen Christian S. , Snodgrass Richard Thomas
Published: November 2005

Temporal, spatial and spatiotemporal queries are inherently multidimensional, combining predicates on explicit attributes with predicates on time dimension(s) and spatial dimension(s). Much confusion has prevailed in the literature on access methods because no consistent notation exists for referring to such queries. As a contribution towards eliminating this problem, we propose a new and simple notation for spatiotemporal queries. The notation aims to address the selection-based spatiotemporal queries commonly studied in the literature of access methods. The notation is extensible and can be applied to more general multidimensional, selection-based queries.
Towards a richer Web object model
Authors: Manola Frank
Published: November 2005

The World Wide Web is becoming an increasingly important factor in planning for enterprise distributed computing environments, both to support external access to enterprise systems and information (e.g., by customers, suppliers, and partners), and to support internal enterprise operations. Organizations perceive a number of advantages in using the Web in enterprise computing, a particular advantage being that it provides an information representation which• supports interlinking of all kinds of content• is easy for end-users to access• supports easy content creation using widely-available toolsHowever, as organizations have attempted to employ the Web in increasingly sophisticated applications, these applications have begun to overlap in complexity the sorts of distributed applications for which distributed object architectures such as OMG's CORBA, and its surrounding Object Management Architecture (OMA) [Sol95] were originally developed. Since the Web was not originally designed to support such applications, Web application development efforts increasingly run into limitations of the basic Web infrastructure.If the Web is to be used as the basis of complex enterprise applications, it must provide generic capabilities similar to those provided by the OMA (although these may need to be adapted to the more open, flexible nature of the Web, and specific requirements of Web applications). This involves such things as providing database-like services (such as enhanced query and transaction support) and their composition in the Web. However, the basic data structuring capabilities provided by the Web (its "object model") must also be addressed, since the ability to define and apply powerful generic services in the Web, and the ability to generally use the Web to support complex applications, depends crucially on the ability of the Web's underlying data structuring facilities to support these complex applications and services.
Repositories and object oriented databases
Authors: Bernstein Philip A.
Published: November 2005

A repository is a shared database of information about engineered artifacts. An object-oriented repository has many of the same features as an object-oriented database: properties, relationships, and versioning. However, the two technologies are different for two reasons. First, a repository system has built-in information models, which are database schemas or object models that cover both generic and tool-specific kinds of information. Second, the features of a repository are often more functional than similar features supported by object-oriented databases. This paper is primarily a survey of the latter features, drawing attention to capabilities that distinguish repositories from object-oriented databases.
PC note
Authors: Styer Eugene
Published: November 2005

Since this will be the last article in the PC Notes series, the topics will be rather wide-ranging. The items include sound, serial ports (including modems and mice), parallel ports, and the keyboard.
Query flocks
Authors: Tsur Dick , Ullman Jeffrey D. , Abiteboul Serge , Clifton Chris , Motwani Rajeev , Nestorov Svetlozar , Rosenthal Arnon
Published: November 2005

Association-rule mining has proved a highly successful technique for extracting useful information from very large databases. This success is attributed not only to the appropriateness of the objectives, but to the fact that a number of new query-optimization ideas, such as the “a-priori” trick, make association-rule mining run much faster than might be expected. In this paper we see that the same tricks can be extended to a much more general context, allowing efficient mining of very large databases for many different kinds of patterns. The general idea, called “query flocks,” is a generate-and-test model for data-mining problems. We show how the idea can be used either in a general-purpose mining system or in a next generation of conventional query optimizers.
Exploratory mining and pruning optimizations of constrained associations rules
Authors: Ng Raymond T. , Lakshmanan Laks V. S. , Han Jiawei , Pang Alex
Published: November 2005

From the standpoint of supporting human-centered discovery of knowledge, the present-day model of mining association rules suffers from the following serious shortcomings: (i) lack of user exploration and control, (ii) lack of focus, and (iii) rigid notion of relationships. In effect, this model functions as a black-box, admitting little user interaction in between. We propose, in this paper, an architecture that opens up the black-box, and supports constraint-based, human-centered exploratory mining of associations. The foundation of this architecture is a rich set of constraint constructs, including domain, class, and SQL-style aggregate constraints, which enable users to clearly specify what associations are to be mined. We propose
constrained association queries
as a means of specifying the constraints to be satisfied by the antecedent and consequent of a mined association.

In this paper, we mainly focus on the technical challenges in guaranteeing a level of performance that is commensurate with the selectivities of the constraints in an association query. To this end, we introduce and analyze two properties of constraints that are critical to pruning:
anti-monotonicity
and
succinctness
. We then develop characterizations of various constraints into four categories, according to these properties. Finally, we describe a mining algorithm called CAP, which achieves a maximized degree of pruning for all categories of constraints. Experimental results indicate that CAP can run much faster, in some cases as much as 80 times, than several basic algorithms. This demonstrates how important the succinctness and anti-monotonicity properties are, in delivering the performance guarantee.
Query unnesting in object-oriented databases
Authors: Fegaras Leonidas
Published: November 2005

There is already a sizable body of proposals on OODB query optimization. One of the most challenging problems in this area is query unnesting, where the embedded query can take any form, including aggregation and universal quantification. Although there is already a number of proposed techniques for query unnesting, most of these techniques are applicable to only few cases. We believe that the lack of a general and simple solution to the query unnesting problem is due to the lack of a uniform algebra that treats all operations (including aggregation and quantification) in the same way.

This paper presents a new query unnesting algorithm that generalizes many unnesting techniques proposed recently in the literature. Our system is capable of removing
any
form of query nesting using a very simple and efficient algorithm. The simplicity of the system is due to the use of the monoid comprehension calculus as an intermediate form for OODB queries. The monoid comphrehension calculus treats operations over multiple collection types, aggregates, and quantifiers in a similar way, resulting in a uniform way of unnesting queries, regardless of their type of nesting.
Automatic subspace clustering of high dimensional data for data mining applications
Authors: Agrawal Rakesh , Gehrke Johannes , Gunopulos Dimitrios , Raghavan Prabhakar
Published: November 2005

Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records. We present CLIQUE, a clustering algorithm that satisfies each of these requirements. CLIQUE identifies dense clusters in subspaces of maximum dimensionality. It generates cluster descriptions in the form of DNF expressions that are minimized for ease of comprehension. It produces identical results irrespective of the order in which input records are presented and does not presume any specific mathematical form for data distribution. Through experiments, we show that CLIQUE efficiently finds accurate cluster in large high dimensional datasets.
Efficient mid-query re-optimization of sub-optimal query execution plans
Authors: Kabra Navin , DeWitt David J.
Published: November 2005

For a number of reasons, even the best query optimizers can very often produce sub-optimal query execution plans, leading to a significant degradation of performance. This is especially true in databases used for complex decision support queries and/or object-relational databases. In this paper, we describe an algorithm that detects sub-optimality of a query execution plan during query execution and attempts to correct the problem. The basic idea is to collect statistics at key points during the execution of a complex query. These statistics are then used to optimize the execution of the query, either by improving the resource allocation for that query, or by changing the execution plan for the remainder of the query. To ensure that this does not significantly slow down the normal execution of a query, the Query Optimizer carefully chooses what statistics to collect, when to collect them, and the circumstances under which to re-optimize the query. We describe an implementation of this algorithm in the Paradise Database System, and we report on performance studies, which indicate that this can result in significant improvements in the performance of complex queries.
The pyramid-technique
Authors: Berchtold Stefan , Böhm Christian , Kriegal Hans-Peter
Published: November 2005

In this paper, we propose the Pyramid-Technique, a new indexing method for high-dimensional data spaces. The Pyramid-Technique is highly adapted to range query processing using the maximum metric L
max
. In contrast to all other index structures, the performance of the Pyramid-Technique does not deteriorate when processing range queries on data of higher dimensionality. The Pyramid-Technique is based on a special partitioning strategy which is optimized for high-dimensional data. The basic idea is to divide the data space first into 2d pyramids sharing the center point of the space as a top. In a second step, the single pyramids are cut into slices parallel to the basis of the pyramid. These slices from the data pages. Furthermore, we show that this partition provides a mapping from the given d-dimensional space to a 1-dimensional space. Therefore, we are able to use a B+-tree to manage the transformed data. As an analytical evaluation of our technique for hypercube range queries and uniform data distribution shows, the Pyramid-Technique clearly outperforms index structures using other partitioning strategies. To demonstrate the practical relevance of our technique, we experimentally compared the Pyramid-Technique with the X-tree, the Hilbert R-tree, and the Linear Scan. The results of our experiments using both, synthetic and real data, demonstrate that the Pyramid-Technique outperforms the X-tree and the Hilbert R-tree by a factor of up to 14 (number of page accesses) and up to 2500 (total elapsed time) for range queries.
Dimensionality reduction for similarity searching in dynamic databases
Authors: Ravi Kanth K. V. , Agrawal Divyakant , Singh Ambuj
Published: November 2005

Databases are increasingly being used to store multi-media objects such as maps, images, audio and video. Storage and retrieval of these objects is accomplished using multi-dimensional index structures such as R*-trees and SS-trees. As dimensionality increases, query performance in these index structures degrades. This phenomenon, generally referred to as the dimensionality curse, can be circumvented by reducing the dimensionality of the data. Such a reduction is however accompanied by a loss of precision of query results. Current techniques such as QBIC use SVD transform-based dimensionality reduction to ensure high query precision. The drawback of this approach is that SVD is expensive to compute, and therefore not readily applicable to dynamic databases. In this paper, we propose novel techniques for performing SVD-based dimensionality reduction in dynamic databases. When the data distribution changes considerably so as to degrade query precision, we recompute the SVD transform and incorporate it in the existing index structure. For recomputing the SVD-transform, we propose a novel technique that uses
aggregate
data from the existing index rather than the entire data. This technique reduces the SVD-computation time without compromising query precision. We then explore efficient ways to incorporate the recomputed SVD-transform in the existing index structure without degrading subsequent query response times. These techniques reduce the computation time by a factor of 20 in experiments on color and texture image vectors. The error due to approximate computation of SVD is less than 10%.
Using schematically heterogeneous structures
Authors: Miller Reée J.
Published: November 2005

Schematic heterogeneity arises when information that is represented as data under one schema, is represented within the schema (as metadata) in another. Schematic heterogeneity is an important class of heterogeneity that arises frequently in integrating legacy data in federated or data warehousing applications. Traditional query languages and view mechanisms are insufficient for reconciling and translating data between schematically heterogeneous schemas. Higher order query languages, that permit quantification over schema labels, have been proposed to permit querying and restructuring of data between schematically disparate schemas. We extend this work by considering how these languages can be used in practice. Specifically, we consider a restricted class of higher order views and show the power of these views in integrating legacy structures. Our results provide insights into the properties of restructuring transformations required to resolve schematic discrepancies. In addition, we show how the use of these views permits schema browsing and new forms of data independence that are important for global information systems. Furthermore, these views provide a framework for integrating semi-structured and unstructured queries, such as keyword searches, into a structured querying environment. We show how these views can be used with minimal extensions to existing query engines. We give conditions under which a higher order view is usable for answering a query and provide query translation algorithms.
The DEDALE system for complex spatial queries
Authors: Grumbach Stéphane , Rigaux Philippe , Segoufin Luc
Published: November 2005

This paper presents DEDALE, a spatial database system intended to overcome some limitations of current systems by providing an abstract and non-specialized data model and query language for the representation and manipulation of spatial objects. DEDALE relies on a logical model based on linear constraints, which generalizes the constraint database model of [KKR90]. While in the classical constraint model, spatial data is always decomposed into its convex components, in DEDALE holes are allowed to fit the need of practical applications. The logical representation of spatial data although slightly more costly in memory, has the advantage of simplifying the algorithms. DEDALE relies on nested relations, in which all sorts of data (thematic, spatial, etc.) are stored in a uniform fashion. This new data model supports declarative query languages, which allow an intuitive and efficient manipulation of spatial objects. Their formal foundation constitutes a basis for practical query optimization. We describe several evaluation rules tailored for geometric data and give the specification of an optimizer module for spatial queries. Except for the latter module, the system has been fully implemented upon the O
2
DBMS, thus proving the effectiveness of a constraint-based approach for the design of spatial database systems.
Similarity query processing using disk arrays
Authors: Papadopoulos Apostolos N. , Manolopoulos Yannis
Published: November 2005

Similarity queries are fundamental operations that are used extensively in many modern applications, whereas disk arrays are powerful storage media of increasing importance. The basic trade-off in similarity query processing in such a system is that increased parallelism leads to higher resource consumptions and low throughput, whereas low parallelism leads to higher response times. Here, we propose a technique which is based on a careful investigation of the currently available data in order to exploit parallelism up to a point, retaining low response times during query processing. The underlying access method is a variation of the R*-tree, which is distributed among the components of a disk array, whereas the system is simulated using event-driven simulation. The performance results conducted, demonstrate that the proposed approach outperforms by factors a previous branch-and-bound algorithm and a greedy algorithm which maximizes parallelism as much as possible. Moreover, the comparison of the proposed algorithm to a hypothetical (non-existing) optimal one (with respect to the number of disk accesses) shows that the former is on average two times slower than the latter.
Caching multidimensional queries using chunks
Authors: Deshpande Prasad M. , Ramasamy Karthikeyan , Shukla Amit , Naughton Jeffrey F.
Published: November 2005

Caching has been proposed (and implemented) by OLAP systems in order to reduce response times for multidimensional queries. Previous work on such caching has considered table level caching and query level caching. Table level caching is more suitable for static schemes. On the other hand, query level caching can be used in dynamic schemes, but is too coarse for “large” query results. Query level caching has the further drawback for small query results in that it is only effective when a new query is subsumed by a previously cached query. In this paper, we propose caching small regions of the multidimensional space called
“chunks”
. Chunk-based caching allows fine granularity caching, and allows queries to partially reuse the results of previous queries with which they overlap. To facilitate the computation of chunks required by a query but missing from the cache, we propose a new organization for relational tables, which we call a “chunked file.” Our experiments show that for workloads that exhibit query locality, chunked caching combined with the chunked file organization performs better than query level caching. An unexpected benefit of the chunked file organization is that, due to its multidimensional clustering properties, it can significantly improve the performance of queries that “miss” the cache entirely as compared to traditional file organizations.
Simultaneous optimization and evaluation of multiple dimensional queries
Authors: Zhao Yihong , Deshpande Prasad M. , Naughton Jeffrey F. , Shukla Amit
Published: November 2005

Database researchers have made significant progress on several research issues related to multidimensional data analysis, including the development of fast cubing algorithms, efficient schemes for creating and maintaining precomputed group-bys, and the design of efficient storage structures for multidimensional data. However, to date there has been little or no work on multidimensional query optimization. Recently, Microsoft has proposed “OLE DB for OLAP” as a standard multidimensional interface for databases. OLE DB for OLAP defines Multi-Dimensional Expressions (MDX), which have the interesting and challenging feature of allowing clients to ask several related dimensional queries in a single MDX expression. In this paper, we present three algorithms to optimize multiple related dimensional queries. Two of the algorithms focus on how to generate a global plan from several related local plans. The third algorithm focuses on generating a good global plan without first generating local plans. We also present three new query evaluation primitives that allow related query plans to share portions of their evaluation. Our initial performance results suggest that the exploitation of common subtask evaluation and global optimization can yield substantial performance improvements when relational database systems are used as data sources for multidimensional analysis.
Enhanced hypertext categorization using hyperlinks
Authors: Chakrabarti Soumen , Dom Byron , Indyk Piotr
Published: November 2005

A major challenge in indexing unstructured hypertext databases is to automatically extract meta-data that enables structured search using topic taxonomies, circumvents keyword ambiguity, and improves the quality of search and profile-based routing and filtering. Therefore, an accurate classifier is an essential component of a hypertext database. Hyperlinks pose new problems not addressed in the extensive text classification literature. Links clearly contain high-quality semantic clues that are lost upon a purely term-based classifier, but exploiting link information is non-trivial because it is noisy. Naive use of terms in the link neighborhood of a document can even
degrade
accuracy. Our contribution is to propose robust statistical models and a
relaxation labeling
technique for better classification by exploiting link information in a small neighborhood around documents. Our technique also adapts gracefully to the fraction of neighboring documents having known topics. We experimented with pre-classified samples from Yahoo!
1
and the US Patent Database
2
. In previous work, we developed a text classifier that misclassified only 13% of the documents in the well-known Reuters benchmark; this was comparable to the best results ever obtained. This classifier misclassified 36% of the patents, indicating that classifying hypertext can be more difficult than classifying text. Naively using terms in neighboring documents increased error to 38%; our hypertext classifier reduced it to 21%. Results with the Yahoo! sample were more dramatic: the text classifier showed 68% error, whereas our hypertext classifier reduced this to only 21%.
New sampling-based summary statistics for improving approximate query answers
Authors: Gibbons Phillip B. , Matias Yossi
Published: November 2005

In large data recording and warehousing environments, it is often advantageous to provide fast, approximate answers to queries, whenever possible. Before DBMSs providing highly-accurate approximate answers can become a reality, many new techniques for summarizing data and for estimating answers from summarized data must be developed. This paper introduces two new sampling-based summary statistics, concise samples and counting samples, and presents new techniques for their fast incremental maintenance regardless of the data distribution. We quantify their advantages over standard sample views in terms of the number of additional sample points for the same view size, and hence in providing more accurate query answers. Finally, we consider their application to providing fast approximate answers to hot list queries. Our algorithms maintain their accuracy in the presence of ongoing insertions to the data warehouse.
Catching the boat with Strudel
Authors: Fernández Mary , Florescu Daniela , Kang Jaewoo , Levy Alon , Suciu Dan
Published: November 2005

The Strudel system applies concepts from database management systems to the process of building Web sites. Strudel's key idea is separating the management of the site's data, the creation and management of the site's structure, and the visual presentation of the site's pages. First, the site builder creates a uniform model of all data available at the site. Second, the builder uses this model to declaratively define the Web site's structure by applying a “site-definition query” to the underlying data. The result of evaluating this query is a “site graph”, which represents both the site's content and structure. Third, the builder specifies the visual presentation of pages in Strudel's HTML-template language. The data model underlying Strudel is a semi-structured model of labeled directed graphs.

We describe Strudel's key characteristics, report on our experiences using Strudel, and present the technical problems that arose from our experience. We describe our experience constructing several Web sites with Strudel and discuss the impact of potential users' requirements on Strudel's design. We address two main questions: (1) when does a declarative specification of site structure provide significant benefits, and (2) what are the main advantages provided by the semi-structured data model.
Approximate medians and other quantiles in one pass and with limited memory
Authors: Manku Gurmeet Singh , Rajagopalan Sridhar , Lindsay Bruce G.
Published: November 2005

We present new algorithms for computing approximate quantiles of large datasets in a single pass. The approximation guarantees are explicit, and apply for arbitrary value distributions and arrival distributions of the dataset. The main memory requirements are smaller than those reported earlier by an order of magnitude.

We also discuss methods that couple the approximation algorithms with random sampling to further reduce memory requirements. With sampling, the approximation guarantees are explicit but probabilistic, i.e. they apply with respect to a (user controlled) confidence parameter.

We present the algorithms, their theoretical analysis and simulation results on different datasets.
Random sampling for histogram construction
Authors: Chaudhuri Surajit , Motwani Rajeev , Narasayya Vivek
Published: November 2005

Random sampling is a standard technique for constructing (approximate) histograms for query optimization. However, any real implementation in commercial products requires solving the hard problem of determining
“How much sampling is enough?”
We address this critical question in the context of equi-height histograms used in many commercial products, including Microsoft SQL Server. We introduce a
conservative
error metric capturing the intuition that for an approximate histogram to have low error, the error must be small in
all
regions of the histogram. We then present a result establishing an optimal bound on the amount of sampling required for pre-specified error bounds. We also describe an
adaptive page sampling
algorithm which achieves greater efficiency by using all values in a sampled page but adjusts the amount of sampling depending on clustering of values in pages. Next, we establish that the problem of estimating the number of distinct values is
provably difficult
, but propose a new error metric which has a reliable estimator and can still be exploited by query optimizers to influence the choice of execution plans. The algorithm for histogram construction was prototyped on Microsoft SQL Server 7.0 and we present experimental results showing that the adaptive algorithm accurately approximates the true histogram over different data distributions.