Arrow Research search

Author name cluster

Jeffrey Scott Vitter

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

37 papers
2 author rows

Possible papers

37

TCS Journal 2013 Journal Article

Faster compressed dictionary matching

  • Wing-Kai Hon
  • Tsung-Han Ku
  • Rahul Shah
  • Sharma V. Thankachan
  • Jeffrey Scott Vitter

Given a set D of d patterns, the dictionary matching problem is to index D such that for any query text T, we can locate the occurrences of any pattern within T efficiently. When D contains a total of n characters drawn from an alphabet of size σ, Hon et al. (2008) [12] gave an n H k ( D ) + o ( n log σ ) -bit index which supports a query in O ( | T | ( log ϵ n + log d ) + o c c ) time, where ϵ > 0 and H k ( D ) denotes the k th-order entropy of D. Very recently, Belazzougui (2010) [3] has proposed an elegant scheme, which takes n log σ + O ( n ) bits of index space and supports a query in optimal O ( | T | + o c c ) time. In this paper, we provide connections between Belazzougui’s index and the XBW compression of Ferragina and Manzini (2005) [8], and show that Belazzougui’s index can be slightly modified to be stored in n H k ( D ) + O ( n ) bits, while query time remains optimal; this improves the compressed index by Hon et al. (2008) [12] in both space and time.

Details DOI

TCS Journal 2011 Journal Article

Cache-oblivious index for approximate string matching

  • Wing-Kai Hon
  • Tak-Wah Lam
  • Rahul Shah
  • Siu-Lung Tam
  • Jeffrey Scott Vitter

This paper revisits the problem of indexing a text for approximate string matching. Specifically, given a text T of length n and a positive integer k, we want to construct an index of T such that for any input pattern P, we can find all its k -error matches in T efficiently. This problem is well-studied in the internal-memory setting. Here, we extend some of these recent results to external-memory solutions, which are also cache-oblivious. Our first index occupies O ( ( n log k n ) / B ) disk pages and finds all k -error matches with O ( ( | P | + o c c ) / B + log k n log log B n ) I/Os, where B denotes the number of words in a disk page. To the best of our knowledge, this index is the first external-memory data structure that does not require Ω ( | P | + o c c + poly ( log n ) ) I/Os. The second index reduces the space to O ( ( n log n ) / B ) disk pages, and the I/O complexity is O ( ( | P | + o c c ) / B + log k ( k + 1 ) n log log n ).

Details DOI

FOCS Conference 2009 Conference Paper

Space-Efficient Framework for Top-k String Retrieval Problems

  • Wing-Kai Hon
  • Rahul Shah 0001
  • Jeffrey Scott Vitter

Given a set D={d 1, d 2, .. ., d D } of D strings of total length n, our task is to report the "most relevant"strings for a given query pattern P. This involves somewhat more advanced query functionality than the usual pattern matching, as some notion of "most relevant" is involved. In information retrieval literature, this task is best achieved by using inverted indexes. However, inverted indexes work only for some predefined set of patterns. In the pattern matching community, the most popular pattern-matching data structures are suffix trees and suffix arrays. However, a typical suffix tree search involves going through all the occurrences of the pattern over the entire string collection, which might be a lot more than the required relevant documents. The first formal framework to study such kind of retrieval problems was given by Muthukrishnan. He considered two metrics for relevance: frequency and proximity. He took a threshold-based approach on these metrics and gave data structures taking O(n log n) words of space. We study this problem in a slightly different framework of reporting the top k most relevant documents (in sorted order) under similar and more general relevance metrics. Our framework gives linear space data structure with optimal query times for arbitrary score functions. As a corollary, it improves the space utilization for the problems in while maintaining optimal query performance. We also develop compressed variants of these data structures for several specific relevance metrics.

Details

TCS Journal 2007 Journal Article

Compressed data structures: Dictionaries and data-aware measures

  • Ankur Gupta
  • Wing-Kai Hon
  • Rahul Shah
  • Jeffrey Scott Vitter

