Vid integrering av data från autonoma källor, exakta matchningar av dataobjekt som representerar samma verkliga objekt ofta misslyckas på grund av en brist på gemensamma nycklar. Ändå finns i många fall strukturell information tillgänglig och kan användas för att matcha sådana uppgifter. Vanligtvis måste matchningen vara ungefärlig eftersom representationerna i källorna skiljer sig åt. Vi föreslår pq-gram för att ungefär matcha hierarkiska data från autonoma källor och definiera pq-gramavståndet mellan beställda märkta träd som en effektiv och effektiv approximation av det fanoutviktade trädredigeringsavståndet. Vi bevisar att pq-gram avstånd är en lägre gräns för fanout viktade träd redigera avstånd och ge en normalisering av pq-gram avstånd som triangeln ojämlikhet innehar. Experiment på syntetiska och verkliga data (residensadresser och XML) bekräftar skalbarheten av vår strategi och visar effektiviteten av pq-gram.
Senare i REF ändras pq-gramavståndet för att fungera som en lägre gräns till det fanoutviktade trädredigeringsavståndet, men inte till det allmänt använda enhetskostnadsträdets redigeringsavstånd eller det allmänna fallet.
The pq-gram distance between ordered labeled trees
{'venue': 'TODS', 'journal': None, 'mag_field_of_study': ['Computer Science']}