bluuebunny/crossref_metadata_2025 huggingface dataset:
Finding generalized projected clusters in high dimensional spaces
Authors: Aggarwal Charu C. , Yu Philip S.
Published: November 2005

High dimensional data has always been a challenge for clustering algorithms because of the inherent sparsity of the points. Recent research results indicate that in high dimensional data, even the concept of proximity or clustering may not be meaningful. We discuss very general techniques for projected clustering which are able to construct clusters in arbitrarily aligned subspaces of lower dimensionality. The subspaces are specific to the clusters themselves. This definition is substantially more general and realistic than currently available techniques which limit the method to only projections from the original set of attributes. The generalized projected clustering technique may also be viewed as a way of trying to redefine clustering for high dimensional applications by searching for hidden subspaces with clusters which are created by inter-attribute correlations. We provide a new concept of using extended cluster feature vectors in order to make the algorithm scalable for very large databases. The running time and space requirements of the algorithm are adjustable, and are likely ta tradeoff with better accuracy.
Density biased sampling
Authors: Palmer Christopher R. , Faloutsos Christos
Published: November 2005

Data mining in large data sets often requires a sampling or summarization step to form an in-core representation of the data that can be processed more efficiently. Uniform random sampling is frequently used in practice and also frequently criticized because it will miss small clusters. Many natural phenomena are known to follow Zipf's distribution and the inability of uniform sampling to find small clusters is of practical concern. Density Biased Sampling is proposed to probabilistically under-sample dense regions and over-sample light regions. A weighted sample is used to preserve the densities of the original data. Density biased sampling naturally includes uniform sampling as a special case. A memory efficient algorithm is proposed that approximates density biased sampling using only a single scan of the data. We empirically evaluate density biased sampling using synthetic data sets that exhibit varying cluster size distributions finding up to a factor of six improvement over uniform sampling.
Answering complex SQL queries using automatic summary tables
Authors: Zaharioudakis Markos , Cochrane Roberta , Lapis George , Pirahesh Hamid , Urata Monica
Published: November 2005

We investigate the problem of using materialized views to answer SQL queries. We focus on modern decision-support queries, which involve joins, arithmetic operations and other (possibly user-defined) functions, aggregation (often along multiple dimensions), and nested subqueries. Given the complexity of such queries, the vast amounts of data upon which they operate, and the requirement for interactive response times, the use of materialized views (MVs) of similar complexity is often mandatory for acceptable performance. We present a novel algorithm that is able to rewrite a user query so that it will access one or more of the available MVs instead of the base tables. The algorithm extends prior work by addressing the new sources of complexity mentioned above, that is, complex expressions, multidimensional aggregation, and nested subqueries. It does so by relying on a graphical representation of queries and a bottom-up, pair-wise matching of nodes from the query and MV graphs. This approach offers great modularity and extensibility, allowing for the rewriting of a large class of queries.
XTRACT
Authors: Garofalakis Minos , Gionis Aristides , Rastogi Rajeev , Seshadri S. , Shim Kyuseok
Published: November 2005

XML is rapidly emerging as the new standard for data representation and exchange on the Web. An XML document can be accompanied by a
Document Type Descriptor
(DTD) which plays the role of a schema for an XML data collection. DTDs contain valuable information on the structure of documents and thus have a crucial role in the efficient storage of XML data, as well as the effective formulation and optimization of XML queries. In this paper, we propose XTRACT, a novel system for inferring a DTD schema for a database of XML documents. Since the DTD syntax incorporates the full expressive power of
regular expressions
, naive approaches typically fail to produce concise and intuitive DTDs. Instead, the XTRACT inference algorithms employ a sequence of sophisticated steps that involve: (1) finding patterns in the input sequences and replacing them with regular expressions to generate “general” candidate DTDs, (2) factoring candidate DTDs using adaptations of algorithms from the logic optimization literature, and (3) applying the Minimum Description Length (MDL) principle to find the best DTD among the candidates. The results of our experiments with real-life and synthetic DTDs demonstrate the effectiveness of XTRACT's approach in inferring concise and semantically meaningful DTD schemas for XML databases.
MOCHA
Authors: Rodríguez-Martínez Manuel , Roussopoulos Nick
Published: November 2005

We present MOCHA, a new self-extensible database middleware system designed to interconnect distributed data sources. MOCHA is designed to scale to large environments and is based on the idea that some of the user-defined functionality in the system should be deployed by the middleware system itself. This is realized by shipping Java code implementing either advanced data types or tailored query operators to remote data sources and have it executed remotely. Optimized query plans push the evaluation of powerful
data-reducing
operators to the data source sites while executing
data-inflating
operators near the client's site. The Volume Reduction Factor is a new and more explicit metric introduced in this paper to select the best site to execute query operators and is shown to be more accurate than the standard selectivity factor alone. MOCHA has been implemented in Java and runs on top of Informix and Oracle. We present the architecture of MOCHA, the ideas behind it, and a performance study using scientific data and queries. The results of this study demonstrate that MOCHA provides a more flexible, scalable and efficient framework for distributed query processing compared to those in existing middleware solutions.
Closest pair queries in spatial databases
Authors: Corral Antonio , Manolopoulos Yannis , Theodoridis Yannis , Vassilakopoulos Michael
Published: November 2005

This paper addresses the problem of finding the K closest pairs between two spatial data sets, where each set is stored in a structure belonging in the R-tree family. Five different algorithms (four recursive and one iterative) are presented for solving this problem. The case of 1 closest pair is treated as a special case. An extensive study, based on experiments performed with synthetic as well as with real point data sets, is presented. A wide range of values for the basic parameters affecting the performance of the algorithms, especially the effect of overlap between the two data sets, is explored. Moreover, an algorithmic as well as an experimental comparison with existing incremental algorithms addressing the same problem is presented. In most settings, the new algorithms proposed clearly outperform the existing ones.
Towards self-tuning data placement in parallel database systems
Authors: Lee Mong Li , Kitsuregawa Masaru , Ooi Beng Chin , Tan Kian-Lee , Mondal Anirban
Published: November 2005

Parallel database systems are increasingly being deployed to support the performance demands of end-users. While declustering data across multiple nodes facilitates parallelism, initial data placement may not be optimal due to skewed workloads and changing access patterns. To prevent performance degradation, the placement of data must be reorganized, and this must be done on-line to minimize disruption to the system.

In this paper, we consider a dynamic self-tuning approach to reorganization in a shared nothing system. We introduce a new index-based method that faciliates fast and efficient migration of data. Our solution incorporates a globally height-balanced structure and load tracking at different levels of granularity. We conducted an extensive performance study, and implemented the methods on the Fujitsu AP3000 machine. Both the simulation and empirical results demonstratic that our proposed method is indeed scalable and effective in correcting any deterioration in system throughput.
Efficient and extensible algorithms for multi query optimization
Authors: Roy Prasan , Seshadri S. , Sudarshan S. , Bhobe Siddhesh
Published: November 2005

Complex queries are becoming commonplace, with the growing use of decision support systems. These complex queries often have a lot of common sub-expressions, either within a single query, or across multiple such queries run as a batch. Multiquery optimization aims at exploiting common sub-expressions to reduce evaluation cost. Multi-query optimization has hither-to been viewed as impractical, since earlier algorithms were exhaustive, and explore a doubly exponential search space.

In this paper we demonstrate that multi-query optimization using heuristics is practical, and provides significant benefits. We propose three cost-based heuristic algorithms: Volcano-SH and Volcano-RU, which are based on simple modifications to the Volcano search strategy, and a greedy heuristic. Our greedy heuristic incorporates novel optimizations that improve efficiency greatly. Our algorithms are designed to be easily added to existing optimizers. We present a performance study comparing the algorithms, using workloads consisting of queries from the TPC-D benchmark. The study shows that our algorithms provide significant benefits over traditional optimization, at a very acceptable overhead in optimization time.
Indexing the positions of continuously moving objects
Authors: Šaltenis Simonas , Jensen Christian S. , Leutenegger Scott T. , Lopez Mario A.
Published: November 2005

The coming years will witness dramatic advances in wireless communications as well as positioning technologies. As a result, tracking the changing positions of objects capable of continuous movement is becoming increasingly feasible and necessary. The present paper proposes a novel, R*-tree based indexing technique that supports the efficient querying of the current and projected future positions of such moving objects. The technique is capable of indexing objects moving in one-, two-, and three-dimensional space. Update algorithms enable the index to accommodate a dynamic data set, where objects may appear and disappear, and where changes occur in the anticipated positions of existing objects. A comprehensive performance study is reported.
Adaptive multi-stage distance join processing
Authors: Shin Hyoseop , Moon Bongki , Lee Sukho
Published: November 2005

A spatial distance join is a relatively new type of operation introduced for spatial and multimedia database applications. Additional requirements for ranking and stopping cardinality are often combined with the spatial distance join in on-line query processing or internet search environments. These requirements pose new challenges as well as opportunities for more efficient processing of spatial distance join queries. In this paper, we first present an efficient
k
-distance join algorithm that uses spatial indexes such as R-trees. Bi-directional node expansion and plane-sweeping techniques are used for fast pruning of distant pairs, and the plane-sweeping is further optimized by novel strategies for selecting a sweeping axis and direction. Furthermore, we propose adaptive multi-stage algorithms for
k
-distance join and incremental distance join operations. Our performance study shows that the proposed adaptive multi-stage algorithms outperform previous work by up to an order of magnitude for both
k
-distance join and incremental distance join queries, under various operational conditions.
Finding replicated Web collections
Authors: Cho Junghoo , Shivakumar Narayanan , Garcia-Molina Hector
Published: November 2005

Many web documents (such as JAVA FAQs) are being replicated on the Internet. Often entire document collections (such as hyperlinked Linux manuals) are being replicated many times. In this paper, we make the case for identifying replicated documents and collections to improve web crawlers, archivers, and ranking functions used in search engines. The paper describes how to efficiently identify replicated documents and hyperlinked document collections. The challenge is to identify these replicas from an input data set of several tens of millions of web pages and several hundreds of gigabytes of textual data. We also present two real-life case studies where we used replication information to improve a crawler and a search engine. We report these results for a data set of 25 million web pages (about 150 gigabytes of HTML data) crawled from the web.
WebView materialization
Authors: Labrinidis Alexandros , Roussopoulos Nick
Published: November 2005

A
WebView
is a web page automatically created from base data typically stored in a DBMS. Given the multi-tiered architecture behind database-backed web servers, we have the option of materializing a WebView inside the DBMS, at the web server, or not at all, always computing it on the fly (virtual). Since WebViews must be up to date, materialized WebViews are immediately refreshed with every update on the base data. In this paper we compare the three materialization policies (materialized inside the DBMS, materialized at the web server and virtual) analytically, through a detailed cost model, and quantitatively, through extensive experiments on an implemented system. Our results indicate that materializing at the web server is a more scalable solution and can facilitate an order of magnitude more users than the virtual and materialized inside the DBMS policies, even under high update workloads.
Privacy-preserving data mining
Authors: Agrawal Rakesh , Srikant Ramakrishnan
Published: November 2005

A fruitful direction for future data mining research will be the development of techniques that incorporate privacy concerns. Specifically, we address the following question. Since the primary task in data mining is the development of models about aggregated data, can we develop accurate models without access to precise information in individual data records? We consider the concrete case of building a decision-tree classifier from training data in which the values of individual records have been perturbed. The resulting data records look very different from the original records and the distribution of data values is also very different from the original distribution. While it is not possible to accurately estimate original values in individual data records, we propose a novel reconstruction procedure to accurately estimate the distribution of original data values. By using these reconstructed distributions, we are able to build classifiers whose accuracy is comparable to the accuracy of classifiers built with the original data.
Designing and mining multi-terabyte astronomy archives
Authors: Szalay Alexander S. , Kunszt Peter Z. , Thakar Ani , Gray Jim , Slutz Don , Brunner Robert J.
Published: November 2005

