On The Marriage of Lp-norms and Edit Distance

Summary: Introduces ERP, a metric combining L1 distance with edit operations to support local time shifting. A B+-tree-indexable lower bound combined with triangle-inequality pruning enables highly effective, state-of-the-art time-series similarity search. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h7750c4d2f70bd295
Venue: VLDB
Year: 2004
Pagerank: 0.00021575844
Overall Rank: 306 | 97.95%
DOI: 10.1016/B978-012088469-8.50070-X

Incoming Non-self Citations Over Time

Authors

1. Lei Chen (University of Waterloo)
2. Raymond Ng (University of British Columbia)

BibTeX Citation

@article{chen_vldb04,
        title = {{On The Marriage of Lp-norms and Edit Distance}},
        author = {Chen, Lei and Ng, Raymond},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {792},
        doi = {10.1016/B978-012088469-8.50070-X},
        url = {https://doi.org/10.1016/B978-012088469-8.50070-X},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 51 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,662	Effective Data Co-Reduction for Multimedia Similarity Search	2011	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
42	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00045773967
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040370171
193	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00025648171
227	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.0002393284
478	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017631293
613	Exact Indexing of Dynamic Time Warping	2002	VLDB	0.00015570505
621	Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences	1997	SIGMOD	0.00015492309
1,070	Warping Indexes with Envelope Transforms for Query by Humming	2003	SIGMOD	0.00012174775
1,349	Querying Shapes of Histories	1995	VLDB	0.00010946376

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,379	On Repairing Timestamps for Regular Interval Time Series	2022	VLDB
2	613	Exact Indexing of Dynamic Time Warping	2002	VLDB
3	5,722	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB
4	7,006	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB
5	6,890	On Efficiently Searching Trajectories and Archival Data for Historical Similarities	2008	VLDB
6	2,494	An Efficient and Accurate Method for Evaluating Time Series Similarity	2007	SIGMOD
7	3,108	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
8	8,286	Anticipatory DTW for Efficient Similarity Search in Time Series Databases	2009	VLDB
9	193	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD
10	478	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB