Comparing Hierarchical Data in External Memory
Summary: An external-memory algorithm computes minimum-cost edit scripts for rooted, ordered, labeled trees by extending sequence-comparison mappings to shortest paths in edit graphs. Its distinctive feature is provable I/O, RAM, and CPU bounds, with surplus RAM enabling a quadratic reduction in I/O cost. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Sudarshan S. Chawathe (University of Maryland)
BibTeX Citation
@article{chawathe_vldb99,
title = {{Comparing Hierarchical Data in External Memory}},
author = {Chawathe, Sudarshan S.},
journal = {PVLDB},
series = {{VLDB} '99},
pages = {90--101},
year = {1999}
}Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,231 | RTED: A Robust Algorithm for the Tree Edit Distance | 2012 | VLDB | 7.5038443e-05 |
| 12,577 | Synthetising Changes in XML Documents as PULs | 2013 | VLDB | 4.9793485e-05 |
| 13,008 | Automatic Extraction of Dynamic Record Sections From Search Engine Result Pages | 2006 | VLDB | 4.9793485e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 908 | Meaningful Change Detection in Structured Data | 1997 | SIGMOD | 0.00013157386 |
| 1,531 | Change Detection in Hierarchically Structured Information | 1996 | SIGMOD | 0.0001033805 |
| 1,640 | Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results | 1994 | SIGMOD | 0.00010011692 |
| 3,911 | Structural Matching and Discovery in Document Databases | 1997 | SIGMOD | 6.9306937e-05 |
| 4,872 | Efficient Snapshot Differential Algorithms for Data Warehousing | 1996 | VLDB | 6.3731903e-05 |
| 6,413 | External Memory Algorithms | 1998 | PODS | 5.7931958e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,973 | A Scalable Index for Top-k Subtree Similarity Queries | 2019 | SIGMOD |
| 2 | 9,786 | Memory-Efficient Search Trees for Database Management Systems | 2021 | SIGMOD |
| 3 | 12,840 | The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects | 2008 | PODS |
| 4 | 7,086 | Indexing for Subtree Similarity-Search using Edit Distance | 2013 | SIGMOD |
| 5 | 5,928 | Sorting Hierarchical Data in External Memory for Archiving | 2008 | VLDB |
| 6 | 12,268 | Write-Optimized Skip Lists | 2017 | PODS |
| 7 | 4,433 | Efficient External-Memory Bisimulation on DAGs | 2012 | SIGMOD |
| 8 | 3,231 | RTED: A Robust Algorithm for the Tree Edit Distance | 2012 | VLDB |
| 9 | 6,007 | Clustering Techniques for Minimizing External Path Length | 1996 | VLDB |
| 10 | 3,108 | Similarity Evaluation on Tree-structured Data | 2005 | SIGMOD |