The next-generation astronomy digital archives will cover most of the sky at fine resolution in many wavelengths, from X-rays, through ultraviolet, optical, and infrared. The archives will be stored at diverse geographical locations. One of the first of these projects, the Sloan Digital Sky Survey (SDSS) is creating a 5-wavelength catalog over 10,000 square degrees of the sky (see http://www.sdss.org/). The 200 million objects in the multi-terabyte database will have mostly numerical attributes in a 100+ dimensional space. Points in this space have highly correlated distributions.

The archive will enable astronomers to explore the data interactively. Data access will be aided by multidimensional spatial and attribute indices. The data will be partitioned in many ways. Small
tag
objects consisting of the most popular attributes will accelerate frequent searches. Splitting the data among multiple servers will allow parallel, scalable I/O and parallel data analysis. Hashing techniques will allow efficient clustering, and pair-wise comparison algorithms that should parallelize nicely. Randomly sampled subsets will allow de-bugging otherwise large queries at the desktop. Central servers will operate a data pump to support sweep searches touching most of the data. The anticipated queries will require special operators related to angular distances and complex similarity tests of object properties, like shapes, colors, velocity vectors, or temporal behaviors. These issues pose interesting data management challenges.
Making B+- trees cache conscious in main memory
Authors: Rao Jun , Ross Kenneth A.
Published: November 2005

Previous research has shown that cache behavior is important for main memory index structures. Cache conscious index structures such as Cache Sensitive Search Trees (CSS-Trees) perform lookups much faster than binary search and T-Trees. However, CSS-Trees are designed for decision support workloads with relatively static data. Although B
+
-Trees are more cache conscious than binary search and T-Trees, their utilization of a cache line is low since half of the space is used to store child pointers. Nevertheless, for applications that require incremental updates, traditional B
+
-Trees perform well.

Our goal is to make B
+
-Trees as cache conscious as CSS-Trees without increasing their update cost too much. We propose a new indexing technique called “Cache Sensitive B
+
-Trees” (CSB
+
-Trees). It is a variant of B
+
-Trees that stores all the child nodes of any given node contiguously, and keeps only the address of the first child in each node. The rest of the children can be found by adding an offset to that address. Since only one child pointer is stored explicitly, the utilization of a cache line is high. CSB
+
-Trees support incremental updates in a way similar to B
+
-Trees.

We also introduce two variants of CSB
+
-Trees. Segmented CSB
+
-Trees divide the child nodes into segments. Nodes within the same segment are stored contiguously and only pointers to the beginning of each segment are stored explicitly in each node. Segmented CSB
+
-Trees can reduce the copying cost when there is a split since only one segment needs to be moved. Full CSB
+
-Trees preallocate space for the full node group and thus reduce the split cost. Our performance studies show that CSB
+
-Trees are useful for a wide range of applications.
Congressional samples for approximate answering of group-by queries
Authors: Acharya Swarup , Gibbons Phillip B. , Poosala Viswanath
Published: November 2005

In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex decision support queries using precomputed summary statistics, such as samples. Decision support queries routinely segment the data into groups and then aggregate the information in each group (
group-by
queries). Depending on the data, there can be a wide disparity between the number of data items in each group. As a result, approximate answers based on uniform random samples of the data can result in poor accuracy for groups with very few data items, since such groups will be represented in the sample by very few (often zero) tuples.

In this paper, we propose a general class of techniques for obtaining fast, highly-accurate answers for group-by queries. These techniques rely on precomputed non-uniform (biased) samples of the data. In particular, we propose
congressional samples
, a hybrid union of uniform and biased samples. Given a fixed amount of space, congressional samples seek to maximize the accuracy for all possible group-by queries on a set of columns. We present a one pass algorithm for constructing a congressional sample and use this technique to also incrementally maintain the sample up-to-date without accessing the base relation. We also evaluate query rewriting strategies for providing approximate answers from congressional samples. Finally, we conduct an extensive set of experiments on the TPC-D database, which demonstrates the efficacy of the techniques proposed.
Counting, enumerating, and sampling of execution plans in a cost-based query optimizer
Authors: Waas Florian , Galindo-Legaria César
Published: November 2005

Testing an SQL database system by running large sets of deterministic or stochastic SQL statements is common practice in commercial database development. However, code defects often remain undetected as the query optimizer's choice of an execution plan is not only depending on the query but strongly influenced by a large number of parameters describing the database and the hardware environment. Modifying these parameters in order to steer the optimizer to select other plans is difficult since this means anticipating often complex search strategies implemented in the optimizer.

In this paper we devise algorithms for counting, exhaustive generation, and uniform sampling of plans from the complete search space. Our techniques allow extensive validation of both generation of alternatives, and execution algorithms with plans other than the optimized one—if two candidate plans fail to produce the same results, then either the optimizer considered an invalid plan, or the execution code is faulty. When the space of alternatives becomes too large for exhaustive testing, which can occur even with a handful of joins, uniform random sampling provides a mechanism for unbiased testing.

The technique is implemented in Microsoft's SQL Server, where it is an integral part of the validation and testing process.
Expressing business rules
Authors: Ross Ronald G.
Published: November 2005

Business rules are formal statements about the data and processes of an enterprise. My overall approach to business rules is described in [1, 2]. Here, I will briefly discuss things we have learned about the expression of business rules in the last several years. This will shed light on where we stand in understanding business rules today.

First, it is clearly important to separate analysis-level expression of business rules from their design-level expression. Most of what I will say here is aimed toward the design level, but let me start with the analysis level.

Effective expression of business rules at the analysis level requires formative guidelines or Business Rule Statement Templates. Such language templates are now offered commercially (by my company and others). Think of these language templates as text or sentence patterns, to ensure higher clarity and consistency. These templates are important for making the business rule approach practical.

At the design level, how business rules are expressed to users must be cleanly separated from how they are represented inside the system. What is good for one is not good for the other.
DLFM
Authors: Hsiao Hui-I , Narang Inderpal
Published: November 2005

The DataLinks technology developed at IBM Almaden Research Center and now available in DB2 UDB 5.2 introduces a new data type called DATALINK for a database to reference and manage files stored external to the database. An external file is put under a database control by “linking” the file to the database. Control to a file can also be removed by “unlinking” it. The technology provides transactional semantics with respect to linking or unlinking the file when DATALINK value is stored or updated. Further more, it provides the following set of properties: (1) managing access control to linked files, (2) enforcing referential integrity, such as referenced file cannot be deleted or renamed as long as it is referenced from the RDBMS, and (3) providing coordinated backup and recovery of RDBMS data with the file data.

DataLinks File Manager (DLFM) is a key component of the DataLinks technology. DLFM is a sophisticated SQL application with a set of daemon processes residing at a file server node that work cooperatively with the host database server(s) to manage external files. To reduce the number of messages between database server and DLFM, DLFM maintains a set of meta data on the file system and the files that are under database control. One of the major decisions we made was to build DLFM on top of an existing database manager, such as DB2, instead of implementing a proprietary persistent data store. We have mixed feelings about using the RDBMS to build such a resource manager. One of the major challenges is to support transactional semantics for DLFM operations. To do this, we implemented the two-phase commit protocol in DLFM and designed an innovative scheme to enable
rolling
back transaction update after local database commit. Also a major gotchas is that the RDBMS' cost based optimizer generates the access plan, which does not take into account the locking costs of a concurrent workload. Using the RDBMS as a black box can cause “havoc” in terms of causing the lock timeouts and deadlocks and reducing the throughput of a concurrent workload. To solve the problem, we came up with a simple but effective way of influencing the optimizer to generate access plans matching the needs of DLFM implementation. Also several precautions had to be taken to ensure that lock escalation did not take place; next key locking was disabled to avoid deadlocks on heavily used indexes and SQL tables; and timeout mechanism was applied to break global deadlocks.

We were able to run 100-client workload for 24 hours without much deadlock/timeout problem in system test. This paper describes the motivation for building the DLFM and the lessons that we have learned from this experience.
Internet traffic warehouse
Authors: Chen Chung-Min , Cochinwala Munir , Petrone Claudio , Pucci Marc , Samtani Sunil , Santa Patrizia
Published: November 2005

We report on a network traffic warehousing project at Telcordia. The warehouse supports a variety of applications that require access to Internet traffic data. The applications include Service Level Agreement (SLA), web traffic analysis, network capacity engineering and planning, and billing. We describe the design of the warehouse and the issues encountered in building the warehouse.
SQLEM
Authors: Ordonez Carlos , Cereghini Paul
Published: November 2005

Clustering is one of the most important tasks performed in Data Mining applications. This paper presents an efficient SQL implementation of the EM algorithm to perform clustering in very large databases. Our version can effectively handle high dimensional data, a high number of clusters and more importantly, a very large number of data records. We present three strategies to implement EM in SQL: horizontal, vertical and a hybrid one. We expect this work to be useful for data mining programmers and users who want to cluster large data sets inside a relational DBMS.
Anatomy of a real E-commerce system
Authors: Jhingran Anant
Published: November 2005

Today's E-Commerce systems are a complex assembly of databases, web servers, home grown glue code, and networking services for security and scalability. The trend is towards larger pieces of these coming together in bundled offerings from leading software vendors, and the networking/hardware being offered through service delivery companies. In this paper we examine the bundle by looking in detail at IBM's WebSphere, Commerce Edition, and its deployment at a major customer site.
Index research (panel session)
Authors: Hellerstein Joseph M. , Kriegel Hans-Peter , Comet David , Falsutsos Christos , Ramakrishnan Raghu , Brown Paul
Published: November 2005

Indexes and access methods have been a staple of database research — and indeed of computer science in general — for decades. A glance at the contents of this year's SIGMOD and PODS proceedings shows another bumper crop of indexing papers.

Given the hundreds of indexing papers published in the database literature, a pause for reflection seems in order. From a scientific perspective, it is natural to ask why definitive indexing solutions have eluded us for so many years. What is the grand challenge in indexing? What basic complexities or intricacies underlie this large body of work? What would constitute a successful completion of this research agenda, and what steps will best move us in that direction? Or is it the case that the problem space branches in so many ways that we should expect to continuously need to solve variants of the indexing problem?

From the practitioner's perspective, the proliferation of indexing solutions in the literature may be more confusing than helpful. Comprehensively evaluating the research to date is a near-impossible task. An evaluation has to include both functionality (applicability to the practitioner's problem, integration with other data management services like buffer management, query processing and transactions) as well as performance for the practitioner's workloads. Unfortunately, there are no standard benchmarks for advanced indexing problems, and there has been relatively little work on methodologies for index experimentation and customization. How should the research community promote technology transfer in this area? Are the new extensibility interfaces in object-relational DBMSs conducive to this effort?
Data access (tutorial session)
Authors: Blakeley José A. , Deshpande Anand
Published: November 2005

With an explosion of data on the web, consistent data access to diverse data sources has become a challenging task. In this tutorial will present topics of interest to database researchers and developers building: interoperable middle-ware, gateways, distributed heterogeneous query processors, federated databases, data source wrappers, mediators, and DBMS extensions.

All of these require access to diverse information through common data access abstractions, powerful APIs, and common data exchange formats. With the emergence of the web, database applications are being run over the intranet and the extranet. This tutorial presents an overview of existing and emerging data access technologies. We will concentrate on some of the technical challenges that have to be addressed to enable uniform data access across various platforms and some of the issues that went into the design of these data access strategies.
FACT
Authors: Chen Songting , Diao Yanlei , Lu Hongjun , Tian Zengping
Published: November 2005

FACT (Fast and ACcuraTe) is a query processing system aimed at providing users with facilities so that they can get the query results from the Web in a database-like fashion. The system takes user queries in the form of keywords (free text) and returns segments of Web pages that contain the required information. It works as follows. The input from a user is passed to a general- purpose search engine to obtain a set of URLs of Web pages that may contain the required information. The system later locates the query results from the Web pages reachable from these URLs. Since queries expressed in keywords may be not able to express query requirements precisely or may not guarantee the discovery of required information inherently, the user is asked to first browse a few pages, during which the system learns from her/him about the exact query requirements and heuristics of finding the required information through a series of hyperlinks. The system will process the rest URLs and present the results in the form of segments of Web pages to the user.
i3
Authors: Sarawagi Sunita , Sathe Gayatri
Published: November 2005

The goal of the i
3
(eye cube) project is to enhance multidimensional database products with a suite of advanced operators to automate data analysis tasks that are currently handled through manual exploration. Most OLAP products are rather simplistic and rely heavily on the user's intuition to manually drive the discovery process. Such ad hoc user-driven exploration gets tedious and error-prone as data dimensionality and size increases. We first investigated how and why analysts currently explore the data cube and then automated them using advanced operators that can be invoked interactively like existing simple operators.

Our proposed suite of extensions appear in the form of a toolkit attached with a OLAP product. At this demo we will present three such operators: DIFF, RELAX and INFORM with illustrations from real-life datasets.
AJAX
Authors: Galhardas Helena , Florescu Daniela , Shasha Dennis , Simon Eric
Published: November 2005

@@@@
groups together matching pairs with a high similarity value by applying a given grouping criteria (e.g. by transitive closure). Finally,
ging
collapses each individual cluster into a tuple of the resulting data source. AJAX provides @@@@ for specifying data cleaning programs, which consists of SQL statements enriched with a set of specific primitives to express these transformations.

AJAX also @@@@. It allows the user to interact with an executing data cleaning program to handle exceptional cases and to inspect intermediate results. Finally, AJAX provides @@@@ @@@@ that permits users to determine the source and processing of data for debugging purposes.

We will present the AJAX system applied to two real world problems: the consolidation of a telecommunication database, and the conversion of a dirty database of bibliographic references into a set of clean, normalized, and redundancy free relational tables maintaining the same data.
Towards data mining benchmarking
Authors: Pei Jian , Mao Runying , Hu Kan , Zhu Hua
Published: November 2005

Performance benchmarking has played an important role in the research and development in relational DBMS, object-relational DBMS, data warehouse systems, etc. We believe that benchmarking data mining algorithms is a long overdue task, and it will play an important role in the research and development of data mining systems as well.

Frequent pattern mining forms a core component in mining associations, correlations, sequential patterns, partial periodicity, etc., which are of great potential value in applications. There have been a lot of methods proposed and developed for efficient frequent pattern mining in various kinds of databases, including transaction databases, time-series databases, etc. However, so far there is no serious performance benchmarking study of different frequent pattern mining methods.

To facilitate an analytical comparison of different frequent mining methods, we have constructed an open test bed for performance study of a set of recently developed, popularly used methods for mining frequent patterns in transaction databases and mining sequential patterns in sequence databases, with different data characteristics. The testbed consists of the following components.

A synthetic data generator, which can generate large sets of synthetic data in various kinds of data distributions. A few large data sets from real world applications will also be provided.

A good set of typical frequent pattern mining methods, ranging from classical algorithms to recent studies. The method are grouped into three classes:
frequent pattern mining, max-pattern mining
, and
sequential pattern mining
. For frequent pattern mining, we will demonstrate Apriori, hashing, partitioning, sampling, TreeProjection, and FP-growth. For maximal pattern mining, we will demonstrate MaxMiner, TreeProjection, and FP-growth-max.

For sequential pattern mining, we will demonstrate GSP and FreeSpan.

A set of performance curves. These algorithms their running speeds, scalabilities, bottlenecks, and performance on different data distributions, will be compared and demonstrated upon request. Some performance curves from our pre-conference experimental evaluations will also be shown.

An open testbed. Our goal is to construct an extensible test bed which integrates the above components and supports an open-ended testing service. Researchers can upload the object codes of their mining algorithms, and run them in the test bed using these data sets. The architecture is shown in Figure 1.

This testbed is our first step towards benchmarking data mining algorithms. By doing so, performance of different algorithms can be reported consistently, on the same platform, and in the same environment. After the demo, we plan to make the testbed available on the WWW so that it may, hopefully, benefit further research and development of efficient data mining methods.
A goal-driven auto-configuration tool for the distributed workflow management system mentorlite
Authors: Gillmann Michael , Weissenfels Jeanine , Shegalov German , Wonner Wolfgang , Weikum Gerhard
Published: November 2005

