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: hc2ce8813ee736ad2
Venue: VLDB
Year: 2006
Pagerank: 5.7319339e-05
Overall Rank: 6,619 | 55.50%
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,507	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD	7.2494536e-05
6,305	Reference-Based Alignment in Large Sequence Databases	2009	VLDB	5.818151e-05
7,006	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	5.6234186e-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.00040370171
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
597	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00015766567
2,059	A Database Index to Large Biological Sequences	2001	VLDB	9.1020248e-05
3,228	OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences	2003	VLDB	7.5077929e-05
4,889	An Efficient Index Structure for String Databases	2001	VLDB	6.3682428e-05

Semantically Similar Papers

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