Reference-Based Indexing of Sequence Databases

Summary: Proposes a reference-based index for large sequence databases under edit distance, reducing expensive computations with limited memory. Two novel reference-selection strategies and a new assignment method prune up to 20x–30x more candidates than Omni and frequency vectors, scalable to long sequences. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9693
Venue: VLDB
Year: 2006
Pagerank: 5.8632988e-05
Overall Rank: 6,496 | 55.44%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jayendra Venkateswaran (University of Florida)
2. Deepak Lachwani (University of Florida)
3. Tamer Kahveci (University of Florida)
4. Christopher Jermaine (University of Florida)

BibTeX Citation

@article{venkateswaran_vldb06,
        title = {{Reference-Based Indexing of Sequence Databases}},
        author = {Venkateswaran, Jayendra and Lachwani, Deepak and Kahveci, Tamer and Jermaine, Christopher},
        journal = {PVLDB},
        series = {{VLDB} '06},
        pages = {906--917},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,440	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD	7.4142918e-05
6,182	Reference-Based Alignment in Large Sequence Databases	2009	VLDB	5.9493566e-05
6,858	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	5.7523396e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
592	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00016029789
2,008	A Database Index to Large Biological Sequences	2001	VLDB	9.310515e-05
3,164	OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences	2003	VLDB	7.6778551e-05
4,776	An Efficient Index Structure for String Databases	2001	VLDB	6.513844e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,036	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD
2	12,283	RCSI: Scalable similarity search in thousand(s) of genomes	2013	VLDB
3	8,078	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
4	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
5	6,780	Discovering Longest-lasting Correlation in Sequence Databases	2013	VLDB
6	3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD
7	4,776	An Efficient Index Structure for String Databases	2001	VLDB
8	6,858	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB
9	10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
10	6,182	Reference-Based Alignment in Large Sequence Databases	2009	VLDB