Jeffrey Scott Vitter
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:
- Hongwei Huo
School of Computer Science and Technology Xidian University Xi'an China
8 shared publications - Jun Huan
University of Kansas
3 shared publications - Jun Huan
Amazon Web Services, Santa Clara, CA, USA
2 shared publications - Xiaoyang Chen
Department of Computer Science, Xidian University, 47905 Xian, Shaanxi China
2 shared publications - Xiaoyang Chen
Dept. of Computer Science Xidian University
2 shared publications - Yossi Matias
Google, Mountain View, USA
2 shared publications
Latest Publications
- 24 June 2023
- Published by Elsevier in Computational Geometry
- Vol. 116
Approximating Gromov-Hausdorff distance in Euclidean space
- 24 June 2023
- Published by Elsevier in Computational Geometry
- Vol. 116
Approximating Gromov-Hausdorff distance in Euclidean space
- Open Access
- 31 January 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 19 (1) , 1-12
Ranked Document Retrieval in External Memory
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.
- 31 January 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 19 (1) , 1-12
Open AccessRanked Document Retrieval in External Memory
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.
- 22 September 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 35 (3) , 2943-2960
Practical High-Order Entropy-Compressed Text Self-Indexing
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.
- 22 September 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 35 (3) , 2943-2960
Practical High-Order Entropy-Compressed Text Self-Indexing
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.
- 15 September 2021
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 38 (2) , 335-343
CIndex: compressed indexes for fast retrieval of FASTQ files
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 and , 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.- 15 September 2021
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 38 (2) , 335-343
CIndex: compressed indexes for fast retrieval of FASTQ files
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 and , 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.- 1 July 2020
- Published by Elsevier in Neurocomputing
- Vol. 397, 114-126
Feature reduction based on semantic similarity for graph classification
- 1 July 2020
- Published by Elsevier in Neurocomputing
- Vol. 397, 114-126
Feature reduction based on semantic similarity for graph classification
- 21 January 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 18 (6) , 2394-2408
Efficient Compression and Indexing for Highly Repetitive DNA Sequence Collections
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.
- 21 January 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 18 (6) , 2394-2408
Efficient Compression and Indexing for Highly Repetitive DNA Sequence Collections
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.
- 20 November 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 33 (6) , 2654-2668
MSQ-Index: A Succinct Index for Fast Graph Similarity Search
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.
- 20 November 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 33 (6) , 2654-2668
MSQ-Index: A Succinct Index for Fast Graph Similarity Search
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
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 AccessFast Computation of Graph Edit Distance
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
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 AccessMSQ-Index: A Succinct Index for Fast Graph Similarity Search
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
- 19 July 2016
- Published by Springer Nature in BMC Bioinformatics
- Vol. 17 (S9) , 266
RefSelect: a reference sequence selection algorithm for planted (l, d) motif search
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.
- 19 July 2016
- Published by Springer Nature in BMC Bioinformatics
- Vol. 17 (S9) , 266
Open AccessRefSelect: a reference sequence selection algorithm for planted (l, d) motif search
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.