Comparing Hierarchical Data in External Memory
Summary: External-memory algorithm for minimum-cost edit script between rooted, ordered, labeled trees; I/O 4*m1*n1 + 7*m1 + 5*n1, RAM 6*S, CPU O((M*N+(M+N)*S)^1.5). Extends sequence-comparison to trees via shortest-path problems in edit graphs; uses surplus RAM to quadratically reduce I/O. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,301 | RTED: A Robust Algorithm for the Tree Edit Distance | 2012 | VLDB | 7.2515266e-05 |
| 12,089 | Synthetising Changes in XML Documents as PULs | 2013 | VLDB | 4.1945683e-05 |
| 12,525 | Automatic Extraction of Dynamic Record Sections From Search Engine Result Pages | 2006 | VLDB | 4.1945683e-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 |
|---|---|---|---|---|
| 728 | Meaningful Change Detection in Structured Data | 1997 | SIGMOD | 0.00017494982 |
| 1,390 | Change Detection in Hierarchically Structured Information | 1996 | SIGMOD | 0.00012248349 |
| 1,433 | Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results | 1994 | SIGMOD | 0.00012009649 |
| 3,128 | Structural Matching and Discovery in Document Databases | 1997 | SIGMOD | 7.5033864e-05 |
| 4,760 | Efficient Snapshot Differential Algorithms for Data Warehousing | 1996 | VLDB | 5.9410726e-05 |
| 5,979 | External Memory Algorithms | 1998 | PODS | 5.2450009e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,615 | A Scalable Index for Top-k Subtree Similarity Queries | 2019 | SIGMOD | 5.4101086e-05 |
| 9,498 | Memory-Efficient Search Trees for Database Management Systems | 2021 | SIGMOD | 4.3341665e-05 |
| 12,357 | The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects | 2008 | PODS | 4.1945683e-05 |
| 6,807 | Indexing for Subtree Similarity-Search using Edit Distance | 2013 | SIGMOD | 4.9217776e-05 |
| 5,207 | Sorting Hierarchical Data in External Memory for Archiving | 2008 | VLDB | 5.6297675e-05 |
| 11,764 | Write-Optimized Skip Lists | 2017 | PODS | 4.1945683e-05 |
| 3,677 | Efficient External-Memory Bisimulation on DAGs | 2012 | SIGMOD | 6.8533416e-05 |
| 3,301 | RTED: A Robust Algorithm for the Tree Edit Distance | 2012 | VLDB | 7.2515266e-05 |
| 5,196 | Clustering Techniques for Minimizing External Path Length | 1996 | VLDB | 5.6365164e-05 |
| 3,199 | Similarity Evaluation on Tree-structured Data | 2005 | SIGMOD | 7.3927291e-05 |