The Mentor-lite prototype has been developed within the research project “Architecture, Configuration, and Administration of Large Workflow Management Systems” funded by the German Science Foundation (DFG). It has evolved from its predecessor Mentor [1], but aims at a simpler architecture. The main goal of Mentor-lite has been to build a light-weight, extensible, and tailorable workflow management system (WFMS) with small footprint and easy-to-use administration capabilities. Our approach is to provide only kernel functionality inside the workflow engine, and consider system components like history management and worklist management as extensions on top of the kernel. The key point to retain the light-weight nature is that these extensions are implemented as workflows themselves.

The workflow specifications are interpreted at runtime, which is a crucial prerequisite for flexible exception handling and dynamic modifications during runtime. The interpreter performs a stepwise execution of the workflow specification according to its formal semantics. For each step, the activities to be performed by the step are determined and started.

Mentor-lite supports a protocol for distributed execution of workflows spread across multiple workflow engines. This support is crucial for workflows that span large, decentralized enterprises with largely autonomous organizational units or even cross multiple enterprises to form so-called “virtual enterprises”. A communication manager is responsible for sending and receiving synchronization messages between the engines. In order to guarantee a consistent global state even in the presence of site or network failures, we have built reliable message queues using the CORBA Object Transaction Services.

For administration, Mentor-lite provides a Java-based workbench for workflow design, workflow partitioning across multiple workflow servers, and a Java-based runtime monitoring tool.
SPIRE
Authors: Li Chung-Sheng , Bergman Lawrence D. , Chang Yuan-Chi , Castelli Vittorio , Smith John R.
Published: November 2005

In this demo, we will show the implementation of a content-based SPatial Image Retrieval Engine (SPIRE) for multimodal unstructured data. This architecture provides a framework for retrieving multi-modal data including image, image sequence, time series and parametric data from large archives. Dramatic speedup (from a factor of 4 to 35) has been achieved for many search operations such as template matching, texture feature extraction. This framework has been applied and validated in solar flares and petroleum exploration in which spatial and spatial-temporal phenomena are located.
The MLPQ/GIS constraint database system
Authors: Revesz Peter , Chen Rui , Kanjamala Pradip , Li Yiming , Liu Yuguo , Wang Yonghui
Published: November 2005

MLPQ/GIS [4,6] is a
constraint database
[5] system like CCUBE [1] and DEDALE [3] but with a special emphases on spatio-temporal data. Features include data entry tools (first four icons in Fig. 1), icon-based queries such as @@@@ Intersection, @@@@ Union, @@@@ Area, @@@@ Buffer, @@@@ Max and @@@@ Min, which optimize linear objective functions, and @@@@ for Datalog queries. For example, in Fig. 1 we loaded and displayed a constraint database that represents the midwest United States and loaded two contraint relations describing the movements of two persons. The query icon opened a dialog box into which we entered the query which finds (
t, i
) pairs such that the two people are in the same state
i
at the same time
t
.

MLPQ/GIS can animate [2] spatio-temporal objects that are linear constraint relations over and
t
.

Users can also display in discrete color zones (isometric maps) any spatially distributed variable
z
that is a linear function and For example, Fig. 2 shows the mean annual air temperature Nebraska. Animation and isometric map display can be combined.
Generating dynamic content at database-backed web servers
Authors: Labrinidis Alexandros , Roussopoulos Nick
Published: November 2005

Web servers are increasingly being used to deliver dynamic content rather than static HTML pages. In order to generate web pages dynamically, servers need to execute a script, which typically connects to a DBMS. Although CGI was the first approach at server side scripting, it has significant performance shortcomings. Currently, there are many alternative server side scripting architectures which offer better performance than CGI. In this paper, we report our experiences using
mod_perl
, an Apache Server module, which can improve the performance of CGI scripts by at least an order of magnitude. Except for presenting results from our experiments, we also briefly describe the implementation of an industrial strength database-backed web site that we recently built and give a quick overview of the various server-side scripting mechanisms.
Hierarchies and relative operators in the OLAP environment
Authors: Pourabbas Elaheh , Rafanelli Maurizio
Published: November 2005

In the last few years, numerous proposals for modelling and querying Multidimensional Databases (MDDB) are proposed. A rigorous classification of the different types of hierarchies is still an open problem. In this paper we propose and discuss some different types of hierarchies within a single dimension of a cube. These hierarchies divide in different levels of aggregation a single dimension. Depending on them, we discuss the characterization of some OLAP operators that refer to hierarchies in order to maintain the data cube consistency. Moreover, we propose a set of operators for changing the hierarchy structure. The issues discussed provide modelling flexibility during the scheme design phase and correct data analysis.
An optimisation scheme for coalesce/valid time selection operator sequences
Authors: Vassilakis Costas
Published: November 2005

