An Efficient Index Structure for String Databases

Summary: Substrings mapped to an integer space by wavelet coefficients for scalable, on-disk substring search. MBR-based indexing with a lower-bound edit-distance proxy enables NN and range pruning, yielding 50–95% pruning and substantial I/O/CPU savings. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h0d57b671444df334
Venue: VLDB
Year: 2001
Pagerank: 6.3682428e-05
Overall Rank: 4,889 | 67.14%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Tamer Kahveci (University of California)
2. Ambuj K. Singh (University of California)

BibTeX Citation

@article{kahveci_vldb01,
        title = {{An Efficient Index Structure for String Databases}},
        author = {Kahveci, Tamer and Singh, Ambuj K.},
        journal = {PVLDB},
        series = {{VLDB} '01},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,228	OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences	2003	VLDB	7.5077929e-05
3,255	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.4890984e-05
6,619	Reference-Based Indexing of Sequence Databases	2006	VLDB	5.7319339e-05
12,468	Similarity Joins for Uncertain Strings	2014	SIGMOD	4.9793485e-05
13,131	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
826	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.0001363793
837	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013551047

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,298	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD
2	3,535	Practical Suffix Tree Construction	2004	VLDB
3	13,788	On the String Matching with k Differences in DNA Databases	2021	VLDB
4	6,619	Reference-Based Indexing of Sequence Databases	2006	VLDB
5	4,955	The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space	2012	PODS
6	2,072	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD
7	6,952	Space-efficient Substring Occurrence Estimation	2011	PODS
8	6,616	Two-dimensional Substring Indexing	2001	PODS
9	7,842	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
10	2,706	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD