Search

Your search keyword '"Vitter, Jeffrey Scott"' showing total 515 results
Start Over Author "Vitter, Jeffrey Scott"
515 results on '"Vitter, Jeffrey Scott"'

1. Fast Computation of Graph Edit Distance

Author

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

Subjects
Computer Science - Data Structures and Algorithms
Abstract

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.

Published
2017

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

Author

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

Subjects
Computer Science - Databases
Abstract

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., Comment: prepare to submit

Published
2016

3. Dynamic Data Structures for Document Collections and Graphs

Author

Munro, J. Ian, Nekrich, Yakov, and Vitter, Jeffrey Scott

Subjects
Computer Science - Data Structures and Algorithms
Abstract

In the dynamic indexing problem, we must maintain a changing collection of text documents so that we can efficiently support insertions, deletions, and pattern matching queries. We are especially interested in developing efficient 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.

Published
2015

5. Space-Efficient String Indexing for Wildcard Pattern Matching

Author

Lewenstein, Moshe, Nekrich, Yakov, and Vitter, Jeffrey Scott

Subjects
Computer Science - Data Structures and Algorithms
Abstract

In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses $O(n\log^{\varepsilon}n)$ bits for any $\varepsilon>0$ and reports all $\mathrm{occ}$ occurrences of a wildcard string in $O(m+\sigma^g \cdot\mu(n) + \mathrm{occ})$ time, where $\mu(n)=o(\log\log\log n)$, $\sigma$ is the alphabet size, $m$ is the number of alphabet symbols and $g$ is the number of wildcard symbols in the query string. We also present an $O(n)$-bit index with $O((m+\sigma^g+\mathrm{occ})\log^{\varepsilon}n)$ query time and an $O(n(\log\log n)^2)$-bit index with $O((m+\sigma^g+\mathrm{occ})\log\log n)$ query time. These are the first non-trivial data structures for this problem that need $o(n\log n)$ bits of space., Comment: 15 pages, extended version of the STACS paper

Published
2014

6. Optimal Color Range Reporting in One Dimension

Author

Nekrich, Yakov and Vitter, Jeffrey Scott

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Color (or categorical) range reporting is a variant of the orthogonal range reporting problem in which every point in the input is assigned a \emph{color}. While the answer to an orthogonal point reporting query contains all points in the query range $Q$, the answer to a color reporting query contains only distinct colors of points in $Q$. In this paper we describe an O(N)-space data structure that answers one-dimensional color reporting queries in optimal $O(k+1)$ time, where $k$ is the number of colors in the answer and $N$ is the number of points in the data structure. Our result can be also dynamized and extended to the external memory model.

Published
2013

7. On Optimal Top-K String Retrieval

Author

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

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Let ${\cal{D}}$ = $\{d_1, d_2, d_3, ..., d_D\}$ be a given set of $D$ (string) documents of total length $n$. The top-$k$ document retrieval problem is to index $\cal{D}$ such that when a pattern $P$ of length $p$, and a parameter $k$ come as a query, the index returns the $k$ most relevant documents to the pattern $P$. Hon et. al. \cite{HSV09} gave the first linear space framework to solve this problem in $O(p + k\log k)$ time. This was improved by Navarro and Nekrich \cite{NN12} to $O(p + k)$. These results are powerful enough to support arbitrary relevance functions like frequency, proximity, PageRank, etc. In many applications like desktop or email search, the data resides on disk and hence disk-bound indexes are needed. Despite of continued progress on this problem in terms of theoretical, practical and compression aspects, any non-trivial bounds in external memory model have so far been elusive. Internal memory (or RAM) solution to this problem decomposes the problem into $O(p)$ subproblems and thus incurs the additive factor of $O(p)$. In external memory, these approaches will lead to $O(p)$ I/Os instead of optimal $O(p/B)$ I/O term where $B$ is the block-size. We re-interpret the problem independent of $p$, as interval stabbing with priority over tree-shaped structure. This leads us to a linear space index in external memory supporting top-$k$ queries (with unsorted outputs) in near optimal $O(p/B + \log_B n + \log^{(h)} n + k/B)$ I/Os for any constant $h${$\log^{(1)}n =\log n$ and $\log^{(h)} n = \log (\log^{(h-1)} n)$}. Then we get $O(n\log^*n)$ space index with optimal $O(p/B+\log_B n + k/B)$ I/Os., Comment: 3 figures

Published
2012

11. Top-k Document Retrieval in External Memory

Author

Shah, Rahul, Sheng, Cheng, Thankachan, Sharma V., Vitter, Jeffrey Scott, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bodlaender, Hans L., editor, and Italiano, Giuseppe F., editor

Published
2013
Full Text
View/download PDF

12. Indexes for Document Retrieval with Relevance

Author

Hon, Wing-Kai, Patil, Manish, Shah, Rahul, Thankachan, Sharma V., Vitter, Jeffrey Scott, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Brodnik, Andrej, editor, López-Ortiz, Alejandro, editor, Raman, Venkatesh, editor, and Viola, Alfredo, editor

Published
2013
Full Text
View/download PDF

13. Document Listing for Queries with Excluded Pattern

Author

Hon, Wing-Kai, Shah, Rahul, Thankachan, Sharma V., Vitter, Jeffrey Scott, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Kärkkäinen, Juha, editor, and Stoye, Jens, editor

Published
2012
Full Text
View/download PDF

14. Compressed Text Indexing with Wildcards

Author

Hon, Wing-Kai, Ku, Tsung-Han, Shah, Rahul, Thankachan, Sharma V., Vitter, Jeffrey Scott, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Grossi, Roberto, editor, Sebastiani, Fabrizio, editor, and Silvestri, Fabrizio, editor

Published
2011
Full Text
View/download PDF

16. Faster Compressed Dictionary Matching

Author

Hon, Wing-Kai, Ku, Tsung-Han, Shah, Rahul, Thankachan, Sharma V., Vitter, Jeffrey Scott, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Chavez, Edgar, editor, and Lonardi, Stefano, editor

Published
2010
Full Text
View/download PDF

17. String Retrieval for Multi-pattern Queries

Author

Hon, Wing-Kai, Shah, Rahul, Thankachan, Sharma V., Vitter, Jeffrey Scott, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Chavez, Edgar, editor, and Lonardi, Stefano, editor

Published
2010
Full Text
View/download PDF

18. Compression, Indexing, and Retrieval for Massive String Data

Author

Hon, Wing-Kai, Shah, Rahul, Vitter, Jeffrey Scott, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Amir, Amihood, editor, and Parida, Laxmi, editor

Published
2010
Full Text
View/download PDF

19. Succinct Index for Dynamic Dictionary Matching

Author

Hon, Wing-Kai, Lam, Tak-Wah, Shah, Rahul, Tam, Siu-Lung, Vitter, Jeffrey Scott, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dong, Yingfei, editor, Du, Ding-Zhu, editor, and Ibarra, Oscar, editor

Published
2009
Full Text
View/download PDF

20. On Entropy-Compressed Text Indexing in External Memory

Author

Hon, Wing-Kai, Shah, Rahul, Thankachan, Sharma V., Vitter, Jeffrey Scott, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Karlgren, Jussi, editor, Tarhio, Jorma, editor, and Hyyrö, Heikki, editor

Published
2009
Full Text
View/download PDF

23. Cache-Oblivious Index for Approximate String Matching

Author

Hon, Wing-Kai, Lam, Tak-Wah, Shah, Rahul, Tam, Siu-Lung, Vitter, Jeffrey Scott, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ma, Bin, editor, and Zhang, Kaizhong, editor

Published
2007
Full Text
View/download PDF

24. A Framework for Dynamizing Succinct Data Structures

Author

Gupta, Ankur, Hon, Wing-Kai, Shah, Rahul, Vitter, Jeffrey Scott, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Arge, Lars, editor, Cachin, Christian, editor, Jurdziński, Tomasz, editor, and Tarlecki, Andrzej, editor

Published
2007
Full Text
View/download PDF

25. Compressed Dictionaries: Space Measures, Data Sets, and Experiments

Author

Gupta, Ankur, Hon, Wing-Kai, Shah, Rahul, Vitter, Jeffrey Scott, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Àlvarez, Carme, editor, and Serna, María, editor

Published
2006
Full Text
View/download PDF

29. Bkd-Tree: A Dynamic Scalable kd-Tree

Author

Procopiuc, Octavian, Agarwal, Pankaj K., Arge, Lars, Vitter, Jeffrey Scott, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Hadzilacos, Thanasis, editor, Manolopoulos, Yannis, editor, Roddick, John, editor, and Theodoridis, Yannis, editor

Published
2003
Full Text
View/download PDF

33. Characterizing Web Document Change

Author

Lim, Lipyeow, Wang, Min, Padmanabhan, Sriram, Vitter, Jeffrey Scott, Agarwal, Ramesh, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Wang, X. Sean, editor, Yu, Ge, editor, and Lu, Hongjun, editor

Published
2001
Full Text
View/download PDF

35. A Unified Approach for Indexed and Non-indexed Spatial Joins

Author

Arge, Lars, Procopiuc, Octavian, Ramaswamy, Sridhar, Suel, Torsten, Vahrenhold, Jan, Vitter, Jeffrey Scott, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Zaniolo, Carlo, editor, Lockemann, Peter C., editor, Scholl, Marc H., editor, and Grust, Torsten, editor

Published
2000
Full Text
View/download PDF

40. External Memory Algorithms

Author

Vitter, Jeffrey Scott, Goos, G., editor, Hartmanis, J., editor, van Leeuwen, J., editor, Bilardi, Gianfranco, editor, Italiano, Giuseppe F., editor, Pietracaprina, Andrea, editor, and Pucci, Geppino, editor

Published
1998
Full Text
View/download PDF

43. Online perfect matching and mobile computing

Author

Grove, Edward F., Kao, Ming-Yang, Krishnan, P., Vitter, Jeffrey Scott, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Akl, Selim G., editor, Dehne, Frank, editor, Sack, Jörg-Rüdiger, editor, and Santoro, Nicola, editor

Published
1995
Full Text
View/download PDF

48. Efficient memory access in large-scale computation

Author

Vitter, Jeffrey Scott, Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Choffrut, Christian, editor, and Jantzen, Matthias, editor

Published
1991
Full Text
View/download PDF

49. Design and Analysis of Fast Text Compression Based on Quasi-Arithmetic Coding.

Author

Howard, Paul G and Vitter, Jeffrey Scott

Abstract

Describes a detailed algorithm for fast text compression. Related to the PPM (prediction by partial matching) method, it simplifies the modeling phase by eliminating the escape mechanism and speeds up coding by using a combination of quasi-arithmetic coding and Rice coding. Details of the use of quasi-arithmetic code tables are given, and their compression performance is analyzed. (11 references) (Author/KRN)

Published
1994

50. Output-sensitive generation of the perspective view of isothetic parallelepipeds

Author

Preparata, Franco P., Vitter, Jeffrey Scott, Yvinec, Mariette, Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Gilbert, John R., editor, and Karlsson, Rolf, editor

Published
1990
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results