Rank joins for web based data sources

Rank join operators perform a relational join among two or more relations, assign numeric scores to the join results based on the given scoring function and return K join results with the highest scores. The top-K join results are obtained by accessing a subset of data from the input relations, provided these relations provide the tuples in descending order of score. Several rank join operators have been proposed to compute top-K joins with various different settings and assumptions. Classical applications of rank join are concerned with data stored within databases, whereas, very few of them have considered top-K query processing for Web based data sources. In this thesis, we address the problem of computing top-K join results from Web based data sources. Unlike the data stored in databases, the Web based data sources are characterized by non-negligible response time. This delay in data extraction slows down the execution of classical rank join algorithms, and they take a long time to get top-K joins. In this thesis, we propose score guided rank join algorithms with the following objectives: i) minimize the time to get top-K join results. ii) avoid the access to the data that does not contribute to the top-K join results. Furthermore, two main join topologies are defined in databases, namely, parallel and pipe joins. In parallel join topology, data extraction from data sources is independent of one another, and we can extract data in parallel. Instead, in pipe join topology, data extraction of one source depends upon data extracted from another source, hence, data extraction has to be pipe lined. We present rank join algorithms for both these join topologies which are customized for Web based data sources. We analyse the effectiveness of our proposed rank join algorithms with extensive experimental evaluation with synthetic and real data sets. The results reveal that our propose algorithms minimize the time to get top-K joins, while incurring a few extra data accesses as compared to the optimal number of data accesses. Most of the rank join operators store the results in an output buffer before reporting them. Because reporting of these results depends upon the score upper bound of all unseen join results. Especially, in the case of Web based data sources there is a large delay between observing and reporting of a join results, as they involve non-negligible response time. Therefore, we augment rank joins with a method to efficiently report a join result as soon as it is observed, with certain probabilistic guarantees to be among the final top-K joins. The experimental analysis of the results shows that our proposed probabilistic reporting algorithm reports the join results much earlier than the deterministic algorithms.

Posizione operatori di join eseguire un join relazionale tra due o più relazioni, assegnare i punteggi numerici per unire i risultati in base alla funzione di punteggio dato e tornare K unirsi risultati con i punteggi più alti. I top-K risultati join si ottengono l'accesso a un sottoinsieme di dati dalle relazioni di ingresso, a condizione che questi rapporti forniscono le tuple in ordine decrescente di punteggio. Diversi operatori di join rango sono stati proposti per calcolare top-K si unisce con le varie regolazioni diverse e ipotesi. Applicazioni classiche di rango unirsi riguardano i dati memorizzati nel database, mentre, molto pochi di loro hanno considerato top-K per l'elaborazione di query Web basati su fonti di dati. In questa tesi, possiamo affrontare il problema del calcolo top-K unire i risultati provenienti da fonti di dati web based. A differenza dei dati memorizzati nei database, le origini dati basate su Web sono caratterizzati dalla non trascurabile tempo di risposta. Questo ritardo nella estrazione dei dati rallenta l'esecuzione di rango classici algoritmi di join, e prendono molto tempo per ottenere top-K join. In questa tesi, vi proponiamo rank score guidata unirsi algoritmi con i seguenti obiettivi: i) ridurre al minimo il tempo per ottenere top-K join risultati. ii) evitare l'accesso ai dati che non contribuiscono alla top-K join risultati. Inoltre, due join principali topologie sono definiti nei database, vale a dire, parallela e pipe si unisce. In parallelo unisciti ad topologia, all'estrazione di dati dalle origini dati è indipendenti l'uno dall'altro, e possiamo estrarre i dati in parallelo. Invece, in tubo di join topologia, l'estrazione dei dati di una fonte dipende da dati estratti da un'altra fonte, quindi, l'estrazione di dati deve essere tubo rivestito. Vi presentiamo rank unirsi algoritmi per entrambi questi unirsi a topologie che sono adattati per le fonti di dati sul web. Analizziamo l'efficacia del nostro rango proposto algoritmi di join con ampia valutazione sperimentale con set di dati sintetici e reali. I risultati rivelano che proporre i nostri algoritmi di ridurre al minimo il tempo per ottenere top-K si unisce, mentre incorrere in alcuni dati aggiuntivi accede rispetto al numero ottimale di accessi ai dati. La maggior parte del rango operatori di join memorizzare i risultati in un buffer di output prima di trasmetterle. Poiché la segnalazione di questi risultati dipende dal punteggio superiore legato di tutti i risultati di join invisibili. Specialmente, nel caso di fonti di dati web based c'è un ritardo grande tra osservazione e descrizione di un risultati di join, in cui implicano non trascurabile tempo di risposta. Pertanto, abbiamo aumentare rango si unisce con un metodo per segnalare in modo efficiente un risultato join appena si osserva, con determinate garanzie probabilistiche di essere tra l'ultimo top-K join. L'analisi sperimentale dei risultati mostra che il nostro algoritmo probabilistico proposto reporting riporta i risultati di join molto prima di quanto gli algoritmi deterministici.