Next: Return to Jeff Vitter Up: Online Electronic Catalog of Previous: 8 COMBINATORIAL ALGORITHMS AND
We examine a version of the dynamic dictionary problem in which stored items have expiration times and can be removed from the dictionary once they have expired. We show that under several reasonable assumptions about the distribution of the items, hashing with lazy deletion uses little more space than methods that use eager deletion. The simple algorithm suggested by this observation was used in a program for analyzing integrated circuit artwork.
We introduce and analyze a new one-pass algorithm for constructing
dynamic Huffman codes and also analyze the one-pass algorithm due to
Faller, Gallager, and Knuth. In each algorithm, both the sender and the
receiver maintain equivalent dynamically varying Huffman trees, and the
coding is done in real time. We show that the number of bits used by
the new algorithm to encode a message containing 
letters
is 
bits more than that used by the conventional two-pass Huffman scheme,
independent of the alphabet size. This is best possible in the worst
case, for any one-pass Huffman method. Tight upper and lower bounds are
derived. Empirical tests show that the encodings produced by the new
algorithm are shorter than those of the other one-pass algorithm and,
except for long messages, are shorter than those of the two-pass method.
The new algorithm is well-suited for online encoding/decoding in data
networks and for file compression.
We present a Pascal implementation of the one-pass algorithm for
constructing dynamic Huffman codes that is described and analyzed in a
companion paper [Vitter, 1987]. The program runs in real time; that is,
the processing time for each letter of the message is proportional to
the length of its codeword. The number of bits used to encode a message
of letters is less than bits more than that used by the
well-known two-pass algorithm. This is best possible for any one-pass
Huffman scheme. In practice it uses fewer bits than all other Huffman
schemes. The algorithm has applications in file compression and network
transmission.
We answer questions about the distribution of the maximum
size of queues and data structures as a function of time.
The concept of "maximum" occurs in many issues of resource
allocation. We consider several models of growth, including
general birth-and-death processes, the M/G/
model, and a
non-Markovian process (data structure) for processing
plane-sweep information in computational geometry, called
"hashing with lazy deletion" (HwLD). It has been shown that
HwLD is optimal in terms of expected time and dynamic space;
our results show that it is also optimal in terms of
expected preallocated space, up to a constant factor.
We take two independent and complementary approaches: first, in
Section 2, we use a variety of algebraic and analytical
techniques to derive exact formulas for the distribution of
the maximum queue size in stationary birth-and-death
processes and in a nonstationary model related to file
histories. The formulas allow numerical evaluation and some
asymptotics. In our second approach, in Section 3, we
consider the M/G/ model (which includes M/M/ as a
special case) and use techniques from the analysis of
algorithms to get optimal big-oh bounds on the expected
maximum queue size and on the expected maximum amount of
storage used by HwLD in excess of the optimal amount. The
techniques appear extendible to other models, such as M/M/1.
This paper develops two probabilistic methods that allow the analysis of the maximum data structure size encountered during a sequence of insertions and deletions in data structures such as priority queues, dictionaries, linear lists, and symbol tables, and in sweepline structures for geometry and Very-Large- Scale-Integration (VLSI) applications. The notion of the "maximum" is basic to issues of resource preallocation. The methods here are applied to combinatorial models of file histories and probabilistic models, as well as to a non-Markovian process (algorithm) for processing sweepline information in an efficient way, called "hashing with lazy deletion" (HwLD). Expressions are derived for the expected maximum data structure size that are asymptotically exact, that is, correct up to lower-order terms; in several cases of interest the expected value of the maximum size is asymptotically equal to the maximum expected size. This solves several open problems, including longstanding questions in queueing theory. Both of these approaches are robust and rely upon novel applications of techniques from the analysis of algorithms. At a high level, the first method isolates the primary contribution to the maximum and bounds the lesser effects. In the second technique the continuous-time probabilistic model is related to its discrete analog-the maximum slot occupancy in hashing.
We present a new complexity theoretic approach to incremental computation. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to existing complexity classes. We show that problems that have small sequential space complexity also have small incremental time complexity.
We show that all common LOGSPACE-complete problems for P are also incr-POLYLOGTIME-complete for P. We introduce a restricted notion of completeness called NRP-completeness and show that problems which are NRP-complete for P are also incr-POLYLOGTIME-complete for P. We also give incrementally complete problems for NLOGSPACE, LOGSPACE, and non-uniform NC1. We show that under certain restrictions problems which have efficient dynamic solutions also have efficient parallel solutions. We also consider a non-uniform model of incremental computation and show that in this model most problems have almost linear complexity. In addition, we present some techniques for lower bounding the complexity of explicitly defined problems.
We also look at the time complexity of circuit value and network stability problems restricted to comparator gates. We show that the comparator-circuit value problem and the “Lex-First Maximal Matching” problem are in incr-LOGSPACE while the comparator-network stability and the “Man-Optimal Stable Marriage Problem” are in rincr-LOGSPACE. This shows that the dynamic versions of these problems are solvable quickly in parallel even though there are no known NC algorithms to solve them from scratch.
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 
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.
We present and analyze efficient new algorithms for generating a
random variate distributed according to a dynamically changing set
of 
weights. The base version of each algorithm generates the
discrete random variate in 
expected time and updates a
weight in
expected time in the worst case. We
then show how to reduce the update time to amortized
expected time. We show how to apply our techniques to a recent lookup
table technique in order to obtain an expected constant time in the
worst case for generation and update. The algorithms are
conceptually simple. We give parallel algorithms for parallel
generation and update having optimal processors-time product. We
also give an efficient dynamic algorithm for maintaining
approximate heaps of elements; each query is required to return an
element whose value is within an 
factor of the maximal
element value. For
, each query,
insertion, or deletion takes
time.
Keywords: random number generator, random variate, alias, bucket, rejection, dynamic data structure, update, approximate priority queue.
In this paper we introduce the notion of approximate data
structures, in which a small amount of error is tolerated in the
output. Approximate data structures trade error of approximation for
faster operation, leading to theoretical and practical speedups for a
wide variety of algorithms. We give approximate variants of the van
Emde Boas data structure, which support the same dynamic operations as
the standard van Emde Boas data structure, except that answers to
queries are approximate. The variants support all operations in
constant time provided the error of approximation is
, and in 
time provided the error is
, for 
elements in the data
structure.
We consider the tolerance of prototypical algorithms to approximate data
structures. We study in particular Prim's minimum spanning tree
algorithm, Dijkstra's single-source shortest paths algorithm, and an
on-line variant of Graham's convex hull algorithm. To obtain output
which approximates the desired output with the error of approximation
tending to zero, Prim's algorithm requires only linear time, Dijkstra's
algorithm requires
time, and the on-line variant of
Graham's algorithm requires constant amortized time per operation.
We present a natural online
perfect matching problem motivated by problems in mobile computing.
A total of customers connect and disconnect sequentially,
and each customer has an associated
set of stations to which it may connect.
Each station has a capacity limit.
We allow the network to preemptively switch a customer between
allowed stations to make room for a new arrival.
We wish to minimize the total number of switches required to
provide service to every customer. Equivalently, we wish to maintain a
perfect matching between customers and stations and minimize
the lengths of the augmenting paths.
We measure performance by the worst case ratio of the number of switches
made to the minimum number required.
When each customer can be connected to at most
two stations:
and
.
.
.
when
the station capacities are 2.
Norm,”
Proceedings of the 36th Annual IEEE Symposium on Foundations of
Computer Science (FOCS '95), Milwaukee, WI, October 1995.
In the load balancing problem, there is a set of servers, and jobs
arrive sequentially. Each job can be run on some subset of the servers,
and must be assigned to one of them in an online fashion. Traditionally,
the assignment of jobs to servers is measured by the 
norm;
in other words, an assignment of jobs to servers is quantified by the
maximum load assigned to any server. In this measure the performance of
the greedy load balancing algorithm may be a logarithmic factor higher
than the offline optimal.
In many applications, the norm is not a suitable way to
measure how well the jobs are balanced. If each job sees a delay that is
proportional to the number of jobs on its server, then the average delay among all jobs is proportional to the sum of the
squares of the numbers of jobs assigned to the servers. Minimizing the
average delay is equivalent to minimizing the Euclidean (or 
) norm.
For any fixed 
,
, we show that the greedy algorithm
performs within a constant factor of the offline optimal with respect
to the norm. The constant grows linearly with , which is
best possible, but does not depend on the number of servers and jobs.
We present a new approach to designing data structures for the
important problem of external-memory range searching in two and three
dimensions. We construct data structures for answering range queries
in
I/O operations, where
is the number of points in the data structure, 
is the I/O
block size, and 
is the number of points in the answer to the
query. We base our data structures on the novel concept of
-approximate boundaries, which are manifolds that partition space
into regions based on the output size of queries at points within the
space.
Our data structures answer a longstanding open problem by providing
three dimensional results comparable to those provided by Sairam and
Ramaswamy 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- logarithmic
search overhead (namely,
) and a fully
blocked output component (namely, 
). This gives us an overall
I/O complexity extremely close to the well-known lower bound of
. The space usage is more than linear by
a logarithmic or polylogarithmic factor, depending on type of range
search.
We present a space- and I/O-optimal external-memory data structure for
answering stabbing queries on a set of dynamically maintained intervals.
Our data structure settles an open problem in databases and I/O algorithms
by providing the first optimal external-memory solution to the dynamic
interval management problem, which is a special case of 2-dimensional range
searching and a central problem for object-oriented and temporal databases
and for constraint logic programming. Our data structure simultaneously
uses optimal linear space (that is, 
blocks of disk space) and
achieves the optimal
I/O query bound and 
I/O update bound, where is the I/O block size and 
the number of
elements in the answer to a query. Our structure is also the first optimal
external data structure for a 2-dimensional range searching problem that
has worst-case as opposed to amortized update bounds. Part of the data
structure uses a novel balancing technique for efficient worst-case
manipulation of balanced trees, which is of independent interest.
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 
-disk parallel I/O system and a globally shared I/O buffer
that can hold up to 
disk blocks, we derive a lower bound of
on the competitive ratio of any deterministic
online prefetching algorithm with 
lookahead. NOM is shown to match
the lower bound using global -block lookahead. In contrast, using only
local lookahead results in an 
competitive ratio. When the
buffer is distributed into portions of 
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.
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 $
. 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
time and space, and its expected cost for the th
resource use converges to optimal as
, for any
bounded probability distribution on the resource use
times. Alternatively, using 
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 
, the relative importance of response time
to energy conservation. (The buy cost varies linearly with .)
We observe that by varying , 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 , 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 seconds). In addition, for small values
of (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%.
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 
lower bound on competitive ratio
proved for classical paging for a 
-sized cache.
For a size- cache shared by 
application processes that always
make good cache replacement decisions, we develop an online
application-controlled paging algorithm with a competitive ratio of
. Typically, is much smaller than , perhaps by
several orders of magnitude. Our competitive ratio improves upon the
competitive ratio achieved by Cao et al. We show
for this problem that no online algorithm 
can have a competitive
ratio better than 
even if the application processes aiding
have perfect knowledge of individual request sequences. Our results
are with respect to a worst-case interleaving of the individual request
sequences of the 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.
We describe the first known algorithm for efficiently maintaining a
Binary Space Partition (BSP) for continuously moving segments in
the plane. Under reasonable assumptions on the motion, we show that
the total number of times the BSP changes is 
, and that we can
update the BSP in expected time per change. We also
consider the problem of constructing a BSP for triangles in
three-dimensional Euclidean space. We present a randomized algorithm
that constructs a BSP of expected size in
expected time. We also describe a deterministic algorithm that
constructs a BSP of size
and height
in
time, where is the number of
intersection points between the edges of the projections of the
triangles onto the 
-plane.
For a polyhedral terrain, the contour at 
-coordinate 
is
defined to be the intersection of the
plane 
with the terrain. In this paper, we study the
contour-line extraction problem, where we want to preprocess
the terrain into a data structure so that given a query
-coordinate , we can report the -contour quickly. This problem
is central to geographic information systems (GIS),
where terrains are often stored as Triangular Irregular Networks
(TINs). We present an I/O-optimal algorithm for this problem which
stores a terrain with vertices using blocks,
where is the size of a disk block, so that for any query ,
the -contour can be computed using
I/O operations, where 
denotes the size of the -contour.
We also present an improved algorithm for a more general problem of blocking bounded-degree planar graphs such as TINs (i.e., storing them on disk so that any graph traversal algorithm can traverse the graph in an I/O-efficient manner). We apply it to two problems that arise in GIS.
We show how to preprocess a set 
of points in 
-dimensional
Euclidean space to get an external memory data structure that
efficiently supports linear-constraint queries. Each query is in the
form of a linear constraint
; the data
structure must report all the points of that satisfy the query.
(This problem is called halfspace range searching in the computational
geometry literature.) Our goal is to minimize the number of disk
blocks required to store the data structure and the number of disk
accesses (I/Os) required to answer a query. For 
, we present
the first near-linear size data structures that can answer
linear-constraint queries using an optimal number of I/Os. We also
present a linear-size data structure that can answer queries
efficiently in the worst case. We combine these two approaches to
obtain tradeoffs between space and query time. Finally, we show that
some of our techniques extend to higher dimensions.
In recent years there has been an upsurge of interest in spatial databases. A major issue is how to efficiently manipulate massive amounts of spatial data stored on disk in multidimensional spatial indexes (data structures). Construction of spatial indexes (bulk loading) has been researched intensively in the database community. The continuous arrival of massive amounts of new data make it important to efficiently update existing indexes (bulk updating).
In this article we present a simple technique for performing bulk update and query operations on multidimensional indexes. We present our technique in terms of the so-called R-tree and its variants, as they have emerged as practically efficient indexing methods for spatial data. Our method uses ideas from the buffer tree lazy buffering technique and fully utilizes the available internal memory and the page size of the operating system. We give a theoretical analysis of our technique, showing that it is efficient both in terms of I/O communication, disk storage, and internal computation time. We also present the results of an extensive set of experiments showing that in practice our approach performs better than the previously best known bulk update methods with respect to update time, and that it produces a better quality index in terms of query performance. One important novel feature of our technique is that in most cases it allows us to perform a batch of updates and queries simultaneously. To be able to do so is essential in environments where queries have to be answered even while the index is being updated and reorganized.
We present an efficient external-memory dynamic data structure for point
location in monotone planar subdivisions. Our data structure uses
disk blocks to store a monotone subdivision of size , where
is the size of a disk block. It supports queries in 
I/Os (worst-case) and updates in I/Os (amortized).
We also propose a new variant of -trees, called level-balanced
-trees, which allow insert, delete, merge, and split operations in
I/Os (amortized),
, even if each node stores a pointer to its parent.
Here is the size of main memory. Besides being essential to our
point-location data structure, we believe that level-balanced
B-trees are of significant independent interest. They can, for
example, be used to dynamically maintain a planar st-graph using
I/Os
(amortized) per update, so that reachability queries can be answered in
I/Os (worst case).
In this paper we settle several longstanding open problems in theory of indexability and external orthogonal range searching. In the first part of the paper, we apply the theory of indexability to the problem of two-dimensional range searching. We show that the special case of 3-sided querying can be solved with constant redundancy and access overhead. From this, we derive indexing schemes for general 4-sided range queries that exhibit an optimal tradeoff between redundancy and access overhead.
In the second part of the paper, we develop dynamic external memory data
structures for the two query types. Our structure for 3-sided queries
occupies disk blocks, and it supports insertions and deletions
in I/Os and queries in
I/Os, where
is the disk block size, is the number of points, and is the
query output size. These bounds are optimal. Our structure for general
(4-sided) range searching occupies
disk blocks and answers queries in
I/Os, which are optimal. It also supports updates in
I/Os.
This survey article is superseded by a more comprehensive book. The book is available online and is recommended as the preferable reference.
Slides for ICALP '99 talk (gzip-compressed postscript)
The data sets for many of today's computer applications are too large to fit within the computer's internal memory and must instead be stored on external storage devices such as disks. A major performance bottleneck can be the input/output communication (or I/O) between the external and internal memories. In this paper we discuss a variety of online data structures for external memory, some very old and some very new, such as hashing (for dictionaries), B-trees (for dictionaries and 1-D range search), buffer trees (for batched dynamic problems), interval trees with weight-balanced B-trees (for stabbing queries), priority search trees (for 3-sided 2-D range search), and R-trees and other spatial structures. We also discuss several open problems along the way.
We consider the problem of devising external memory algorithms whose memory allocations can change dynamically and unpredictably at run-time. The investigation of “memory-adaptive” algorithms, which are designed to adapt to dynamically changing memory allocations, can be considered a natural extension of the investigation of traditional, non-adaptive external memory algorithms. Our study is motivated by high performance database systems and operating systems in which applications are prioritized and internal memory is dynamically allocated in accordance with the priorities. In such situations, external memory applications are expected to perform as well as possible for the current memory allocation. The computation must be reorganized to adapt to the sequence of memory allocations in an online manner.
In this paper we present a simple and natural dynamic memory allocation model. We define memory-adaptive external memory algorithms and specify what is needed for them to be dynamically optimal. Using novel techniques, we design and analyze dynamically optimal memory-adaptive algorithms for the problems of sorting, permuting, FFT, permutation networks, (standard) matrix multiplication and LU decomposition. We also present a dynamically optimal (in an amortized sense) memory-adaptive version of the buffer tree, a generic external memory data structure for a large number of batched dynamic applications. We show that a previously devised approach to memory-adaptive external mergesort is provably nonoptimal because of fundamental drawbacks. The lower bound proof techniques for sorting and matrix multiplication are fundamentally distinct techniques, and they are invoked by most other external memory lower bounds; hence we anticipate that the techniques presented here will apply to many external memory problems.
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.
Slides for a talk (Adobe pdf format)
This survey article is superseded by a more comprehensive book. The book is available online and is recommended as the preferable reference.
Slides for talk (Adobe pdf format)
The proliferation of online text, such as on the World Wide Web and
in databases, motivates the need for space-efficient index methods
that support fast search. Consider a text of binary symbols
to index. Given any query pattern of binary symbols, the
goal is to search for in quickly, with being fully
scanned only once, namely, when the index is created. All indexing
schemes published in the last thirty years support searching in
worst-case time and require 
memory words (or
bits), which is significantly larger than the
text itself. In this paper we provide a breakthrough both in
searching time and index space under the same model of computation
as the one adopted in previous work. Based upon new compressed
representations of suffix arrays and suffix trees, we construct an
index structure that occupies only 
bits and compares
favorably with inverted lists in space. We can search any binary
pattern , stored in 
words, in only 
time.
Specifically, searching takes time for 
, and
time for
and any fixed
. That is, we achieve optimal
search time for sufficiently large
.
We can list all the 
pattern occurrences in optimal
additional time when
or when
; otherwise, listing takes
additional time.
This paper investigates the problem of high-level querying of multimedia data by imposing arbitrary domain-specific constraints among multimedia objects. We argue that the current structured query model, and the query-by-content model, are insufficient for many important applications, and we propose an alternative query framework that unifies and extends the previous two models. The proposed framework is based on the querying-by-concept paradigm, where the query is expressed simply in terms of concepts, regardless of the complexity of the underlying multimedia search engines. The query-by-concept paradigm was previously illustrated by the CAMEL system. The present paper builds upon and extends that work by adding arbitrary constraints and multiple levels of hierarchy in the concept representation model.
We consider queries simply as descriptions of virtual data sets, and that allows us to use the same unifying concept representation for query specification, as well as for data annotation purposes. We also identify some key issues and challenges presented by the new framework, and we outline possible approaches for overcoming them. In particular, we study the problems of concept representation, extraction, refinement, storage, and matching.
The problem of content-based image searching has received considerable attention in the last few years. Thousands of images are now available on the internet, and many important applications require searching of images in domains such as E-commerce, medical imaging, weather prediction, satellite imagery, and so on. Yet, content-based image querying is still largely unestablished as a mainstream field, nor is it widely used by search engines. We believe that two of the major hurdles for this poor acceptance are poor retrieval quality and usability.
In this paper, we introduce the CAMEL system--an acronym for Concept Annotated iMagE Libraries--as an effort to address both of the above problems. The CAMEL system provides and easy-to-use, and yet powerful, text-only query interface, which allows users to search for images based on visual concepts, identified by specifying relevant keywords. Conceptually, CAMEL annotates images with the visual concepts that are relevant to them. In practice, CAMEL defines visual concepts by looking at sample images off-line and extracting their relevant visual features. Once defined, such visual concepts can be used to search for relevant images on the fly, using content-based search methods. The visual concepts are stored in a Concept Library and are represented by an associated set of wavelet features, which in our implementation were extracted by the WALRUS image querying system. Even though the CAMEL framework applies independently of the underlying query engine, for our prototype we have chosen WALRUS as a back-end, due to its ability to extract and query with image region features.
CAMEL improves retrieval quality because it allows experts to build very accurate representations of visual concepts that can be used even by novice users. At the same time, CAMEL improves usability by supporting the familiar text-only interface currently used by most search engines on the web. Both improvements represent a departure from traditional approaches to improving image query systems--instead of focusing on query execution, we emphasize query specification by allowing simpler and yet more precise query specification.
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.
Recent work on incremental crawling has enabled the indexed document collection of a search engine to be more synchronized with the changing World Wide Web. However, this synchronized collection is not immediately searchable, because the keyword index is rebuilt from scratch less frequently than the collection can be refreshed. An inverted index is usually used to index documents crawled from the web. Complete index rebuild at high frequency is expensive. Previous work on incremental inverted index updates have been restricted to adding and removing documents. Updating the inverted index for previously indexed documents that have changed has not been addressed.
In this paper, we propose an efficient method to update the inverted index for previously indexed documents whose contents have changed. Our method uses the idea of landmarks together with the diff algorithm to significantly reduce the number of postings in the inverted index that need to be updated. Our experiments verify that our landmark-diff method results in significant savings in the number of update operations on the inverted index.
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.
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.
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
competitive
ratio and a randomized online algorithm threshold-MARK which
achieves
competitive ratio for
the caching/prefetching problem on the parallel disk model
(PDM), where is the number of disks, is the size of fast
memory buffer, and 
is the amount of lookahead
available in the request sequence. The best-known lower
bound on the competitive ratio is
for
lookahead 
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
can be achieved. This problem generalizes the
well-known paging problem on a single disk to the parallel
disk model.
One of the central tasks in managing, monitoring and mining data streams is that of identifying outliers. There is a long history of study of various outliers in statistics and databases, and a recent focus on mining outliers in data streams. Here, we adopt the notion of deviants from Jagadish et al as outliers. Deviants are based on one of the most fundamental statistical concept of standard deviation (or variance). Formally, deviants are defined based on a representation sparsity metric, i.e., deviants are values whose removal from the dataset leads to an improved compressed representation of the remaining items. Thus, deviants are not global maxima/minima, but rather these are appropriate local aberrations. Deviants are known to be of great mining value in time series databases. We present first-known algorithms for identifying deviants on massive data streams. Our algorithms monitor streams using very small space (polylogarithmic in data size) and are able to quickly find deviants at any instant, as the data stream evolves over time. For all versions of this problem--univariate vs multivariate time series, optimal vs nearoptimal vs heuristic solutions, offline vs streaming--our algorithms have the same framework of maintaining a hierarchical set of candidate deviants that are updated as the time series data gets progressively revealed. We show experimentally using real network traffic data (SNMP aggregate time series) as well as synthetic data that our algorithm is remarkably accurate in determining the deviants.
It is infeasible for a sensor database to contain the exact value of each sensor at all points in time. This uncertainty is inherent in these systems due to measurement and sampling errors, and resource limitations. In order to avoid drawing erroneous conclusions based upon stale data, the use of uncertainty intervals that model each data item as a range and associated probability density function (pdf) rather than a single value has recently been proposed. Querying these uncertain data introduces imprecision into answers, in the form of probability values that specify the likeliness the answer satisfies the query. These queries are more expensive to evaluate than their traditional counterparts but are guaranteed to be correct and more informative due to the probabilities accompanying the answers. Although the answer probabilities are useful, for many applications, it is only necessary to know whether the probability exceeds a given threshold; we term these Probabilistic Threshold Queries (PTQ). In this paper we address the efficient computation of these types of queries.
In particular, we develop two index structures and associated algorithms to efficiently answer PTQs. The first index scheme is based on the idea of augmenting uncertainty information to an R-tree. We establish the difficulty of this problem by mapping one-dimensional intervals to a two-dimensional space, and show that the problem of interval indexing with probabilities is significantly harder than interval indexing which is considered a well-studied problem. To overcome the limitations of this R-tree based structure, we apply a technique we call variance-based clustering, where data points with similar degrees of uncertainty are clustered together. Our extensive index structure can answer the queries for various kinds of uncertainty pdfs, in an almost optimal sense. We conduct experiments to validate the superior performance of both indexing schemes.
In an uncertain database, each data item is modeled as a range associated with a probability density function. Previous works for this kind of data have focused on simple queries such as range and nearest-neighbor queries. Queries that join multiple relations have not been addressed in earlier work despite the significance of joins in databases. In this paper, we address probabilistic join over uncertain data, essentially a query that augments the results with probability guarantees to indicate the likelihood of each join tuple being part of the result. We extend the notion of join operators, such as equality and inequality, for uncertain data. We also study the performance of probabilistic join. We observe that a user may only need to know whether the probability of the results exceeds a given threshold, instead of the precise probability value. By incorporating this constraint, it is possible to achieve much better performance. In particular, we develop three sets of optimization techniques, namely item-level, page-level and index-level pruning, for different join operators. These techniques facilitate pruning with little space and time overhead, and are easily adapted to most join algorithms. We verify the performance of these techniques experimentally.
Run-Length-Encoding (RLE) is a data compression technique
that is used in various applications, e.g., biological se-
quence databases, multimedia, and facsimile transmission.
One of the main challenges is how to operate, e.g.,
indexing, searching, and retrieval, on the compressed data
without decompressing it. In this paper, we present the
String B-tree for Compressed sequences, termed the SBC-tree,
for indexing and searching RLE-compressed sequences of
arbitrary length. The SBC-tree is a two-level index
structure based on the well-known String B-tree and a
3-sided range query structure. The SBC-tree supports
substring as well as prefix matching, and range search
operations over RLE-compressed sequences. The SBC-tree has
an optimal external-memory space complexity of pages,
where is the total length of the compressed sequences, and
is the disk page size. The insertion and deletion of all
suffixes of a compressed sequence of length m takes
I/O operations. Substring matching, prefix
matching, and range search execute in an optimal
I/O operations, where 
is the length of the
compressed query pattern and is the query output size. We
present also two variants of the SBC-tree: the SBC-tree that
is based on an R-tree instead of the 3-sided structure, and
the one-level SBC-tree that does not use a two-dimensional
index.
These variants do not have provable worst-case theoretical
bounds for search operations, but perform well in practice.
The SBC-tree index is realized inside PostgreSQL in the
context of a biological protein database
application. Performance results illustrate that using the
SBC-tree to index
RLE-compressed sequences achieves up to an order of
magnitude reduction in storage, up to 30% reduction in I/Os
for
the insertion operations, and retains the optimal search
performance achieved by the String B-tree over the uncompressed sequences.
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 memory blocks along with a
request sequence
where
each block 
resides on one of 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
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 
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 
competitive ratio. We show a lower bound that states, for
lookahead 
, that any online algorithm must be
-competitive. For lookahead 
greater than
, where is a constant, the tight
upper bound of
on competitive ratio is
achieved by our algorithm SKEW. The previous algorithm tLRU
was
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.
We consider a central problem in text indexing: Given a
text over an alphabet , construct a compressed
data structure answering the queries
,
, and
for a symbol 
.
Many data structures consider these queries for static
text . We consider the dynamic version of the problem,
where we are allowed to insert and delete symbols at
arbitrary positions of . This problem is a key challenge
in compressed text indexing and has direct application to
dynamic XML indexing structures that answer subpath
queries [XBW].
We build on the results of [RRR, GMR] and give the best
known query bounds for the dynamic version of this problem,
supporting arbitrary insertions and deletions of symbols
in . Specifically, with an amortized update time of
, we suggest how to support
,
, and
queries in
time, for any 
.
The best previous query times for this problem were
, given by [Makinen Navarro]. Our bounds
are competitive with state-of-the-art static structures
[GMR]. Some applicable lower bounds for the partial sums
problem [PD] show that our update/query tradeoff is also
nearly optimal. In addition, our space bound is competitive
with the corresponding static structures. For the special
case of bitvectors (i.e., 
), we also show the
best tradeoffs for query/update time, improving upon the
results of [Makinen Navarro, Hon, RRR].
Our focus on fast query/slower update is
well-suited for a query-intensive XML indexing environment.
Using the XBW transform [XBW], we also present a
dynamic data structure that succinctly maintains an ordered
labeled tree and supports a powerful set of queries
on .
aw, Poland, July 2007,
published in Lecture Notes in Computer Science, 4596
Springer-Verlag, Berlin, Germany, 521-532.
We present a framework to dynamize succinct data structures,
to encourage their use over non-succinct versions in a wide
variety of important application areas. Our framework can
dynamize most state-of-the-art succinct data structures for
dictionaries, ordinal trees, labeled trees, and text
collections. Of particular note is its direct application to
XML indexing structures that answer
queries. Our
framework focuses on achieving information-theoretically
optimal space along with near-optimal update/query bounds.
As the main part of our work, we consider the following
problem central to text indexing: Given a text over an
alphabet , construct a compressed data structure
answering the queries
,
, and
for a symbol . Many data
structures consider these queries for static text . We
build on these results and give the best known query bounds
for the dynamic version of this problem, supporting
arbitrary insertions and deletions of symbols in .
Specifically, with an amortized update time of
, any static succinct data structure for
, taking 
time for queries, can be converted by our
framework into a dynamic succinct data structure that
supports
,
,
and
queries in
time, for any constant
. When
, we achieve
query times. Our update/query bounds are near-optimal
with respect to the lower bounds.
Slides for a talk (Adobe pdf format)
Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. In this book we discuss the state of the art in the design and analysis of external memory (or EM) algorithms and data structures, where the goal is to exploit locality in order to reduce the I/O costs. We consider a variety of EM paradigms for solving batched and online problems efficiently in external memory.
For the batched problem of sorting and related problems like permuting and fast Fourier transform, the key paradigms include distribution and merging. The paradigm of disk striping offers an elegant way to use multiple disks in parallel. For sorting, however, disk striping can be nonoptimal with respect to I/O, so to gain further improvements we discuss prefetching, distribution, and merging techniques for using the disks independently. We also consider useful techniques for batched EM problems involving matrices (such as matrix multiplication and transposition), geometric data (such as finding intersections and constructing convex hulls) and graphs (such as list ranking, connected components, topological sorting, and shortest paths). In the online domain, canonical EM applications include dictionary lookup and range searching. The two important classes of indexed data structures are based upon extendible hashing and B-trees. The paradigms of filtering and bootstrapping provide a convenient means in online data structures to make effective use of the data accessed from disk. We also reexamine some of the above EM problems in slightly different settings, such as when the data items are moving, when the data items are variable-length (e.g., text strings), when the internal data representations are compressed, or when the allocated amount of internal memory can change dynamically.
Programming tools and environments are available for simplifying the EM programming task. During the course of the book, we report on some experiments in the domain of spatial databases using the TPIE system (Transparent Parallel I/O programming Environment). The newly developed EM algorithms and data structures that incorporate the paradigms we discuss are significantly faster than methods currently used in practice.
This book is an expanded version of an earlier survey article.
In the dynamic indexing problem, we must maintain a changing collection of text documents so that we can e ciently support insertions, deletions, and pattern matching queries. We are especially interested in developing e cient data structures that store and query the documents in compressed form. All previous compressed solutions to this problem rely on answering rank and select queries on a dynamic sequence of symbols. Because of the lower bound in [Fredman and Saks, 1989], answering rank queries presents a bottleneck in compressed dynamic indexing. In this paper we show how this lower bound can be circumvented using our new framework. We demonstrate that the gap between static and dynamic variants of the indexing problem can be almost closed. Our method is based on a novel framework for adding dynamism to static compressed data structures. Our framework also applies more generally to dynamizing other problems. We show, for example, how our framework can be applied to develop compressed representations of dynamic graphs and binary relations.