text:
@inproceedings{10.1145/1007568.1007570,
author = {Gray, Jim},
title = {The next Database Revolution},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007570},
doi = {10.1145/1007568.1007570},
abstract = {Database system architectures are undergoing revolutionary changes. Most importantly, algorithms and data are being unified by integrating programming languages with the database system. This gives an extensible object-relational system where non-procedural relational operators manipulate object sets. Coupled with this, each DBMS is now a web service. This has huge implications for how we structure applications. DBMSs are now object containers. Queues are the first objects to be added. These queues are the basis for transaction processing and workflow applications. Future workflow systems are likely to be built on this core. Data cubes and online analytic processing are now baked into most DBMSs. Beyond that, DBMSs have a framework for data mining and machine learning algorithms. Decision trees, Bayes nets, clustering, and time series analysis are built in; new algorithms can be added. There is a rebirth of column stores for sparse tables and to optimize bandwidth. Text, temporal, and spatial data access methods, along with their probabilistic reasoning have been added to database systems. Allowing approximate and probabilistic answers is essential for many applications. Many believe that XML and xQuery will be the main data structure and access pattern. Database systems must accommodate that perspective. External data increasingly arrives as streams to be compared to historical data; so stream-processing operators are being added to the DBMS. Publish-subscribe systems invert the data-query ratios; incoming data is compared against millions of queries rather than queries searching millions of records. Meanwhile, disk and memory capacities are growing much faster than their bandwidth and latency, so the database systems increasingly use huge main memories and sequential disk access. These changes mandate a much more dynamic query optimization strategy - one that adapts to current conditions and selectivities rather than having a static plan. Intelligence is moving to the periphery of the network. Each disk and each sensor will be a competent database machine. Relational algebra is a convenient way to program these systems. Database systems are now expected to be self-managing, self-healing, and always-up. We researchers and developers have our work cut out for us in delivering all these features.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {1–4},
numpages = {4},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007571,
author = {Maurer, Ueli},
title = {The Role of Cryptography in Database Security},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007571},
doi = {10.1145/1007568.1007571},
abstract = {In traditional database security research, the database is usually assumed to be trustworthy. Under this assumption, the goal is to achieve security against external attacks (e.g. from hackers) and possibly also against users trying to obtain information beyond their privileges, for instance by some type of statistical inference. However, for many database applications such as health information systems there exist conflicting interests of the database owner and the users or organizations interacting with the database, and also between the users. Therefore the database cannot necessarily be assumed to be fully trusted.In this extended abstract we address the problem of defining and achieving security in a context where the database is not fully trusted, i.e., when the users must be protected against a potentially malicious database. Moreover, we address the problem of the secure aggregation of databases owned by mutually mistrusting organisations, for example by competing companies.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {5–10},
numpages = {6},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007573,
author = {Jain, Ankur and Chang, Edward Y. and Wang, Yuan-Fang},
title = {Adaptive Stream Resource Management Using Kalman Filters},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007573},
doi = {10.1145/1007568.1007573},
abstract = {To answer user queries efficiently, a stream management system must handle continuous, high-volume, possibly noisy, and time-varying data streams. One major research area in stream management seeks to allocate resources (such as network bandwidth and memory) to query plans, either to minimize resource usage under a precision requirement, or to maximize precision of results under resource constraints. To date, many solutions have been proposed; however, most solutions are ad hoc with hard-coded heuristics to generate query plans. In contrast, we perceive stream resource management as fundamentally a filtering problem, in which the objective is to filter out as much data as possible to conserve resources, provided that the precision standards can be met. We select the Kalman Filter as a general and adaptive filtering solution for conserving resources. The Kalman Filter has the ability to adapt to various stream characteristics, sensor noise, and time variance. Furthermore, we realize a significant performance boost by switching from traditional methods of caching static data (which can soon become stale) to our method of caching dynamic procedures that can predict data reliably at the server without the clients' involvement. In this work we focus on minimization of communication overhead for both synthetic and real-world streams. Through examples and empirical studies, we demonstrate the flexibility and effectiveness of using the Kalman Filter as a solution for managing trade-offs between precision of results and resources in satisfying stream queries.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {11–22},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007574,
author = {Wu, Huanmei and Salzberg, Betty and Zhang, Donghui},
title = {Online Event-Driven Subsequence Matching over Financial Data Streams},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007574},
doi = {10.1145/1007568.1007574},
abstract = {Subsequence similarity matching in time series databases is an important research area for many applications. This paper presents a new approximate approach for automatic online subsequence similarity matching over massive data streams. With a simultaneous on-line segmentation and pruning algorithm over the incoming stream, the resulting piecewise linear representation of the data stream features high sensitivity and accuracy. The similarity definition is based on a permutation followed by a metric distance function, which provides the similarity search with flexibility, sensitivity and scalability. Also, the metric-based indexing methods can be applied for speed-up. To reduce the system burden, the event-driven similarity search is performed only when there is a potential event. The query sequence is the most recent subsequence of piecewise data representation of the incoming stream which is automatically generated by the system. The retrieved results can be analyzed in different ways according to the requirements of specific applications. This paper discusses an application for future data movement prediction based on statistical information. Experiments on real stock data are performed. The correctness of trend predictions is used to evaluate the performance of subsequence similarity matching.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {23–34},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007575,
author = {Cormode, Graham and Johnson, Theodore and Korn, Flip and Muthukrishnan, S. and Spatscheck, Oliver and Srivastava, Divesh},
title = {Holistic UDAFs at Streaming Speeds},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007575},
doi = {10.1145/1007568.1007575},
abstract = {Many algorithms have been proposed to approximate holistic aggregates, such as quantiles and heavy hitters, over data streams. However, little work has been done to explore what techniques are required to incorporate these algorithms in a data stream query processor, and to make them useful in practice.In this paper, we study the performance implications of using user-defined aggregate functions (UDAFs) to incorporate selection-based and sketch-based algorithms for holistic aggregates into a data stream management system's query processing architecture. We identify key performance bottlenecks and tradeoffs, and propose novel techniques to make these holistic UDAFs fast and space-efficient for use in high-speed data stream applications. We evaluate performance using generated and actual IP packet data, focusing on approximating quantiles and heavy hitters. The best of our current implementations can process streaming queries at OC48 speeds (2x 2.4Gbps).},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {35–46},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007577,
author = {Chen, Yi and Davidson, Susan B. and Zheng, Yifeng},
title = {BLAS: An Efficient XPath Processing System},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007577},
doi = {10.1145/1007568.1007577},
abstract = {We present BLAS, a Bi-LAbeling based System, for efficiently processing complex XPath queries over XML data. BLAS uses P-labeling to process queries involving consecutive child axes, and D-labeling to process queries involving descendant axes traversal. The XML data is stored in labeled form, and indexed to optimize descendent axis traversals. Three algorithms are presented for translating complex XPath queries to SQL expressions, and two alternate query engines are provided. Experimental results demonstrate that the BLAS system has a substantial performance improvement compared to traditional XPath processing using D-labeling.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {47–58},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007578,
author = {Jiang, Haifeng and Lu, Hongjun and Wang, Wei},
title = {Efficient Processing of XML Twig Queries with OR-Predicates},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007578},
doi = {10.1145/1007568.1007578},
abstract = {An XML twig query, represented as a labeled tree, is essentially a complex selection predicate on both structure and content of an XML document. Twig query matching has been identified as a core operation in querying tree-structured XML data. A number of algorithms have been proposed recently to process a twig query holistically. Those algorithms, however, only deal with twig queries without OR-predicates. A straightforward approach that first decomposes a twig query with OR-predicates into multiple twig queries without OR-predicates and then combines their results is obviously not optimal in most cases. In this paper, we study novel holistic-processing algorithms for twig queries with OR-predicates without decomposition. In particular, we present a merge-based algorithm for sorted XML data and an index-based algorithm for indexed XML data. We show that holistic processing is much more efficient than the decomposition approach. Furthermore, we show that using indexes can significantly improve the performance for matching twig queries with OR-predicates, especially when the queries have large inputs but relatively small outputs.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {59–70},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007579,
author = {Paparizos, Stelios and Wu, Yuqing and Lakshmanan, Laks V. S. and Jagadish, H. V.},
title = {Tree Logical Classes for Efficient Evaluation of XQuery},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007579},
doi = {10.1145/1007568.1007579},
abstract = {XML is widely praised for its flexibility in allowing repeated and missing sub-elements. However, this flexibility makes it challenging to develop a bulk algebra, which typically manipulates sets of objects with identical structure. A set of XML elements, say of type book, may have members that vary greatly in structure, e.g. in the number of author sub-elements. This kind of heterogeneity may permeate the entire document in a recursive fashion: e.g., different authors of the same or different book may in turn greatly vary in structure. Even when the document conforms to a schema, the flexible nature of schemas for XML still allows such significant variations in structure among elements in a collection. Bulk processing of such heterogeneous sets is problematic.In this paper, we introduce the notion of logical classes (LC) of pattern tree nodes, and generalize the notion of pattern tree matching to handle node logical classes. This abstraction pays off significantly in allowing us to reason with an inherently heterogeneous collection of elements in a uniform, homogeneous way. Based on this, we define a Tree Logical Class (TLC) algebra that is capable of handling the heterogeneity arising in XML query processing, while avoiding redundant work. We present an algorithm to obtain a TLC algebra expression from an XQuery statement (for a large fragment of XQuery). We show how to implement the TLC algebra efficiently, introducing the nest-join as an important physical operator for XML query processing. We show that evaluation plans generated using the TLC algebra not only are simpler but also perform better than those generated by competing approaches. TLC is the algebra used in the Timber [8] system developed at the University of Michigan.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {71–82},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007581,
author = {Amer-Yahia, Sihem and Lakshmanan, Laks V. S. and Pandit, Shashank},
title = {FleXPath: Flexible Structure and Full-Text Querying for XML},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007581},
doi = {10.1145/1007568.1007581},
abstract = {Querying XML data is a well-explored topic with powerful database-style query languages such as XPath and XQuery set to become W3C standards. An equally compelling paradigm for querying XML documents is full-text search on textual content. In this paper, we study fundamental challenges that arise when we try to integrate these two querying paradigms.While keyword search is based on approximate matching, XPath has exact match semantics. We address this mismatch by considering queries on structure as a "template", and looking for answers that best match this template and the full-text search. To achieve this, we provide an elegant definition of relaxation on structure and define primitive operators to span the space of relaxations. Query answering is now based on ranking potential answers on structural and full-text search conditions. We set out certain desirable principles for ranking schemes and propose natural ranking schemes that adhere to these principles. We develop efficient algorithms for answering top-K queries and discuss results from a comprehensive set of experiments that demonstrate the utility and scalability of the proposed framework and algorithms.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {83–94},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007582,
author = {Wu, Wensheng and Yu, Clement and Doan, AnHai and Meng, Weiyi},
title = {An Interactive Clustering-Based Approach to Integrating Source Query Interfaces on the Deep Web},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007582},
doi = {10.1145/1007568.1007582},
abstract = {An increasing number of data sources now become available on the Web, but often their contents are only accessible through query interfaces. For a domain of interest, there often exist many such sources with varied coverage or querying capabilities. As an important step to the integration of these sources, we consider the integration of their query interfaces. More specifically, we focus on the crucial step of the integration: accurately matching the interfaces. While the integration of query interfaces has received more attentions recently, current approaches are not sufficiently general: (a) they all model interfaces with flat schemas; (b) most of them only consider 1:1 mappings of fields over the interfaces; (c) they all perform the integration in a blackbox-like fashion and the whole process has to be restarted from scratch if anything goes wrong; and (d) they often require laborious parameter tuning. In this paper, we propose an interactive, clustering-based approach to matching query interfaces. The hierarchical nature of interfaces is captured with ordered trees. Varied types of complex mappings of fields are examined and several approaches are proposed to effectively identify these mappings. We put the human integrator back in the loop and propose several novel approaches to the interactive learning of parameters and the resolution of uncertain mappings. Extensive experiments are conducted and results show that our approach is highly effective.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {95–106},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007583,
author = {Zhang, Zhen and He, Bin and Chang, Kevin Chen-Chuan},
title = {Understanding Web Query Interfaces: Best-Effort Parsing with Hidden Syntax},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007583},
doi = {10.1145/1007568.1007583},
abstract = {Recently, the Web has been rapidly "deepened" by many searchable databases online, where data are hidden behind query forms. For modelling and integrating Web databases, the very first challenge is to understand what a query interface says- or what query capabilities a source supports. Such automatic extraction of interface semantics is challenging, as query forms are created autonomously. Our approach builds on the observation that, across myriad sources, query forms seem to reveal some "concerted structure," by sharing common building blocks. Toward this insight, we hypothesize the existence of a hidden syntax that guides the creation of query interfaces, albeit from different sources. This hypothesis effectively transforms query interfaces into a visual language with a non-prescribed grammar- and, thus, their semantic understanding a parsing problem. Such a paradigm enables principled solutions for both declaratively representing common patterns, by a derived grammar, and systematically interpreting query forms, by a global parsing mechanism. To realize this paradigm, we must address the challenges of a hypothetical syntax- that it is to be derived, and that it is secondary to the input. At the heart of our form extractor, we thus develop a 2P grammar and a best-effort parser, which together realize a parsing mechanism for a hypothetical syntax. Our experiments show the promise of this approach-it achieves above 85% accuracy for extracting query conditions across random sources.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {107–118},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007584,
author = {Lerman, Kristina and Getoor, Lise and Minton, Steven and Knoblock, Craig},
title = {Using the Structure of Web Sites for Automatic Segmentation of Tables},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007584},
doi = {10.1145/1007568.1007584},
abstract = {Many Web sites, especially those that dynamically generate HTML pages to display the results of a user's query, present information in the form of list or tables. Current tools that allow applications to programmatically extract this information rely heavily on user input, often in the form of labeled extracted records. The sheer size and rate of growth of the Web make any solution that relies primarily on user input is infeasible in the long term. Fortunately, many Web sites contain much explicit and implicit structure, both in layout and content, that we can exploit for the purpose of information extraction. This paper describes an approach to automatic extraction and segmentation of records from Web tables. Automatic methods do not require any user input, but rely solely on the layout and content of the Web source. Our approach relies on the common structure of many Web sites, which present information as a list or a table, with a link in each entry leading to a detail page containing additional information about that item. We describe two algorithms that use redundancies in the content of table and detail pages to aid in information extraction. The first algorithm encodes additional information provided by detail pages as constraints and finds the segmentation by solving a constraint satisfaction problem. The second algorithm uses probabilistic inference to find the record segmentation. We show how each approach can exploit the web site structure in a general, domain-independent manner, and we demonstrate the effectiveness of each algorithm on a set of twelve Web sites.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {119–130},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007586,
author = {Vlachos, Michail and Meek, Christopher and Vagena, Zografoula and Gunopulos, Dimitrios},
title = {Identifying Similarities, Periodicities and Bursts for Online Search Queries},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007586},
doi = {10.1145/1007568.1007586},
abstract = {We present several methods for mining knowledge from the query logs of the MSN search engine. Using the query logs, we build a time series for each query word or phrase (e.g., 'Thanksgiving' or 'Christmas gifts') where the elements of the time series are the number of times that a query is issued on a day. All of the methods we describe use sequences of this form and can be applied to time series data generally. Our primary goal is the discovery of semantically similar queries and we do so by identifying queries with similar demand patterns. Utilizing the best Fourier coefficients and the energy of the omitted components, we improve upon the state-of-the-art in time-series similarity matching. The extracted sequence features are then organized in an efficient metric tree index structure. We also demonstrate how to efficiently and accurately discover the important periods in a time-series. Finally we propose a simple but effective method for identification of bursts (long or short-term). Using the burst information extracted from a sequence, we are able to efficiently perform 'query-by-burst' on the database of time-series. We conclude the presentation with the description of a tool that uses the described methods, and serves as an interactive exploratory data discovery tool for the MSN query database.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {131–142},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007587,
author = {Cong, Gao and Tung, Anthony K. H. and Xu, Xin and Pan, Feng and Yang, Jiong},
title = {FARMER: Finding Interesting Rule Groups in Microarray Datasets},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007587},
doi = {10.1145/1007568.1007587},
abstract = {Microarray datasets typically contain large number of columns but small number of rows. Association rules have been proved to be useful in analyzing such datasets. However, most existing association rule mining algorithms are unable to efficiently handle datasets with large number of columns. Moreover, the number of association rules generated from such datasets is enormous due to the large number of possible column combinations.In this paper, we describe a new algorithm called FARMER that is specially designed to discover association rules from microarray datasets. Instead of finding individual association rules, FARMER finds interesting rule groups which are essentially a set of rules that are generated from the same set of rows. Unlike conventional rule mining algorithms, FARMER searches for interesting rules in the row enumeration space and exploits all user-specified constraints including minimum support, confidence and chi-square to support efficient pruning. Several experiments on real bioinformatics datasets show that FARMER is orders of magnitude faster than previous association rule mining algorithms.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {143–154},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007588,
author = {Cormode, Graham and Korn, Flip and Muthukrishnan, S. and Srivastava, Divesh},
title = {Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007588},
doi = {10.1145/1007568.1007588},
abstract = {Data items archived in data warehouses or those that arrive online as streams typically have attributes which take values from multiple hierarchies (e.g., time and geographic location; source and destination IP addresses). Providing an aggregate view of such data is important to summarize, visualize, and analyze. We develop the aggregate view based on certain hierarchically organized sets of large-valued regions ("heavy hitters"). Such Hierarchical Heavy Hitters (HHHs) were previously introduced as a crucial aggregation technique in one dimension. In order to analyze the wider range of data warehousing applications and realistic IP data streams, we generalize this problem to multiple dimensions.We identify and study two variants of HHHs for multi-dimensional data, namely the "overlap" and "split" cases, depending on how an aggregate computed for a child node in the multi-dimensional hierarchy is propagated to its parent element(s). For data warehousing applications, we present offline algorithms that take multiple passes over the data and produce the exact HHHs. For data stream applications, we present online algorithms that find approximate HHHs in one pass, with provable accuracy guarantees.We show experimentally, using real and synthetic data, that our proposed online algorithms yield outputs which are very similar (virtually identical, in many cases) to their offline counterparts. The lattice property of the product of hierarchical dimensions ("diamond") is crucially exploited in our online algorithms to track approximate HHHs using only a small, fixed number of statistics per candidate node, regardless of the number of dimensions.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {155–166},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007589,
author = {Chen, Lei and Huang, Zheng and Ramakrishnan, Raghu},
title = {Cost-Based Labeling of Groups of Mass Spectra},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007589},
doi = {10.1145/1007568.1007589},
abstract = {We make two main contributions in this paper. First, we motivate and introduce a novel class of data mining problems that arise in labeling a group of mass spectra, specifically for analysis of atmospheric aerosols, but with natural applications to market-basket datasets. This builds upon other recent work in which we introduced the problem of labeling a single spectrum, and is motivated by the advent of a new generation of Aerosol Time-of-Flight Spectrometers, which are capable of generating mass spectra for hundreds of aerosol particles per minute. We also describe two algorithms for group labeling, which differ greatly in how they utilize a linear programming (LP) solver, and also differ greatly from algorithms for labeling a single spectrum.Our second contribution is to show how to automatically select between these two algorithms in a cost-based manner, analogous to how a query optimizer selects from a space of query plans. While the details are specific to the labeling problem, we believe that is a promising first step towards a general framework for cost-based data mining, and opens up an important direction for future search.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {167–178},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007591,
author = {Bowman, Ivan T. and Salem, Kenneth},
title = {Optimization of Query Streams Using Semantic Prefetching},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007591},
doi = {10.1145/1007568.1007591},
abstract = {Streams of relational queries submitted by client applications to database servers contain patterns that can be used to predict future requests. We present the Scalpel system, which detects these patterns and optimizes request streams using context-based predictions of future requests. Scalpel uses its predictions to provide a form of semantic prefetching, which involves combining a predicted series of requests into a single request that can be issued immediately. Scalpel's semantic prefetching reduces not only the latency experienced by the application but also the total cost of query evaluation. We describe how Scalpel learns to predict optimizable request patterns by observing the application's request stream during a training phase. We also describe the types of query pattern rewrites that Scalpel's cost-based optimizer considers. Finally, we present empirical results that show the costs and benefits of Scalpel's optimizations.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {179–190},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007592,
author = {Zhou, Jingren and Ross, Kenneth A.},
title = {Buffering Databse Operations for Enhanced Instruction Cache Performance},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007592},
doi = {10.1145/1007568.1007592},
abstract = {As more and more query processing work can be done in main memory access is becoming a significant cost component of database operations. Recent database research has shown that most of the memory stalls are due to second-level cache data misses and first-level instruction cache misses. While a lot of research has focused on reducing the data cache misses, relatively little research has been done on improving the instruction cache performance of database systems.We first answer the question "Why does a database system incur so many instruction cache misses?" We demonstrate that current demand-pull pipelined query execution engines suffer from significant instruction cache thrashing between different operators. We propose techniques to buffer database operations during query execution to avoid instruction cache thrashing. We implement a new light-weight "buffer" operator and study various factors which may affect the cache performance. We also introduce a plan refinement algorithm that considers the query plan and decides whether it is beneficial to add additional "buffer" operators and where to put them. The benefit is mainly from better instruction locality and better hardware branch prediction. Our techniques can be easily integrated into current database systems without significant changes. Our experiments in a memory-resident PostgreSQL database system show that buffering techniques can reduce the number of instruction cache misses by up to 80% and improve query performance by up to 15%.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {191–202},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007593,
author = {Ilyas, Ihab F. and Shah, Rahul and Aref, Walid G. and Vitter, Jeffrey Scott and Elmagarmid, Ahmed K.},
title = {Rank-Aware Query Optimization},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007593},
doi = {10.1145/1007568.1007593},
abstract = {Ranking is an important property that needs to be fully supported by current relational query engines. Recently, several rank-join query operators have been proposed based on rank aggregation algorithms. Rank-join operators progressively rank the join results while performing the join operation. The new operators have a direct impact on traditional query processing and optimization.We introduce a rank-aware query optimization framework that fully integrates rank-join operators into relational query engines. The framework is based on extending the System R dynamic programming algorithm in both enumeration and pruning. We define ranking as an interesting property that triggers the generation of rank-aware query plans. Unlike traditional join operators, optimizing for rank-join operators depends on estimating the input cardinality of these operators. We introduce a probabilistic model for estimating the input cardinality, and hence the cost of a rank-join operator. To our knowledge, this paper is the first effort in estimating the needed input size for optimal rank aggregation algorithms. Costing ranking plans, although challenging, is key to the full integration of rank-join operators in real-world query processing engines. We experimentally evaluate our framework by modifying the query optimizer of an open-source database management system. The experiments show the validity of our framework and the accuracy of the proposed estimation model.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {203–214},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007594,
author = {Govindaraju, Naga K. and Lloyd, Brandon and Wang, Wei and Lin, Ming and Manocha, Dinesh},
title = {Fast Computation of Database Operations Using Graphics Processors},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007594},
doi = {10.1145/1007568.1007594},
abstract = {We present new algorithms for performing fast computation of several common database operations on commodity graphics processors. Specifically, we consider operations such as conjunctive selections, aggregations, and semi-linear queries, which are essential computational components of typical database, data warehousing, and data mining applications. While graphics processing units (GPUs) have been designed for fast display of geometric primitives, we utilize the inherent pipelining and parallelism, single instruction and multiple data (SIMD) capabilities, and vector processing functionality of GPUs, for evaluating boolean predicate combinations and semi-linear queries on attributes and executing database operations efficiently. Our algorithms take into account some of the limitations of the programming model of current GPUs and perform no data rearrangements. Our algorithms have been implemented on a programmable GPU (e.g. NVIDIA's GeForce FX 5900) and applied to databases consisting of up to a million records. We have compared their performance with an optimized implementation of CPU-based algorithms. Our experiments indicate that the graphics processor available on commodity computer systems is an effective co-processor for performing database operations.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {215–226},
numpages = {12},
keywords = {semi-linear query, selectivity analysis, selection query, aggregation, graphics processor, query optimization},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007596,
author = {Abiteboul, Serge and Benjelloun, Omar and Cautis, Bogdan and Manolescu, Ioana and Milo, Tova and Preda, Nicoleta},
title = {Lazy Query Evaluation for Active XML},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007596},
doi = {10.1145/1007568.1007596},
abstract = {In this paper, we study query evaluation on Active XML documents (AXML for short), a new generation of XML documents that has recently gained popularity. AXML documents are XML documents whose content is given partly extensionally, by explicit data elements, and partly intensionally, by embedded calls to Web services, which can be invoked to generate data.A major challenge in the efficient evaluation of queries over such documents is to detect which calls may bring data that is relevant for the query execution, and to avoid the materialization of irrelevant information. The problem is intricate, as service calls may be embedded anywhere in the document, and service invocations possibly return data containing calls to new services. Hence, the detection of relevant calls becomes a continuous process. Also, a good analysis must take the service signatures into consideration.We formalize the problem, and provide algorithms to solve it. We also present an implementation that is compliant with XML and Web services standards, and is used as part of the ActiveXML system. Finally, we experimentally measure the performance gains obtained by a careful filtering of the service calls to be triggered.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {227–238},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007597,
author = {Bose, Sujoe and Fegaras, Leonidas},
title = {Data Stream Management for Historical XML Data},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007597},
doi = {10.1145/1007568.1007597},
abstract = {We are presenting a framework for continuous querying of time-varying streamed XML data. A continuous stream in our framework consists of a finite XML document followed by a continuous stream of updates. The unit of update is an XML fragment, which can relate to other fragments through system-generated unique IDs. The reconstruction of temporal data from continuous updates at a current time is never materialized and historical queries operate directly on the fragmented streams. We are incorporating temporal constructs to XQuery with minimal changes to the existing language structure to support continuous querying of time-varying streams of XML data. Our extensions use time projections to capture time-sliding windows, version control for tuple-based windows, and coincidence queries to synchronize events between streams. These XQuery extensions are compiled away to standard XQuery code and the resulting queries operate continuously over the existing fragmented streams.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {239–250},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007598,
author = {Jagadish, H. V. and Lakshmanan, Laks V. S. and Scannapieco, Monica and Srivastava, Divesh and Wiwatwattana, Nuwee},
title = {Colorful XML: One Hierarchy Isn't Enough},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007598},
doi = {10.1145/1007568.1007598},
abstract = {XML has a tree-structured data model, which is used to uniformly represent structured as well as semi-structured data, and also enable concise query specification in XQuery, via the use of its XPath (twig) patterns. This in turn can leverage the recently developed technology of structural join algorithms to evaluate the query efficiently. In this paper, we identify a fundamental tension in XML data modeling: (i) data represented as deep trees (which can make effective use of twig patterns) are often un-normalized, leading to update anomalies, while (ii) normalized data tends to be shallow, resulting in heavy use of expensive value-based joins in queries.Our solution to this data modeling problem is a novel multi-colored trees (MCT) logical data model, which is an evolutionary extension of the XML data model, and permits trees with multi-colored nodes to signify their participation in multiple hierarchies. This adds significant semantic structure to individual data nodes. We extend XQuery expressions to navigate between structurally related nodes, taking color into account, and also to create new colored trees as restructurings of an MCT database. While MCT serves as a significant evolutionary extension to XML as a logical data model, one of the key roles of XML is for information exchange. To enable exchange of MCT information, we develop algorithms for optimally serializing an MCT database as XML. We discuss alternative physical representations for MCT databases, using relational and native XML databases, and describe an implementation on top of the Timber native XML database. Experimental evaluation, using our prototype implementation, shows that not only are MCT queries/updates more succinct and easier to express than equivalent shallow tree XML queries, but they can also be significantly more efficient to evaluate than equivalent deep and shallow tree XML queries/updates.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {251–262},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007599,
author = {Polyzotis, Neoklis and Garofalakis, Minos and Ioannidis, Yannis},
title = {Approximate XML Query Answers},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007599},
doi = {10.1145/1007568.1007599},
abstract = {The rapid adoption of XML as the standard for data representation and exchange foreshadows a massive increase in the amounts of XML data collected, maintained, and queried over the Internet or in large corporate data-stores. Inevitably, this will result in the development of on-line decision support systems, where users and analysts interactively explore large XML data sets through a declarative query interface (e.g., XQuery or XSLT). Given the importance of remaining interactive, such on-line systems can employ approximate query answers as an effective mechanism for reducing response time and providing users with early feedback. This approach has been successfully used in relational systems and it becomes even more compelling in the XML world, where the evaluation of complex queries over massive tree-structured data is inherently more expensive.In this paper, we initiate a study of approximate query answering techniques for large XML databases. Our approach is based on a novel, conceptually simple, yet very effective XML-summarization mechanism: TREESKETCH synopses. We demonstrate that, unlike earlier techniques focusing solely on selectivity estimation, our TREESKETCH synopses are much more effective in capturing the complete tree structure of the underlying XML database. We propose novel construction algorithms for building TREESKETCH summaries of limited size, and describe schemes for processing general XML twig queries over a concise TREESKETCH in order to produce very fast, approximate tree-structured query answers. To quantify the quality of such approximate answers, we propose a novel, intuitive error metric that captures the quality of the approximation in terms of both the overall structure of the XML tree and the distribution of document edges. Experimental results on real-life and synthetic data sets verify the effectiveness of our TREESKETCH synopses in producing fast, accurate approximate answers and demonstrate their benefits over previously proposed techniques that focus solely on selectivity estimation. In particular, TREESKETCHes yield faster, more accurate approximate answers and selectivity estimates, and are more efficient to construct. To the best of our knowledge, ours is the first work to address the timely problem of producing fast, approximate tree-structured answers for complex XML queries.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {263–274},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007601,
author = {Haas, Peter J. and K\"{o}nig, Christian},
title = {A Bi-Level Bernoulli Scheme for Database Sampling},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007601},
doi = {10.1145/1007568.1007601},
abstract = {Current database sampling methods give the user insufficient control when processing ISO-style sampling queries. To address this problem, we provide a bi-level Bernoulli sampling scheme that combines the row-level and page-level sampling methods currently used in most commercial systems. By adjusting the parameters of the method, the user can systematically trade off processing speed and statistical precision---the appropriate choice of parameter settings becomes a query optimization problem. We indicate the SQL extensions needed to support bi-level sampling and determine the optimal parameter settings for an important class of sampling queries with explicit time or accuracy constraints. As might be expected, row-level sampling is preferable when data values on each page are homogeneous, whereas page-level sampling should be used when data values on a page vary widely. Perhaps surprisingly, we show that in many cases the optimal sampling policy is of the "bang-bang" type: we identify a "page-heterogeneity index" (PHI) such that optimal sampling is as "row-like" as possible if the PHI is less than 1 and as "page-like" as possible otherwise. The PHI depends upon both the query and the data, and can be estimated by means of a pilot sample. Because pilot sampling can be nontrivial to implement in commercial database systems, we also give a heuristic method for setting the sampling parameters; the method avoids pilot sampling by using a small number of summary statistics that are maintained in the system catalog. Results from over 1100 experiments on 372 real and synthetic data sets show that the heuristic method performs optimally about half of the time, and yields sampling errors within a factor of 2.2 of optimal about 93% of the time. The heuristic method is stable over a wide range of sampling rates and performs best in the most critical cases, where the data is highly clustered or skewed.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {275–286},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007602,
author = {Chaudhuri, Surajit and Das, Gautam and Srivastava, Utkarsh},
title = {Effective Use of Block-Level Sampling in Statistics Estimation},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007602},
doi = {10.1145/1007568.1007602},
abstract = {Block-level sampling is far more efficient than true uniform-random sampling over a large database, but prone to significant errors if used to create database statistics. In this paper, we develop principled approaches to overcome this limitation of block-level sampling for histograms as well as distinct-value estimations. For histogram construction, we give a novel two-phase adaptive method in which the sample size required to reach a desired accuracy is decided based on a first phase sample. This method is significantly faster than previous iterative methods proposed for the same problem. For distinct-value estimation, we show that existing estimators designed for uniform-random samples may perform very poorly if used directly on block-level samples. We present a key technique that computes an appropriate subset of a block-level sample that is suitable for use with most existing estimators. This, to the best of our knowledge, is the first principled method for distinct-value estimation with block-level samples. We provide extensive experimental results validating our methods.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {287–298},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007603,
author = {Jermaine, Christopher and Pol, Abhijit and Arumugam, Subramanian},
title = {Online Maintenance of Very Large Random Samples},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007603},
doi = {10.1145/1007568.1007603},
abstract = {Random sampling is one of the most fundamental data management tools available. However, most current research involving sampling considers the problem of how to use a sample, and not how to compute one. The implicit assumption is that a "sample" is a small data structure that is easily maintained as new data are encountered, even though simple statistical arguments demonstrate that very large samples of gigabytes or terabytes in size can be necessary to provide high accuracy. No existing work tackles the problem of maintaining very large, disk-based samples from a data management perspective, and no techniques now exist for maintaining very large samples in an online manner from streaming data. In this paper, we present online algorithms for maintaining on-disk samples that are gigabytes or terabytes in size. The algorithms are designed for streaming data, or for any environment where a large sample must be maintained online in a single pass through a data set. The algorithms meet the strict requirement that the sample always be a true, statistically random sample (without replacement) of all of the data processed thus far. Our algorithms are also suitable for biased or unequal probability sampling.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {299–310},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007604,
author = {Bruno, Nicolas and Chaudhuri, Surajit},
title = {Conditional Selectivity for Statistics on Query Expressions},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007604},
doi = {10.1145/1007568.1007604},
abstract = {Cardinality estimation during query optimization relies on simplifying assumptions that usually do not hold in practice. To diminish the impact of inaccurate estimates during optimization, statistics on query expressions (SITs) have been previously proposed. These statistics help directly model the distribution of tuples on query sub-plans. Past work in statistics on query expressions has exploited view matching technology to harness their benefits. In this paper we argue against such an approach as it overlooks significant opportunities for improvement in cardinality estimations. We then introduce a framework to reason with SITs based on the notion of conditional selectivity. We present a dynamic programming algorithm to efficiently find the most accurate selectivity estimation for given queries, and discuss how such an approach can be incorporated into existing optimizers with a small number of changes. Finally, we demonstrate experimentally that our technique results in superior cardinality estimations than previous approaches with very little overhead.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {311–322},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007606,
author = {Graefe, Goetz and Zwilling, Michael},
title = {Transaction Support for Indexed Summary Views},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007606},
doi = {10.1145/1007568.1007606},
abstract = {Materialized views have become a standard technique for performance improvement in decision support databases and for a variety of monitoring purposes. In order to avoid inconsistencies and thus unpredictable query results, materialized views and their indexes should be maintained immediately within user transaction just like indexes on ordinary tables. Unfortunately, the smaller a materialized view is, the higher the concurrency contention between queries and updates as well as among concurrent updates. Therefore, we have investigated methods that reduce contention without forcing users to sacrifice serializability and thus predictable application semantics. These methods extend escrow locking with multi-granularity (hierarchical) locking, snapshot transactions, multi-version concurrency control, key range locking, and system transactions, i.e., multiple proven database implementation techniques. The complete design eliminates all contention between pure read transactions and pure update transactions as well as contention among pure update transactions as well as contention among pure update transactions; it enables maximal concurrency of mixed read-write transactions with other transactions; it supports bulk operations such as data import and online index creation; and it provides recovery for transaction, media, and system failures.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {323–334},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007607,
author = {Yan, Xifeng and Yu, Philip S. and Han, Jiawei},
title = {Graph Indexing: A Frequent Structure-Based Approach},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007607},
doi = {10.1145/1007568.1007607},
abstract = {Graph has become increasingly important in modelling complicated structures and schemaless data such as proteins, chemical compounds, and XML documents. Given a graph query, it is desirable to retrieve graphs quickly from a large database via graph-based indices. In this paper, we investigate the issues of indexing graphs and propose a novel solution by applying a graph mining technique. Different from the existing path-based methods, our approach, called gIndex, makes use of frequent substructure as the basic indexing feature. Frequent substructures are ideal candidates since they explore the intrinsic characteristics of the data and are relatively stable to database updates. To reduce the size of index structure, two techniques, size-increasing support constraint and discriminative fragments, are introduced. Our performance study shows that gIndex has 10 times smaller index size, but achieves 3--10 times better performance in comparison with a typical path-based method, GraphGrep. The gIndex approach not only provides and elegant solution to the graph indexing problem, but also demonstrates how database indexing and query processing can benefit form data mining, especially frequent pattern mining. Furthermore, the concepts developed here can be applied to indexing sequences, trees, and other complicated structures as well.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {335–346},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007608,
author = {Arge, Lars and de Berg, Mark and Haverkort, Herman J. and Yi, Ke},
title = {The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007608},
doi = {10.1145/1007568.1007608},
abstract = {We present the Priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using O((N/B)1 1/d + T/B) I/Os, where N is the number of d-dimensional (hyper-) rectangles stored in the R-tree, B is the disk block size, and T is the output size. This is provably asymptotically optimal and significantly better than other R-tree variants, where a query may visit all N/B leaves in the tree even when T = 0. We also present an extensive experimental study of the practical performance of the PR-tree using both real-life and synthetic data. This study shows that the PR-tree performs similar to the best known R-tree variants on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {347–358},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007609,
author = {Agrawal, Sanjay and Narasayya, Vivek and Yang, Beverly},
title = {Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007609},
doi = {10.1145/1007568.1007609},
abstract = {In addition to indexes and materialized views, horizontal and vertical partitioning are important aspects of physical design in a relational database system that significantly impact performance. Horizontal partitioning also provides manageability; database administrators often require indexes and their underlying tables partitioned identically so as to make common operations such as backup/restore easier. While partitioning is important, incorporating partitioning makes the problem of automating physical design much harder since: (a) The choices of partitioning can strongly interact with choices of indexes and materialized views. (b) A large new space of physical design alternatives must be considered. (c) Manageability requirements impose a new constraint on the problem. In this paper, we present novel techniques for designing a scalable solution to this integrated physical design problem that takes both performance and manageability into account. We have implemented our techniques and evaluated it on Microsoft SQL Server. Our experiments highlight: (a) the importance of taking an integrated approach to automated physical design and (b) the scalability of our techniques.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {359–370},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007611,
author = {Yu, Cong and Popa, Lucian},
title = {Constraint-Based XML Query Rewriting for Data Integration},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007611},
doi = {10.1145/1007568.1007611},
abstract = {We study the problem of answering queries through a target schema, given a set of mappings between one or more source schemas and this target schema, and given that the data is at the sources. The schemas can be any combination of relational or XML schemas, and can be independently designed. In addition to the source-to-target mappings, we consider as part of the mapping scenario a set of target constraints specifying additional properties on the target schema. This becomes particularly important when integrating data from multiple data sources with overlapping data and when such constraints can express data merging rules at the target. We define the semantics of query answering in such an integration scenario, and design two novel algorithms, basic query rewrite and query resolution, to implement the semantics. The basic query rewrite algorithm reformulates target queries in terms of the source schemas, based on the mappings. The query resolution algorithm generates additional rewritings that merge related information from multiple sources and assemble a coherent view of the data, by incorporating target constraints. The algorithms are implemented and then evaluated using a comprehensive set of experiments based on both synthetic and real-life data integration scenarios.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {371–382},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007612,
author = {Dhamankar, Robin and Lee, Yoonkyong and Doan, AnHai and Halevy, Alon and Domingos, Pedro},
title = {IMAP: Discovering Complex Semantic Matches between Database Schemas},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007612},
doi = {10.1145/1007568.1007612},
abstract = {Creating semantic matches between disparate data sources is fundamental to numerous data sharing efforts. Manually creating matches is extremely tedious and error-prone. Hence many recent works have focused on automating the matching process. To date, however, virtually all of these works deal only with one-to-one (1-1) matches, such as address = location. They do not consider the important class of more complex matches, such as address = concat (city, state) and room-pric = room-rate* (1 + tax-rate).We describe the iMAP system which semi-automatically discovers both 1-1 and complex matches. iMAP reformulates schema matching as a search in an often very large or infinite match space. To search effectively, it employs a set of searchers, each discovering specific types of complex matches. To further improve matching accuracy, iMAP exploits a variety of domain knowledge, including past complex matches, domain integrity constraints, and overlap data. Finally, iMAP introduces a novel feature that generates explanation of predicted matches, to provide insights into the matching process and suggest actions to converge on correct matches quickly. We apply iMAP to several real-world domains to match relational tables, and show that it discovers both 1-1 and complex matches with high accuracy.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {383–394},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007613,
author = {Ives, Zachary G. and Halevy, Alon Y. and Weld, Daniel S.},
title = {Adapting to Source Properties in Processing Data Integration Queries},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007613},
doi = {10.1145/1007568.1007613},
abstract = {An effective query optimizer finds a query plan that exploits the characteristics of the source data. In data integration, little is known in advance about sources' properties, which necessitates the use of adaptive query processing techniques to adjust query processing on-the-fly. Prior work in adaptive query processing has focused on compensating for delays and adjusting for mis-estimated cardinality or selectivity values. In this paper, we present a generalized architecture for adaptive query processing and introduce a new technique, called adaptive data partitioning (ADP), which is based on the idea of dividing the source data into regions, each executed by different, complementary plans. We show how this model can be applied in novel ways to not only correct for underestimated selectivity and cardinality values, but also to discover and exploit order in the source data, and to detect and exploit source data that can be effectively pre-aggregated. We experimentally compare a number of alternative strategies and show that our approach is effective.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {395–406},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007615,
author = {Babu, Shivnath and Motwani, Rajeev and Munagala, Kamesh and Nishizawa, Itaru and Widom, Jennifer},
title = {Adaptive Ordering of Pipelined Stream Filters},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007615},
doi = {10.1145/1007568.1007615},
abstract = {We consider the problem of pipelined filters, where a continuous stream of tuples is processed by a set of commutative filters. Pipelined filters are common in stream applications and capture a large class of multiway stream joins. We focus on the problem of ordering the filters adaptively to minimize processing cost in an environment where stream and filter characteristics vary unpredictably over time. Our core algorithm, A-Greedy (for Adaptive Greedy), has strong theoretical guarantees: If stream and filter characteristics were to stabilize, A-Greedy would converge to an ordering within a small constant factor of optimal. (In experiments A-Greedy usually converges to the optimal ordering.) One very important feature of A-Greedy is that it monitors and responds to selectivities that are correlated across filters (i.e., that are nonindependent), which provides the strong quality guarantee but incurs run-time overhead. We identify a three-way tradeoff among provable convergence to good orderings, run-time overhead, and speed of adaptivity. We develop a suite of variants of A-Greedy that lie at different points on this tradeoff spectrum. We have implemented all our algorithms in the STREAM prototype Data Stream Management System and a thorough performance evaluation is presented.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {407–418},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007616,
author = {Ayad, Ahmed M. and Naughton, Jeffrey F.},
title = {Static Optimization of Conjunctive Queries with Sliding Windows over Infinite Streams},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007616},
doi = {10.1145/1007568.1007616},
abstract = {We define a framework for static optimization of sliding window conjunctive queries over infinite streams. When computational resources are sufficient, we propose that the goal of optimization should be to find an execution plan that minimizes resource usage within the available resource constraints. When resources are insufficient, on the other hand, we propose that the goal should be to find an execution plan that sheds some of the input load (by randomly dropping tuples) to keep resource usage within bounds while maximizing the output rate. An intuitive approach to load shedding suggests starting with the plan that would be optimal if resources were sufficient and adding "drop boxes" to this plan. We find this to be often times suboptimal - in many instances the optimal partial answer plan results from adding drop boxes to plans that are not optimal in the unlimited resource case. In view of this, we use our framework to investigate an approach to optimization that unifies the placement of drop boxes and the choice of the query plan from which to drop tuples. The effectiveness of our optimizer is experimentally validated and the results show the promise of this approach.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {419–430},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007617,
author = {Zhu, Yali and Rundensteiner, Elke A. and Heineman, George T.},
title = {Dynamic Plan Migration for Continuous Queries over Data Streams},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007617},
doi = {10.1145/1007568.1007617},
abstract = {Dynamic plan migration is concerned with the on-the-fly transition from one continuous query plan to a semantically equivalent yet more efficient plan. Migration is important for stream monitoring systems where long-running queries may have to withstand fluctuations in stream workloads and data characteristics. Existing migration methods generally adopt a pause-drain-resume strategy that pauses the processing of new data, purges all old data in the existing plan, until finally the new plan can be plugged into the system. However, these existing strategies do not address the problem of migrating query plans that contain stateful operators, such as joins. We now develop solutions for online plan migration for continuous stateful plans. In particular, in this paper, we propose two alternative strategies, called the moving state strategy and the parallel track strategy, one exploiting reusability and the second employs parallelism to seamlessly migrate between continuous join plans without affecting the results of the query. We develop cost models for both migration strategies to analytically compare them. We embed these migration strategies into the CAPE [7], a prototype system of a stream query engine, and conduct a comparative experimental study to evaluate these two strategies for window-based join plans. Our experimental results illustrate that the two strategies can vary significantly in terms of output rates and intermediate storage spaces given distinct system configurations and stream workloads.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {431–442},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007619,
author = {Yiu, Man Lung and Mamoulis, Nikos},
title = {Clustering Objects on a Spatial Network},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007619},
doi = {10.1145/1007568.1007619},
abstract = {Clustering is one of the most important analysis tasks in spatial databases. We study the problem of clustering objects, which lie on edges of a large weighted spatial network. The distance between two objects is defined by their shortest path distance over the network. Past algorithms are based on the Euclidean distance and cannot be applied for this setting. We propose variants of partitioning, density-based, and hierarchical methods. Their effectiveness and efficiency is evaluated for collections of objects which appear on real road networks. The results show that our methods can correctly identify clusters and they are scalable for large problems.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {443–454},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007620,
author = {B\"{o}hm, Christian and Kailing, Karin and Kr\"{o}ger, Peer and Zimek, Arthur},
title = {Computing Clusters of Correlation Connected Objects},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007620},
doi = {10.1145/1007568.1007620},
abstract = {The detection of correlations between different features in a set of feature vectors is a very important data mining task because correlation indicates a dependency between the features or some association of cause and effect between them. This association can be arbitrarily complex, i.e. one or more features might be dependent from a combination of several other features. Well-known methods like the principal components analysis (PCA) can perfectly find correlations which are global, linear, not hidden in a set of noise vectors, and uniform, i.e. the same type of correlation is exhibited in all feature vectors. In many applications such as medical diagnosis, molecular biology, time sequences, or electronic commerce, however, correlations are not global since the dependency between features can be different in different subgroups of the set. In this paper, we propose a method called 4C (Computing Correlation Connected Clusters) to identify local subgroups of the data objects sharing a uniform but arbitrarily complex correlation. Our algorithm is based on a combination of PCA and density-based clustering (DBSCAN). Our method has a determinate result and is robust against noise. A broad comparative evaluation demonstrates the superior performance of 4C over competing methods such as DBSCAN, CLIQUE and ORCLUS.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {455–466},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007621,
author = {Nassar, Samer and Sander, J\"{o}rg and Cheng, Corrine},
title = {Incremental and Effective Data Summarization for Dynamic Hierarchical Clustering},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007621},
doi = {10.1145/1007568.1007621},
abstract = {Mining informative patterns from very large, dynamically changing databases poses numerous interesting challenges. Data summarizations (e.g., data bubbles) have been proposed to compress very large static databases into representative points suitable for subsequent effective hierarchical cluster analysis. In many real world applications, however, the databases dynamically change due to frequent insertions and deletions, possibly changing the data distribution and clustering structure over time. Completely reapplying both the data summarization and the clustering algorithm to detect the changes in the clustering structure and update the uncovered data patterns following such deletions and insertions is prohibitively expensive for large fast changing databases. In this paper, we propose a new scheme to maintain data bubbles incrementally. By using incremental data bubbles, a high-quality hierarchical clustering is quickly available at any point in time. In our scheme, a quality measure for incremental data bubbles is used to identify data bubbles that do not compress well their underlying data points after certain insertions and deletions. Only these data bubbles are re-built using efficient split and merge operations. An extensive experimental evaluation shows that the incremental data bubbles provide significantly faster data summarization than completely re-building the data bubbles after a certain number of insertions and deletions, and are effective in preserving (and in some cases even improving) the quality of the data summarization.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {467–478},
numpages = {12},
keywords = {incremental data bubbles, data summarization, clustering},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007623,
author = {Tian, Feng and Reinwald, Berthold and Pirahesh, Hamid and Mayr, Tobias and Myllymaki, Jussi},
title = {Implementing a Scalable XML Publish/Subscribe System Using Relational Database Systems},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007623},
doi = {10.1145/1007568.1007623},
abstract = {An XML publish/subscribe system needs to match many XPath queries (subscriptions) over published XML documents. The performance and scalability of the matching algorithm is essential for the system when the number of XPath subscriptions is large. Earlier solutions to this problem usually built large finite state automata for all the XPath subscriptions in memory. The scalability of this approach is limited by the amount of available physical memory. In this paper, we propose an implementation that uses a relational database as the matching engine. The heavy lifting part of evaluating a large number of subscriptions is done inside a relational database using indices and joins. We described several different implementation strategies and presented a performance evaluation. The system shows very good performance and scalability in our experiments, handling millions of subscriptions with moderate amount of physical memory.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {479–490},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007624,
author = {Yi, Ke and He, Hao and Stanoi, Ioana and Yang, Jun},
title = {Incremental Maintenance of XML Structural Indexes},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007624},
doi = {10.1145/1007568.1007624},
abstract = {Increasing popularity of XML in recent years has generated much interest in query processing over graph-structured data. To support efficient evaluation of path expressions, many structural indexes have been proposed. The most popular ones are the 1-index, based on the notion of graph bisimilarity, and the recently proposed A(k)-index, based on the notion of local similarity to provide a trade-off between index size and query answering power. For these indexes to be practical, we need effective and efficient incremental maintenance algorithms to keep them consistent with the underlying data. However, existing update algorithms for structural indexes essentially provide no guarantees on the quality of the index; the updated index is usually larger size than necessary, degrading the performance for subsequent queries.In this paper, we propose update algorithms for the 1-index and the A(k)-index with provable guarantees on the resulting index quality. Our algorithms always maintain a minimal index, i.e., merging any two index nodes would result in an incorrect index. For the 1-index, if the data graph is acyclic, our algorithm further ensures that the index is minimum, i.e., it has the least number of index nodes possible. For the A(k)-index, we show that the minimal index our algorithm maintains is also the unique minimum A(k)-index, for both acyclic and cyclic data graphs. Finally, through experimental evaluation, we demonstrate that our algorithms bring significant improvement over previous methods, in terms of both index size and update time.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {491–502},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007625,
author = {Bohannon, Philip and Choi, Byron and Fan, Wenfei},
title = {Incremental Evaluation of Schema-Directed XML Publishing},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007625},
doi = {10.1145/1007568.1007625},
abstract = {When large XML documents published from a database are maintained externally, it is inefficient to repeatedly recompute them when the database is updated. Vastly preferable is incremental update, as common for views stored in a data warehouse. However, to support schema-directed publishing, there may be no simple query that defines the mapping from the database to the external document. To meet the need for efficient incremental update, this paper studies two approaches for incremental evaluation of ATGs [4], a formalism for schema-directed XML publishing. The reduction approach seeks to push as much work as possible to the underlying DBMS. It is based on a relational encoding of XML trees and a nontrivial translation of ATGs to SQL 99 queries with recursion. However, a weakness of this approach is that it relies on high-end DBMS features rather than the lowest common denominator. In contrast, the bud-cut approach pushes only simple queries to the DBNS and performs the bulk of the work in middleware. It capitalizes on the tree-structure of XML views to minimize unnecessary recomputations and leverages optimization techniques developed for XML publishing. While implementation of the reduction approach is not yet in the reach of commercial DBMS, we have implemented the bud-cut approach and experimentally evaluated its performance compared to recomputation.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {503–514},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007627,
author = {Bawa, Mayank and Gionis, Aristides and Garcia-Molina, Hector and Motwani, Rajeev},
title = {The Price of Validity in Dynamic Networks},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007627},
doi = {10.1145/1007568.1007627},
abstract = {Massive-scale self-administered networks like Peer-to-Peer and Sensor Networks have data distributed across thousands of participant hosts. These networks are highly dynamic with short-lived hosts being the norm rather than an exception. In recent years, researchers have investigated best-effort algorithms to efficiently process aggregate queries (e.g., sum, count, average, minimum and maximum) [6, 13, 21, 34, 35, 37] on these networks. Unfortunately, query semantics for best-effort algorithms are ill-defined, making it hard to reason about guarantees associated with the result returned. In this paper, we specify a correctness condition, single-site validity, with respect to which the above algorithms are best-effort. We present a class of algorithms that guarantee validity in dynamic networks. Experiments on real-life and synthetic network topologies validate performance of our algorithms, revealing the hitherto unknown price of validity.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {515–526},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007628,
author = {Deligiannakis, Antonios and Kotidis, Yannis and Roussopoulos, Nick},
title = {Compressing Historical Information in Sensor Networks},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007628},
doi = {10.1145/1007568.1007628},
abstract = {We are inevitably moving into a realm where small and inexpensive wireless devices would be seamlessly embedded in the physical world and form a wireless sensor network in order to perform complex monitoring and computational tasks. Such networks pose new challenges in data processing and dissemination because of the limited resources (processing, bandwidth, energy) that such devices possess. In this paper we propose a new technique for compressing multiple streams containing historical data from each sensor. Our method exploits correlation and redundancy among multiple measurements on the same sensor and achieves high degree of data reduction while managing to capture even the smallest details of the recorded measurements. The key to our technique is the base signal, a series of values extracted from the real measurements, used for encoding piece-wise linear correlations among the collected data values. We provide efficient algorithms for extracting the base signal features from the data and for encoding the measurements using these features. Our experiments demonstrate that our method by far outperforms standard approximation techniques like Wavelets. Histograms and the Discrete Cosine Transform, on a variety of error metrics and for real datasets from different domains.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {527–538},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007629,
author = {Tatarinov, Igor and Halevy, Alon},
title = {Efficient Query Reformulation in Peer Data Management Systems},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007629},
doi = {10.1145/1007568.1007629},
abstract = {Peer data management systems (PDMS) offer a flexible architecture for decentralized data sharing. In a PDMS, every peer is associated with a schema that represents the peer's domain of interest, and semantic relationships between peers are provided locally between pairs (or small sets) of peers. By traversing semantic paths of mappings, a query over one peer can obtain relevant data from any reachable peer in the network. Semantic paths are traversed by reformulating queries at a peer into queries on its neighbors.Naively following semantic paths is highly inefficient in practice. We describe several techniques for optimizing the reformulation process in a PDMS and validate their effectiveness using real-life data sets. In particular, we develop techniques for pruning paths in the reformulation process and for minimizing the reformulated queries as they are created. In addition, we consider the effect of the strategy we use to search through the space of reformulations. Finally, we show that pre-computing semantic paths in a PDMS can greatly improve the efficiency of the reformulation process. Together, all of these techniques form a basis for scalable query reformulation in PDMS.To enable our optimizations, we developed practical algorithms, of independent interest, for checking containment and minimization of XML queries, and for composing XML mappings.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {539–550},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007631,
author = {Rizvi, Shariq and Mendelzon, Alberto and Sudarshan, S. and Roy, Prasan},
title = {Extending Query Rewriting Techniques for Fine-Grained Access Control},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007631},
doi = {10.1145/1007568.1007631},
abstract = {Current day database applications, with large numbers of users, require fine-grained access control mechanisms, at the level of individual tuples, not just entire relations/views, to control which parts of the data can be accessed by each user. Fine-grained access control is often enforced in the application code, which has numerous drawbacks; these can be avoided by specifying/enforcing access control at the database level. We present a novel fine-grained access control model based on authorization views that allows "authorization-transparent" querying; that is, user queries can be phrased in terms of the database relations, and are valid if they can be answered using only the information contained in these authorization views. We extend earlier work on authorization-transparent querying by introducing a new notion of validity, conditional validity. We give a powerful set of inference rules to check for query validity. We demonstrate the practicality of our techniques by describing how an existing query optimizer can be extended to perform access control checks by incorporating these inference rules.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {551–562},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007632,
author = {Agrawal, Rakesh and Kiernan, Jerry and Srikant, Ramakrishnan and Xu, Yirong},
title = {Order Preserving Encryption for Numeric Data},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007632},
doi = {10.1145/1007568.1007632},
abstract = {Encryption is a well established technology for protecting sensitive data. However, once encrypted, data can no longer be easily queried aside from exact matches. We present an order-preserving encryption scheme for numeric data that allows any comparison operation to be directly applied on encrypted data. Query results produced are sound (no false hits) and complete (no false drops). Our scheme handles updates gracefully and new values can be added without requiring changes in the encryption of other values. It allows standard databse indexes to be built over encrypted tables and can easily be integrated with existing database systems. The proposed scheme has been designed to be deployed in application environments in which the intruder can get access to the encrypted database, but does not have prior domain information such as the distribution of values and annot encrypt or decrypt arbitrary values of his choice. The encryption is robust against estimation of the true value in such environments.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {563–574},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007633,
author = {Miklau, Gerome and Suciu, Dan},
title = {A Formal Analysis of Information Disclosure in Data Exchange},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007633},
doi = {10.1145/1007568.1007633},
abstract = {We perform a theoretical study of the following query-view security problem: given a view V to be published, does V logically disclose information about a confidential query S? The problem is motivated by the need to manage the risk of unintended information disclosure in today's world of universal data exchange. We present a novel information-theoretic standard for query-view security. This criterion can be used to provide a precise analysis of information disclosure for a host of data exchange scenarios, including multi-party collusion and the use of outside knowledge by an adversary trying to learn privileged facts about the database. We prove a number of theoretical results for deciding security according to this standard. We also generalize our security criterion to account for prior knowledge a user or adversary may possess, and introduce techniques for measuring the magnitude of partical disclosures. We believe these results can be a foundation for practical efforts to secure data exchange frameworks, and also illuminate a nice interaction between logic and probability theory.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {575–586},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007634,
author = {Fan, Wenfei and Chan, Chee-Yong and Garofalakis, Minos},
title = {Secure XML Querying with Security Views},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007634},
doi = {10.1145/1007568.1007634},
abstract = {The prevalent use of XML highlights the need for a generic, flexible access-control mechanism for XML documents that supports efficient and secure query access, without revealing sensitive information unauthorized users. This paper introduces a novel paradigm for specifying XML security constraints and investigates the enforcement of such constraints during XML query evaluation. Our approach is based on the novel concept of security views, which provide for each user group (a) an XML view consisting of all and only the information that the users are authorized to access, and (b) a view DTD that the XML view conforms to. Security views effectively protect sensitive data from access and potential inferences by unauthorized user, and provide authorized users with necessary schema information to facilitate effective query formulation and optimization. We propose an efficient algorithm for deriving security view definitions from security policies (defined on the original document DTD) for different user groups. We also develop novel algorithms for XPath query rewriting and optimization such that queries over security views can be efficiently answered without materializing the views. Our algorithms transform a query over a security view to an equivalent query over the original document, and effectively prune query nodes by exploiting the structural properties of the document DTD in conjunction with approximate XPath containment tests. Our work is the first to study a flexible, DTD-based access-control model for XML and its implications on the XML query-execution engine. Furthermore, it is among the first efforts for query rewriting and optimization in the presence of general DTDs for a rich a class of XPath queries. An empirical study based on real-life DTDs verifies the effectiveness of our approach.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {587–598},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007636,
author = {Cai, Yuhan and Ng, Raymond},
title = {Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007636},
doi = {10.1145/1007568.1007636},
abstract = {In this paper, we attempt to approximate and index a d- dimensional (d ≥ 1) spatio-temporal trajectory with a low order continuous polynomial. There are many possible ways to choose the polynomial, including (continuous)Fourier transforms, splines, non-linear regressino, etc. Some of these possiblities have indeed been studied beofre. We hypothesize that one of the best possibilities is the polynomial that minimizes the maximum deviation from the true value, which is called the minimax polynomial. Minimax approximation is particularly meaningful for indexing because in a branch-and-bound search (i.e., for finding nearest neighbours), the smaller the maximum deviation, the more pruning opportunities there exist. However, in general, among all the polynomials of the same degree, the optimal minimax polynomial is very hard to compute. However, it has been shown thta the Chebyshev approximation is almost identical to the optimal minimax polynomial, and is easy to compute [16]. Thus, in this paper, we explore how to use the Chebyshev polynomials as a basis for approximating and indexing d-dimenstional trajectories.The key analytic result of this paper is the Lower Bounding Lemma. that is, we show that the Euclidean distance between two d-dimensional trajectories is lower bounded by the weighted Euclidean distance between the two vectors of Chebyshev coefficients. this lemma is not trivial to show, and it ensures that indexing with Chebyshev cofficients aedmits no false negatives. To complement that analystic result, we conducted comprehensive experimental evaluation with real and generated 1-dimensional to 4-dimensional data sets. We compared the proposed schem with the Adaptive Piecewise Constant Approximation (APCA) scheme. Our preliminary results indicate that in all situations we tested, Chebyshev indexing dominates APCA in pruning power, I/O and CPU costs.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {599–610},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007637,
author = {Tao, Yufei and Faloutsos, Christos and Papadias, Dimitris and Liu, Bin},
title = {Prediction and Indexing of Moving Objects with Unknown Motion Patterns},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007637},
doi = {10.1145/1007568.1007637},
abstract = {Existing methods for peediction spatio-temporal databases assume that objects move according to linear functions. This severely limits their applicability, since in practice movement is more complex, and individual objects may follow drastically diffferent motion patterns. In order to overcome these problems, we first introduce a general framework for monitoring and indexing moving objects, where (i) each boject computes individually the function that accurately captures its movement and (ii) a server indexes the object locations at a coarse level and processes queries using a filter-refinement mechanism. Our second contribution is a novel recursive motion function that supports a broad class of non-linear motion patterns. The function does not presume any a-priori movement but can postulate the particular motion of each object by examining its locations at recent timestamps. Finally. we propse an efficient indexing scheme that faciliates the processing of predicitive queries without false misses.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {611–622},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007638,
author = {Mokbel, Mohamed F. and Xiong, Xiaopeing and Aref, Walid G.},
title = {SINA: Scalable Incremental Processing of Continuous Queries in Spatio-Temporal Databases},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007638},
doi = {10.1145/1007568.1007638},
abstract = {This paper intoduces the Scalable INcremental hash-based Algorithm (SINA, for short); a new algorithm for evaluting a set of concurrent continuous spatio-temporal queries. SINA is designed with two goals in mind: (1) Scalability in terms of the number of concurrent continuous spatio-temporal queries, and (2) Incremental evaluation of continyous spatio-temporal queries. SINA achieves scalability by empolying a shared execution paradigm where the execution of continuous spatio-temporal queries is abstracted as a spatial join between a set of moving objects and a set of moving queries. Incremental evaluation is achived by computing only the updates of the previously reported answer. We introduce two types of updaes, namely positive and negative updates. Positive or negative updates indicate that a certain object should be added to or removed from the previously reported answer, respectively. SINA manages the computation of postive and negative updates via three phases: the hashing phase, the invalidation phase, and the joining phase. the hashing phase employs an in-memory hash-based join algorithm that results in a set a positive upldates. The invalidation phase is triggered every T seconds or when the memory is fully occupied to produce a set of negative updates. Finally, the joining phase is triggered by the end of the invalidation phase to produce a set of both positive and negative updates that result from joining in-memory data with in-disk data. Experimental results show that SINA is scalable and is more efficient than other index-based spatio-temporal algorithms.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {623–634},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007639,
author = {Patel, Jignesh M. and Chen, Yun and Chakka, V. Prasad},
title = {STRIPES: An Efficient Index for Predicted Trajectories},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007639},
doi = {10.1145/1007568.1007639},
abstract = {Moving object databases are required to support queries on a large number of continuously moving objects. A key requirement for indexing methods in this domain is to efficiently support both update and query operations. Previous work on indexing such databases can be broadly divided into categories: indexing the past positions and indexing the future predicted positions. In this paper we focus on an efficient indexing method for indexing the future positions of moving objects.In this paper we propose an indexing method, called STRIPES, which indexes predicted trajectories in a dual transformed space. Trajectories for objects in d-dimensional space become points in a higher-dimensional 2d-space. This dual transformed space is then indexed using a regular hierarchical grid decomposition indexing structure. STRIPES can evaluate a range of queries including time-slice, window, and moving queries. We have carried out extensive experimental evaluation comparing the performance of STRIPES with the best known existing predicted trajectory index (the TPR*-tree), and show that our approach is significantly faster than TPR*-tree for both updates and search queries.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {635–646},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007641,
author = {Ilyas, Ihab F. and Markl, Volker and Haas, Peter and Brown, Paul and Aboulnaga, Ashraf},
title = {CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007641},
doi = {10.1145/1007568.1007641},
abstract = {The rich dependency structure found in the columns of real-world relational databases can be exploited to great advantage, but can also cause query optimizers---which usually assume that columns are statistically independent---to underestimate the selectivities of conjunctive predicates by orders of magnitude. We introduce CORDS, an efficient and scalable tool for automatic discovery of correlations and soft functional dependencies between columns. CORDS searches for column pairs that might have interesting and useful dependency relations by systematically enumerating candidate pairs and simultaneously pruning unpromising candidates using a flexible set of heuristics. A robust chi-squared analysis is applied to a sample of column values in order to identify correlations, and the number of distinct values in the sampled columns is analyzed to detect soft functional dependencies. CORDS can be used as a data mining tool, producing dependency graphs that are of intrinsic interest. We focus primarily on the use of CORDS in query optimization. Specifically, CORDS recommends groups of columns on which to maintain certain simple joint statistics. These "column-group" statistics are then used by the optimizer to avoid naive selectivity estimates based on inappropriate independence assumptions. This approach, because of its simplicity and judicious use of sampling, is relatively easy to implement in existing commercial systems, has very low overhead, and scales well to the large numbers of columns and large table sizes found in real-world databases. Experiments with a prototype implementation show that the use of CORDS in query optimization can speed up query execution times by an order of magnitude. CORDS can be used in tandem with query feedback systems such as the LEO learning optimizer, leveraging the infrastructure of such systems to correct bad selectivity estimates and ameliorating the poor performance of feedback systems during slow learning phases.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {647–658},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007642,
author = {Markl, Volker and Raman, Vijayshankar and Simmen, David and Lohman, Guy and Pirahesh, Hamid and Cilimdzic, Miso},
title = {Robust Query Processing through Progressive Optimization},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007642},
doi = {10.1145/1007568.1007642},
abstract = {Virtually every commercial query optimizer chooses the best plan for a query using a cost model that relies heavily on accurate cardinality estimation. Cardinality estimation errors can occur due to the use of inaccurate statistics, invalid assumptions about attribute independence, parameter markers, and so on. Cardinality estimation errors may cause the optimizer to choose a sub-optimal plan. We present an approach to query processing that is extremely robust because it is able to detect and recover from cardinality estimation errors. We call this approach "progressive query optimization" (POP). POP validates cardinality estimates against actual values as measured during query execution. If there is significant disagreement between estimated and actual values, execution might be stopped and re-optimization might occur. Oscillation between optimization and execution steps can occur any number of times. A re-optimization step can exploit both the actual cardinality and partial results, computed during a previous execution step. Checkpoint operators (CHECK) validate the optimizer's cardinality estimates against actual cardinalities. Each CHECK has a condition that indicates the cardinality bounds within which a plan is valid. We compute this validity range through a novel sensitivity analysis of query plan operators. If the CHECK condition is violated, CHECK triggers re-optimization. POP has been prototyped in a leading commercial DBMS. An experimental evaluation of POP using TPC-H queries illustrates the robustness POP adds to query processing, while incurring only negligible overhead. A case-study applying POP to a real-world database and workload shows the potential of POP, accelerating complex OLAP queries by almost two orders of magnitude.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {659–670},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007643,
author = {Rao, Jun and Pirahesh, Hamid and Zuzarte, Calisto},
title = {Canonical Abstraction for Outerjoin Optimization},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007643},
doi = {10.1145/1007568.1007643},
abstract = {Outerjoins are an important class of joins and are widely used in various kinds of applications. It is challenging to optimize queries that contain outerjoins because outerjoins do not always commute with inner joins. Previous work has studied this problem and provided techniques that allow certain reordering of the join sequences. However, the optimization of outerjoin queries is still not as powerful as that of inner joins.An inner join query can always be canonically represented as a sequence of Cartesian products of all relations, followed by a sequence of selection operations, each applying a conjunct in the join predicates. This canonical abstraction is very powerful because it enables the optimizer to use any join sequence for plan generation. Unfortunately, such a canonical abstraction for outerjoin queries has not been developed. As a result, existing techniques always exclude certain join sequences from planning, which can lead to a severe performance penalty.Given a query consisting of a sequence of inner and outer joins, we, for the first time, present a canonical abstraction based on three operations: outer Cartesian products, nullification, and best match. Like the inner join abstraction, our outerjoin abstraction permits all join sequences, and preserves the property of both commutativity and transitivity among predicates. This allows us to generate plans that are very desirable for performance reasons but that couldn't be done before. We present an algorithm that produces such a canonical abstraction, and a method that extends an inner-join optimizer to generate plans in an expanded search space. We also describe an efficient implementation of the best match operation using the OLAP functionalities in SQL:1999. Our experimental results show that our technique can significantly improve the performance of outerjoin queries.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {671–682},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007645,
author = {Enderle, Jost and Hampel, Matthias and Seidl, Thomas},
title = {Joining Interval Data in Relational Databases},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007645},
doi = {10.1145/1007568.1007645},
abstract = {The increasing use of temporal and spatial data in present-day relational systems necessitates an efficient support of joins on interval-valued attributes. Standard join algorithms do not support those data types adequately, whereas special approaches for interval joins usually require an augmentation of the internal access methods which is not supported by existing relational systems. To overcome these problems we introduce new join algorithms for interval data. Based on the Relational Interval Tree, these algorithms can easily be implemented on top of any relational database system while providing excellent performance on joining intervals. As experimental results on an Oracle9i server show, the new techniques outperform existing relational methods for joining intervals significantly.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {683–694},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007646,
author = {Das, Abhinandan and Gehrke, Johannes and Riedewald, Mirek},
title = {Approximation Techniques for Spatial Data},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007646},
doi = {10.1145/1007568.1007646},
abstract = {Spatial Database Management Systems (SDBMS), e.g., Geographical Information Systems, that manage spatial objects such as points, lines, and hyper-rectangles, often have very high query processing costs. Accurate selectivity estimation during query optimization therefore is crucially important for finding good query plans, especially when spatial joins are involved. Selectivity estimation has been studied for relational database systems, but to date has only received little attention in SDBMS. In this paper, we introduce novel methods that permit high-quality selectivity estimation for spatial joins and range queries. Our techniques can be constructed in a single scan over the input, handle inserts and deletes to the database incrementally, and hence they can also be used for processing of streaming spatial data. In contrast to previous approaches, our techniques return approximate results that come with provable probabilistic quality guarantees. We present a detailed analysis and experimentally demonstrate the efficacy of the proposed techniques.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {695–706},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007647,
author = {Cohen, Edith and Kaplan, Haim},
title = {Spatially-Decaying Aggregation over a Network: Model and Algorithms},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007647},
doi = {10.1145/1007568.1007647},
abstract = {Data items are often associated with a location in which they are present or collected, and their relevance or influence decays with their distance. Aggregate values over such data thus depend on the observing location, where the weight given to each item depends on its distance from that location. We term such aggregation spatially-decaying.Spatially-decaying aggregation has numerous applications: Individual sensor nodes collect readings of an environmental parameter such as contamination level or parking spot availability; the nodes then communicate to integrate their readings so that each location obtains contamination level or parking availability in its neighborhood. Nodes in a p2p network could use a summary of content and properties of nodes in their neighborhood in order to guide search. In graphical databases such as Web hyperlink structure, properties such as subject of pages that can reach or be reached from a page using link traversals provide information on the page.We formalize the notion of spatially-decaying aggregation and develop efficient algorithms for fundamental aggregation functions, including sums and averages, random sampling, heavy hitters, quantiles, and Lp norms.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {707–718},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007649,
author = {Hung, Edward and Deng, Yu and Subrahmanian, V. S.},
title = {TOSS: An Extension of TAX with Ontologies and Similarity Queries},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007649},
doi = {10.1145/1007568.1007649},
abstract = {TAX is perhaps the best known extension of the relational algebra to handle queries to XML databases. One problem with TAX (as with many existing relational DBMSs) is that the semantics of terms in a TAX DB are not taken into account when answering queries. Thus, even though TAX answers queries with 100% precision, the recall of TAX is relatively low. Our TOSS system improves the recall of TAX via the concept of a similarity enhanced ontology (SEO). Intuitively, an ontology is a set of graphs describing relationships (such as isa, partof, etc.) between terms in a DB. An SEO also evaluates how similarities between terms (e.g. "J. Ullman", "Jeff Ullman", and "Jeffrey Ullman") affect ontologies. Finally, we show how the algebra proposed in TAX can be extended to take SEOs into account. The result is a system that provides a much higher answer quality than TAX does alone (quality is defined as the square root of the product of precision and recall). We experimentally evaluate the TOSS system on the DBLP and SIGMOD bibliographic databases and show that TOSS has acceptable performance.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {719–730},
numpages = {12},
keywords = {ontologies, semantic integration of heterogeneous data, XML databases, similarity enhancement},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007650,
author = {Andritsos, Periklis and Miller, Ren\'{e}e J. and Tsaparas, Panayiotis},
title = {Information-Theoretic Tools for Mining Database Structure from Large Data Sets},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007650},
doi = {10.1145/1007568.1007650},
abstract = {Data design has been characterized as a process of arriving at a design that maximizes the information content of each piece of data (or equivalently, one that minimizes redundancy). Information content (or redundancy) is measured with respect to a prescribed model for the data, a model that is often expressed as a set of constraints. In this work, we consider the problem of doing data redesign in an environment where the prescribed model is unknown or incomplete. Specifically, we consider the problem of finding structural clues in an instance of data, an instance which may contain errors, missing values, and duplicate records. We propose a set of information-theoretic tools for finding structural summaries that are useful in characterizing the information content of the data, and ultimately useful in data design. We provide algorithms for creating these summaries over large, categorical data sets. We study the use of these summaries in one specific physical design task, that of ranking functional dependencies based on their data redundancy. We show how our ranking can be used by a physical data-design tool to find good vertical decompositions of a relation (decompositions that improve the information content of the design). We present an evaluation of the approach on real data sets.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {731–742},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007652,
author = {Sarawagi, Sunita and Kirpal, Alok},
title = {Efficient Set Joins on Similarity Predicates},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007652},
doi = {10.1145/1007568.1007652},
abstract = {In this paper we present an efficient, scalable and general algorithm for performing set joins on predicates involving various similarity measures like intersect size, Jaccard-coefficient, cosine similarity, and edit-distance. This expands the existing suite of algorithms for set joins on simpler predicates such as, set containment, equality and non-zero overlap. We start with a basic inverted index based probing method and add a sequence of optimizations that result in one to two orders of magnitude improvement in running time. The algorithm folds in a data partitioning strategy that can work efficiently with an index compressed to fit in any available amount of main memory. The optimizations used in our algorithm generalize to several weighted and unweighted measures of partial word overlap between sets.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {743–754},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007653,
author = {Chakrabarti, Kaushik and Chaudhuri, Surajit and Hwang, Seung-won},
title = {Automatic Categorization of Query Results},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007653},
doi = {10.1145/1007568.1007653},
abstract = {Exploratory ad-hoc queries could return too many answers - a phenomenon commonly referred to as "information overload". In this paper, we propose to automatically categorize the results of SQL queries to address this problem. We dynamically generate a labeled, hierarchical category structure - users can determine whether a category is relevant or not by examining simply its label; she can then explore just the relevant categories and ignore the remaining ones, thereby reducing information overload. We first develop analytical models to estimate information overload faced by a user for a given exploration. Based on those models, we formulate the categorization problem as a cost optimization problem and develop heuristic algorithms to compute the min-cost categorization.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {755–766},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007655,
author = {Ipeirotis, Panagiotis G. and Gravano, Luis},
title = {When One Sample is Not Enough: Improving Text Database Selection Using Shrinkage},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007655},
doi = {10.1145/1007568.1007655},
abstract = {Database selection is an important step when searching over large numbers of distributed text databases. The database selection task relies on statistical summaries of the database contents, which are not typically exported by databases. Previous research has developed algorithms for constructing an approximate content summary of a text database from a small document sample extracted via querying. Unfortunately, Zipf's law practically guarantees that content summaries built this way for any relatively large database will fail to cover many low-frequency words. Incomplete content summaries might negatively affect the database selection process, especially for short queries with infrequent words. To improve the coverage of approximate content summaries, we build on the observation that topically similar databases tend to have related vocabularies. Therefore, the approximate content summaries of topically related databases can complement each other and increase their coverage. Specifically, we exploit a (given or derived) hierarchical categorization of the databases and adapt the notion of "shrinkage" -a form of smoothing that has been used successfully for document classification-to the content summary construction task. A thorough evaluation over 315 real web databases as well as over TREC data suggests that the shrinkage-based content summaries are substantially more complete than their "unshrunk" counterparts. We also describe how to modify existing database selection algorithms to adaptively decide -at run-time-whether to apply shrinkage for a query. Our experiments, which rely on TREC data sets, queries, and the associated "relevance judgments," show that our shrinkage-based approach significantly improves state-of-the-art database selection algorithms, and also outperforms a recently proposed hierarchical strategy that exploits database classification as well.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {767–778},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007656,
author = {Kaushik, Raghav and Krishnamurthy, Rajasekar and Naughton, Jeffrey F. and Ramakrishnan, Raghu},
title = {On the Integration of Structure Indexes and Inverted Lists},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007656},
doi = {10.1145/1007568.1007656},
abstract = {Several methods have been proposed to evaluate queries over a native XML DBMS, where the queries specify both path and keyword constraints. These broadly consist of graph traversal approaches, optimized with auxiliary structures known as structure indexes; and approaches based on information-retrieval style inverted lists. We propose a strategy that combines the two forms of auxiliary indexes, and a query evaluation algorithm for branching path expressions based on this strategy. Our technique is general and applicable for a wide range of choices of structure indexes and inverted list join algorithms. Our experiments over the Niagara XML DBMS show the benefit of integrating the two forms of indexes. We also consider algorithmic issues in evaluating path expression queries when the notion of relevance ranking is incorporated. By integrating the above techniques with the Threshold Algorithm proposed by Fagin et al., we obtain instance optimal algorithms to push down top k computation.},
booktitle = {Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data},
pages = {779–790},
numpages = {12},
location = {Paris, France},
series = {SIGMOD '04}
}

@inproceedings{10.1145/1007568.1007658,
author = {Luo, Gang and Naughton, Jeffrey F. and Ellmann, Curt J. and Watzke, Michael W.},
title = {Toward a Progress Indicator for Database Queries},
year = {2004},
isbn = {1581138598},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007568.1007658},
doi = {10.1145/1007568.1007658},
abstract = {Many modern software systems provide progress indicators for long-running tasks. These progress indicators make systems more user-friendly by helping the user quickly estimate how much of the task has been completed and when the task will finish. However, none of the existing commercial RDBMSs provides a non-trival progress indicator for long-running queries. In this paper, we consider the problem of supporting such progress indicators. After discussing the goals and challenges inherent in this problem, we present a set of techniques sufficient for implementing a simple yet useful progress indicator for a large subset of RDBMS queries. We report an initial implementation of these techniques in PostgreSQL.},
booktitle

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr