DBScholar

Back to papers

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

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 50 of 51 citing papers.

Rank Citing Paper Year Venue Pagerank
227 Robust and Fast Similarity Search for Moving Object Trajectories 2005 SIGMOD 0.0002393284
915 Querying and Mining of Time Series Data: Experimental Comparison of Representations and Distance Measures 2008 VLDB 0.00013099703
1,579 k-Shape: Efficient and Accurate Clustering of Time Series 2015 SIGMOD 0.00010186397
1,731 Indexable PLA for Efficient Similarity Search 2007 VLDB 9.7639519e-05
1,783 Swarm: Mining Relaxed Temporal Moving Object Clusters 2010 VLDB 9.6511944e-05
1,942 Discovery of Convoys in Trajectory Databases 2008 VLDB 9.3285345e-05
2,021 Distributed Trajectory Similarity Search 2017 VLDB 9.1719539e-05
2,196 DITA: Distributed In-Memory Trajectory Analytics 2018 SIGMOD 8.8780862e-05
2,494 An Efficient and Accurate Method for Evaluating Time Series Similarity 2007 SIGMOD 8.3888883e-05
2,536 STRG-Index: Spatio-Temporal Region Graph Indexing for Large Video Databases 2005 SIGMOD 8.3321989e-05
3,009 Trajectory Simplification: An Experimental Study and Quality Analysis 2018 VLDB 7.7578378e-05
3,613 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.162283e-05
3,770 Calibrating Trajectory Data for Similarity-based Analysis 2013 SIGMOD 7.0297827e-05
4,316 GRAIL: Efficient Time-Series Representation Learning 2019 VLDB 6.6683448e-05
4,352 Searching Trajectories by Locations - An Efficiency Study 2010 SIGMOD 6.6423022e-05
4,473 AutoPlait: Automatic Mining of Co-evolving Time Sequences 2014 SIGMOD 6.5841437e-05
4,703 Debunking Four Long-Standing Misconceptions of Time-Series Distance Measures 2020 SIGMOD 6.4621968e-05
5,011 Fast Large-Scale Trajectory Clustering 2020 VLDB 6.3148258e-05
5,188 Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints 2020 VLDB 6.2370687e-05
5,444 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 6.1268526e-05
6,031 Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning 2020 VLDB 5.9104518e-05
6,627 Interactive Time Series Exploration Powered by the Marriage of Similarity Distances 2017 VLDB 5.7281902e-05
6,730 Trajectory Similarity Measurement: An Efficiency Perspective 2024 VLDB 5.6939772e-05
6,790 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 5.6812765e-05
6,890 On Efficiently Searching Trajectories and Archival Data for Historical Similarities 2008 VLDB 5.6544825e-05
7,006 A Generic Framework for Efficient and Effective Subsequence Retrieval 2012 VLDB 5.6234186e-05
7,094 Time-Series Clustering: A Comprehensive Study of Data Mining, Machine Learning, and Deep Learning Methods 2025 VLDB 5.601767e-05
7,442 Set-based Similarity Search for Time Series 2016 SIGMOD 5.5254761e-05
7,641 A Structured Study of Multivariate Time-Series Distance Measures 2025 SIGMOD 5.4772833e-05
7,659 Ratel: Interactive Analytics for Large Scale Trajectories 2019 SIGMOD 5.4772833e-05
7,665 Online Video Recommendation in Sharing Community 2015 SIGMOD 5.4772833e-05
7,698 EDS: A Segment-based Distance Measure for Sub-trajectory Similarity Search 2014 SIGMOD 5.4752594e-05
7,810 Mining Frequent Itemsets over Uncertain Databases 2012 VLDB 5.4488716e-05
8,286 Anticipatory DTW for Efficient Similarity Search in Time Series Databases 2009 VLDB 5.3620578e-05
8,875 The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem 2022 VLDB 5.2577831e-05
8,897 Ghost: A General Framework for High-Performance Online Similarity Queries over Distributed Trajectory Streams 2023 SIGMOD 5.2559789e-05
9,412 Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases 2008 VLDB 5.1826275e-05
9,758 A Subsequence Matching with Gaps-Range-Tolerances Framework: A Query-By-Humming Application 2011 VLDB 5.1349531e-05
10,150 RED: Effective Trajectory Representation Learning with Comprehensive Information 2025 VLDB 5.0715586e-05
10,463 GoodTP: An Effective Data Selection Framework for Enhancing Trajectory Similarity Learning via Monte Carlo Tree Search 2026 SIGMOD 4.9793485e-05
10,483 MUFASA: Fast and Accurate Multivariate Time-Series Clustering 2026 SIGMOD 4.9793485e-05
11,214 Revisiting CNNs for Trajectory Similarity Learning 2025 VLDB 4.9793485e-05
11,255 SimRN: Trajectory Similarity Learning in Road Networks based on Distributed Deep Reinforcement Learning 2025 VLDB 4.9793485e-05
11,266 TMLKD: Few-shot Trajectory Metric Learning via Knowledge Distillation 2025 VLDB 4.9793485e-05
11,749 Accelerating Similarity Search for Elastic Measures: A Study and New Generalization of Lower Bounding Distances 2023 VLDB 4.9793485e-05
11,768 Efficient Non-Learning Similar Subtrajectory Search 2023 VLDB 4.9793485e-05
12,220 DITA: A Distributed In-Memory Trajectory Analytics System 2018 SIGMOD 4.9793485e-05
12,413 SMiLer: A Semi-Lazy Time Series Prediction System for Sensors 2015 SIGMOD 4.9793485e-05
12,479 Attraction and Avoidance Detection from Movements 2014 VLDB 4.9793485e-05
12,481 MoveMine 2.0: Mining Object Relationships from Movement Data 2014 VLDB 4.9793485e-05
Previous Page 1 / 2 Next

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
Previous Page 1 / 1 Next

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