In this paper, we propose measures for compressed data structures, in which space usage is measured in a data-aware manner. In particular, we consider the fundamental dictionary problem on set data, where the task is to construct a data structure for representing a set S of n items out of a universe U = { 0, …, u − 1 } and supporting various queries on S. We use a well-known data-aware measure for set data called gap to bound the space of our data structures. We describe a novel dictionary structure that requires gap + O ( n log ( u / n ) / log n ) + O ( n log log ( u / n ) ) bits. Under the RAM model, our dictionary supports membership, rank, and predecessor queries in nearly optimal time, matching the time bound of Andersson and Thorup’s predecessor structure [A. Andersson, M. Thorup, Tight(er) worst-case bounds on dynamic searching and priority queues, in: ACM Symposium on Theory of Computing, STOC, 2000], while simultaneously improving upon their space usage. We support select queries even faster in O ( log log n ) time. Our dictionary structure uses exactly gap bits in the leading term (i. e. , the constant factor is 1) and answers queries in near-optimal time. When seen from the worst-case perspective, we present the first O ( n log ( u / n ) ) -bit dictionary structure that supports these queries in near-optimal time under the RAM model. We also build a dictionary which requires the same space and supports membership, select, and partial rank queries even more quickly in O ( log log n ) time. We go on to show that for many (real-world) datasets, data-aware methods lead to a worthwhile compression over combinatorial methods. To the best of our knowledge, these are the first results that achieve data-aware space usage and retain near-optimal time.

Details DOI

FOCS Conference 1999 Conference Paper

A Theoretical Framework for Memory-Adaptive Algorithms

  • Rakesh D. Barve
  • Jeffrey Scott Vitter

External memory algorithms play a key role in database management systems and large scale processing systems. External memory algorithms are typically tuned for efficient performance given a fixed, statically allocated amount of internal memory. However, with the advent of real-time database system and database systems based upon administratively defined goals, algorithms must increasingly be able to adapt in an online manner when the amount of internal memory allocated to them changes dynamically and unpredictably. We present a theoretical and applicable framework for memory-adaptive algorithms (or simply MA algorithms). We define the competitive worst-case notion of what it means for an MA algorithm to be dynamically optimal and prove fundamental lower bounds on the performance of MA algorithms for problems such as sorting, standard matrix multiplication, and several related problems. Our main tool for proving dynamic optimality is the notion of resource consumption, which measures how efficiently an MA algorithm adapts itself to memory fluctuations. We present the first dynamically optimal algorithm for sorting (based upon mergesort), permuting, FFT, permutation networks, buffer trees, (standard) matrix multiplication, and LU decomposition. In each case, dynamic optimality is demonstrated via a potential function argument showing that the algorithm's resource consumption is within a constant factor of optimal.

Details

FOCS Conference 1996 Conference Paper

Binary Search Partitions for Fat Rectangles

  • Pankaj K. Agarwal
  • Edward F. Grove
  • T. M. Murali 0001
  • Jeffrey Scott Vitter

The authors consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in R/sup 3/ such that the aspect ratio of each rectangle in S is at most /spl alpha/, for some constant a /spl alpha//spl ges/1. They present an n2/sup O(/spl radic/logn)/-time algorithm to build a binary space partition of size n2/sup O(/spl radic/logn)/ for S. They also show that if m of the n rectangles in S have aspect ratios greater than /spl alpha/, they can contact a BSP of size n/spl radic/m2/sup O(/spl radic/logn)/ for S in n/spl radic/2/sup O(/spl radic/logn)/ time. The constants of proportionality in the big-oh terms are linear in log /spl alpha/. They extend these results to cases in which the input contains non-orthogonal or intersecting objects.

Details

FOCS Conference 1996 Conference Paper

Optimal Dynamic Interval Management in External Memory (extended abstract)

  • Lars Arge
  • Jeffrey Scott Vitter

