Exploring the design space of branch predictors can consume tremendous computational resources. In order to mitigate this problem we present a new non-clustered sampling technique for rapidly evaluating the performance of a large number of branch predictors in a single rapid pass through a trace. The predictors studied in this single pass need not closely resemble one another. Each may use a radically different method of indexing into one or more arrays of two bit counters. In experiments with SPEC95 benchmarks we have found that while sampling on the order of one branch per every ten thousand we can typically produce correct results for all but a few hundredths of a percent of the branches in the sample. The only instances we have found where this is not the case are degenerate cases in which we show that full-trace modeling also fails to give accurate results. Our technique is based on a general approach we call partial sampling. Partial sampling maintains a generic data structure as it scans a trace. At selected sample points in the trace, this structure is queried to determine the behavior of particular operations. The sampled operations need not be clustered.

We present a new approach to designing data structures for the important problem of externalmemory range searching in two and three dimensions. We construct data structures for answering range queries in O((log log log B N) log B N + K=B) I/O operations, where N is the number of points in the data structure, B is the I/O block size, and K is the number of points in the answer to the query. Our data structures answer a longstanding open problem by providing three dimensional results comparable to those provided by [8, 10] for the two dimensional case, though completely new techniques are used. Ours is the first 3-D range search data structure that simultaneously achieves both a base-B logarithmic search overhead (namely, (log log log B N) log B N) and a fully blocked output component (namely, K=B). This gives us an overall I/O complexity extremely close to the well-known lower bound of \\Omega\\Gamma/89 B N +K=B). We base our data structures on the novel concept of B-approximate boundarie...

In this paper we give new techniques for designing efficient algorithms for computational geometry problems that are too large to be solved in internal memory. We use these techniques to develop optimal and practical algorithms for a number of important large-scale problems. We discuss our algorithms primarily in the context of single processor/single disk machines, a domain in which they are not only the first known optimal results but also of tremendous practical value. Our methods also produce the first known optimal algorithms for a wide range of two-level and hierarchical multilevel memory models, including parallel models. The algorithms are optimal both in terms of I/O cost and internal computation.>

We examine I/O-efficient data structures that provide indexing support for new data models. The database languages of these models include concepts from constraint programming (e.g., relational tuples are generalized to conjunctions of constraints) and from object-oriented programming (e.g., objects are organized in class hierarchies). Let n be the size of the database, c the number of classes, B the secondary storage page size, and t the size of the output of a query. Indexing by one attribute in the constraint data model (for a fairly general type of constraints) is equivalent to external dynamic interval management, which is a special case of external dynamic 2-dimensional range searching. We present a semi-dynamic data structure for this problem which has optimal worst-case space O(n/B) pages and optimal query I/O time O(logBn+t/B) and has O(logBn+(log2Bn)/B) amortized insert I/O time. If the order of the insertions is random then the expected number of I/O operations needed to perform insertions is reduced to O(logBn). Indexing by one attribute and by class name in an object-oriented model, where objects are organized as a forest hierarchy of classes, is also a special case of external dynamic 2-dimensional range searching. Based on this observation we first identify a simple algorithm with good worst-case performance for the class indexing problem. Using the forest structure of the class hierarchy and techniques from the constraint indexing problem, we improve its query I/O time from O(log2c logBn + t/B) to O(logB + log2B).