Comparing Hierarchical Data in External Memory.
Sudarshan S. Chawathe:
Comparing Hierarchical Data in External Memory.
VLDB 1999: 90-101@inproceedings{DBLP:conf/vldb/Chawathe99,
author = {Sudarshan S. Chawathe},
editor = {Malcolm P. Atkinson and
Maria E. Orlowska and
Patrick Valduriez and
Stanley B. Zdonik and
Michael L. Brodie},
title = {Comparing Hierarchical Data in External Memory},
booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
UK},
publisher = {Morgan Kaufmann},
year = {1999},
isbn = {1-55860-615-7},
pages = {90-101},
ee = {db/conf/vldb/Chawathe99.html},
crossref = {DBLP:conf/vldb/99},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
We present an external-memory algorithm for
computing a minimum-cost edit script between
two rooted, ordered, labeled trees. The I/O, RAM,
and CPU costs of our algorithm are, respectively,
4mn+7m+5n, 6S, and O(MN+(M+N)S1.5),
where M and N are the input tree sizes,
S is the block size, m=M/S, and n=N/S.
This algorithm can make effective use of surplus RAM
capacity to quadratically reduce I/O cost. We extend to
trees the commonly used mapping from sequence comparison
problems to shortest-path problems in edit graphs.
Copyright © 1999 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdonik, Michael L. Brodie (Eds.):
VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK.
Morgan Kaufmann 1999, ISBN 1-55860-615-7
Contents
References
- [AHU76]
- Alfred V. Aho, Daniel S. Hirschberg, Jeffrey D. Ullman:
Bounds on the Complexity of the Longest Common Subsequence Problem.
J. ACM 23(1): 1-12(1976)
![bibliographical record in XML](../../xml.gif)
- [CAW98]
- Sudarshan S. Chawathe, Serge Abiteboul, Jennifer Widom:
Representing and Querying Changes in Semistructured Data.
ICDE 1998: 4-13
![bibliographical record in XML](../../xml.gif)
- [CGM97]
- Sudarshan S. Chawathe, Hector Garcia-Molina:
Meaningful Change Detection in Structured Data.
SIGMOD Conference 1997: 26-37
![bibliographical record in XML](../../xml.gif)
- [CRGMW96]
- Sudarshan S. Chawathe, Anand Rajaraman, Hector Garcia-Molina, Jennifer Widom:
Change Detection in Hierarchically Structured Information.
SIGMOD Conference 1996: 493-504
![bibliographical record in XML](../../xml.gif)
- [LGM96]
- Wilburt Labio, Hector Garcia-Molina:
Efficient Snapshot Differential Algorithms for Data Warehousing.
VLDB 1996: 63-74
![bibliographical record in XML](../../xml.gif)
- [MM85]
- Webb Miller, Eugene W. Myers:
A File Comparison Program.
Softw., Pract. Exper. 15(11): 1025-1040(1985)
![bibliographical record in XML](../../xml.gif)
- [MP80]
- William J. Masek, Mike Paterson:
A Faster Algorithm Computing String Edit Distances.
J. Comput. Syst. Sci. 20(1): 18-31(1980)
![bibliographical record in XML](../../xml.gif)
- [Mye86]
- Eugene W. Myers:
An O(ND) Difference Algorithm and Its Variations.
Algorithmica 1(2): 251-266(1986)
![bibliographical record in XML](../../xml.gif)
- [Sel77]
- Stanley M. Selkow:
The Tree-to-Tree Editing Problem.
Inf. Process. Lett. 6(6): 184-186(1977)
![bibliographical record in XML](../../xml.gif)
- [SK83]
- ...
- [Tic85]
- Walter F. Tichy:
RCS - A System for Version Control.
Softw., Pract. Exper. 15(7): 637-654(1985)
![bibliographical record in XML](../../xml.gif)
- [Vit98]
- Jeffrey Scott Vitter:
External Memory Algorithms.
PODS 1998: 119-128
![bibliographical record in XML](../../xml.gif)
- [WC76]
- C. K. Wong, Ashok K. Chandra:
Bounds for the String Editing Problem.
J. ACM 23(1): 13-16(1976)
![bibliographical record in XML](../../xml.gif)
- [WCM+94]
- Jason Tsong-Li Wang, Gung-Wei Chirn, Thomas G. Marr, Bruce A. Shapiro, Dennis Shasha, Kaizhong Zhang:
Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results.
SIGMOD Conference 1994: 115-125
![bibliographical record in XML](../../xml.gif)
- [WF74]
- Robert A. Wagner, Michael J. Fischer:
The String-to-String Correction Problem.
J. ACM 21(1): 168-173(1974)
![bibliographical record in XML](../../xml.gif)
- [WMG90]
- Sun Wu, Udi Manber, Gene Myers, Webb Miller:
An O(NP) Sequence Comparison Algorithm.
Inf. Process. Lett. 35(6): 317-323(1990)
![bibliographical record in XML](../../xml.gif)
- [WSC+97]
- Jason Tsong-Li Wang, Dennis Shasha, George Jyh-Shian Chang, Liam Relihan, Kaizhong Zhang, Girish Patel:
Structural Matching and Discovery in Document Databases.
SIGMOD Conference 1997: 560-563
![bibliographical record in XML](../../xml.gif)
- [WZJS94]
- Jason Tsong-Li Wang, Kaizhong Zhang, Karpjoo Jeong, Dennis Shasha:
A System for Approximate Tree Matching.
IEEE Trans. Knowl. Data Eng. 6(4): 559-571(1994)
![bibliographical record in XML](../../xml.gif)
- [Yan91]
- Wuu Yang:
Identifying Syntactic differences Between Two Programs.
Softw., Pract. Exper. 21(7): 739-755(1991)
![bibliographical record in XML](../../xml.gif)
- [ZS89]
- Kaizhong Zhang, Dennis Shasha:
Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems.
SIAM J. Comput. 18(6): 1245-1262(1989)
![bibliographical record in XML](../../xml.gif)
- [ZWS95]
- ...
Copyright © Tue Mar 16 02:22:08 2010
by Michael Ley (ley@uni-trier.de)