The authors present a space- and I/O-optimal external-memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The 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. The data structure simultaneously uses optimal linear space (that is, O(N/B) blocks of disk space) and achieves the optimal O(log/sub B/ N+T/B) I/O query bound and O(log/sub B/ N) I/O update bound, where B is the I/O block size and T the number of elements in the answer to a query. The 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.

Details

I&C Journal 1996 Journal Article

Using Vapnik–Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments

  • Kathleen Romanik
  • Jeffrey Scott Vitter

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.

Details DOI

FOCS Conference 1995 Conference Paper

Application-Controlled Paging for a Shared Cache (Extended Abstract)

  • Rakesh D. Barve
  • Edward F. Grove
  • Jeffrey Scott Vitter

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/sub k/ lower bound on competitive ratio proved for classical paging for a k-sized cache in [FKL/sup +/91]. 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 and competitive ratio of 2H/sub 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 [CFL94a]. We show for this problem that no on-line algorithm A can have a competitive ratio better than H/sub 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.

Details

FOCS Conference 1995 Conference Paper

Load Balancing in the L p Norm

  • Baruch Awerbuch
  • Yossi Azar
  • Edward F. Grove
  • Ming-Yang Kao
  • P. Krishnan
  • Jeffrey Scott Vitter

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 L/sub /spl infin// 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 L/sub /spl infin// 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 L/sub 2/) norm. For any fixed p, 1/spl les/p</spl infin/, we show that the greedy algorithm performs within a constant factor of the offline optimal with respect to the L/sub p/ norm. The constant grows linearly with p, which is best possible, but does not depend on the number of servers and jobs.

Details

TCS Journal 1994 Journal Article

Complexity models for incremental computation

  • Peter Bro Miltersen
  • Sairam Subramanian
  • Jeffrey Scott Vitter
  • Roberto Tamassia

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 nonuniform NC1. We show that under certain restrictions problems which have efficient dynamic solutions also have efficient parallel solutions. We also consider a nonuniform 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(NLOGSPACE). 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.

Details DOI

FOCS Conference 1993 Conference Paper

External-Memory Computational Geometry (Preliminary Version)

  • Michael T. Goodrich
  • Jyh-Jong Tsay
  • Darren Erik Vengroff
  • Jeffrey Scott Vitter

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. >

Details

STOC Conference 1992 Conference Paper

epsilon-Approximations with Minimum Packing Constraint Violation (Extended Abstract)

  • Jyh-Han Lin
  • Jeffrey Scott Vitter

We present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding NP -hard discrete optimization problem. Without any constraint violation, the ε-approximation problem for many problems of this type is itself NP -hard. Our methods provide polynomial-time ε-approximations while attempting to minimize the packing constraint violation.

Details

I&C Journal 1992 Journal Article

Learning in parallel

  • Jeffrey Scott Vitter
  • Jyh-Han Lin

In this paper, we extend Valiant's (Comm. ACM 27 (1984), 1134–1142) sequential model of concept learning from examples and introduce models for the efficient learning of concept classes from examples in parallel. We say that a concept class is 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 NC -learnable in constant time. Some other classes can be shown to be 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 NC -learnable using a nongreedy technique. We also show that (unless P ⊆ RNC ) several polynomial-time learnable concept classes related to linear programming are not NC -learnable. Equivalence of various parallel learning models and issues of fault-tolerance are also discussed.

Details DOI

FOCS Conference 1991 Conference Paper

Optimal Prefetching via Data Compression (Extended Abstract)

  • Jeffrey Scott Vitter
  • P. Krishnan

A form of the competitive philosophy is applied 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. The algorithms 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, one has to be able to predict feature data well, and thus good data compressors should be able to predict well for purposes of prefetching. It is shown for powerful models such as Markov sources and mth order Markov sources that the page fault rates incurred by the prefetching algorithms presented are optimal in the limit for almost all sequences of page accesses. >

Details

FOCS Conference 1985 Conference Paper

Design and Analysis of Dynamic Huffman Coding (Extended Abstract)

  • Jeffrey Scott Vitter

We introduce an efficient new algorithm for dynamic Huffman coding, called Algorithm V. It performs one-pass coding and transmission in real-time, and uses at most one more bit per letter than does the standard two-pass Huffman algorithm; this is optimum in the worst case among all one-pass schemes. We also analyze the dynamic Huffman algorithm due to Faller, Gallager, and Knuth. In each algorithm, both the sender and the receiver maintain equivalent dynamically varying Huffman trees. The processing time required to encode and decode a letter whose node in the dynamic Huffman tree is currently on the lth level is O(l); hence, the processing can be done in real time. Empirical tests show that Algorithm V performs quite well in practice, often better than the two-pass method. The proposed algorithm is well-suited for file compression and online encoding/decoding in data networks.

Details

FOCS Conference 1984 Conference Paper

Shortest Paths in Euclidean Graphs (Extended Abstract)

  • Robert Sedgewick
  • Jeffrey Scott Vitter

We analyze a simple method for finding shortest paths in Euclidean graphs (where vertices are points in a Euclidean space and edge weights are distances between points). For many graph models, the running time of the algorithm to find the shortest path between a specified pair of vertices in a graph with V vertices and E edges is shown to be O(V) as compared with O (V log V + E) required by the classical (Dijkstra) algorithm.

Details

FOCS Conference 1983 Conference Paper

Optimum Algorithms for Two Random Sampling Problems (Extended Abstract)

  • Jeffrey Scott Vitter

Several fast new algorithms are presented for sampling n records at random from a file containing N records. The first problem we solve deals with sampling when N is known, and the the second problem considers the case when N is unknown. The two main results in this paper are Algorithms D and Z. Algorithm D solves the first problem by doing the sampling with a small constant amount of space and in O(n) time, on the average; roughly n uniform random variates are generated, and approximately n exponentiation operations are performed during the sampling The sample is selected sequentially and online; it answers an open problem in [Knuth 81]. Algorithm Z solves the second problem by doing the sampling using O(n) space, roughly n ln(N/n) uniform random variates and O(n(1 + log(N/n))) time, on the average. Both algorithms are time- and space-optimum and are short and easy to implement.

Details

FOCS Conference 1981 Conference Paper

Deletion Algorithms for Hashing that Preserve Randomness (detailed abstract)

  • Jeffrey Scott Vitter

This paper studies the problem of finding efficient deletion algorithms for the coalesced hashing method, in which a portion of memory (called the address region) serves as the range of the hash function while the rest of memory (called the cellar) is devoted solely to storing records that collide when inserted. We present a deletion algorithm, which solves the open problem described in [Knu73, §6. 4-23]. The main result of this paper, Theorem 3, shows that the deletion algorithm preserves randomness for the special case of standard coalesced hashing, in that deleting a record is in some sense like never having inserted it. This means that the formulas for the search times (which are analyzed in [Vit80a] and [Vit80b]) are still valid after deletions. There is as yet no known deletion algorithm that preserves randomness for the general case (when there is a cellar). We give some reasons why and then discuss some heuristics that seem to make deletions practical anyway.

Details

FOCS Conference 1980 Conference Paper

Tuning the Coalesced Hashing Method to Obtain Optimum Performance (Detailed Abstract)

  • Jeffrey Scott Vitter

This paper analyzes the coalesced hashing method, in which a portion of memory (called the address region) serves as the range of the hash function while the rest of memory (called the cellar) is devoted solely to storing records that collide when inserted. If the cellar should get full, subsequent colliders must be stored in empty slots in the address region and, thus, may cause later collisions. Varying the relative size of the cellar affects search performance. The main result of this paper expresses the average search times as a function of the number of records and the cellar size, solving the long-standing open problem described in [Knu73, §6. 4-43]. We use these formulas to pick the cellar size that leads to optimum search performance and then show that this "tuned" method is competitive with several well-known hashing schemes.

Details
v2026.09.13