4 LEARNING, PREDICTION, ESTIMATION, CACHING, AND PREFETCHING

• J.-H. Lin and J. S. Vitter. ``Complexity Results on Learning by Neural Nets,'' Machine Learning, 6, 1991, 211-230. A shorter version appears in Proceedings of the 2nd Annual ACM Workshop on Computational Learning Theory (COLT '89), Santa Cruz, CA, July-August 1989, published by Morgan Kaufmann, San Mateo, CA, 118-133.

  We consider the computational complexity of learning by neural nets. We are interested in how hard it is to design appropriate neural net architectures and to train neural nets for general and specialized learning tasks. Our main result shows that the training problem for 2-cascade neural nets (which have only two non-input nodes, one of which is hidden) is $\cal NP$-complete, which implies that finding an optimal net (in terms of the number of non-input units) that is consistent with a set of examples is also $\cal NP$-complete. This result also demonstrates a surprising gap between the computational complexities of one-node (perceptron) and two-node neural net training problems, since the perceptron training problem can be solved in polynomial time by linear programming techniques. We conjecture that training a $k$-cascade neural net, which is a classical threshold network training problem, is also $\cal NP$-complete, for each fixed $k \geq 2$. We also show that the problem of finding an optimal perceptron (in terms of the number of non-zero weights) consistent with a set of training examples is $\cal NP$-hard.

  Our neural net learning model encapsulates the idea of modular neural nets, which is a popular approach to overcoming the scaling problem in training neural nets. We investigate how much easier the training problem becomes if the class of concepts to be learned is known a priori and the net architecture is allowed to be sufficiently non-optimal. Finally, we classify several neural net optimization problems within the polynomial-time hierarchy.

• J. S. Vitter and J.-H. Lin. ``Learning in Parallel,'' Information and Computation, 92(2), February 1992, 179-202. A shorter version appears in Proceedings of the 1st Annual ACM Workshop on Computational Learning Theory (COLT '88), Cambridge, MA, August 1988, published by Morgan Kaufmann, San Mateo, CA, 106-124.

  In this paper, we extend Valiant's sequential model of concept learning from examples [Valiant 1984] and introduce models for the efficient learning of concept classes from examples in parallel. We say that a concept class is ${\cal NC}$-learnable if it can be learned in polylog time with a polynomial number of processors. We show that several concept classes which are polynomial-time learnable are ${\cal NC}$-learnable in constant time. Some other classes can be shown to be ${\cal NC}$-learnable in logarithmic time, but not in constant time. Our main result shows that other classes, such as $s$-fold unions of geometrical objects in Euclidean space, which are polynomial-time learnable by a greedy set cover technique, are ${\cal NC}$-learnable using a non-greedy technique. We also show that (unless ${\cal P}\subseteq {\cal RNC}$) several polynomial-time learnable concept classes related to linear programming are not ${\cal NC}$-learnable. Equivalence of various parallel learning models and issues of fault-tolerance are also discussed.

• J. S. Vitter and P. Krishnan. ``Optimal Prefetching via Data Compression,''Journal of the ACM, 43(5) September 1996, 771-793. A shorter version appears in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS '91), San Juan, Puerto Rico, October 1991, 121-130.

  Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms for caching. In this paper, we apply a form of the competitive philosophy for the first time to the problem of prefetching to develop an optimal universal prefetcher in terms of fault ratio, with particular applications to large-scale databases and hypertext systems. Our algorithms for prefetching are novel in that they are based on data compression techniques that are both theoretically optimal and good in practice. Intuitively, in order to compress data effectively, you have to be able to predict future data well, and thus good data compressors should be able to predict well for purposes of prefetching. We show for powerful models such as Markov sources and $m$th order Markov sources that the page fault rates incurred by our prefetching algorithms are optimal in the limit for almost all sequences of page accesses.

• K. M. Curewitz, P. Krishnan, and J. S. Vitter. ``Practical Prefetching via Data Compression,''Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD '93), Washington, D. C, May 1993, 257-266. This work is the basis of a patent by the authors, ``Online Background Predictors and Prefetchers,'' United States Patent No. 5,485,609, Duke University, January 16, 1996.

  An important issue that affects response time performance in current OODB and hypertext systems is the I/O involved in moving objects from slow memory to cache. A promising way to tackle this problem is to use prefetching, in which we predict the user's next page requests and get those pages into cache in the background. Current databases perform limited prefetching using techniques derived from older virtual memory systems. A novel idea of using data compression techniques for prefetching was recently advocated by Vitter in Krishnan in which the prefetchers based on the Lempel-Ziv data compressor (the UNIX compress command) were shown theoretically to be optimal in the limit. In this paper we analyze the practical aspects of using data compression techniques for prefetching. We adapt three well-known data compressors to get three simple, deterministic, and universal prefetchers. We simulate our prefetchers on sequences of page accesses derived from the OO1 and OO7 benchmarks and from CAD applications, and demonstrate significant reductions in fault-rate. We examine the important issues of cache replacement, size of the data structure used by the prefetcher, and problems arising from bursts of ``fast'' page requests (that leave virtually no time between adjacent requests for prefetching and book keeping). We conclude that prediction for prefetching based on data compression techniques holds great promise.

• P. Krishnan and J. S. Vitter. ``Optimal Prediction for Prefetching in the Worst Case,'' SIAM Journal on Computing, 27(6), December 1998, 1617-1636. A shorter version appears in Proceedings of the 5th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '94), Alexandria, VA, January 1994, 392-401.

  Response time delays caused by I/O is a major problem in many systems and database applications. Prefetching and cache-replacement methods are attracting renewed attention because of their success in avoiding costly I/Os. Prefetching can be looked upon as a type of online sequential prediction, where the predictions must be accurate as well as made in a computationally efficient way. Unlike other online problems, prefetching cannot admit a competitive analysis, since the optimal offline prefetcher incurs no cost when it knows the future page requests. Previous analytical work on prefetching by Vitter and Krishnan consisted of modeling the user as a probabilistic Markov source.

  In this paper, we look at the much stronger form of worst-case analysis and derive a randomized algorithm that we prove analytically converges almost surely to the optimal fault rate in the worst case for every sequence of page request with respect to the important class of finite state prefetchers. In particular, we make no assumption about how the sequence of page requests is generated. This analysis model can be looked upon as a generalization of the competitive framework, in that it compares an online algorithm in a worst-case manner over all sequences against a powerful yet non-clairvoyant opponent. We simultaneously achieve the computational goal of implementing our prefetcher in optimal constant expected time per prefetched page, using the optimal dynamic discrete random variate generator of Matias, Vitter, and Ni.

• K. Romanik and J.S. Vitter. ``Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments,'' Information and Computation, 128(2), August 1, 1996, 87-108. A shorter version appears in ``Using Computational Learning Theory to Analyze the Testing Complexity of Program Segments,'' Proceedings of the 17th Annual IEEE International Computer Software and Applications Conference (COMpostscriptAC '93), Phoenix, 1993, 367-373.

  We examine the complexity of testing different program constructs. We do this by defining a measure of testing complexity known as VCP-dimension, which is similar to the Vapnik-Chervonenkis dimension, and applying it to classes of programs, where all programs in a class share the same syntactic structure. VCP-dimension gives bounds on the number of test points needed to determine that a program is approximately correct, so by studying it for a class of programs we gain insight into the difficulty of testing the program construct represented by the class. We investigate the VCP-dimension of straight line code, if-then-else statements, and for loops. We also compare the VCP-dimension of nested and sequential if-then-else statements as well as that of two types of for loops with embedded if-then-else statements. Finally, we perform an empirical study to estimate the expected complexity of straight line code.

• J.-H. Lin and J. S. Vitter. ``A Theory for Memory-Based Learning,'' special issue of Machine Learning, 17(2/3), November/December 1994, 143-167. A shorter version appears in Proceedings of the 5th Annual ACM Conference on Computational Learning Theory (COLT '92), Pittsburgh, PA, July 1992, 103-115.

  A memory-based learning system is an extended memory management system that decomposes the input space either statically or dynamically into subregions for the purpose of storing and retrieving functional information. The main generalization techniques employed by memory-based learning systems are the nearest-neighbor search, space decomposition techniques, and clustering. Research on memory-based learning is still in its early stage. In particular, there are very few rigorous theoretical results regarding memory requirement, sample size, expected performance, and computational complexity. In this paper, we propose a model for memory-based learning and use it to analyze several methods -- $\epsilon$-covering, hashing, clustering, tree-structured clustering, and receptive-fields -- for learning smooth functions. The sample size and system complexity are derived for each method. Our model is built upon the generalized PAC learning model of Haussler and is closely related to the method of vector quantization in data compression. Our main result is that we can build memory-based learning systems using new clustering algorithms of Lin and Vitter to PAC-learn in polynomial time using only polynomial storage in typical situations.

• K. J. Basye, T. L. Dean, and J. S. Vitter. ``Coping with Uncertainty in Map Learning,'' Machine Learning, 29(1), 1997, 65-88. A shorter version appears in Proceedings of the 11th Joint Conference on Artificial Intelligence (IJCAI '89), Detroit, MI, August 1989, 663-668, and in Autonomous Mobile Robots: Perception, Mapping, and Navigation, (edited by S. S.Iyengar and Alberto Elfes), IEEE Computer Society Press.

  In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a representation as a map, and the process of constructing a map from a set of measurements as map learning. In this paper, we develop a framework for describing map-learning problems in which the measurements taken by the robot are subject to known errors. We investigate approaches to learning maps under such conditions based on Valiant's probably approximately correct learning model. We focus on the problem of coping with accumulated error in combining local measurements to make global inferences. In one approach, the effects of accumulated error are eliminated by the use of local sensing methods that never mislead but occasionally fail to produce an answer. In another approach, the effects of accumulated error are reduced to acceptable levels by repeated exploration of the area to be learned. We also suggest some insights into why certain existing techniques for map learning perform as well as they do. The learning problems explored in this paper are quite different from most of the classification and boolean-function learning problems appearing in the literature. The methods described, while specific to map learning, suggest directions to take in tackling other learning problems.

• P. Krishnan, P. M. Long, and J. S. Vitter. ``Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments,'' Algorithmica, 23(1), January 1999, 31-56. An extended abstract also appears in Machine Learning: Proceedings of the Twelfth International Conference, Armand Prieditis and Stuart Russell, eds., Morgan Kaufmann Publishers, San Fransisco, CA, 1995, under the title ``Learning to Make Rent-to-Buy Decisions with Systems Applications.''

  In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource for $1 per unit time or buy it once and for all for $$c$. In this paper we study algorithms that make a sequence of single rent-to-buy decisions, using the assumption that the resource use times are independently drawn from an unknown probability distribution. Our study of this rent-to-buy problem is motivated by important systems applications, specifically, problems arising from deciding when to spindown disks to conserve energy in mobile computers [DKM, LKH, MDK], thread blocking decisions during lock acquisition in multiprocessor applications [KLM], and virtual circuit holding times in IP-over-ATM networks [KLP, SaK].

  We develop a provably optimal and computationally efficient algorithm for the rent-to-buy problem and evaluate its practical merit for the disk spindown scenario via simulation studies. Our algorithm uses $O(\sqrt{t})$ time and space, and its expected cost for the $t$th resource use converges to optimal as $O(\sqrt{\log t/t})$, for any bounded probability distribution on the resource use times. Alternatively, using $O(1)$ time and space, the algorithm almost converges to optimal.

  We describe the results of simulating our algorithm for the disk spindown problem using disk access traces obtained from an HP workstation environment. We introduce the natural notion of effective cost which merges the effects of energy conservation and response time performance into one metric based on a user specified parameter $a$, the relative importance of response time to energy conservation. (The buy cost $c$ varies linearly with $a$.) We observe that by varying $a$, we can model the tradeoff between power and response time well. We also show that our algorithm is best in terms of effective cost for almost all values of $a$, saving effective cost by 6-25% over the optimal online algorithm in the competitive model (i.e., the 2-competitive algorithm that spins down the disk after waiting $c$ seconds). In addition, for small values of $a$ (corresponding to when saving energy is critical), our algorithm when compared against the optimal online algorithm in the competitive model reduces excess energy by 17-60%, and when compared against the 5 second threshold reduces excess energy by 6-42%.

• R. D. Barve, E. F. Grove, and J. S. Vitter. ``Application-Controlled Paging for a Shared Cache,'' SIAM Journal on Computing, 29(4), 2000, 1290-1303. An extended abstract also appears in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS '95), Milwaukee, WI, October 1995.

  We consider a cache shared by several concurrently running application processes and propose a provably efficient application-controlled global strategy for the shared cache. Using future information implicitly in the form of good decisions by application processes, we are able to break through the $H_k$ lower bound on competitive ratio proved for classical paging for a $k$-sized cache. For a size-$k$ cache shared by $P$ application processes that always make good cache replacement decisions, we develop an online application-controlled paging algorithm with a competitive ratio of $2H_{P-1}+2$. Typically, $P$ is much smaller than $k$, perhaps by several orders of magnitude. Our competitive ratio improves upon the $2P+2$ competitive ratio achieved by Cao et al. We show for this problem that no online algorithm $A$ can have a competitive ratio better than $H_{P-1}$ even if the application processes aiding $A$ have perfect knowledge of individual request sequences. Our results are with respect to a worst-case interleaving of the individual request sequences of the $P$ applications.

  We introduce a notion of fairness in the more realistic situation when application processes do not always make good cache replacement decisions. We show that our algorithm ensures that no application process needs to evict one of its cached pages to service some page fault caused by a mistake of some other application. Our algorithm is not only fair, but remains efficient; the global paging performance can be bounded in terms of the number of mistakes that application processes make.

• P. Krishnan, J. S. Vitter, and B. Iyer. ``Estimating Alphanumeric Selectivity in the Presence of Wildcards,''Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data (SIGMOD '96), Montreal, Canada, May 1996, 282-293.

  Success of commercial query optimizers and database management systems (object-oriented or relational) depend on accurate cost estimation of various query reorderings [BGI]. Estimating predicate selectivity, or the fraction of rows in a database that satisfy a selection predicate, is key to determining the optimal join order. Previous work has concentrated on estimating selectivity for numeric fields [ASW, HaSa, IoP, LNS, SAC, WVT]. With the popularity of textual data being stored in databases, it has become important to estimate selectivity accurately for alphanumeric fields. A particularly problematic predicate used against alphanumeric fields is the SQL LIKE predicate [Dat]. Techniques used for estimating numeric selectivity are not suited for estimating alphanumeric selectivity.

  In this paper, we study for the first time the problem of estimating alphanumeric selectivity in the presence of wildcards. Based on the intuition that the model built by a data compressor on an input text encapsulates information about common substrings in the text, we develop a technique based on the suffix tree data structure to estimate alphanumeric selectivity. In a statistics generation pass over the database, we construct a compact suffix tree-based structure from the columns of the database. We then look at three families of methods that utilize this structure to estimate selectivity during query plan costing, when a query with predicates on alphanumeric attributes contains wildcards in the predicate.

  We evaluate our methods empirically in the context of the TPC-D benchmark. We study our methods experimentally against a variety of query patterns and identify five techniques that hold promise.

• R. D. Barve, M. Kallahalla, P. J. Varman, and J. S. Vitter. ``Competitive Analysis of Buffer Management Algorithms for Parallel I/O Systems,'' Journal of Algorithms, 36, August 2000. A shorter version appeared as ``Competitive Parallel Disk Prefetching and Buffer Management,'' Proceedings of the Fifth Annual Workshop on I/O in Parallel and Distributed Systems (IOPADS), 1997, San Jose, California, 47-56.

  We provide a competitive analysis framework for online prefetching and buffer management algorithms in parallel I/O systems, using a read-once model of block references. This has widespread applicability to key I/O-bound applications such as external merging and concurrent playback of multiple video streams. Two realistic lookahead models, global lookahead and local lookahead, are defined. Algorithms NOM and GREED based on these two forms of lookahead are analyzed for shared buffer and distributed buffer configurations, both of which occur frequently in existing systems. An important aspect of our work is that we show how to implement both the models of lookahead in practice using the simple techniques of forecasting and flushing.

  Given a $D$-disk parallel I/O system and a globally shared I/O buffer that can hold up to $M$ disk blocks, we derive a lower bound of $\Omega(\smash{\sqrt{D}})$ on the competitive ratio of any deterministic online prefetching algorithm with $O(M)$ lookahead. NOM is shown to match the lower bound using global $M$-block lookahead. In contrast, using only local lookahead results in an $\Omega(D)$ competitive ratio. When the buffer is distributed into $D$ portions of $M/D$ blocks each, the algorithm GREED based on local lookahead is shown to be optimal, and NOM is within a constant factor of optimal. Thus we provide a theoretical basis for the intuition that global lookahead is more valuable for prefetching in the case of a shared buffer configuration whereas it is enough to provide local lookahead in case of the distributed configuration. Finally, we analyze the performance of these algorithms for reference strings generated by a uniformly-random stochastic process and we show that they achieve the minimal expected number of I/Os. These results also give bounds on the worst-case expected performance of algorithms which employ randomization in the data layout.

• Y. Matias, J. S. Vitter, and M. Wang. ``Wavelet-Based Histograms for Selectivity Estimation,''Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data (SIGMOD'98), Seattle, Washington, June 1998.

  Query optimization is an integral part of relational database management systems. One important task in query optimization is selectivity estimation, that is, given a query $P$, we need to estimate the fraction of records in the database that satisfy $P$. Many commercial database systems maintain histograms to approximate the frequency distribution of values in the attributes of relations.

  In this paper, we present a technique based upon a multiresolution wavelet decomposition for building histograms on the underlying data distributions, with applications to databases, statistics, and simulation. Histograms built on the cumulative data distributions give very good approximations with limited space usage. We give fast algorithms for constructing histograms and using them in an on-line fashion for selectivity estimation. Our histograms also provide quick approximate answers to OLAP queries when the exact answers are not required. Our method captures the joint distribution of multiple attributes effectively, even when the attributes are correlated. Experiments confirm that our histograms offer substantial improvements in accuracy over random sampling and other previous approaches.

• M. Wang, B. Iyer, and J. S. Vitter. ``Scalable Mining for Classification Rules in Relational Databases,'' Herman Rubin Festschrift, Lecture Notes Monograph Series, 45, Institute of Mathematical Statistics, Hayward, CA, Fall 2004.

  Classification is a key function of many ``business intelligence'' toolkits and a fundamental building block in data mining. Immense data may be needed to train a classifier for good accuracy. The state-of-art classifiers need an in-memory data structure of size $O(N)$, where $N$ is the size of the training data, to achieve efficiency. For large data sets, such a data structure will not fit in the internal memory. The best previously known classifier does a quadratic number of I/Os for large $N$.

  In this paper, we propose a novel classification algorithm (classifier) called MIND (MINing in Databases). MIND can be phrased in such a way that its implementation is very easy using the extended relational calculus SQL, and this in turn allows the classifier to be built into a relational database system directly. MIND is truly scalable with respect to I/O efficiency, which is important since scalability is a key requirement for any data mining algorithm.

  We built a prototype of MIND in the relational database manager DB2 and benchmarked its performance. We describe the working prototype and report the measured performance with respect to the previous method of choice. MIND scales not only with the size of the datasets but also with the number of processors on an IBM SP2 computer system. Even on uniprocessors, MIND scales well beyond the dataset sizes previously published for classifiers. We also give some insights that may have an impact on the evolution of the extended relational calculus SQL.

• J. S. Vitter, M. Wang, and B. Iyer. ``Data Cube Approximation and Histograms via Wavelets,''Proceedings of Seventh International Conference on Information and Knowledge Management (CIKM'98), Washington D.C., November 1998.

  There has recently been an explosion of interest in the analysis of data in data warehouses in the field of On-Line Analytical Processing (OLAP). Data warehouses can be extremely large, yet obtaining quick answers to queries is important. In many situations, obtaining the exact answer to an OLAP query is prohibitively expensive in terms of time and/or storage space. It can be advantageous to have fast, approximate answers to queries.

  In this paper, we present an I/O-efficient technique based upon a multiresolution wavelet decomposition that yields an approximate and space-efficient representation of the data cube, which is one of the core OLAP operators. We build our compact data cube on the logarithms of the partial sums of the raw data values of a multidimensional array. We get excellent approximations for on-line range-sum queries with limited space usage and computational cost. Multiple data cubes can be handled simultaneously. Each query can generally be answered, depending upon the accuracy supported, in one I/O or a small number of I/Os. Experiments show that our method performs significantly better than other approximation techniques such as histograms and random sampling.

• J. S. Vitter and M. Wang. ``Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets,''Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data (SIGMOD'99), Philadelphia, PA, June 1999.

  Computing multidimensional aggregates in high dimensions is a performance bottleneck for many OLAP applications. Obtaining the exact answer to an aggregation query can be prohibitively expensive in terms of time and/or storage space in a data warehouse environment. It is advantageous to have fast, approximate answers to OLAP aggregation queries.

  In this paper, we present a novel method that provides approximate answers to high-dimensional OLAP aggregation queries in massive sparse data sets in a time-efficient and space-efficient manner. We construct a compact data cube, which is an approximate and space-efficient representation of the underlying multidimensional array, based upon a multiresolution wavelet decomposition. In the on-line phase, each aggregation query can generally be answered using the compact data cube in one I/O or a small number of I/Os, depending upon the desired accuracy.

  We present two I/O-efficient algorithms to construct the compact data cube for the important case of sparse high-dimensional arrays, which often arise in practice. The traditional histogram methods are infeasible for the massive high-dimensional data sets in OLAP applications. Previously developed wavelet techniques are efficient only for dense data. Our on-line query processing algorithm is very fast and capable of refining answers as the user demands more accuracy. Experiments on real data show that our method provides significantly more accurate results for typical OLAP aggregation queries than other efficient approximation techniques such as random sampling.

• Y. Matias, J. S. Vitter, and M. Wang. ``Dynamic Maintenance of Wavelet-Based Histograms,'' Proceedings of the 26th International Conference on Very Large Databases (VLDB '00), Cairo, Egypt, September 2000.

  In this paper, we introduce an efficient method for the dynamic maintenance of wavelet-based histograms (and other transform-based histograms). Previous work has shown that wavelet-based histograms provide more accurate selectivity estimation than traditional histograms, such as equi-depth histograms. But since wavelet-based histograms are built by a nontrivial mathematical procedure, namely, wavelet transform decomposition, it is hard to maintain the accuracy of the histogram when the underlying data distribution changes over time. In particular, simple techniques, such as split and merge, which works well for equi-depth histograms, and updating a fixed set of wavelet coefficients, are not suitable here.

  We propose a novel approach based upon probabilistic counting and sampling to maintain wavelet-based histograms with very little online time and space costs. The accuracy of our method is robust to changing data distributions, and we get a considerable improvement over previous methods for updating transform-based histograms. A very nice feature of our method is that it can be extended naturally to maintain multidimensional wavelet-based histograms, while traditional multidimensional histograms can be less accurate and prohibitively expensive to build and maintain.

• L. Lim, M. Wang, S. Padmanabhan, J. S. Vitter, and R. Parr. ``XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation,'' Proceedings of the 28th International Conference on Very Large Databases (VLDB '02), Hong Kong, China, August 2002.

  The extensible mark-up language (XML) is gaining widespread use as a format for data exchange and storage on the World Wide Web. Queries over XML data require accurate selectivity estimation of path expressions to optimize query execution plans. Selectivity estimation of XML path expression is usually done based on summary statistics about the structure of the underlying XML repository. All previous methods require an off-line scan of the XML repository to collect the statistics.

  In this paper, we propose XPathLearner, a method for estimating selectivity of the most commonly used types of path expressions without looking at the XML data. XPathLearner gathers and refines the statistics using query feedback in an on-line manner and is especially suited to queries in Internet scale applications since the underlying XML repositories are likely to be inaccessible or too large to be scanned entirely. Besides the on-line property, our method also has two other novel features: (a) XPathLearner is workload aware in collecting the statistics and thus can be dramatically more accurate than the more costly off-line method under tight memory constraints, and (b) XPathLearner automatically adjusts the statistics using query feedback when the underlying XML data change. We show empirically the estimation accuracy of our method using several real data sets.

• S. Anastasiadis, P. Varman, J. S. Vitter, and K. Yi. ``Optimal Lexicographic Shaping of Aggregate Streaming Data,'' IEEE Transactions on Computers, 54(4), 398-408, April 2005. A shorter version appeared in S. Anastasiadis, P. Varman, and J. S. Vitter. ``Lexicographically Optimal Smoothing for Broadband Traffic Multiplexing,'' Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC '02), July 2002, Monterey, CA.

  We investigate the problem of smoothing multiplexed network traffic, when either a streaming server transmits data to multiple clients, or a server accesses data from multiple storage devices or other servers. We introduce efficient algorithms for lexicographically optimally smoothing the aggregate bandwidth requirements over a shared network link. In the data transmission problem, we consider the case in which the clients have different buffer capacities but no bandwidth constraints, or no buffer capacities but different bandwidth constraints. For the data access problem, we handle the general case of a shared buffer capacity and individual network bandwidth constraints. Previous approaches in the literature for the data access problem handled either the case of only a single stream or did not compute the lexicographically optimal schedule.

  Lexicographically optimal smoothing (lexopt smoothing) has several advantages. By provably minimizing the variance of the required aggregate bandwidth, maximum resource requirements within the network become more predictable, and useful resource utilization increases. Fairness in sharing a network link by multiple users can be improved, and new requests from future clients are more likely to be successfully admitted without the need for frequently rescheduling previously accepted traffic. Efficient resource management at the network edges can better meet quality of service requirements without restricting the scalability of the system.

• L. Lim, M. Wang, and J. S. Vitter. ``SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads,'' Proceedings of the 29th International Conference on Very Large Databases (VLDB '03), Berlin, Germany, September 2003.

  Most RDBMSs maintain a set of histograms for estimating the selectivities of given queries. These selectivities are typically used for cost-based query optimization. While the problem of building an accurate histogram for a given attribute or attribute set has been well-studied, little attention has been given to the problem of building and tuning a set of histograms collectively for multidimensional queries in a self-managed manner based only on query feedback.

  In this paper, we present SASH, a Self-Adaptive Set of Histograms that addresses the problem of building and maintaining a set of histograms. SASH uses a novel two-phase method to automatically build and maintain itself using query feedback information only. In the online tuning phase, the current set of histograms is tuned in response to the estimation error of each query in an online manner. In the restructuring phase, a new and more accurate set of histograms replaces the current set of histograms. The new set of histograms (attribute sets and memory distribution) is found using information from a batch of query feedback. We present experimental results that show the effectiveness and accuracy of our approach.

• R. Shah, P. J. Varman, and J. S. Vitter. ``Online Algorithms for Prefetching and Caching in Parallel Disks,'' Proceedings of the 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '04), Barcelona, Spain, June 2004.

  Parallel disks provide a cost effective way of speeding up I/Os in applications that work with large amounts of data. The main challenge is to achieve as much parallelism as possible, using prefetching to avoid bottlenecks in disk access. Efficient algorithms have been developed for some particular patterns of accessing the disk blocks. In this paper, we consider general request sequences. When the request sequence consists of unique block requests, the problem is called prefetching and is a well-solved problem for arbitrary request sequences. When the reference sequence can have repeated references to the same block, we need to devise an effective caching policy as well. While optimum offline algorithms have been recently designed for the problem, in the online case, no effective algorithm was previously known. Our main contribution is a deterministic online algorithm threshold-LRU which achieves $O((MD/L)^{2/3})$ competitive ratio and a randomized online algorithm threshold-MARK which achieves $O(\sqrt((MD/L) \log(MD/L)))$ competitive ratio for the caching/prefetching problem on the parallel disk model (PDM), where $D$ is the number of disks, $M$ is the size of fast memory buffer, and $M + L$ is the amount of lookahead available in the request sequence. The best-known lower bound on the competitive ratio is $O(\sqrt(MD/L))$ for lookahead $L >= M$ in both models. We also show that if the deterministic online algorithm is allowed to have twice the memory of the offline then a tight competitive ratio of $O(\sqrt(MD/L))$ can be achieved. This problem generalizes the well-known paging problem on a single disk to the parallel disk model.

• L. Lim, M. Wang, and J. S. Vitter. ``CXHist: An On-line Classification-based Histogram for XML String Selectivity Estimation,'' Proceedings of the 31st International Conference on Very Large Databases (VLDB '05), Trondheim, Norway, August-September 2005.

  Query optimization in IBM's System RX, the first truly hybrid relational-XML data management system, requires accurate selectivity estimation of path-value pairs, i.e., the number of nodes in the XML tree reachable by a given path with the given text value. Previous techniques have been inadequate, because they have focused mainly on the tag-labeled paths (tree structure) of the XML data. For most real XML data, the number of distinct string values at the leaf nodes is orders of magnitude larger than the set of distinct rooted tag paths. Hence, the real challenge lies in accurate selectivity estimation of the string predicates on the leaf values reachable via a given path.

  In this paper, we present CXHist, a novel workload-aware histogram technique that provides accurate selectivity estimation on a broad class of XML string-based queries. CXHist builds a histogram in an on-line manner by grouping queries into buckets using their true selectivity obtained from query feedback. The set of queries associated with each bucket is summarized into feature distributions. These feature distributions mimic a Bayesian classifier that is used to route a query to its associated bucket during selectivity estimation. We show how CXHist can be used for two general types of (path,string) queries: exact match queries and substring match queries. Experiments using a prototype show that CXHist provides accurate selectivity estimation for both exact match queries and substring match queries.

• W.-K. Hon, R. Shah, P. J. Varman, and J. S. Vitter. ``Tight Competitive Ratios for Parallel Disk Prefetching,'' Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '08), Munich, Germany, June 2008, 352-361.

  We consider the natural extension of the well-known single disk caching problem to the parallel disk I/O model (PDM) [17]. The main challenge is to achieve as much parallelism as possible and avoid I/O bottlenecks. We are given a fast memory (cache) of size $M$ memory blocks along with a request sequence $\Sigma = (b_1, b_2, \dots, b_n)$ where each block $b_i$ resides on one of $D$ disks. In each parallel I/O step, at most one block from each disk can be fetched. The task is to serve in the minimum number of parallel I/Os. Thus, each I/O is analogous to a page fault. The difference here is that during each page fault, up to $D$ blocks can be brought into memory, as long as all of the new blocks entering the memory reside on different disks. The problem has a long history. Note that this problem is non-trivial even if all requests in $\Sigma$ are unique. This restricted version is called read-once. Despite the progress in the online ver- sion and read-once version, the general online problem still remained open. Here, we provide comprehensive results with a full general solution for the problem with asymptotically tight competitive ratios.

  To exploit parallelism, any parallel disk algorithm needs a certain amount of lookahead into future requests. To provide effective caching, an online algorithm must achieve $o(D)$ competitive ratio. We show a lower bound that states, for lookahead $L \leq M$, that any online algorithm must be $\Omega(D)$-competitive. For lookahead $L$ greater than $M(1 + 1/\epsilon)$, where $\epsilon$ is a constant, the tight upper bound of $O(\sqrt{MD/L})$ on competitive ratio is achieved by our algorithm SKEW. The previous algorithm tLRU was $O((MD/L)^{2/3})$ competitive and this was also shown to be tight for an LRU-based strategy. We achieve the tight ratio using a fairly different strategy than LRU. We also show tight results for randomized algorithms against oblivious adversary and give an algorithm achieving better bounds in the resource augmentation model.