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: 8950
Venue: VLDB
Year: 2001
Pagerank: 6.513844e-05
Overall Rank: 4,776 | 67.24%
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,164	OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences	2003	VLDB	7.6778551e-05
3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.649474e-05
6,496	Reference-Based Indexing of Sequence Databases	2006	VLDB	5.8632988e-05
12,177	Similarity Joins for Uncertain Strings	2014	SIGMOD	5.093636e-05
12,841	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	5.093636e-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
796	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00013932561
815	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013835761

Semantically Similar Papers

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