JVJeffrey Scott Vitter

Jeffrey Scott Vitter

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Jeffrey Scott Vitter has a total of 30 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Ranked Document Retrieval in External Memory

    by Rahul Shah, Cheng Sheng, Sharma V. Thankachan, Jeffrey Scott Vitter

    The ranked (or top- k ) document retrieval problem is defined as follows: preprocess a collection {T 1 ,T 2 ,… ,T d } of d strings (called documents) of total length n into a data structure, such that for any given query (P,k) , where P is a string (called pattern) of length p ≥ 1 and k ∈ [1,d] is an integer, the identifiers of those k documents that are most relevant to P can be reported, ideally in the sorted order of their relevance. The seminal work by Hon et al. [FOCS 2009 and Journal of the ACM 2014] presented an O(n) -space (in words) data structure with O(p+k log k) query time. The query time was later improved to O(p+k) [SODA 2012] and further to O(p/ log σn+k ) [SIAM Journal on Computing 2017] by Navarro and Nekrich, where σ is the alphabet size. We revisit this problem in the external memory model and present three data structures. The first one takes O(n) -space and answer queries in O(p/B + log B n + k/B+ log * (n/B) ) I/Os, where B is the block size. The second one takes O(n log * (n/B) ) space and answer queries in optimal O(p/B + log B n + k/B) I/Os. In both cases, the answers are reported in the unsorted order of relevance. To handle sorted top- k document retrieval, we present an O(n log (d/B)) space data structure with optimal query cost.

  • Practical High-Order Entropy-Compressed Text Self-Indexing

    by Hongwei Huo, Peng Long, Jeffrey Scott Vitter

    Compressed self-indexes are used widely in string processing applications, such as information retrieval, genome analysis, data mining, and web searching. The index not only indexes the data, but also encodes the data, and it is in compressed form. Moreover, the index and the data it encodes can be operated upon directly, without need to uncompress the entire index, thus saving time while maintaining small storage space. In some applications, such as in genome analysis, existing methods do not exploit the full possibilities of compressed self-indexes, and thus we seek faster and more space-efficient indexes. In this paper, we propose a practical high-order entropy-compressed self-index for efficient pattern matching in a text. We give practical implementations of compressed suffix arrays using a hybrid encoding in the representation of the neighbor function . We analyze the performance in theory and practice of our recommended indexing method, called GeCSA. We can improve retrieval time further using an iterated version of the neighbor function. Experimental results on the tested data demonstrate that the proposed index GeCSA has good overall advantages in space usage and retrieval time over the state-of-the-art indexing methods, especially on the repetitive data.


  • CIndex: compressed indexes for fast retrieval of FASTQ files

    by Hongwei Huo, Pengfei Liu, Chenhui Wang, Hongbo Jiang, Jeffrey Scott Vitter

    Ultrahigh-throughput next-generation sequencing instruments continue to generate vast amounts of genomic data. These data are generally stored in FASTQ format. Two important simultaneous goals are space-efficient compressed storage of the genomic data and fast query performance. Toward that end, we introduce compressed indexing to store and retrieve FASTQ files. We propose a compressed index for FASTQ files called CIndex. CIndex uses the Burrows–Wheeler transform and the wavelet tree, combined with hybrid encoding, succinct data structures and tables REF and Rγ⁠, to achieve minimal space usage and fast retrieval on the compressed FASTQ files. Experiments conducted over real publicly available datasets from various sequencing instruments demonstrate that our proposed index substantially outperforms existing state-of-the-art solutions. For count, locate and extract queries on reads, our method uses 2.7–41.66% points less space and provides a speedup of 70–167.16 times, 1.44–35.57 times and 1.3–55.4 times. For extracting records in FASTQ files, our method uses 2.86–14.88% points less space and provides a speedup of 3.13–20.1 times. CIndex has an additional advantage in that it can be readily adapted to work as a general-purpose text index; experiments show that it performs very well in practice. The software is available on Github: https://github.com/Hongweihuo-Lab/CIndex. Supplementary data are available at Bioinformatics online.


  • Feature reduction based on semantic similarity for graph classification

    by Zhigang Sun, Hongwei Huo, Jun Huan, Jeffrey Scott Vitter


  • Efficient Compression and Indexing for Highly Repetitive DNA Sequence Collections

    by Hongwei Huo, Xiaoyang Chen, Xu Guo, Jeffrey Scott Vitter

    In this paper, we focus upon the important problem of indexing and searching highly repetitive DNA sequence collections. Given a collection G of t sequences Si of length n each, we can represent G succinctly in 2nHk(T) + O(n'loglog n) + o(qn') + o(tn) bits using O(tn2 + qn') time, where Hk(T) is the k-order empirical entropy of the sequence T ∈ G that is used as the reference sequence, n' is the total number of variations between T and the sequences in G, and q is a small fixed constant. We can restore any length len substring S[sp, ..., sp + len - 1] of S ∈ G in O(ns' + len(log n)2/ log n) time and report all positions where P occurs in G in O(m·t + occ·t ·(log n)2/ log log n) time. In addition, we propose a dynamic programming method to find the variations between T and the sequences in G in a space-efficient way, with which we can build succinct structures to enable efficient search. For highly repetitive sequences, experimental results on the tested data demonstrate that the proposed method has significant advantages in space usage and retrieval time over the current state-of-the-art methods. The source code is available online.


  • MSQ-Index: A Succinct Index for Fast Graph Similarity Search

    by Xiaoyang Chen, Hongwei Huo, Jun Huan, Jeffrey Scott Vitter, Weiguo Zheng, Lei Zou

    Graph similarity search has received considerable attention in many applications, such as bioinformatics, pattern recognition and social networks. Existing methods have limited scalability because of the huge amount of memory they consume when handling very large graph databases with tens of millions of graphs. In this paper, we present a succinct index that incorporates succinct data structures and hybrid encoding to achieve improved query time performance with minimal space usage. Specifically, the space usage of our index requires only 5%-15% of the previous state-of-the-art indexing size while at the same time achieving several times acceleration in query time on the tested data. We also improve the query performance by augmenting the global filter with range searching, which allows us to search in a reduced region. Besides, we propose two effective lower bounds together with a boosting technique to obtain the possible smallest candidate set. Extensive experiments demonstrate that our proposed approach is superior both in space and filtering to the state-of-the-art approaches. To the best of our knowledge, our index is the first in-memory index that successfully scales to cope with the large dataset of 25 million chemical graphs from the PubChem dataset. The source code is available online.


  • Open Access

    Fast Computation of Graph Edit Distance

    by Xiaoyang Chen, Hongwei Huo, Jun Huan, Jeffrey Scott Vitter

    The graph edit distance (GED) is a well-established distance measure widely used in many applications. However, existing methods for the GED computation suffer from several drawbacks including oversized search space, huge memory consumption, and lots of expensive backtracking. In this paper, we present BSS_GED, a novel vertex-based mapping method for the GED computation. First, we create a small search space by reducing the number of invalid and redundant mappings involved in the GED computation. Then, we utilize beam-stack search combined with two heuristics to efficiently compute GED, achieving a flexible trade-off between available memory and expensive backtracking. Extensive experiments demonstrate that BSS GED is highly efficient for the GED computation on sparse as well as dense graphs and outperforms the state-of-the-art GED methods. In addition, we also apply BSS_GED to the graph similarity search problem and the practical results confirm its efficiency.

  • Open Access

    MSQ-Index: A Succinct Index for Fast Graph Similarity Search

    by Xiaoyang Chen, Hongwei Huo, Jun Huan, Jeffrey Scott Vitter

    Graph similarity search has received considerable attention in many applications, such as bioinformatics, data mining, pattern recognition, and social networks. Existing methods for this problem have limited scalability because of the huge amount of memory they consume when handling very large graph databases with millions or billions of graphs. In this paper, we study the problem of graph similarity search under the graph edit distance constraint. We present a space-efficient index structure based upon the q-gram tree that incorporates succinct data structures and hybrid encoding to achieve improved query time performance with minimal space usage. Specifically, the space usage of our index requires only 5%-15% of the previous state-of-the-art indexing size on the tested data while at the same time achieving 2-3 times acceleration in query time with small data sets. We also boost the query performance by augmenting the global filter with range search, which allows us to perform a query in a reduced region. In addition, we propose two effective filters that combine degree structures and label structures. Extensive experiments demonstrate that our proposed approach is superior in space and competitive in filtering to the state-of-the-art approaches. To the best of our knowledge, our index is the first in-memory index for this problem that successfully scales to cope with the large dataset of 25 million chemical structure graphs from the PubChem dataset.

  • Open Access

    RefSelect: a reference sequence selection algorithm for planted (l, d) motif search

    by Qiang Yu, Hongwei Huo, Ruixing Zhao, Dazheng Feng, Jeffrey Scott Vitter, Jun Huan

    The planted (l, d) motif search (PMS) is an important yet challenging problem in computational biology. Pattern-driven PMS algorithms usually use k out of t input sequences as reference sequences to generate candidate motifs, and they can find all the (l, d) motifs in the input sequences. However, most of them simply take the first k sequences in the input as reference sequences without elaborate selection processes, and thus they may exhibit sharp fluctuations in running time, especially for large alphabets. In this paper, we build the reference sequence selection problem and propose a method named RefSelect to quickly solve it by evaluating the number of candidate motifs for the reference sequences. RefSelect can bring a practical time improvement of the state-of-the-art pattern-driven PMS algorithms. Experimental results show that RefSelect (1) makes the tested algorithms solve the PMS problem steadily in an efficient way, (2) particularly, makes them achieve a speedup of up to about 100× on the protein data, and (3) is also suitable for large data sets which contain hundreds or more sequences. The proposed algorithm RefSelect can be used to solve the problem that many pattern-driven PMS algorithms present execution time instability. RefSelect requires a small amount of storage space and is capable of selecting reference sequences efficiently and effectively. Also, the parallel version of RefSelect is provided for handling large data sets.