text:
@inproceedings{10.5555/1315451.1315452,
author = {Eleftheriou, E. and B\"{a}chtold, P. and Cherubini, G. and Dholakia, A. and Hagleitner, C. and Loeliger, T. and Pantazi, A. and Pozidis, H. and Albrecht, T. R. and Binnig, G. K. and Despont, M. and Drechsler, U. and D\"{u}rig, U. and Gotsmann, B. and Jubin, D. and H\"{a}berle, W. and Lantz, M. A. and Rothuizen, H. and Stutz, R. and Vettiger, P. and Wiesmann, D.},
title = {A Nanotechnology-Based Approach to Data Storage},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Ultrahigh storage densities of up to 1 Tb/in2. or more can be achieved by using local-probe techniques to write, read back, and erase data in very thin polymer films. The thermomechanical scanning-probe-based data-storage concept, internally dubbed "millipede", combines ultrahigh density, small form factor, and high data rates. High data rates are achieved by parallel operation of large 2D arrays with thousands micro/nanomechanical cantilevers/tips that can be batch-fabricated by silicon surface-micromachining techniques. The inherent parallelism, the ultrahigh areal densities and the small form factor may open up new perspectives and opportunities for application in areas beyond those envisaged today.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {3–7},
numpages = {5},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315453,
author = {Mattos, Nelson Mendon\c{c}a},
title = {Integrating Information for on Demand Computing},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Information integration provides a competitive advantage to businesses and is fundamental to on demand computing. It is strategic area of investment by software companies today whose goal is to provide a unified view of the data regardless of differences in data format, data location and access interfaces, dynamically manage data placement to match availability, currency and performance requirements, and provide autonomic features that reduce the burden on IT staffs for managing complex data architectures. This paper describes the motivation for integrating information for on demand computing, explains its requirements, and illustrates its value through usage scenarios. As shown in the paper, there is still a tremendous amount of research, engineering, and development work needed to make the full information integration vision a reality and it is expected that software companies will continue to heavily invest in aggressively pursing the information integration vision.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {8–14},
numpages = {7},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315454,
author = {Shenker, Scott},
title = {The Data-Centric Revolution in Networking},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Historically, there has been little overlap between the database and networking research communities; they operate on very different levels and focus on very different issues. While this strict separation of concerns has lasted for many years, in this talk I will argue that the gap has recently narrowed to the point where the two fields now have much to say to each other.Networking research has traditionally focused on enabling communication between network hosts. This research program has produced a myriad of specific algorithms and protocols to solve such problems as error recovery, congestion control, routing, multicast and quality-of-service. It has also led to a set of general architectural principles, such as fate sharing and the end-to-end principle, that provide widely applicable guidelines for allocating functionality among network entities.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {15},
numpages = {1},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315455,
author = {Ioannidis, Yannis},
title = {The History of Histograms (Abridged)},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The history of histograms is long and rich, full of detailed information in every step. It includes the course of histograms in different scientific fields, the successes and failures of histograms in approximating and compressing information, their adoption by industry, and solutions that have been given on a great variety of histogram-related problems. In this paper and in the same spirit of the histogram techniques themselves, we compress their entire history (including their "future history" as currently anticipated) in the given/fixed space budget, mostly recording details for the periods, events, and results with the highest (personally-biased) interest. In a limited set of experiments, the semantic distance between the compressed and the full form of the history was found relatively small!},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {19–30},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315456,
author = {Raghavan, Sriram and Garcia-Molina, Hector},
title = {Complex Queries over Web Repositories},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Web repositories, such as the Stanford WebBase repository, manage large heterogeneous collections of Web pages and associated indexes. For effective analysis and mining, these repositories must provide a declarative query interface that supports complex expressive Web queries. Such queries have two key characteristics: (i) They view a Web repository simultaneously as a collection of text documents, as a navigable directed graph, and as a set of relational tables storing properties of Web pages (length, URL, title, etc.). (ii) The queries employ application-specific ranking and ordering relationships over pages and links to filter out and retrieve only the "best" query results. In this paper, we model a Web repository in terms of "Web relations" and describe an algebra for expressing complex Web queries. Our algebra extends traditional relational operators as well as graph navigation operators to uniformly handle plain, ranked, and ordered Web relations. In addition, we present an overview of the cost-based optimizer and execution engine that we have developed, to efficiently execute Web queries over large repositories.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {33–44},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315457,
author = {Cohen, Sara and Mamou, Jonathan and Kanza, Yaron and Sagiv, Yehoshua},
title = {XSEarch: A Semantic Search Engine for XML},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {XSEarch, a semantic search engine for XML, is presented. XSEarch has a simple query language, suitable for a naive user. It returns semantically related document fragments that satisfy the user's query. Query answers are ranked using extended information-retrieval techniques and are generated in an order similar to the ranking. Advanced indexing techniques were developed to facilitate efficient implementation of XSEarch. The performance of the different techniques as well as the recall and the precision were measured experimentally. These experiments indicate that XSEarch is efficient, scalable and ranks quality results highly.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {45–56},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315458,
author = {Shah, Shetal and Dharmarajan, Shyamshankar and Ramamritham, Krithi},
title = {An Efficient and Resilient Approach to Filtering and Disseminating Streaming Data},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Many web users monitor dynamic data such as stock prices, real-time sensor data and traffic data for making on-line decisions. Instances of such data can be viewed as data streams. In this paper, we consider techniques for creating a resilient and efficient content distribution network for such dynamically changing streaming data. We address the problem of maintaining the coherency of dynamic data items in a network of repositories: data disseminated to one repository is filtered by that repository and disseminated to repositories dependent on it. Our method is resilient to link failures and repository failures. This resiliency implies that data fidelity is not lost even when the repository from which (or a communication path through which) a user obtains data experiences failures. Experimental evaluation, using real world traces of streaming data, demonstrates that (i) the (computational and communication) cost of adding this redundancy is low, and (ii) surprisingly, in many cases, adding resiliency enhancing features actually improves the fidelity provided by the system even in cases when there are no failures. To further enhance fidelity, we also propose efficient techniques for filtering data arriving at one repository and for scheduling the dissemination of filtered data to another repository. Our results show that the combination of resiliency enhancing and efficiency improving techniques in fact help derive the potential that push based systems are said to have in delivering 100% fidelity. Without them, computational and communication delays inherent in dissemination networks can lead to a large fidelity loss even in push based dissemination.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {57–68},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315459,
author = {Yang, Liang Huai and Lee, Mong Li and Hsu, Wynne},
title = {Efficient Mining of XML Query Patterns for Caching},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {As XML becomes ubiquitous, the efficient retrieval of XML data becomes critical. Research to improve query response time has been largely concentrated on indexing paths, and optimizing XML queries. An orthogonal approach is to discover frequent XML query patterns and cache their results to improve the performance of XML management systems. In this paper, we present an efficient algorithm called FastXMiner, to discover frequent XML query patterns. We develop theorems to prove that only a small subset of the generated candidate patterns needs to undergo expensive tree containment tests. In addition, we demonstrate how the frequent query patterns can be used to improve caching performance. Experiments results show that FastXMiner is efficient and scalable, and caching the results of frequent patterns significantly improves the query response time.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {69–80},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315460,
author = {Aggarwal, Charu C. and Han, Jiawei and Wang, Jianyong and Yu, Philip S.},
title = {A Framework for Clustering Evolving Data Streams},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The clustering problem is a difficult problem for the data stream domain. This is because the large volumes of data arriving in a stream renders most traditional algorithms too inefficient. In recent years, a few one-pass clustering algorithms have been developed for the data stream problem. Although such methods address the scalability issues of the clustering problem, they are generally blind to the evolution of the data and do not address the following issues: (1) The quality of the clusters is poor when the data evolves considerably over time. (2) A data stream clustering algorithm requires much greater functionality in discovering and exploring clusters over different portions of the stream.The widely used practice of viewing data stream clustering algorithms as a class of one-pass clustering algorithms is not very useful from an application point of view. For example, a simple one-pass clustering algorithm over an entire data stream of a few years is dominated by the outdated history of the stream. The exploration of the stream over different time windows can provide the users with a much deeper understanding of the evolving behavior of the clusters. At the same time, it is not possible to simultaneously perform dynamic clustering over all possible time horizons for a data stream of even moderately large volume.This paper discusses a fundamentally different philosophy for data stream clustering which is guided by application-centered requirements. The idea is divide the clustering process into an online component which periodically stores detailed summary statistics and an offine component which uses only this summary statistics. The offine component is utilized by the analyst who can use a wide variety of inputs (such as time horizon or number of clusters) in order to provide a quick understanding of the broad clusters in the data stream. The problems of efficient choice, storage, and use of this statistical data for a fast data stream turns out to be quite tricky. For this purpose, we use the concepts of a pyramidal time frame in conjunction with a microclustering approach. Our performance experiments over a number of real and synthetic data sets illustrate the effectiveness, efficiency, and insights provided by our approach.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {81–92},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315461,
author = {Teng, Wei-Guang and Chen, Ming-Syan and Yu, Philip S.},
title = {A Regression-Based Temporal Pattern Mining Scheme for Data Streams},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We devise in this paper a regression-based algorithm, called algorithm FTP-DS (Frequent Temporal Patterns of Data Streams), to mine frequent temporal patterns for data streams. While providing a general framework of pattern frequency counting, algorithm FTP-DS has two major features, namely one data scan for online statistics collection and regression-based compact pattern representation.To attain the feature of one data scan, the data segmentation and the pattern growth scenarios are explored for the frequency counting purpose. Algorithm FTP-DS scans online transaction flows and generates candidate frequent patterns in real time. The second important feature of algorithm FTP-DS is on the regression-based compact pattern representation. Specifically, to meet the space constraint, we devise for pattern representation a compact ATF (standing for Accumulated Time and Frequency) form to aggregately comprise all the information required for regression analysis. In addition, we develop the techniques of the segmentation tuning and segment relaxation to enhance the functions of FTP-DS. With these features, algorithm FTP-DS is able to not only conduct mining with variable time intervals but also perform trend detection effectively. Synthetic data and a real dataset which contains net-Permission work alarm logs from a major telecommunication company are utilized to verify the feasibility of algorithm FTP-DS.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {93–104},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315462,
author = {Kumaran, A. and Haritsa, Jayant R.},
title = {On the Cost of Multilingualism in Database Systems},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Database engines are well-designed for storing and processing text data based on Latin scripts. But in today's global village, databases should ideally support multilingual text data equally efficiently. While current database systems do support management of multilingual data, we are not aware of any prior studies that compare and quantify their performance in this regard. In this paper, we first compare the multilingual functionality provided by a suite of popular database systems. We find that while the systems support most SQL-defined multilingual functionality, some needed features are not yet implemented. We then profile their performance in handling text data in IS0:8859, the standard database character set, and in Unicode, the multilingual character set. Our experimental results indicate significant performance degradation while handling multilingual data in these database systems. Worse, we find that the query optimizer's accuracy is different between standard and multilingual data types. As a first step towards alleviating the above problems, we propose Cuniform, a compressed format that is trivially convertible to Unicode. Our initial experimental results with Cuniform indicate that it largely eliminates the performance degradation for multilingual scripts with small repertoires. Further, the Cuniform format can elegantly support extensions to SQL for multilexical text processing.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {105–116},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315463,
author = {Yu, Clement and Philip, George and Meng, Weiyi},
title = {Distributed Top-N Query Processing with Possibly Uncooperative Local Systems},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We consider the problem of processing top-N queries in a distributed environment with possibly uncooperative local database systems. For a given top-N query, the problem is to find the N tuples that satisfy the query the best but not necessarily completely in an efficient manner. Top-N queries are gaining popularity in relational databases and are expected to be very useful for e-commerce applications. Many companies provide the same type of goods and services to the public on the Web, and relational databases may be employed to manage the data. It is not feasible for a user to query a large number of databases. It is therefore desirable to provide a facility where a user query is accepted at some site, suitable tuples from appropriate sites are retrieved and the results are merged and then presented to the user. In this paper, we present a method for constructing the desired facility. Our method consists of two steps. The first step determines which databases are likely to contain the desired tuples for a given query so that the databases can be ranked based on their desirability with respect to the query. Four different techniques are introduced for this step with one requiring no cooperation from local systems. The second step determines how the ranked databases should be searched and what tuples from the searched databases should be returned. A new algorithm is proposed for this purpose. Experimental results are presented to compare different methods and very promising results are obtained using the method that requires no cooperation from local databases.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {117–128},
numpages = {12},
keywords = {top-N queries, query processing, distributed databases},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315464,
author = {Long, Xiaohui and Suel, Torsten},
title = {Optimized Query Execution in Large Search Engines with Global Page Ordering},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Large web search engines have to answer thousands of queries per second with interactive response times. A major factor in the cost of executing a query is given by the lengths of the inverted lists for the query terms, which increase with the size of the document collection and are often in the range of many megabytes. To address this issue, IR and database researchers have proposed pruning techniques that compute or approximate term-based ranking functions without scanning over the full inverted lists.Over the last few years, search engines have incorporated new types of ranking techniques that exploit aspects such as the hyperlink structure of the web or the popularity of a page to obtain improved results. We focus on the question of how such techniques can be efficiently integrated into query processing. In particular, we study pruning techniques for query execution in large engines in the case where we have a global ranking of pages, as provided by Pagerank or any other method, in addition to the standard term-based approach. We describe pruning schemes for this case and evaluate their efficiency on an experimental cluster-based search engine with million web pages. Our results show that there is significant potential benefit in such techniques.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {129–140},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315465,
author = {Buneman, Peter and Grohe, Martin and Koch, Christoph},
title = {Path Queries on Compressed XML},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Central to any XML query language is a path language such as XPath which operates on the tree structure of the XML document. We demonstrate in this paper that the tree structure can be effectively compressed and manipulated using techniques derived from symbolic model checking. Specifically, we show first that succinct representations of document tree structures based on sharing subtrees are highly effective. Second, we show that compressed structures can be queried directly and efficiently through a process of manipulating selections of nodes and partial decompression. We study both the theoretical and experimental properties of this technique and provide algorithms for querying our compressed instances using node-selecting path query languages such as XPath.We believe the ability to store and manipulate large portions of the structure of very large XML documents in main memory is crucial to the development of efficient, scalable native XML databases and query engines.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {141–152},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315466,
author = {Flesca, S. and Furfaro, F. and Masciari, E.},
title = {On the Minimization of Xpath Queries},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {XML queries are usually expressed by means of XPath expressions identifying portions of the selected documents. An XPath expression defines a way of navigating an XML tree and returns the set of nodes which are reachable from one or more starting nodes through the paths specified by the expression. The problem of efficiently answering XPath queries is very interesting and has recently received increasing attention by the research community. In particular, an increasing effort has been devoted to define effective optimization techniques for XPath queries. One of the main issues related to the optimization of XPath queries is their minimization. The minimization of XPath queries has been studied for limited fragments of XPath, containing only the descendent, the child and the branch operators. In this work, we address the problem of minimizing XPath queries for a more general fragment, containing also the wildcard operator. We characterize the complexity of the minimization of XPath queries, stating that it is NP-hard, and propose an algorithm for computing minimum XPath queries. Moreover, we identify an interesting tractable case and propose an ad hoc algorithm handling the minimization of this kind of queries in polynomial time.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {153–164},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315467,
author = {Ramanan, Prakash},
title = {Covering Indexes for XML Queries: Bisimulation - Simulation = Negation},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Tree Pattern Queries (TPQ), Branching Path Queries (BPQ), and Core XPath (CXPath) are subclasses of the XML query language XPath, TPQ ⊂ BPQ ⊂ CX Path ⊂ X Path. Let TPQ = TPQ+ ⊂ BPQ+ ⊂ CX Path+ ⊂ X Path+ denote the corresponding subclasses, consisting of queries that do not involve the boolean negation operator not in their predicates. Simulation and bisimulation are two different binary relations on graph vertices that have previously been studied in connection with some of these classes. For instance, TPQ queries can be minimized using simulation. Most relevantly, for an XML document, its bisimulation quotient is the smallest index that covers (i.e., can be used to answer) all BPQ queries. Our results are as follows: • A CXPath+ query can be evaluated on an XML document by computing the simulation of the query tree by the document graph. • For an XML document, its simulation quotient is the smallest covering index for BPQ+. This, together with the previously-known result stated above, leads to the following: For BPQ covering indexes of XML documents, Bisimulation - Simulation = Negation. • For an XML document, its simulation quotient, with the idref edges ignored throughout, is the smallest covering index for TPQ.For any XML document, its simulation quotient is never larger than its bisimulation quotient; in some instances, it is exponentially smaller. Our last two results show that disallowing negation in the queries could substantially reduce the size of the smallest covering index.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {165–176},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315468,
author = {Amer-Yahia, Sihem and Fern\'{a}ndez, Mary and Srivastava, Divesh and Xu, Yu},
title = {Phrase Matching in XML},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Phrase matching is a common IR technique to search text and identify relevant documents in a document collection. Phrase matching in XML presents new challenges as text may be interleaved with arbitrary markup, thwarting search techniques that require strict contiguity or close proximity of keywords. We present a technique for phrase matching in XML that permits dynamic specification of both the phrase to be matched and the markup to be ignored. We develop an effective algorithm for our technique that utilizes inverted indices on phrase words and XML tags. We describe experimental results comparing our algorithm to an indexed-nested loop algorithm that illustrate our algorithm's efficiency.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {177–188},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315469,
author = {Chen, Yi and Davidson, Susan and Hara, Carmem and Zheng, Yifeng},
title = {RRXS: Redundancy Reducing XML Storage in Relations},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Current techniques for storing XML using relational technology consider the structure of an XML document but ignore its semantics as expressed by keys or functional dependencies. However, when the semantics of a document are considered redundancy may be reduced, node identifiers removed where value-based keys are available, and semantic constraints validated using relational primary key technology.In this paper, we propose a novel constraint definition called XFDs that capture structural as well as semantic information. We present a set of rewriting rules for XFDs, and use them to design a polynomial time algorithm which, given an input set of XFDs, computes a reduced set of XFDs. Based on this algorithm, we present a redundancy removing storage mapping from XML to relations called RRXS. The effectiveness of the mapping is demonstrated by experiments on three data sets.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {189–200},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315470,
author = {Deutsch, Alin and Tannen, Val},
title = {MARS: A System for Publishing XML from Mixed and Redundant Storage},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We present a system for publishing as XML data from mixed (relational+XML) proprietary storage, while supporting redundancy in storage for tuning purposes. The correspondence between public and proprietary schemas is given by a combination of LAV-and GAV-style views expressed in XQuery. XML and relational integrity constraints are also taken into consideration. Starting with client XQueries formulated against the public schema the system achieves the combined effect of rewriting-with-views, composition-with-views and query minimization under integrity constraints to obtain optimal reformulations against the proprietary schema. The paper focuses on the engineering and the experimental evaluation of the MARS system.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {201–212},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315471,
author = {Marian, Am\'{e}lie and Sim\'{e}on, J\'{e}r\^{o}me},
title = {Projecting XML Documents},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {XQuery is not only useful to query XML in databases, but also to applications that must process XML documents as files or streams. These applications suffer from the limitations of current main-memory XQuery processors which break for rather small documents. In this paper we propose techniques, based on a notion of projection for XML, which can be used to drastically reduce memory requirements in XQuery processors. The main contribution of the paper is a static analysis technique that can identify at compile time which parts of the input document are needed to answer an arbitrary XQuery. We present a loading algorithm that takes the resulting information to build a projected document, which is smaller than the original document, and on which the query yields the same result. We implemented projection in the Galax XQuery processor. Our experiments show that projection reduces memory requirements by a factor of 20 on average, and is effective for a wide variety of queries. In addition, projection results in some speedup during query evaluation.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {213–224},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315472,
author = {Halverson, Alan and Burger, Josef and Galanis, Leonidas and Kini, Ameet and Krishnamurthy, Rajasekar and Rao, Ajith Nagaraja and Tian, Feng and Viglas, Stratis D. and Wang, Yuan and Naughton, Jeffrey F. and DeWitt, David J.},
title = {Mixed Mode XML Query Processing},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Querying XML documents typically involves both tree-based navigation and pattern matching similar to that used in structured information retrieval domains. In this paper, we show that for good performance, a native XML query processing system should support query plans that mix these two processing paradigms. We describe our prototype native XML system, and report on experiments demonstrating that even for simple queries, there are a number of options for how to combine tree-based navigation and structural joins based on information retrieval-style inverted lists, and that these options can have widely varying performance. We present ways of transparently using both techniques in a single system, and provide a cost model for identifying efficient combinations of the techniques. Our preliminary experimental results prove the viability of our approach.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {225–236},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315473,
author = {Chen, Zhimin and Jagadish, H. V. and Lakshmanan, Laks V. S. and Paparizos, Stelios},
title = {From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {XQuery is the de facto standard XML query language, and it is important to have efficient query evaluation techniques available for it. A core operation in the evaluation of XQuery is the finding of matches for specified tree patterns, and there has been much work towards algorithms for finding such matches efficiently. Multiple XPath expressions can be evaluated by computing one or more tree pattern matches.However, relatively little has been done on efficient evaluation of XQuery queries as a whole. In this paper, we argue that there is much more to XQuery evaluation than a tree pattern match. We propose a structure called generalized tree pattern (GTP) for concise representation of a whole XQuery expression. Evaluating the query reduces to finding matches for its GTP. Using this idea we develop efficient evaluation plans for XQuery expressions, possibly involving join, quantifiers, grouping, aggregation, and nesting.XML data often conforms to a schema. We show that using relevant constraints from the schema, one can optimize queries significantly, and give algorithms for automatically inferring GTP simplifications given a schema. Finally, we show, through a detailed set of experiments using the TIMBER XML database system, that plans via GTPs (with or without schema knowledge) significantly outperform plans based on navigation and straightforward plans obtained directly from the query.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {237–248},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315474,
author = {Koch, Christoph},
title = {Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-Based Approach},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We propose a new, highly scalable and efficient technique for evaluating node-selecting queries on XML trees which is based on recent advances in the theory of tree automata.Our query processing techniques require only two linear passes over the XML data on disk, and their main memory requirements are in principle independent of the size of the data. The overall running time is O(m + n), where monly depends on the query and n is the size of the data. The query language supported is very expressive and captures exactly all node-selecting queries answerable with only a bounded amount of memory (thus, all queries that can be answered by any form of finite-state system on XML trees). Visiting each tree node only twice is optimal, and current automata-based approaches to answering path queries on XML streams, which work using one linear scan of the stream, are considerably less expressive.These technical results - which give rise to expressive query engines that deal more efficiently with large amounts of data in secondary storage - are complemented with an experimental evaluation of our work.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {249–260},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315475,
author = {Diao, Yanlei and Franklin, Michael},
title = {Query Processing for High-Volume XML Message Brokering},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {XML filtering solutions developed to date have focused on the matching of documents to large numbers of queries but have not addressed the customization of output needed for emerging distributed information infrastructures. Support for such customization can significantly increase the complexity of the filtering process. In this paper, we show how to leverage an efficient, shared path matching engine to extract the specific XML elements needed to generate customized output in an XML Message Broker. We compare three different approaches that differ in the degree to which they exploit the shared path matching engine. We also present techniques to optimize the post-processing of the path matching engine output, and to enable the sharing of such processing across queries. We evaluate these techniques with a detailed performance study of our implementation.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {261–272},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315476,
author = {Jiang, Haifeng and Wang, Wei and Lu, Hongjun and Yu, Jeffrey Xu},
title = {Holistic Twig Joins on Indexed XML Documents},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Finding all the occurrences of a twig pattern specified by a selection predicate on multiple elements in an XML document is a core operation for efficient evaluation of XML queries. Holistic twig join algorithms were proposed recently as an optimal solution when the twig pattern only involves ancestor-descendant relationships. In this paper, we address the problem of efficient processing of holistic twig joins on all/partly indexed XML documents. In particular, we propose an algorithm that utilizes available indices on element sets. While it can be shown analytically that the proposed algorithm is as efficient as the existing state-of-the-art algorithms in terms of worst case I/O and CPU cost, experimental results on various datasets indicate that the proposed index-based algorithm performs significantly better than the existing ones, especially when binary structural joins in the twig pattern have varying join selectivities.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {273–284},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315477,
author = {Viglas, Stratis D. and Naughton, Jeffrey F. and Burger, Josef},
title = {Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Recently there has been a growing interest in join query evaluation for scenarios in which inputs arrive at highly variable and unpredictable rates. In such scenarios, the focus shifts from completing the computation as soon as possible to producing a prefix of the output as soon as possible. To handle this shift in focus, most solutions to date rely upon some combination of streaming binary operators and "on-the-fly" execution plan reorganization. In contrast, we consider the alternative of extending existing symmetric binary join operators to handle more than two inputs. Toward this end, we have completed a prototype implementation of a multi-way join operator, which we term the "MJoin" operator, and explored its performance. Our results show that in many instances the MJoin produces outputs sooner than any tree of binary operators. Additionally, since MJoins are completely symmetric with respect to their inputs, they can reduce the need for expensive runtime plan reorganization. This suggests that supporting multiway joins in a single, symmetric, streaming operator may be a useful addition to systems that support queries over input streams from remote sites.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {285–296},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315478,
author = {Hammad, Moustafa A. and Franklin, Michael J. and Aref, Walid G. and Elmagarmid, Ahmed K.},
title = {Scheduling for Shared Window Joins over Data Streams},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Continuous Query (CQ) systems typically exploit commonality among query expressions to achieve improved efficiency through shared processing. Recently proposed CQ systems have introduced window specifications in order to support unbounded data streams. There has been, however, little investigation of sharing for windowed query operators. In this paper, we address the shared execution of windowed joins, a core operator for CQ systems. We show that the strategy used in systems to date has a previously unreported performance flaw that can negatively impact queries with relatively small windows. We then propose two new execution strategies for shared joins. We evaluate the alternatives using both analytical models and implementation in a DBMS. The results show that one strategy, called MQT, provides the best performance over a range of workload settings.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {297–308},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315479,
author = {Tatbul, Nesime and \c{C}etintemel, U\u{g}ur and Zdonik, Stan and Cherniack, Mitch and Stonebraker, Michael},
title = {Load Shedding in a Data Stream Manager},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {A Data Stream Manager accepts push-based inputs from a set of data sources, processes these inputs with respect to a set of standing queries, and produces outputs based on Quality-of-Service (QoS) specifications. When input rates exceed system capacity, the system will become overloaded and latency will deteriorate. Under these conditions, the system will shed load, thus degrading the answer, in order to improve the observed latency of the results. This paper examines a technique for dynamically inserting and removing drop operators into query plans as required by the current load. We examine two types of drops: the first drops a fraction of the tuples in a randomized fashion, and the second drops tuples based on the importance of their content. We address the problems of determining when load shedding is needed, where in the query plan to insert drops, and how much of the load should be shed at that point in the plan. We describe efficient solutions and present experimental evidence that they can bring the system back into the useful operating range with minimal degradation in answer quality.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {309–320},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315480,
author = {Huebsch, Ryan and Hellerstein, Joseph M. and Lanham, Nick and Loo, Boon Thau and Shenker, Scott and Stoica, Ion},
title = {Querying the Internet with PIER},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The database research community prides itself on scalable technologies. Yet database systems traditionally do not excel on one important scalability dimension: the degree of distribution. This limitation has hampered the impact of database technologies on massively distributed systems like the Internet.In this paper, we present the initial design of PIER, a massively distributed query engine based on overlay networks, which is intended to bring database query processing facilities to new, widely distributed environments. We motivate the need for massively distributed queries, and argue for a relaxation of certain traditional database research goals in the pursuit of scalability and widespread adoption. We present simulation results showing PIER gracefully running relational queries across thousands of machines, and show results from the same software base in actual deployment on a large experimental cluster.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {321–332},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315481,
author = {Tian, Feng and DeWitt, David J.},
title = {Tuple Routing Strategies for Distributed Eddies},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Many applications that consist of streams of data are inherently distributed. Since input stream rates and other system parameters such as the amount of available computing resources can fluctuate significantly, a stream query plan must be able to adapt to these changes. Routing tuples between operators of a distributed stream query plan is used in several data stream management systems as an adaptive query optimization technique. The routing policy used can have a significant impact on system performance. In this paper, we use a queuing network to model a distributed stream query plan and define performance metrics for response time and system throughput. We also propose and evaluate several practical routing policies for a distributed stream management system. The performance results of these policies are compared using a discrete event simulator. Finally, we study the impact of the routing policy on system throughput and resource allocation when computing resources can be shared between operators.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {333–344},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315482,
author = {Lerner, Alberto and Shasha, Dennis},
title = {AQuery: Query Language for Ordered Data, Optimization Techniques, and Experiments},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {An order-dependent query is one whose result (interpreted as a multiset) changes if the order of the input records is changed. In a stock-quotes database, for instance, retrieving all quotes concerning a given stock for a given day does not depend on order, because the collection of quotes does not depend on order. By contrast, finding a stock's five-price moving-average in a trades table gives a result that depends on the order of the table. Query languages based on the relational data model can handle order-dependent queries only through add-ons. SQL:1999, for instance, has a new "window" mechanism which can sort data in limited parts of a query. Add-ons make order-dependent queries di_cult to write and to optimize. In this paper we show that order can be a natural property of the underlying data model and algebra. We introduce a new query language and algebra, called AQuery, that supports order from-the-ground-up. New order-related query transformations arise in this setting. We show by experiment that this framework - language plus optimization techniques - brings orders-of-magnitude improvement over SQL:1999 systems on many natural order-dependent queries.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {345–356},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315483,
author = {He, Hai and Meng, Weiyi and Yu, Clement and Wu, Zonghuan},
title = {Wise-Integrator: An Automatic Integrator of Web Search Interfaces for E-Commerce},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {More and more databases are becoming Web accessible through form-based search interfaces, and many of these sources are E-commerce sites. Providing a unified access to multiple E-commerce search engines selling similar products is of great importance in allowing users to search and compare products from multiple sites with ease. One key task for providing such a capability is to integrate the Web interfaces of these E-commerce search engines so that user queries can be submitted against the integrated interface. Currently, integrating such search interfaces is carried out either manually or semi-automatically, which is inefficient and difficult to maintain. In this paper, we present WISE-Integrator - a tool that performs automatic integration of Web Interfaces of Search Engines. WISE-Integrator employs sophisticated techniques to identify matching attributes from different search interfaces for integration. It also resolves domain differences of matching attributes. Our experimental results based on 20 and 50 interfaces in two different domains indicate that WISE-Integrator can achieve high attribute matching accuracy and can produce high-quality integrated search interfaces without human interactions.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {357–368},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315484,
author = {Lim, Lipyeow and Wang, Min and Vitter, Jeffrey Scott},
title = {SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Most RDBMSs maintain a set of histograms for estimating the selectivities of given queries. These selectivities are typically used for cost-based query optimization. While the problem of building an accurate histogram for a given attribute or attribute set has been well-studied, little attention has been given to the problem of building and tuning a set of histograms collectively for multidimensional queries in a self-managed manner based only on query feedback. In this paper, we present SASH, a Self-Adaptive Set of Histograms that addresses the problem of building and maintaining a set of histograms. SASH uses a novel two-phase method to automatically build and maintain itself using query feedback information only. In the online tuning phase, the current set of histograms is tuned in response to the estimation error of each query in an online manner. In the restructuring phase, a new and more accurate set of histograms replaces the current set of histograms. The new set of histograms (attribute sets and memory distribution) is found using information from a batch of query feedback. We present experimental results that show the effectiveness and accuracy of our approach.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {369–380},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315485,
author = {Lin, Chi-Chun and Chen, Ming-Syan},
title = {VIPAS: Virtual Link Powered Authority Search in the Web},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {With the exponential growth of the World Wide Web, looking for pages with high quality and relevance in the Web has become an important research field. There have been many keyword-based search engines built for this purpose. However, these search engines usually suffer from the problem that a relevant Web page may not contain the keyword in its page text. Algorithms exploiting the link structure of Web documents, such as HITS, have also been proposed to overcome the problems of traditional search engines. Though these algorithms perform better than keyword-based search engines, they still have some defects. Among others, one major problem is that links in Web pages are only able to reflect the view of the page authors on the topic of those pages but not that of the page readers. In this paper, we propose a new algorithm with the idea of using virtual links which are created according to what the user behaves in browsing the output list of the query result. These virtual links are then employed to identify authoritative resources in the Web. Speci fically, the algorithm, referred to as algorithm VIPAS (standing for virtual link powered authority search), is divided into three phases. The first phase performs basic link analysis. The second phase collects statistics by observing the user behavior in browsing pages listed in the query result, and virtual links are then created according to what observed. In the third phase, these virtual links as well as real ones are taken together to produce an updated list of authoritative pages that will be presented to the user when the query with similar keywords is encountered next time. A Web warehouse is built and the algorithm is integrated into the system. By conducting experiments on the system, we have shown that VIPAS is not only very effective but also very adaptive in providing much more valuable information to users.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {381–392},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315486,
author = {Labrinidis, Alexandros and Roussopoulos, Nick},
title = {Balancing Performance and Data Freshness in Web Database Servers},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Personalization, advertising, and the sheer volume of online data generate a staggering amount of dynamic web content. In addition to web caching, View Materialization has been shown to accelerate the generation of dynamic web content. View materialization is an attractive solution as it decouples the serving of access requests from the handling of updates. In the context of the Web, selecting which views to materialize must be decided online and needs to consider both performance and data freshness, which we refer to as the Online View Selection problem. In this paper, we define data freshness metrics, provide an adaptive algorithm for the online view selection problem, and present experimental results.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {393–404},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315487,
author = {Zhou, Jingren and Ross, Kenneth A.},
title = {Buffering Accesses to Memory-Resident Index Structures},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Recent studies have shown that cache-conscious indexes outperform conventional main memory indexes. Cache-conscious indexes focus on better utilization of each cache line for improving search performance of a single lookup. None has exploited cache spatial and temporal locality between consecutive lookups. We show that conventional indexes, even "cache-conscious" ones, suffer from significant cache thrashing between accesses. Such thrashing can impact the performance of applications such as stream processing and query operations such as index-nested-loops join.We propose techniques to buffer accesses to memory-resident tree-structured indexes to avoid cache thrashing. We study several alternative designs of the buffering technique, including whether to use fixed-size or variable-sized buffers, whether to buffer at each tree level or only at some of the levels, how to support bulk access while there are concurrent updates happening to the index, and how to preserve the order of the incoming lookups in the output results. Our methods improve cache performance for both cache-conscious and conventional index structures. Our experiments show that buffering techniques enable a probe throughput that is two to three times higher than traditional methods.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {405–416},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315488,
author = {Hankins, Richard A. and Patel, Jignesh M.},
title = {Data Morphing: An Adaptive, Cache-Conscious Storage Technique},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The number of processor cache misses has a critical impact on the performance of DBMSs running on servers with large main-memory configurations. In turn, the cache utilization of database systems is highly dependent on the physical organization of the records in main-memory. A recently proposed storage model, called PAX, was shown to greatly improve the performance of sequential file-scan operations when compared to the commonly implemented N-ary storage model. However, the PAX storage model can also demonstrate poor cache utilization for other common operations, such as index scans. Under a workload of heterogenous database operations, neither the PAX storage model nor the N-ary storage model is optimal.In this paper, we propose a flexible data storage technique called Data Morphing. Using Data Morphing, a cache-efficient attribute layout, called a partition, is first determined through an analysis of the query workload. This partition is then used as a template for storing data in a cache-efficient way. We present two algorithms for computing partitions, and also present a versatile storage model that accommodates the dynamic reorganization of the attributes in a file. Finally, we experimentally demonstrate that the Data Morphing technique provides a significant performance improvement over both the traditional N-ary storage model and the PAX model.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {417–428},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315489,
author = {Hinneburg, Alexander and Habich, Dirk and Lehner, Wolfgang},
title = {COMBI-Operator - Database Support for Data Mining Applications},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Database support for data mining has become an important research topic. Especially for large high-dimensional data volumes, comprehensive support from the database side is necessary. In this paper we identify the data intensive subproblem of aggregating high-dimensional data in all possible low-dimensional projections (for instance estimating low-dimensional histograms), which occurs in several established data mining techniques. Second, we show that existing OLAP SQL-extensions are insufficient for high-dimensional data and propose a new SQL-operator, which seamlessly fits into the set of existing OLAP Group By operators. Third, we propose efficient implementations for the operator, which take the limited resources of main memory into account. We demonstrate on a number of real and synthetic data sets that for the identified subproblem our new implementations yield a large speedup (up to factor 10) over existing methods built in commercially available database systems.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {429–439},
numpages = {11},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315490,
author = {Shi, Yong and Song, Yuqing and Zhang, Aidong},
title = {A Shrinking-Based Approach for Multi-Dimensional Data Analysis},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Existing data analysis techniques have difficulty in handling multi-dimensional data. In this paper, we first present a novel data preprocessing technique called shrinking which optimizes the inner structure of data inspired by the Newton's Universal Law of Gravitation[22] in the real world. This data reorganization concept can be applied in many fields such as pattern recognition, data clustering and signal processing. Then, as an important application of the data shrinking preprocessing, we propose a shrinking-based approach for multi-dimensional data analysis which consists of three steps: data shrinking, cluster detection, and cluster evaluation and selection. The process of data shrinking moves data points along the direction of the density gradient, thus generating condensed, widely-separated clusters. Following data shrinking, clusters are detected by finding the connected components of dense cells. The data-shrinking and cluster-detection steps are conducted on a sequence of grids with different cell sizes. The clusters detected at these scales are compared by a cluster-wise evaluation measurement, and the best clusters are selected as the final result. The experimental results show that this approach can effectively and efficiently detect clusters in both low- and high-dimensional spaces.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {440–451},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315491,
author = {Zhou, Jianjun and Sander, J\"{o}rg},
title = {Data Bubbles for Non-Vector Data: Speeding-up Hierarchical Clustering in Arbitrary Metric Spaces},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {To speed-up clustering algorithms, data summarization methods have been proposed, which first summarize the data set by computing suitable representative objects. Then, a clustering algorithm is applied to these representatives only, and a clustering structure for the whole data set is derived, based on the result for the representatives. Most previous methods are, however, limited in their application domain. They are in general based on sufficient statistics such as the linear sum of a set of points, which assumes that the data is from a vector space. On the other hand, in many important applications, the data is from a metric non-vector space, and only distances between objects can be exploited to construct effective data summarizations. In this paper, we develop a new data summarization method based only on distance information that can be applied directly to non-vector data. An extensive performance evaluation shows that our method is very effective in finding the hierarchical clustering structure of non-vector data using only a very small number of data summarizations, thus resulting in a large reduction of runtime while trading only very little clustering quality.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {452–463},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315492,
author = {Cormode, Graham and Korn, Flip and Muthukrishnan, S. and Srivastava, Divesh},
title = {Finding Hierarchical Heavy Hitters in Data Streams},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Aggregation along hierarchies is a critical summary technique in a large variety of on-line applications including decision support and network management (e.g., IP clustering, denial-of-service attack monitoring). Despite the amount of recent study that has been dedicated to online aggregation on sets (e.g., quantiles, hot items), surprisingly little attention has been paid to summarizing hierarchical structure in stream data.The problem we study in this paper is that of finding Hierarchical Heavy Hitters (HHH): given a hierarchy and a fraction φ, we want to find all HHH nodes that have a total number of descendants in the data stream no smaller than φ of the total number of elements in the data stream, after discounting the descendant nodes that are HHH nodes. The resulting summary gives a topological "cartogram" of the hierarchical data. We present deterministic and randomized algorithms for finding HHHs, which builds upon existing techniques by incorporating the hierarchy into the algorithms. Our experiments demonstrate several factors of improvement in accuracy over the straightforward approach, which is due to making algorithms hierarchy-aware.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {464–475},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315493,
author = {Xin, Dong and Han, Jiawei and Li, Xiaolei and Wah, Benjamin W.},
title = {Star-Cubing: Computing Iceberg Cubes by Top-down and Bottom-up Integration},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Data cube computation is one of the most essential but expensive operations in data warehousing. Previous studies have developed two major approaches, top-down vs. bottom-up. The former, represented by the Multi-Way Array Cube (called MultiWay) algorithm [25], aggregates simultaneously on multiple dimensions; however, it cannot take advantage of Apriori pruning [2] when computing iceberg cubes (cubes that contain only aggregate cells whose measure value satisfies a threshold, called iceberg condition). The latter, represented by two algorithms: BUC [6] and H-Cubing[11], computes the iceberg cube bottom-up and facilitates Apriori pruning. BUC explores fast sorting and partitioning techniques; whereas H-Cubing explores a data structure, H-Tree, for shared computation. However, none of them fully explores multi-dimensional simultaneous aggregation.In this paper, we present a new method, Star-Cubing, that integrates the strengths of the previous three algorithms and performs aggregations on multiple dimensions simultaneously. It utilizes a star-tree structure, extends the simultaneous aggregation methods, and enables the pruning of the group-by's that do not satisfy the iceberg condition. Our performance study shows that Star-Cubing is highly efficient and outperforms all the previous methods in almost all kinds of data distributions.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {476–487},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315494,
author = {Kraft, Tobias and Schwarz, Holger and Rantzau, Ralf and Mitschang, Bernhard},
title = {Coarse-Grained Optimization: Techniques for Rewriting SQL Statement Sequences},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Relational OLAP tools and other database applications generate sequences of SQL statements that are sent to the database server as result of a single information request provided by a user. Unfortunately, these sequences cannot be processed efficiently by current database systems because they typically optimize and process each statement in isolation. We propose a practical approach for this optimization problem, called "coarse-grained optimization," complementing the conventional query optimization phase. This new approach exploits the fact that statements of a sequence are correlated since they belong to the same information request. A lightweight heuristic optimizer modifies a given statement sequence using a small set of rewrite rules. Since the optimizer is part of a separate system layer, it is independent of but can be tuned to a specific underlying database system. We discuss implementation details and demonstrate that our approach leads to significant performance improvements.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {488–499},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315495,
author = {Golab, Lukasz and \"{O}zsu, M Tamer},
title = {Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We study sliding window multi-join processing in continuous queries over data streams. Several algorithms are reported for performing continuous, incremental joins, under the assumption that all the sliding windows fit in main memory. The algorithms include multiway incremental nested loop joins (NLJs) and multi-way incremental hash joins. We also propose join ordering heuristics to minimize the processing cost per unit time. We test a possible implementation of these algorithms and show that, as expected, hash joins are faster than NLJs for performing equi-joins, and that the overall processing cost is influenced by the strategies used to remove expired tuples from the sliding windows.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {500–511},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315496,
author = {Iwerks, Glenn S. and Samet, Hanan and Smith, Ken},
title = {Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {In recent years there has been an increasing interest in databases of moving objects where the motion and extent of objects are represented as a function of time. The focus of this paper is on the maintenance of continuous K- nearest neighbor (k-NN) queries on moving points when updates are allowed. Updates change the functions describing the motion of the points, causing pending events to change. Events are processed to keep the query result consistent as points move. It is shown that the cost of maintaining a continuous k-NN query result for moving points represented in this way can be significantly reduced with a modest increase in the number of events processed in the presence of updates. This is achieved by introducing a continuous within query to filter the number of objects that must be taken into account when maintaining a continuous k-NN query. This new approach is presented and compared with other recent work. Experimental results are presented showing the utility of this approach.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {512–523},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315497,
author = {Grust, Torsten and van Keulen, Maurice and Teubner, Jens},
title = {Staircase Join: Teach a Relational DBMS to Watch Its (Axis) Steps},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Relational query processors derive much of their effectiveness from the awareness of specific table properties like sort order, size, or absence of duplicate tuples. This text applies (and adapts) this successful principle to database-supported XML and XPath processing: the relational system is made tree aware, i.e., tree properties like subtree size, intersection of paths, inclusion or disjointness of subtrees are made explicit. We propose a local change to the database kernel, the staircase join, which encapsulates the necessary tree knowledge needed to improve XPath performance. Staircase join operates on an XML encoding which makes this knowledge available at the cost of simple integer operations (e.g., +, ≤ ). We finally report on quite promising experiments with a staircase join enhanced main-memory database kernel.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {524–535},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315498,
author = {Korn, Flip and Muthukrishnan, S. and Zhu, Yunyue},
title = {Checks and Balances: Monitoring Data Quality Problems in Network Traffic Databases},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Internet Service Providers (ISPs) use real-time data feeds of aggregated traffic in their network to support technical as well as business decisions. A fundamental difficulty with building decision support tools based on aggregated traffic data feeds is one of data quality. Data quality problems stem from network-specific issues (irregular polling caused by UDP packet drops and delays, topological mislabelings, etc.) and make it difficult to distinguish between artifacts and actual phenomena, rendering data analysis based on such data feeds ineffective.In principle, traditional integrity constraints and triggers may be used to enforce data quality. In practice, data cleaning is done outside the database and is ad-hoc. Unfortunately, these approaches are too rigid and limited for the subtle data quality problems arising from network data where existing problems morph with network dynamics, new problems emerge over time, and poor quality data in a local region may itself indicate an important phenomenon in the underlying network. We need a new approach - both in principle and in practice - to face data quality problems in network traffic databases.We propose a continuous data quality monitoring approach based on probabilistic, approximate constraints (PACs). These are simple, user-specified rule templates with open parameters for tolerance and likelihood. We use statistical techniques to instantiate suitable parameter values from the data, and show how to apply them for monitoring data quality.In principle, our PAC-based approach can be applied to data quality problems in any data feed. We present PAC-Man, which is the system that manages PACs for the entire aggregate network traffic database in a large ISP, and show that it is very effective in monitoring data quality problems.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {536–547},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315499,
author = {Luebbers, Dominik and Grimmer, Udo and Jarke, Matthias},
title = {Systematic Development of Data Mining-Based Data Quality Tools},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Data quality problems have been a persistent concern especially for large historically grown databases. If maintained over long periods, interpretation and usage of their schemas often shifts. Therefore, traditional data scrubbing techniques based on existing schema and integrity constraint documentation are hardly applicable. So-called data auditing environments circumvent this problem by using machine learning techniques in order to induce semantically meaningful structures from the actual data, and then classifying outliers that do not fit the induced schema as potential errors.However, as the quality of the analyzed database is a-priori unknown, the design of data auditing environments requires special methods for the calibration of error measurements based on the induced schema. In this paper, we present a data audit test generator that systematically generates and pollutes artificial benchmark databases for this purpose. The test generator has been implemented as part of a data auditing environment based on the well-known machine learning algorithm C4.5.Validation in the partial quality audit of a large service-related database at Daimler-Chrysler shows the usefulness of the approach as a complement to standard data scrubbing.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {548–559},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315500,
author = {Papadimitriou, Spiros and Brockwell, Anthony and Faloutsos, Christos},
title = {Adaptive, Hands-off Stream Mining},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Sensor devices and embedded processors are becoming ubiquitous. Their limited resources (CPU, memory and/or communication bandwidth and power) pose some interesting challenges. We need both powerful and concise "languages" to represent the important features of the data, which can (a) adapt and handle arbitrary periodic components, including bursts, and (b) require little memory and a single pass over the data.We propose AWSOM (Arbitrary Window Stream mOdeling Method), which allows sensors in remote or hostile environments to efficiently and effectively discover interesting patterns and trends. This can be done automatically, i.e., with no user intervention and expert tuning before or during data gathering. Our algorithms require limited resources and can thus be incorporated in sensors, possibly alongside a distributed query processing engine [9, 5, 22]. Updates are performed in constant time, using logarithmic space. Existing, state of the art forecasting methods (SARIMA, GARCH, etc) fall short on one or more of these requirements. To the best of our knowledge, AWSOM is the first method that has all the above characteristics.Experiments on real and synthetic datasets demonstrate that AWSOM discovers meaningful patterns over long time periods. Thus, the patterns can also be used to make long-range forecasts, which are notoriously difficult to perform. In fact, AWSOM outperforms manually set up auto-regressive models, both in terms of long-term pattern detection and modeling, as well as by at least 10\texttimes{} in resource consumption.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {560–571},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315501,
author = {Madhavan, Jayant and Halevy, Alon Y.},
title = {Composing Mappings among Data Sources},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Semantic mappings between data sources play a key role in several data sharing architectures. Mappings provide the relationships between data stored in different sources, and therefore enable answering queries that require data from other nodes in a data sharing network. Composing mappings is one of the core problems that lies at the heart of several optimization methods in data sharing networks, such as caching frequently traversed paths and redundancy analysis.This paper investigates the theoretical underpinnings of mapping composition. We study the problem for a rich mapping language, GLAV, that combines the advantages of the known mapping formalisms globalas-view and local-as-view. We first show that even when composing two simple GLAV mappings, the full composition may be an infinite set of GLAV formulas. Second, we show that if we restrict the set of queries to be in CQk (a common restriction in practice), then we can always encode the infinite set of GLAV formulas using a finite representation. Furthermore, we describe an algorithm that given a query and a finite encoding of an infinite set of GLAV formulas, finds all the certain answers to the query. Consequently, we show that for a commonly occuring class of queries it is possible to pre-compose mappings, thereby potentially offering significant savings in query processing.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {572–583},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315502,
author = {Velegrakis, Yannis and Miller, Ren\'{e}e J. and Popa, Lucian},
title = {Mapping Adaptation under Evolving Schemas},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {To achieve interoperability, modern information systems and e-commerce applications use mappings to translate data from one representation to another. In dynamic environments like the Web, data sources may change not only their data but also their schemas, their semantics, and their query capabilities. Such changes must be reflected in the mappings. Mappings left inconsistent by a schema change have to be detected and updated. As large, complicated schemas become more prevalent, and as data is reused in more applications, manually maintaining mappings (even simple mappings like view definitions) is becoming impractical. We present a novel framework and a tool (ToMAS) for automatically adapting mappings as schemas evolve. Our approach considers not only local changes to a schema, but also changes that may affect and transform many components of a schema. We consider a comprehensive class of mappings for relational and XML schemas with choice types and (nested) constraints. Our algorithm detects mappings affected by a structural or constraint change and generates all the rewritings that are consistent with the semantics of the mapped schemas. Our approach explicitly models mapping choices made by a user and maintains these choices, whenever possible, as the schemas and mappings evolve. We describe an implementation of a mapping management and adaptation tool based on these ideas and compare it with a mapping generation tool.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {584–595},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315503,
author = {Luo, Gang and Naughton, Jeffrey F. and Ellmann, Curt J. and Watzke, Michael W.},
title = {Locking Protocols for Materialized Aggregate Join Views},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The maintenance of materialized aggregate join views is a well-studied problem. However, to date the published literature has largely ignored the issue of concurrency control. Clearly immediate materialized view maintenance with transactional consistency, if enforced by generic concurrency control mechanisms, can result in low levels of concurrency and high rates of deadlock. While this problem is superficially amenable to well-known techniques such as fine-granularity locking and special lock modes for updates that are associative and commutative, we show that these previous techniques do not fully solve the problem. We extend previous high concurrency locking techniques to apply to materialized view maintenance, and show how this extension can be implemented even in the presence of indices on the materialized view.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {596–607},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315504,
author = {Lee, Mong Li and Hsu, Wynne and Jensen, Christian S. and Cui, Bin and Teo, Keng Lik},
title = {Supporting Frequent Updates in R-Trees: A Bottom-up Approach},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Advances in hardware-related technologies promise to enable new data management applications that monitor continuous processes. In these applications, enormous amounts of state samples are obtained via sensors and are streamed to a database. Further, updates are very frequent and may exhibit locality. While the R-tree is the index of choice for multi-dimensional data with low dimensionality, and is thus relevant to these applications, R-tree updates are also relatively inefficient. We present a bottom-up update strategy for R-trees that generalizes existing update techniques and aims to improve update performance. It has different levels of reorganization--ranging from global to local--during updates, avoiding expensive top-down updates. A compact main-memory summary structure that allows direct access to the R-tree index nodes is used together with efficient bottom-up algorithms. Empirical studies indicate that the bottom-up strategy outperforms the traditional top-down technique, leads to indices with better query performance, achieves higher throughput, and is scalable.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {608–619},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315505,
author = {Qian, Gang and Zhu, Qiang and Xue, Qiang and Pramanik, Sakti},
title = {The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-Ordered Discrete Data Spaces},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Similarity searches in multidimensional Nonordered Discrete Data Spaces (NDDS) are becoming increasingly important for application areas such as genome sequence databases. Existing indexing methods developed for multidimensional (ordered) Continuous Data Spaces (CDS) such as R-tree cannot be directly applied to an NDDS. This is because some essential geometric concepts/properties such as the minimum bounding region and the area of a region in a CDS are no longer valid in an NDDS. On the other hand, indexing methods based on metric spaces such as M-tree are too general to effectively utilize the data distribution characteristics in an NDDS. Therefore, their retrieval performance is not optimized. To support efficient similarity searches in an NDDS, we propose a new dynamic indexing technique, called the ND-tree. The key idea is to extend the relevant geometric concepts as well as some indexing strategies used in CDSs to NDDSs. Efficient algorithms for ND-tree construction are presented. Our experimental results on synthetic and genomic sequence data demonstrate that the performance of the ND-tree is significantly better than that of the linear scan and M-tree in high dimensional NDDSs.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {620–631},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315506,
author = {Gao, Dengfeng and Snodgrass, Richard T.},
title = {Temporal Slicing in the Evaluation of XML Queries},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {As with relational data, XML data changes over time with the creation, modification, and deletion of XML documents. Expressing queries on time-varying (relational or XML) data is more difficult than writing queries on nontemporal data. In this paper, we present a temporal XML query language, τXQuery, in which we add valid time support to XQuery by minimally extending the syntax and semantics of XQuery. We adopt a stratum approach which maps a τXQuery query to a conventional XQuery. The paper focuses on how to perform this mapping, in particular, on mapping sequenced queries, which are by far the most challenging. The critical issue of supporting sequenced queries (in any query language) is time-slicing the input data while retaining period timestamping. Timestamps are distributed throughout an XML document, rather than uniformly in tuples, complicating the temporal slicing while also providing opportunities for optimization. We propose four optimizations of our initial maximally-fragmented time-slicing approach: selected node slicing, copy-based per-expression slicing, in-place per-expression slicing, and idiomatic slicing, each of which reduces the number of constant periods over which the query is evaluated. While performance tradeoffs clearly depend on the underlying XQuery engine, we argue that there are queries that favor each of the five approaches.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {632–643},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315507,
author = {Tsois, Aris and Sellis, Timos},
title = {The Generalized Pre-Grouping Transformation: Aggregate-Query Optimization in the Presence of Dependencies},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {One of the recently proposed techniques for the efficient evaluation of OLAP aggregate queries is the usage of clustering access methods. These methods store the fact table of a data warehouse clustered according to the dimension hierarchies using special attributes called hierarchical surrogate keys. In the presence of these access methods new processing and optimization techniques have been recently proposed. One important such optimization technique, called Hierarchical Pre-Grouping, uses the hierarchical surrogate keys in order to aggregate the fact table tuples as early as possible and to avoid redundant joins.In this paper, we study the Pre-Grouping transformation, attempting to generalize its applicability and identify its relationship to other similar transformations. Our results include a general algebraic definition of the Pre-Grouping transformation along with the formal definition of sufficient conditions for applying the transformation. Using a provided theorem we show that Pre-Grouping can be applied in the presence of functional and inclusion dependencies without the explicit usage of hierarchical surrogate keys. An additional result of our study is the definition of the Surrogate-Join transformation that can modify a join condition using a number of dependencies. To our knowledge, Surrogate-Join does not belong to any of the Semantic Query Transformation types discussed in the past.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {644–655},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315508,
author = {Helmer, Sven and Neumann, Thomas and Moerkotte, Guido},
title = {Estimating the Output Cardinality of Partial Preaggregation with a Measure of Clusteredness},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We introduce a new parameter, the clusteredness of data, and show how it can be used for estimating the output cardinality of a partial preaggregation operator. This provides the query optimizer with an important piece of information for deciding whether the application of partial preaggregation is beneficial. Experimental results are very promising, due to the high accuracy of the cardinality estimation based on our measure of clusteredness.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {656–667},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315509,
author = {Brown, Paul G. and Hass, Peter J.},
title = {BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We present the BHUNT scheme for automatically discovering algebraic constraints between pairs of columns in relational data. The constraints may be "fuzzy" in that they hold for most, but not all, of the records, and the columns may be in the same table or different tables. Such constraints are of interest in the context of both data mining and query optimization, and the BHUNT methodology can potentially be adapted to discover fuzzy functional dependencies and other useful relationships. BHUNT first identifies candidate sets of column value pairs that are likely to satisfy an algebraic constraint. This discovery process exploits both system catalog information and data samples, and employs pruning heuristics to control processing costs. For each candidate, BHUNT constructs algebraic constraints by applying statistical histogramming, segmentation, or clustering techniques to samples of column values. Using results from the theory of tolerance intervals, the sample sizes can be chosen to control the number of "exception" records that fail to satisfy the discovered constraints. In query-optimization mode, BHUNT can automatically partition the data into normal and exception records. During subsequent query processing, queries can be modified to incorporate the constraints; the optimizer uses the constraints to identify new, more efficient access paths. The results are then combined with the results of executing the original query against the (small) set of exception records. Experiments on a very large database using a prototype implementation of BHUNT show reductions in table accesses of up to two orders of magnitude, leading to speedups in query processing by up to a factor of 6.8.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {668–679},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315510,
author = {Yu, Hailing and Agrawal, Divyakant and El Abbadi, Amr},
title = {Tabular Placement of Relational Data on MEMS-Based Storage Devices},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Due to the advances in semiconductor manufacturing, the gap between main memory and secondary storage is constantly increasing. This becomes a significant performance bottleneck for Database Management Systems, which rely on secondary storage heavily to store large datasets. Recent advances in nanotechnology have led to the invention of alternative means for persistent storage. In particular, MicroElectroMechanical Systems (MEMS) based storage technology has emerged as the leading candidate for next generation storage systems. In order to integrate MEMS-based storage into conventional computing platform, new techniques are needed for I/O scheduling and data placement.In the context of relational data, it has been observed that access to relations needs to be enabled in both row-wise as well as in columnwise fashions. In this paper, we exploit the physical characteristics of MEMS-based storage devices to develop a data placement scheme for relational data that enables retrieval in both row-wise and column-wise manner. We demonstrate that this data layout not only improves I/O utilization, but results in better cache performance.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {680–693},
numpages = {14},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315511,
author = {Anciaux, Nicolas and Bouganim, Luc and Pucheral, Philippe},
title = {Memory Requirements for Query Execution in Highly Constrained Devices},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Pervasive computing introduces data management requirements that must be tackled in a growing variety of lightweight computing devices. Personal folders on chip, networks of sensors and data hosted by autonomous mobile computers are different illustrations of the need for evaluating queries confined in hardware constrained computing devices. RAM is the most limiting factor in this context. This paper gives a thorough analysis of the RAM consumption problem and makes the following contributions. First, it proposes a query execution model that reaches a lower bound in terms of RAM consumption. Second, it devises a new form of optimization, called iteration filter, that drastically reduces the prohibitive cost incurred by the preceding model, without hurting the RAM lower bound. Third, it analyses how the preceding techniques can benefit from an incremental growth of RAM. This work paves the way for setting up co-design rules helping to calibrate the RAM resource of a hardware platform according to given application's requirements as well as to adapt an application to an existing hardware platform. To the best of our knowledge, this work is the first attempt to devise co-design rules for data centric embedded applications. We illustrate the effectiveness of our techniques through a performance evaluation.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {694–705},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315512,
author = {Schindler, Jiri and Ailamaki, Anastassia and Ganger, Gregory R.},
title = {Lachesis: Robust Database Storage Management Based on Device-Specific Performance Characteristics},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Database systems work hard to tune I/O performance, but do not always achieve the full performance potential of modern disk systems. Their abstracted view of storage components hides useful device-specific characteristics, such as disk track boundaries and advanced built-in firmware algorithms. This paper presents a new storage manager architecture, called Lachesis, that exploits and adapts to observable device-specific characteristics in order to achieve and sustain high performance. For DSS queries, Lachesis achieves I/O efficiency nearly equivalent to sequential streaming even in the presence of competing random I/O traffic. In addition, Lachesis simplifies manual configuration and restores the optimizer's assumptions about the relative costs of different access patterns expressed in query plans. Experiments using IBM DB2 I/O traces as well as a prototype implementation show that Lachesis improves standalone DSS performance by 10% on average. More importantly, when running concurrently with an on-line transaction processing (OLTP) workload, Lachesis improves DSS performance by up to 3\texttimes{}, while OLTP also exhibits a 7% speedup.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {706–717},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315513,
author = {Altinel, Mehmet and Bornh\"{o}vd, Christof and Krishnamurthy, Sailesh and Mohan, C. and Pirahesh, Hamid and Reinwald, Berthold},
title = {Cache Tables: Paving the Way for an Adaptive Database Cache},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We introduce a new database object called Cache Table that enables persistent caching of the full or partial content of a remote database table. The content of a cache table is either defined declaratively and populated in advance at setup time, or determined dynamically and populated on demand at query execution time. Dynamic cache tables exploit the characteristics of typical transactional web applications with a high volume of short transactions, simple equality predicates, and 3-4 way joins. Based on federated query processing capabilities, we developed a set of new technologies for database caching: cache tables, "Janus" (two-headed) query execution plans, cache constraints, and asynchronous cache population methods. Our solution supports transparent caching both at the edge of content-delivery networks and in the middle-tier of an enterprise application infrastructure, improving the response time, throughput and scalability of transactional web applications.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {718–729},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315514,
author = {Chaudhuri, Surajit and Ganesan, Prasanna and Narasayya, Vivek},
title = {Primitives for Workload Summarization and Implications for SQL},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Workload information has proved to be a crucial component for database-administration tasks as well as for analysis of query logs to understand user behavior and system usage. These tasks require the ability to summarize large SQL workloads. In this paper, we identify primitives that are important to enable many important workload-summarization tasks. These primitives also appear to be useful in a variety of practical scenarios besides workload summarization. Today's SQL is inadequate to express these primitives conveniently. We discuss possible extensions to SQL and the relational engine to efficiently support such summarization primitives.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {730–741},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315515,
author = {Vieira, Marco and Madeira, Henrique},
title = {A Dependability Benchmark for OLTP Application Environments},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The ascendance of networked information in our economy and daily lives has increased the awareness of the importance of dependability features. OLTP (On-Line Transaction Processing) systems constitute the kernel of the information systems used today to support the daily operations of most of the business. Although these systems comprise the best examples of complex business-critical systems, no practical way has been proposed so far to characterize the impact of faults in such systems or to compare alternative solutions concerning dependability features. This paper proposes a dependability benchmark for OLTP systems. This dependability benchmark uses the workload of the TPC-C performance benchmark and specifies the measures and all the steps required to evaluate both the performance and key dependability features of OLTP systems, with emphasis on availability. This dependability benchmark is presented through a concrete example of benchmarking the performance and dependability of several different transactional systems configurations. The effort required to run the dependability benchmark is also discussed in detail.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {742–753},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315516,
author = {Ilyas, Ihab F. and Aref, Walid G. and Elmagarmid, Ahmed K.},
title = {Supporting Top-K Join Queries in Relational Databases},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Ranking queries produce results that are ordered on some computed score. Typically, these queries involve joins, where users are usually interested only in the top-k join results. Current relational query processors do not handle ranking queries efficiently, especially when joins are involved. In this paper, we address supporting top-k join queries in relational query processors. We introduce a new rank-join algorithm that makes use of the individual orders of its inputs to produce join results ordered on a user-specified scoring function. The idea is to rank the join results progressively during the join operation. We introduce two physical query operators based on variants of ripple join that implement the rank-join algorithm. The operators are nonblocking and can be integrated into pipelined execution plans. We address several practical issues and optimization heuristics to integrate the new join operators in practical query processors. We implement the new operators inside a prototype database engine based on PREDATOR. The experimental evaluation of our approach compares recent algorithms for joining ranked inputs and shows superior performance.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {754–765},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315517,
author = {Hulgeri, Arvind and Sudarshan, S.},
title = {AniPQO: Almost Non-Intrusive Parametric Query Optimization for Nonlinear Cost Functions},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The cost of a query plan depends on many parameters, such as predicate selectivities and available memory, whose values may not be known at optimization time. Parametric query optimization (PQO) optimizes a query into a number of candidate plans, each optimal for some region of the parameter space. We propose a heuristic solution for the PQO problem for the case when the cost functions may be nonlinear in the given parameters. This solution is minimally intrusive in the sense that an existing query optimizer can be used with minor modifications. We have implemented the heuristic and the results of the tests on the TPCD benchmark indicate that the heuristic is very effective. The minimal intrusiveness, generality in terms of cost functions and number of parameters and good performance (up to 4 parameters) indicate that our solution is of significant practical importance.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {766–777},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315518,
author = {Guha, Sudipto and Gunopoulos, Dimitrios and Koudas, Nick and Srivastava, Divesh and Vlachos, Michail},
title = {Efficient Approximation of Optimization Queries under Parametric Aggregation Constraints},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We introduce and study a new class of queries that we refer to as OPAC (optimization under parametric aggregation constraints) queries. Such queries aim to identify sets of database tuples that constitute solutions of a large class of optimization problems involving the database tuples. The constraints and the objective function are specified in terms of aggregate functions of relational attributes, and the parameter values identify the constants used in the aggregation constraints.We develop algorithms that preprocess relations and construct indices to efficiently provide answers to OPAC queries. The answers returned by our indices are approximate, not exact, and provide guarantees for their accuracy. Moreover, the indices can be tuned easily to meet desired accuracy levels, providing a graceful tradeoff between answer accuracy and index space. We present the results of a thorough experimental evaluation analyzing the impact of several parameters on the accuracy and performance of our techniques. Our results indicate that our methodology is effective and can be deployed easily, utilizing index structures such as R-trees.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {778–789},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315519,
author = {Tao, Yufei and Papadias, Dimitris and Sun, Jimeng},
title = {The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {A predictive spatio-temporal query retrieves the set of moving objects that will intersect a query window during a future time interval. Currently, the only access method for processing such queries in practice is the TPR-tree. In this paper we first perform an analysis to determine the factors that affect the performance of predictive queries and show that several of these factors are not considered by the TPR-tree, which uses the insertion/deletion algorithms of the R*-tree designed for static data. Motivated by this, we propose a new index structure called the TPR*- tree, which takes into account the unique features of dynamic objects through a set of improved construction algorithms. In addition, we provide cost models that determine the optimal performance achievable by any data-partition spatio-temporal access method. Using experimental comparison, we illustrate that the TPR*-tree is nearly-optimal and significantly outperforms the TPR-tree under all conditions.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {790–801},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315520,
author = {Papadias, Dimitris and Zhang, Jun and Mamoulis, Nikos and Tao, Yufei},
title = {Query Processing in Spatial Network Databases},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Despite the importance of spatial networks in real-life applications, most of the spatial database literature focuses on Euclidean spaces. In this paper we propose an architecture that integrates network and Euclidean information, capturing pragmatic constraints. Based on this architecture, we develop a Euclidean restriction and a network expansion framework that take advantage of location and connectivity to efficiently prune the search space. These frameworks are successfully applied to the most popular spatial queries, namely nearest neighbors, range search, closest pairs and e-distance joins, in the context of spatial network databases.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {802–813},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315521,
author = {Lin, Xuemin and Liu, Qing and Yuan, Yidong and Zhou, Xiaofang},
title = {Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this paper, we present several novel techniques to effectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important topological relations: contains, contained, overlap, and disjoint. We first present a novel framework to construct a multiscale histogram composed of multiple Euler histograms with the guarantee of the exact summarization results for aligned windows in constant time. Then we present an approximate algorithm, with the approximate ratio 19/12, to minimize the storage spaces of such multiscale Euler histograms, although the problem is generally NP-hard. To conform to a limited storage space where only k Euler histograms are allowed, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy. Finally, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. Our extensive experiments against both synthetic and real world datasets demonstrated that the approximate multiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost efficiency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for the real datasets.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {814–825},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315522,
author = {Wang, Xiaoyu and Cherniack, Mitch},
title = {Avoiding Sorting and Grouping in Processing Queries},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Sorting and grouping are amongst the most costly operations performed during query evaluation. System R [6] used simple inference strategies to determine orderings held of intermediate relations to avoid unnecessary sorting, and to influence join plan selection. Since then, others have proposed using integrity constraint information to infer orderings of intermediate query results. However, these proposals do not consider how to avoid grouping operations by inferring groupings, nor do they consider secondary orderings (where records in the same group satisfy some ordering). In this paper, we introduce a formalism for expressing and reasoning about order properties: ordering and grouping constraints that hold of physical representations of relations. In so doing, we can reason about how the relation is ordered or grouped, both in terms of primary and secondary orders. After formally defining order properties, we introduce a plan refinement algorithm that infers order properties for intermediate and final query results on the basis of those known to hold of query inputs, and then exploits these inferences to avoid unnecessary sorting and grouping. We then show empirical results demonstrating the benefits of plan refinement, and show that the overhead that our algorithm adds to query optimization is low.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {826–837},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315523,
author = {Carney, Don and \c{C}etintemel, U\u{g}ur and Rasin, Alex and Zdonik, Stan and Cherniack, Mitch and Stonebraker, Mike},
title = {Operator Scheduling in a Data Stream Manager},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Many stream-based applications have sophisticated data processing requirements and real-time performance expectations that need to be met under high-volume, time-varying data streams. In order to address these challenges, we propose novel operator scheduling approaches that specify (1) which operators to schedule (2) in which order to schedule the operators, and (3) how many tuples to process at each execution step. We study our approaches in the context of the Aurora data stream manager.We argue that a fine-grained scheduling approach in combination with various scheduling techniques (such as batching of operators and tuples) can significantly improve system efficiency by reducing various system overheads. We also discuss application-aware extensions that make scheduling decisions according to per-application Quality of Service (QoS) specifications. Finally, we present prototype-based experimental results that characterize the efficiency and effectiveness of our approaches under various stream workloads and processing scenarios.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {838–849},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315524,
author = {Hristidis, Vagelis and Gravano, Luis and Papakonstantinou, Yannis},
title = {Efficient IR-Style Keyword Search over Relational Databases},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Applications in which plain text coexists with structured data are pervasive. Commercial relational database management systems (RDBMSs) generally provide querying capabilities for text attributes that incorporate state-of-the-art information retrieval (IR) relevance ranking strategies, but this search functionality requires that queries specify the exact column or columns against which a given list of keywords is to be matched. This requirement can be cumbersome and inflexible from a user perspective: good answers to a keyword query might need to be "assembled" -in perhaps unforeseen ways- by joining tuples from multiple relations. This observation has motivated recent research on free-form keyword search over RDBMSs. In this paper, we adapt IR-style document-relevance ranking strategies to the problem of processing free-form keyword queries over RDBMSs. Our query model can handle queries with both AND and OR semantics, and exploits the sophisticated single-column text-search functionality often available in commercial RDBMSs. We develop query-processing strategies that build on a crucial characteristic of IR-style keyword search: only the few most relevant matches -according to some definition of "relevance"- are generally of interest. Consequently, rather than computing all matches for a keyword query, which leads to inefficient executions, our techniques focus on the top-k matches for the query, for moderate values of k. A thorough experimental evaluation over real data shows the performance advantages of our approach.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {850–861},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315525,
author = {Pottinger, Rachel A. and Bernstein, Philip A.},
title = {Merging Models Based on given Correspondences},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {A model is a formal description of a complex application artifact, such as a database schema, an application interface, a UML model, an ontology, or a message format. The problem of merging such models lies at the core of many meta data applications, such as view integration, mediated schema creation for data integration, and ontology merging. This paper examines the problem of merging two models given correspondences between them. It presents requirements for conducting a merge and a specific algorithm that subsumes previous work.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {862–873},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315526,
author = {Galanis, Leonidas and Wang, Yuan and Jeffery, Shawn R. and DeWitt, David J.},
title = {Locating Data Sources in Large Distributed Systems},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Querying large numbers of data sources is gaining importance due to increasing numbers of independent data providers. One of the key challenges is executing queries on all relevant information sources in a scalable fashion and retrieving fresh results. The key to scalability is to send queries only to the relevant servers and avoid wasting resources on data sources which will not provide any results. Thus, a catalog service, which would determine the relevant data sources given a query, is an essential component in efficiently processing queries in a distributed environment. This paper proposes a catalog framework which is distributed across the data sources themselves and does not require any central infrastructure. As new data sources become available, they automatically become part of the catalog service infrastructure, which allows scalability to large numbers of nodes. Furthermore, we propose techniques for workload adaptability. Using simulation and real-world data we show that our approach is valid and can scale to thousands of data sources.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {874–885},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315527,
author = {Jermaine, Christopher},
title = {Robust Estimation with Sampling and Approximate Pre-Aggregation},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The majority of data reduction techniques for approximate query processing (such as wavelets, histograms, kernels, and so on) are not usually applicable to categorical data. There has been something of a disconnect between research in this area and the reality of data-base data; much recent research has focused on approximate query processing over ordered or numerical attributes, but arguably the majority of database attributes are categorical: country, state, job_title, color, sex, department, and so on.This paper considers the problem of approximation of aggregate functions over categorical data, or mixed categorical/numerical data. We propose a method based upon random sampling, called Approximate Pre-Aggregation (APA). The biggest drawback of sampling for aggregate function estimating is the sensitivity of sampling to attribute value skew, and APA uses several techniques to overcome this sensitivity. The increase in accuracy using APA compared to "plain vanilla" sampling is dramatic. For SUM and AVG queries, the relative error for random sampling alone is more than 700% greater than for sampling with APA. Even if stratified sampling techniques are used, the error is still between 28% and 175% greater than for APA.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {886–897},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315528,
author = {Miklau, Gerome and Suciu, Dan},
title = {Controlling Access to Published Data Using Cryptography},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We propose a framework for enforcing access control policies on published XML documents using cryptography. In this framework the owner publishes a single data instance, which is partially encrypted, and which enforces all access control policies. Our contributions include a declarative language for access policies, and the resolution of these policies into a logical "protection model" which protects an XML tree with keys. The data owner enforces an access control policy by granting keys to users. The model is quite powerful, allowing the data owner to describe complex access scenarios, and is also quite elegant, allowing logical optimizations to be described as rewriting rules. Finally, we describe cryptographic techniques for enforcing the protection model on published data, and provide a performance analysis using real datasets.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {898–909},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315529,
author = {Meek, Colin and Patel, Jignesh M. and Kasetty, Shruti},
title = {OASIS: An Online and Accurate Technique for Local-Alignment Searches on Biological Sequences},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {A common query against large protein and gene sequence data sets is to locate targets that are similar to an input query sequence. The current set of popular search tools, such as BLAST, employ heuristics to improve the speed of such searches. However, such heuristics can sometimes miss targets, which in many cases is undesirable. The alternative to BLAST is to use an accurate algorithm, such as the Smith-Waterman (S-W) algorithm. However, these accurate algorithms are computationally very expensive, which limits their use in practice. This paper takes on the challenge of designing an accurate and efficient algorithm for evaluating local-alignment searches.To meet this goal, we propose a novel search algorithm, called OASIS. This algorithm employs a dynamic programming A*-search driven by a suffix-tree index that is built on the input data set. We experimentally evaluate OASIS and demonstrate that for an important class of searches, in which the query sequence lengths are small, OASIS is more than an order of magnitude faster than S-W. In addition, the speed of OASIS is comparable to BLAST. Furthermore, OASIS returns results in decreasing order of the matching score, making it possible to use OASIS in an online setting. Consequently, we believe that it may now be practically feasible to query large biological sequence data sets using an accurate local-alignment search algorithm.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {910–921},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315530,
author = {Bawa, Mayank and Bayardo, Roberto J. and Agrawal, Rakesh},
title = {Privacy-Preserving Indexing of Documents on the Network},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We address the problem of providing privacy-preserving search over distributed access-controlled content. Indexed documents can be easily reconstructed from conventional (inverted) indexes used in search. The need to avoid breaches of access-control through the index requires the index hosting site to be fully secured and trusted by by all participating content providers. This level of trust is impractical in the increasingly common case where multiple competing organizations or individuals wish to selectively share content. We propose a solution that eliminates the need of such a trusted authority. The solution builds a centralized privacy-preserving index in conjunction with a distributed access-control enforcing search protocol. The new index provides strong and quantifiable privacy guarantees that hold even if the entire index is made public. Experiments on a real-life dataset validate performance of the scheme. The appeal of our solution is two-fold: (a) Content providers maintain complete control in defining access groups and ensuring its compliance, and (b) System implementors retain tunable knobs to balance privacy and efficiency concerns for their particular domains.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {922–933},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315531,
author = {Poess, Meikel and Potapov, Dmitry},
title = {Data Compression in Oracle},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The Oracle RDBMS recently introduced an innovative compression technique for reducing the size of relational tables. By using a compression algorithm specifically designed for relational data, Oracle is able to compress data much more effectively than standard compression techniques. More significantly, unlike other compression techniques, Oracle incurs virtually no performance penalty for SQL queries accessing compressed tables. In fact, Oracle's compression may provide performance gains for queries accessing large amounts of data, as well as for certain data management operations like backup and recovery. Oracle's compression algorithm is particularly well-suited for data warehouses: environments, which contains large volumes of historical data, with heavy query workloads. Compression can enable a data warehouse to store several times more raw data without increasing the total disk storage or impacting query performance.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {937–947},
numpages = {11},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315532,
author = {An, Ning and Kanth, Ravi and Kothuri, V. and Ravada, Siva},
title = {Improving Performance with Bulk-Inserts in Oracle R-Trees},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {Spatial indexes play a major role in fast access to spatial and location data. Most commercial applications insert new data in bulk: in batches or arrays. In this paper, we propose a novel bulk insertion technique for R-Trees that is fast and does not compromise on the quality of the resulting index. We present our experiences with incorporating the proposed bulk insertion strategies into Oracle 10i. Experiments with real datasets show that our bulk insertion strategy improves performance of insert operations by 50%-90%.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {948–951},
numpages = {4},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315533,
author = {Galindo-Legaria, C\'{e}sar A. and Joshi, Milind M. and Waas, Florian and Wu, Ming-Chuan},
title = {Statistics on Views},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The quality of execution plans generated by a query optimizer is tied to the accuracy of its cardinality estimation. Errors in estimation lead to poor performance, erratic behavior, and user frustration. Traditionally, the optimizer is restricted to use only statistics on base table columns and derive estimates bottom-up. This approach has shortcomings with dealing with complex queries, and with rich languages such as SQL: Errors grow as estimation is done on top of estimation, and some constructs are simply not handled.In this paper we describe the creation and utilization of statistics on views in SQL Server, which provides the optimizer with statistical information on the result of scalar or relational expressions. It opens a new dimension on the data available for cardinality estimation and enables arbitrary correction. We describe the implementation of this feature in the optimizer architecture, and show its impact on the quality of plans generated through a number of examples.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {952–962},
numpages = {11},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315534,
author = {Bhattacharjee, Bishwaranjan and Padmanabhan, Sriram and Malkemus, Timothy and Lai, Tony and Cranston, Leslie and Huras, Matthew},
title = {Efficient Query Processing for Multi-Dimensionally Clustered Tables in DB2},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {We have introduced a Multi-Dimensional Clustering (MDC) physical layout scheme in DB2 version 8.0 for relational tables. Multi-Dimensional Clustering is based on the definition of one or more orthogonal clustering attributes (or expressions) of a table. The table is organized physically by associating records with similar values for the dimension attributes in a cluster. Each clustering key is allocated one or more blocks of physical storage with the aim of storing the multiple records belonging to the cluster in almost contiguous fashion. Block oriented indexes are created to access these blocks. In this paper, we describe novel techniques for query processing operations that provide significant performance improvements for MDC tables. Current database systems employ a repertoire of access methods including table scans, index scans, index ANDing, and index ORing. We have extended these access methods for efficiently processing the block based MDC tables. One important concept at the core of processing MDC tables is the block oriented access technique. In addition, since MDC tables can include regular record oriented indexes, we employ novel techniques to combine block and record indexes. Block oriented processing is extended to nested loop joins and star joins as well. We show results from experiments using a star-schema database to validate our claims of performance with minimal overhead.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {963–974},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315535,
author = {Srinivasa, Srinath and Kumar, Sujit},
title = {A Platform Based on the Multi-Dimensional Data Modal for Analysis of Bio-Molecular Structures},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {A platform called AnMol for supporting analytical applications over structural data of large biomolecules is described. The term "biomolecular structure" has various connotations and different representations. AnMol reduces these representations into graph structures. Each of these graphs are then stored as one or more vectors in a database. Vectors encapsulate structural features of these graphs. Structural queries like similarity and substructure are transformed into spatial constructs like distance and containment within regions. Query results are based on inexact matches. A refinement mechanism is supported for increasing accuracy of the results. Design and implementation issues of AnMol including schema structure and performance results are discussed in this paper.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {975–986},
numpages = {12},
keywords = {biomolecular structures, layered star schema, OLAP, bectorization of structure},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315536,
author = {Liu, Chengfei and Lindsay, Bruce G. and Bourbonnais, Serge and Hamel, Elizabeth B. and Truong, Tuong C. and Stankiewitz, Jens},
title = {Capturing Global Transactions from Multiple Recovery Log Files in a Partitioned Database System},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {DB2 DataPropagator is one of the IBM's solutions for asynchronous replication of relational data by two separate programs Capture and Apply. The Capture program captures changes made to source data from recovery log files into staging tables, while the Apply program applies the changes from the staging tables to target data. Currently the Capture program only supports capturing changes made by local transactions in a single database log file. With the increasing deployment of partitioned database systems in OLTP environments there is a need to replicate the operational data from the partitioned systems. This paper introduces a system called CaptureEEE which extends the Capture program to capture global transactions executed on partitioned databases supported by DB2 Enterprise-Extended Edition. The architecture and the components of CaptureEEE are presented. The algorithm for merging log entries from multiple recovery log files is discussed in detail.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {987–996},
numpages = {10},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315537,
author = {Florescu, Daniela and Hillery, Chris and Kossmann, Donald and Lucas, Paul and Riccardi, Fabio and Westmann, Till and Carey, Michael J. and Sundararajan, Arvind and Agrawal, Geetika},
title = {The BEA/XQRL Streaming XQuery Processor},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {In this paper, we describe the design, implementation, and performance characteristics of a complete, industrial-strength XQuery engine, the BEA streaming XQuery processor. The engine was designed to provide very high performance for message processing applications, i.e., for transforming XML data streams, and it is a central component of the 8.1 release of BEA's WebLogic Integration (WLI) product. This XQuery engine is fully compliant with the August 2002 draft of the W3C XML Query Language specification. A goal of this paper is to describe how an efficient, fully compliant XQuery engine can be built from a few relatively simple components and well-understood technologies.},
booktitle = {Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29},
pages = {997–1008},
numpages = {12},
location = {Berlin, Germany},
series = {VLDB '03}
}

@inproceedings{10.5555/1315451.1315538,
author = {Murthy, Ravi and Banerjee, Sandeepan},
title = {Xml Schemas in Oracle XML DB},
year = {2003},
isbn = {0127224424},
publisher = {VLDB Endowment},
abstract = {The W3C XML Scheme language is becomimg increasingly popular for expressing the data model for