Queries in temporal databases often employ the
coalesce
operator, either to coalesce results of projections, or data which are not coalesced upon storage. Therefore, the performance and the optimisation schemes utilised for this operator is of major importance for the performance of temporal DBMSs. Insofar, performance studies for various algorithms that implement this operator have been conducted, however, the joint optimisation of the coalesce operator with other algebraic operators that appear in the query execution plan has only received minimal attention. In this paper, we propose a scheme for combining the coalesce operator with selection operators which are applied to the valid time of the tuples produced from a coalescing operation. The proposed scheme aims at reducing the number of tuples that a coalescing operator must process, while at the same time allows the optimiser to exploit temporal indices on the valid time of the data.
A survey of logical models for OLAP databases
Authors: Vassiliadis Panos , Sellis Timos
Published: November 2005

In this paper, we present different proposals for multidimensional data cubes, which are the basic logical model for OLAP applications. We have grouped the work in the field in two categories: commercial tools (presented along with terminology and standards) and academic efforts. We further divide the academic efforts in two subcategories: the relational model extensions and the cube-oriented approaches. Finally, we attempt a comparative analysis of the various efforts.
Report on ISDO '00
Authors: Ludwig Heiko , Grefen Paul
Published: November 2005

The ISDO '00 workshop on "Infrastructures for Dynamic Business-to-Business Service Outsourcing" [1] was held as a preconference workshop of the 12th Conference on Advanced Information Systems Engineering (CAiSE *00) in Stockholm, Sweden, on June 5 and 6, 2000. C. Bussler (Net-fish Technologies), M. Bichler (Vienna University of Economics and Business Administration), and Y. Hoffner and H. Ludwig (IBM Zurich Research Laboratory) organised the workshop and chaired the program committee.The objective of the workshop was to provide a platform to discuss models and technologies for service outsourcing, with emphasis on the integration of the dynamic establishment, setup, and enactment of service relationships that connect the business processes of service provider and consumer businesses, thereby establishing virtual enterprises.Nowadays, many production companies integrate their procurement processes using online marketplaces and network-based supply chain management systems. However, this is not the case for the service industry. Whereas many service organisations have already automated their internal business process management (e.g. using workflow management systems or enterprise resource planning (ERP) systems), service marketplaces still remain an uncommon phenomenon. The reason for this is that the integration of service sales, service enactment, and customer interaction with the service process still appears to be highly difficult. This is particularly the case where complex services, such as insurance and complex logistics, involve considerable customer interaction.
Report on second international workshop on advanced issues of E-commerce and Web-based information systems
Authors: Wu Kun-Lung , Yu Philip S.
Published: November 2005

The Second International Workshop on Advanced Issues of E-Commerce and Web-Based Information Systems
(WECWIS 2000) was held at the Crowne Plaza San Jose/Silicon Valley in Milpitas, California on June 8-9, 2000. The purpose of this workshop was to bring together leading practitioners, developers and researchers to explore the challenging technical issues and find feasible solutions for advancing the current state of the art in e-commerce and web-based information systems. In particular, the workshop was interested in the infrastructure issues to facilitate e-commerce and Web-based information systems.WECWIS 2000 was successful. There were three invited talks, one industrial panel discussion and six technical sessions. The keynote speech, "The global trading web: A strategic vision for the Internet economy," was delivered by Dr. Jay M. Tenebaum, VP and Chief Scientist, Commerce One, Inc., on June 8 immediately following the opening remarks by the conference chair. The banquet address, "Business issues in e-commerce," was delivered by Mr. Daniel Druker, General Manager, Hyperion e-Business Division. Finally, a lunch address, "B2C, B2B, N2N, N2M: Why 2 is so instrumental?" was delivered by Mr. Mstafa A. Syed, VP of Technology, VertialNet, Inc.The industrial panel was moderated by Dr. L. Mason and Dr. Z. Zhang, both of Blue Martini Software. The panelists included J. Becher, Accrue Software; L. Mellot, Business Objects; A. Srivastava, Blue Martini Software; and C. Zhou, IBM. The panel discussion topic was "Can e-business intelligence survive?" Among the many interesting issues being discussed were: Will privacy concerns stunt e-business intelligence utility? Will integrated e-commerce solutions be able to collect and analyze click steams, contents, products and sales data simultaneously? To what extent can out-of-the-box combined e-commerce and e-business intelligence solutions be useful? Is data mining useful in B2B e-commerce? Both positive and negative responses were hotly debated.There were a total of 30 papers included in the technical presentations, organized into six sessions. They were selected after rigorous reviews by the program committee members. The presented papers cover a wide range of topics, from framework, architecture and protocol issues of e-commerce to various types of e-services to web-based information systems for facilitating e-commerce. The rest of this report provides a brief summary of the technical presentations given in the workshop. The entire workshop proceedings is available from the IEEE Computer Society.